Criptografia Numaboa
MD4 *
|
Sab 24 Set 2005 19:54 |
- Detalhes
- Categoria: Funções Hash
- Atualização: Terça, 14 Abril 2009 13:53
- Autor: vovó Vicki
- Acessos: 17788
A função hash de mão única MD4 foi projetada por Ron Rivest e publicada oficialmente pela primeira vez em outubro de 1990. O algoritmo usa como entrada uma mensagem de comprimento arbitrário e produz uma "impressão digital" ou um "digesto de mensagem" de 128 bits. MD vem de message digest, cuja tradução pode parecer estranha, mas é digesto de mensagem. Um digesto é uma compilação de diretrizes ou uma coleção de decisões, geralmente aplicado como termo jurídico 
O MD4 foi criado para ser utilizado em assinaturas digitais onde um texto longo precisa ser "comprimido" de forma segura antes de ser cifrado com uma chave privada (secreta) por um criptossistema de chave pública. Foi projetado para ser bastante rápido em máquinas de 32 bits. Além disso, não necessita de grandes tabelas de substituição e pode ser facilmente programado de forma compacta. O autor colocou o algoritmo no domínio público.
Descrição do algoritmo MD4
A entrada do MD4 é uma mensagem que pode ter qualquer comprimento, ou seja, qualquer mensagem com um número arbitrário de bits. O número de bits, representado por b, é um número inteiro positivo que varia de zero até o infinito. Para obter o digesto da mensagem, seus bits, representados por m0, m1, ..., m{b-1}, onde b = número de bits da mensagem, são submetidos a diversas operações. Este processo é dividido em cinco etapas ou passos.
Passo 1: Adição de bits
A mensagem é "esticada" com a adição de bits até que atinja um comprimento congruente com 448 no módulo 512, ou seja, adiciona-se tantos bits quantos forem necessários para que o comprimento da mensagem seja 448 ou qualquer múltiplo de 512 menos 64 bits (512 - 64 = 448, 1024 - 64 = 960, etc). Esta adição pressupõe a inclusão de no mínimo um bit e, no máximo, de 512 bits.
O primeiro bit que deve ser adicionado logo no final da mensagem original é um bit "1". Todos os outros, necessários para se atingir o comprimento preconizado, são bits "0".
Passo 2: Incluir comprimento
O valor b, que representa o comprimento em bits da mensagem original, deve ser adicionado à mensagem previamente preparada no passo 1 na forma de 64 bits. É pouco provável que o valor de b seja maior do que 264, porém, caso isto ocorra, apenas os 64 bits menos significativos de b serão usados. Estes 64 bits são adicionados como dois words de 32 bits. O word menos significativo é inserido primeiro, seguido do word mais significativo.
Neste ponto, o comprimento da mensagem resultante é 512 ou um dos seus múltiplos. Também é um múltiplo exato de 16 words pois, se um word possui 32 bits, 16 words possuem 16 x 32 = 512 bits. Estes words podem ser representados por M[0, 1, ..., N-1], onde N é um múltiplo de 16.
Passo 3: Inicialização do buffer MD
Um buffer de quatro words é usado para calcular o digesto da mensagem. Os registradores de 32 bits A, B, C e D são inicializados com os seguintes valores hexadecimais:
word A: 01 23 45 67
word B: 89 ab cd ef
word C: fe dc ba 98
word D: 76 54 32 10
Nestes valores, os bytes mais significativos são colocados após os menos significativos, ou seja
Hexadecimal Binário Decimal
----------- --------------------------------------- -------------
A: 67 45 23 01 0110 0111 0100 0101 0010 0011 0000 0001 1.732.584.193
B: ef cd ab 89 1110 1111 1100 1101 1010 1011 1000 1001 4.023.233.417
C: 98 ba dc fe 1001 1000 1011 1010 1101 1100 1111 1110 2.562.383.102
D: 10 32 54 76 0001 0000 0011 0010 0101 0100 0111 0110 271.733.878
Passo 4: Processamento da mensagem em blocos de 16 words
Inicialmente são definidas três funções auxiliares. Estas funções usam como entrada três words (3 x 32 = 96 bits) para produzirem uma saída de um word (32 bits). São elas
F(X,Y,Z) = (X and Y) or ((not X) and Z)
G(X,Y,Z) = (X and Y) or (X and Z) or (Y and Z)
H(X,Y,Z) = X xor Y xor Z
Em cada um dos bits, a função F atua condicionalmente, ou seja, se X então Y, senão Z. G atua como uma função de maioria: se pelo menos dois bits de X, Y e Z estiverem ligados, G produz um bit "1" nesta posição, senão o bit será "0". A função H é um XOR bit a bit ou função de paridade.
Antes de aplicar estas funções, os valores de A, B, C e D precisam ser preservados pois serão usados no final do cálculo. As variáveis de trabalho, baseadas nestes valores e usadas neste texto serão a = A, b = B, c = C e d = D
A seguir, as funções são aplicadas considerando-se que:
Tendo [abcd k s i] a operação será a = ((a + F(b,c,d) + X[k] + T[i]) <<< s) + b
T[i] é uma constante
X[k] é o sub-bloco de texto
<<< s é rotação dos bits para a esquerda
Aplica-se inicialmente a função F para completar a primeira rodada, onde a constante T[i] = 0:
/* Rodada 1
[abcd 0 3] a = ((a + ((b and c) or ((not b) and d)) + X[0]) <<< 3)
[dabc 1 7] d = ((d + ((a and b) or ((not a) and c)) + X[1]) <<< 7)
[cdab 2 11] c = ((c + ((d and a) or ((not d) and b)) + X[2]) <<< 11)
[bcda 3 19] b = ((b + ((c and d) or ((not c) and a)) + X[3]) <<< 19)
[abcd 4 3] a = ((a + ((b and c) or ((not b) and d)) + X[4]) <<< 3)
[dabc 5 7] d = ((d + ((a and b) or ((not a) and c)) + X[5]) <<< 7)
[cdab 6 11] c = ((c + ((d and a) or ((not d) and b)) + X[6]) <<< 11)
[bcda 7 19] b = ((b + ((c and d) or ((not c) and a)) + X[7]) <<< 19)
[abcd 8 3] a = ((a + ((b and c) or ((not b) and d)) + X[8]) <<< 3)
[dabc 9 7] d = ((d + ((a and b) or ((not a) and c)) + X[9]) <<< 7)
[cdab 10 11] c = ((c + ((d and a) or ((not d) and b)) + X[10]) <<< 11)
[bcda 11 19] b = ((b + ((c and d) or ((not c) and a)) + X[11]) <<< 19)
[abcd 12 3] a = ((a + ((b and c) or ((not b) and d)) + X[12]) <<< 3)
[dabc 13 7] d = ((d + ((a and b) or ((not a) and c)) + X[13]) <<< 7)
[cdab 14 11] c = ((c + ((d and a) or ((not d) and b)) + X[14]) <<< 11)
[bcda 15 19] b = ((b + ((c and d) or ((not c) and a)) + X[15]) <<< 19)
A função G é usada na segunda rodada, onde a constante T[i] tem o valor hexadecimal 5A82 7999 (é o valor da raiz quadrada de 2):
/* Rodada 2
[abcd 0 3] a = ((a + ((b and c) or (b and d) or (c and d)) + X[0] + 5A827999) <<< 3)
[dabc 4 5] d = ((d + ((a and b) or (a and c) or (b and c)) + X[4] + 5A827999) <<< 5)
[cdab 8 9] c = ((c + ((d and a) or (d and b) or (a and b)) + X[8] + 5A827999) <<< 9)
[bcda 12 13] b = ((b + ((c and d) or (c and a) or (d and a)) + X[12] + 5A827999) <<< 13)
[abcd 1 3] a = ((a + ((b and c) or (b and d) or (c and d)) + X[1] + 5A827999) <<< 3)
[dabc 5 5] d = ((d + ((a and b) or (a and c) or (b and c)) + X[5] + 5A827999) <<< 5)
[cdab 9 9] c = ((c + ((d and a) or (d and b) or (a and b)) + X[9] + 5A827999) <<< 9)
[bcda 13 13] b = ((b + ((c and d) or (c and a) or (d and a)) + X[13] + 5A827999) <<< 13)
[abcd 2 3] a = ((a + ((b and c) or (b and d) or (c and d)) + X[2] + 5A827999) <<< 3)
[dabc 6 5] d = ((d + ((a and b) or (a and c) or (b and c)) + X[6] + 5A827999) <<< 5)
[cdab 10 9] c = ((c + ((d and a) or (d and b) or (a and b)) + X[10] + 5A827999) <<< 9)
[bcda 14 13] b = ((b + ((c and d) or (c and a) or (d and a)) + X[14] + 5A827999) <<< 13)
[abcd 3 3] a = ((a + ((b and c) or (b and d) or (c and d)) + X[3] + 5A827999) <<< 3)
[dabc 7 5] d = ((d + ((a and b) or (a and c) or (b and c)) + X[7] + 5A827999) <<< 5)
[cdab 11 9] c = ((c + ((d and a) or (d and b) or (a and b)) + X[11] + 5A827999) <<< 9)
[bcda 15 13] b = ((b + ((c and d) or (c and a) or (d and a)) + X[15] + 5A827999) <<< 13)
Na terceira rodada é aplicada a função H com a constante T[i] tem o valor hexadecimal 6ED9 EBA1 (é o valor da raiz quadrada de 3):
/* Rodada 3
[abcd 0 3] a = ((a + (b xor c xor d) + X[0] + 6ED9EBA1) <<< 3)
[dabc 8 9] d = ((d + (a xor b xor c) + X[8] + 6ED9EBA1) <<< 9)
[cdab 4 11] c = ((c + (d xor a xor b) + X[4] + 6ED9EBA1) <<< 11)
[bcda 12 15] b = ((b + (c xor d xor a) + X[12] + 6ED9EBA1) <<< 15)
[abcd 2 3] a = ((a + (b xor c xor d) + X[2] + 6ED9EBA1) <<< 3)
[dabc 10 9] d = ((d + (a xor b xor c) + X[10] + 6ED9EBA1) <<< 9)
[cdab 5 11] c = ((c + (d xor a xor b) + X[9] + 6ED9EBA1) <<< 11)
[bcda 13 15] b = ((b + (c xor d xor a) + X[13] + 6ED9EBA1) <<< 13)
[abcd 1 3] a = ((a + (b xor c xor d) + X[1] + 6ED9EBA1) <<< 3)
[dabc 9 9] d = ((d + (a xor b xor c) + X[9] + 6ED9EBA1) <<< 9)
[cdab 5 11] c = ((c + (d xor a xor b) + X[5] + 6ED9EBA1) <<< 11)
[bcda 13 15] b = ((b + (c xor d xor a) + X[13] + 6ED9EBA1) <<< 15)
[abcd 3 3] a = ((a + (b xor c xor d) + X[3] + 6ED9EBA1) <<< 3)
[dabc 11 9] d = ((d + (a xor b xor c) + X[11] + 6ED9EBA1) <<< 9)
[cdab 7 11] c = ((c + (d xor a xor b) + X[7] + 6ED9EBA1) <<< 11)
[bcda 15 15] b = ((b + (c xor d xor a) + X[15] + 6ED9EBA1) <<< 15)
Finalmente, os resultados obtidos para a, b, c, d são somados aos valores originais A, B, C e D:
A = a + A
B = b + B
C = c + C
D = d + D
Passo 5: Obtenção do valor hash
O digesto da mensagem é produzido concatenando-se A, B, C e D, começando com o byte menos significativo de A e terminando com o mais significativo de D.
A dança dos bits
Para visualizar o que acontece no nível dos bits, vamos tomar como exemplo o texto "abc". Os valores dos caracteres que compõem esta mensagem são:
Decimal Hexa Binário
------- ---- ---------
a 97 61 0110 0001
b 98 62 0110 0010
c 99 63 0110 0011
O texto fornece apenas um bloco de 512 bits, dividido em 16 sub-blocos de 32 bits. Logo depois dos bits da mensagem está o bit marcador "1" que, dentro do byte, assume a forma 1000 0000. Os bytes são colocados no registrador de "trás para frente", ou seja:
1 0 6 3 6 2 6 1 (valor hexadecimal)
---- ---- ---- ---- ---- ---- ---- ----
X[0] = 1000 0000 0110 0011 0110 0010 0110 0001
X[1] = 0000 0000 0000 0000 0000 0000 0000 0000
...
X[15] = 0000 0000 0000 0000 0000 0000 0001 1000 = 24 (comprimento da mensagem em bits)
A dança dos bits - A primeira rodada (função F)
A primeira etapa da primeira rodada utiliza a função F(b,c,d), soma o resultado com a e com o texto, para finalmente fazer uma rotação de três posições da esquerda para a direita para obter o novo valor de a.
b = 1110 1111 1100 1101 1010 1011 1000 1001
AND c = 1001 1000 1011 1010 1101 1100 1111 1110
---------------------------------------
1000 1000 1000 1000 1000 1000 1000 1000 (1)
NOT b = 0001 0000 0011 0010 0101 0100 0111 0110
AND d = 0001 0000 0011 0010 0101 0100 0111 0110
---------------------------------------
0001 0000 0011 0010 0101 0100 0111 0110 (2)
(1) = 1000 1000 1000 1000 1000 1000 1000 1000
OR (2) = 0001 0000 0011 0010 0101 0100 0111 0110
---------------------------------------
F(b,c,d) = 1001 1000 1011 1010 1101 1100 1111 1110
+ a 0110 0111 0100 0101 0010 0011 0000 0001
---------------------------------------
1111 1111 1111 1111 1111 1111 1111 1111
+ texto X[0] 1000 0000 0110 0011 0110 0010 0110 0001
---------------------------------------
1000 0000 0110 0011 0110 0010 0110 0000
<<< 3 = 0000 0011 0001 1011 0001 0011 0000 0100 = a
A segunda etapa da primeira rodada repete o procedimento anterior aplicando a função F(a,b,c).
a = 0000 0011 0001 1011 0001 0011 0000 0100
AND b = 1110 1111 1100 1101 1010 1011 1000 1001
---------------------------------------
0000 0011 0000 1001 0000 0011 0000 0000 (1)
NOT a = 1111 1100 1110 0100 1110 1100 1111 1011
AND c = 1001 1000 1011 1010 1101 1100 1111 1110
---------------------------------------
1001 1000 1010 0000 1100 1100 1111 1010 (2)
(1) = 0000 0011 0000 1001 0000 0011 0000 0000
OR (2) = 1001 1000 1010 0000 1100 1100 1111 1010
---------------------------------------
F(a,b,c) = 1001 1011 1010 1001 1100 1111 1111 1010
+ d 0001 0000 0011 0010 0101 0100 0111 0110
---------------------------------------
1010 1011 1101 1100 0010 0100 0111 0000
+ texto X[1] 0000 0000 0000 0000 0000 0000 0000 0000
---------------------------------------
1010 1011 1101 1100 0010 0100 0111 0000
<<< 7 = 1110 1110 0001 0010 0011 1000 0101 0101 = d
Depois das 16 etapas da primeira rodada, os valores encontrados são:
a = 1010 0010 1001 1001 1010 0101 0100 0000
b = 1101 1010 0111 0001 0111 0011 1001 0101
c = 0010 0100 1011 1010 1010 1101 1100 1011
d = 0000 0100 1110 0001 1001 0010 1001 0011
A dança dos bits - A segunda rodada (função G)
A segunda rodada usa os valores encontrados e aplica a função G:
b = 1101 1010 0111 0001 0111 0011 1001 0101
AND c = 0010 0100 1011 1010 1010 1101 1100 1011
---------------------------------------
0000 0000 0011 0000 0010 0001 1000 0001 (1)
b = 1101 1010 0111 0001 0111 0011 1001 0101
AND d = 0000 0100 1110 0001 1001 0010 1001 0011
---------------------------------------
0000 0000 0110 0001 0001 0010 1001 0001 (2)
c = 0010 0100 1011 1010 1010 1101 1100 1011
AND d = 0000 0100 1110 0001 1001 0010 1001 0011
---------------------------------------
0000 0100 1010 0000 1000 0000 1000 0011 (3)
(1) = 0000 0000 0011 0000 0010 0001 1000 0001
OR (2) = 0000 0000 0110 0001 0001 0010 1001 0001
---------------------------------------
0000 0000 0111 0001 0011 0011 1001 0001
OR (3) = 0000 0100 1010 0000 1000 0000 1000 0011
---------------------------------------
G(b,c,d) = 0000 0100 1111 0001 1011 0011 1001 0011
+ a 1010 0010 1001 1001 1010 0101 0100 0000
---------------------------------------
1010 0111 1000 1011 0101 1000 1101 0011
texto X[0] = 1000 0000 0110 0011 0110 0010 0110 0001
---------------------------------------
0010 0111 1110 1110 1011 1011 0011 0100
+ const 0101 1010 1000 0010 0111 1001 1001 1001 (hexadecimal 5A827999)
---------------------------------------
1000 0010 0111 0001 0011 0100 1100 1101
<<< 3 0001 0011 1000 1001 1010 0110 0110 1100 = a
Seguindo o mesmo esquema, completa-se as 16 rodadas da segunda etapa com o auxílio da função G para se obter os novos valores:
a = 0111 0010 1001 0110 0101 1001 0100 1100
b = 1000 1110 0101 0011 0001 1011 1000 1111
c = 0011 1101 1101 0100 0010 0100 0010 0010
d = 0100 1110 0111 1110 0001 0111 0100 1000
A dança dos bits - A terceira rodada (função H)
A terceira rodada usa os valores encontrados e aplica a função H:
b = 1000 1110 0101 0011 0001 1011 1000 1111
XOR c = 0011 1101 1101 0100 0010 0100 0010 0010
---------------------------------------
1011 0011 1000 0111 0011 1111 1010 1101
XOR d = 0100 1110 0111 1110 0001 0111 0100 1000
---------------------------------------
H(b,c,d) = 1111 1101 1111 1001 0010 1000 1110 0101
+ a 0111 0010 1001 0110 0101 1001 0100 1100
---------------------------------------
0111 0000 1000 1111 1000 0010 0011 0001
texto X[0] = 1000 0000 0110 0011 0110 0010 0110 0001
---------------------------------------
1111 0000 1111 0010 1110 0100 1001 0010
+ const 0110 1110 1101 1001 1110 1011 1010 0001 (hexadecimal 6ED9EBA1)
---------------------------------------
0101 1111 1100 1100 1101 0000 0011 0011
<<< 3 1111 1110 0110 0110 1000 0001 1001 1010 = a
No final das 16 etapas da terceira rodada os valores são:
a = 0001 0010 1011 1100 0010 0101 1010 0011
b = 0110 0011 0000 1010 0111 0110 0010 0110
c = 0100 1111 0100 1111 1110 0100 0110 0001
d = 1000 1101 0100 0000 0101 0010 0000 0100
A dança dos bits - O cálculo final para obter o hash
Somando os valores obtidos aos valores iniciais correspondentes e concatenando os resultados obtém-se o hash:
a = 0001 0010 1011 1100 0010 0101 1010 0011
+ A = 0110 0111 0100 0101 0010 0011 0000 0001
---------------------------------------
0111 1010 0000 0001 0100 1000 1010 0100
---- ---- ---- ---- ---- ---- ---- ----
| 7 A | 0 1 | 4 8 | A 4 | = A448 017A
b = 0110 0011 0000 1010 0111 0110 0010 0110
+ B = 1110 1111 1100 1101 1010 1011 1000 1001
---------------------------------------
0101 0010 1101 1000 0010 0001 1010 1111
---- ---- ---- ---- ---- ---- ---- ----
| 5 2 | D 8 | 2 1 | A F | = AF21 D852
c = 0100 1111 0100 1111 1110 0100 0110 0001
+ C = 1001 1000 1011 1010 1101 1100 1111 1110
---------------------------------------
1110 1000 0000 1010 1100 0001 0101 1111
---- ---- ---- ---- ---- ---- ---- ----
| E 8 | 0 A | C 1 | 5 F | = 5FC1 0AE8
d = 1000 1101 0100 0000 0101 0010 0000 0100
+ D = 0001 0000 0011 0010 0101 0100 0111 0110
---------------------------------------
1001 1101 0111 0010 1010 0110 0111 1010
---- ---- ---- ---- ---- ---- ---- ----
| 9 D | 7 2 | A 6 | 7 A | = 7AA6 729D
Ao vivo e em cores
Se toda esta salada de bits deu um nó na sua cabeça, não se desespere. Aqui está uma ferramenta on line para quebrar o galho. O que parecia tão complicado, na verdade é tão simples que pode até ser implementado em JavaScript. Confira.
Bateria de testes MD4
Confira a precisão do script fazendo os testes sugeridos pelo autor do algoritmo. Lembre-se: não existem hashes parecidos, apenas hashes idênticos conferem autenticidade.
- MD4 ("") = 31d6cfe0d16ae931b73c59d7e0c089c0
- MD4 ("a") = bde52cb31de33e46245e05fbdbd6fb24
- MD4 ("abc") = a448017aaf21d8525fc10ae87aa6729d
- MD4 ("message digest") = d9130a8164549fe818874806e1c7014b
- MD4 ("abcdefghijklmnopqrstuvwxyz") = d79e1c308aa5bbcdeea8ed63df412da9
- MD4 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = 043f8582f241db351ce627e153e7f0e4
- MD4 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = e33b4ddc9c38f2199c3e7b164fcc0536
Considerações finais
Apesar de ser aparentemente seguro, Rivest substituíu o MD4 pelo MD5 em abril de 1992. Mesmo assim, o MD4 constinuou sendo usado por alguns anos porque sua fragilidade não passava da especulação. Foi quando, na Eurocrypt de 1996, um ataque de H. Dobbertin mostrou que se podia achar colisões com uma probabilidade de 1/222. Até este ponto, nada de sério, mas a situação do MD4 ficou crítica em 2004 quando pesquisadores chineses - Xiaoyun Wang, Dengguo Feng, Xuejia Lai e Hongbo Yu1 - mostraram que podiam encontrar colisões apenas com cálculos feitos a mão. Na Eurocrypt de 2005, Xiaoyun Wang, Xuejia Lai, Dengguo Feng, Hui Chen e Xiuyuan Yu apresentaram um trabalho sobre a criptoanálise das funções hash MD4 e RIPEMD que praticamente aposentou este hash. Na seção de downloads da Aldeia (Criptologia/Papers) encontra-se o arquivo PDF deste último trabalho.
Fontes de referência
- R. Rivest, "The MD4 Message Digest Algorithm", RFC 1186, outubro 1990.
- R. Rivest, "The MD4 Message Digest Algorithm", RFC 1320, abril 1992.
- JavaScript do algoritmo MD4 Versão 2.1 Copyright (C) Jerrad Pierce, Paul Johnston 1999 - 2002.
- Bruce Schneier, "Applied Cryptography"
- Xiaoyun Wang, Collisions for Some Hash Functions MD4, MD5, HAVAL-128, RIPEMD
- Xiaoyun Wang, Cryptanalysis of the Hash Functions MD4 and RIPEMD