Detalhes

Categoria: Funções Hash

Atualização: Terça, 23 Outubro 2012 19:50

Autor: vovó Vicki

Acessos: 19589

O MD5 foi desenvolvido por Ron Rivest em 1991. É basicamente o MD4 com um "cinto de segurança" - os cálculos são um pouco mais lentos, mas, em compensação, é muito mais seguro.

Da mesma forma que outras funções hash, o MD5 é usado 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 máquinas de 32 bits, podendo ser facilmente programado de forma compacta. O autor colocou o algoritmo no domínio público em abril de 1992.

Como o texto sobre a função hash MD4 é bastante minucioso e o MD5 é muito parecido, não há a necessidade de entrar em muitos detalhes. Caso você tenha dúvidas, complemente a leitura com o texto MD4.

Descrição do algoritmo MD5

O entrada do MD5 é um fluxo de dados (mensagem) que pode ter um número arbitrário 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: Preparação do fluxo de dados

Adiciona-se à mensagem os bits necessários para que seu tamanho mais 64 bits seja divisível por 512.

Passo 2: Inclusão do comprimento

Depois da adição de bits, uma representação binária do tamanho original da mensagem e que ocupa 64 bits, é adicionada à mesma. O conjunto obtido é processado em blocos de 512 bits na estrutura iterativa de Damgård/Merkle, sendo que cada bloco é processado em quatro rodadas distintas.

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

Passo 4: Processamento da mensagem em blocos de 16 words (512 bits)

Primeiro definse-se quatro funções auxiliares. Cada uma delas usa três words de 32 bits para produzir uma saída de um word de 32 bits.

     F(X,Y,Z) = (X and Y) or (not(X) and Z)
     G(X,Y,Z) = (X and Z) or (Y and not(Z))
     H(X,Y,Z) = X xor Y xor Z
     I(X,Y,Z) = Y xor (X or not(Z))

A função F atua como condicional sobre cada um dos bits: se X então Y senão Z. É importante frisar que, se os bits de X, Y e Z são independentes e não induzidos (unbiased) então cada bit de F(X,Y,Z) também será independente e não induzido.

As funções G, H e I são semelhantes à função F quanto à ação "paralela bit a bit" produzindo saídas de bits independentes e não induzidos se os mesmos tiverem estas características. A função H é apenas um "XOR" ou função de "paridade" das suas entradas.

As etapas deste passo usam uma tabela de 64 elementos, T[1] a T[64], construída à partir da função seno. T[i] for o nésimo elemento da tabela e é igual à parte inteira de abs(seno(i)) multiplicada por 4294967296, onde i é expresso em radianos.

Antes de iniciar o processamento, deve-se armazenar os valores de A, B, C e D. Neste texto, as variáveis de trabalho serão expressas em letras minúsculas, portanto armazenamos a = A, b = B, c = C e d = D.

Divide-se cada bloco de 512 bits em 16 sub-blocos de 32 bits, aqui identificados por X[0] a X[15]. Genericamente, os sub-blocos são designados por X[k]. A seguir, aplica-se as funções F, G, H e I em quatro rodadas:

     /* Rodada 1
     /* Seja [abcd k s i] a operação a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s)
     /* Faça as seguintes 16 operações.

     [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
     [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
     [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
     [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]


     /* Rodada 2
     /* Seja [abcd k s i] a operação a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s)
     /* Faça as seguintes 16 operações.

     [ABCD  1  5 17]  [DABC  6  9 18]  [CDAB 11 14 19]  [BCDA  0 20 20]
     [ABCD  5  5 21]  [DABC 10  9 22]  [CDAB 15 14 23]  [BCDA  4 20 24]
     [ABCD  9  5 25]  [DABC 14  9 26]  [CDAB  3 14 27]  [BCDA  8 20 28]
     [ABCD 13  5 29]  [DABC  2  9 30]  [CDAB  7 14 31]  [BCDA 12 20 32]


     /* Rodada 3
     /* Seja [abcd k s i] a operação a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s)
     /* Faça as seguintes 16 operações

     [ABCD  5  4 33]  [DABC  8 11 34]  [CDAB 11 16 35]  [BCDA 14 23 36]
     [ABCD  1  4 37]  [DABC  4 11 38]  [CDAB  7 16 39]  [BCDA 10 23 40]
     [ABCD 13  4 41]  [DABC  0 11 42]  [CDAB  3 16 43]  [BCDA  6 23 44]
     [ABCD  9  4 45]  [DABC 12 11 46]  [CDAB 15 16 47]  [BCDA  2 23 48]


     /* Rodada 4
     /* Seja [abcd k s i] a operação a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s)
     /* Faça as seguintes 16 operações

     [ABCD  0  6 49]  [DABC  7 10 50]  [CDAB 14 15 51]  [BCDA  5 21 52]
     [ABCD 12  6 53]  [DABC  3 10 54]  [CDAB 10 15 55]  [BCDA  1 21 56]
     [ABCD  8  6 57]  [DABC 15 10 58]  [CDAB  6 15 59]  [BCDA 13 21 60]
     [ABCD  4  6 61]  [DABC 11 10 62]  [CDAB  2 15 63]  [BCDA  9 21 64]


     /* Finalmente, faça as adições dos resultados obtidos para a, b, c, d
     /* com os valores iniciais de A, B, C e D
     A = a + A
     B = b + B
     C = c + C
     D = d + D

Passo 5: A saída

O digesto da mensagem produzido na saída é a concatenação de A, B, C e D. Começa-se com o byte menos significativo de A e termina-se com o byte mais significativo de D.

As rodadas em detalhes

               Rodada 1                             Rodada 2
     --------------------------------     -------------------------------
     F(a,b,c,d, X[ 0], 7, 0xd76aa478)     G(a,b,c,d, X[ 1], 5, 0xf61e2562)
     F(d,a,b,c, X[ 1],12, 0xe8c7b756)     G(d,a,b,c, X[ 6], 9, 0xc040b340)
     F(c,d,a,b, X[ 2],17, 0x242070db)     G(c,d,a,b, X[11],14, 0x265e5a51)
     F(b,c,d,a, X[ 3],22, 0xc1bdceee)     G(b,c,d,a, X[ 0],20, 0xe9b6c7aa)
     F(a,b,c,d, X[ 4], 7, 0xf57cc0af)     G(a,b,c,d, X[ 5], 5, 0xd62f105d)
     F(d,a,b,c, X[ 5],12, 0x4787c62a)     G(d,a,b,c, X[10], 9, 0x02441453)
     F(c,d,a,b, X[ 6],17, 0xa8304613)     G(c,d,a,b, X[15],14, 0xd8a1e681)
     F(b,c,d,a, X[ 7],22, 0xfd469501)     G(b,c,d,a, X[ 4],20, 0xe7d3fbc8)
     F(a,b,c,d, X[ 8], 7, 0x698098d8)     G(a,b,c,d, X[ 9], 5, 0x21e1cde6)
     F(d,a,b,c, X[ 9],12, 0x8b44f7af)     G(d,a,b,c, X[14], 9, 0xc33707d6)
     F(c,d,a,b, X[10],17, 0xffff5bb1)     G(c,d,a,b, X[ 3],14, 0xf4d50d87)
     F(b,c,d,a, X[11],22, 0x895cd7be)     G(b,c,d,a, X[ 8],20, 0x455a14ed)
     F(a,b,c,d, X[12], 7, 0x6b901122)     G(a,b,c,d, X[13], 5, 0xa9e3e905)
     F(d,a,b,c, X[13],12, 0xfd987193)     G(d,a,b,c, X[ 2], 9, 0xfcefa3f8)
     F(c,d,a,b, X[14],17, 0xa679438e)     G(c,d,a,b, X[ 7],14, 0x676f02d9)
     F(b,c,d,a, X[15],22, 0x49b40821)     G(b,c,d,a, X[12],20, 0x8d2a4c8a)


               Rodada 3                             Rodada 4
     --------------------------------     -------------------------------
     H(a,b,c,d, X[ 5], 4, 0xfffa3942)     I(a,b,c,d, X[ 0], 6, 0xf4292244)
     H(d,a,b,c, X[ 8],11, 0x8771f681)     I(d,a,b,c, X[ 7],10, 0x411aff97)
     H(c,d,a,b, X[11],16, 0x6d9d6122)     I(c,d,a,b, X[14],15, 0xab9423a7)
     H(b,c,d,a, X[14],23, 0xfde5380c)     I(b,c,d,a, X[ 5],21, 0xfc93a039)
     H(a,b,c,d, X[ 1], 4, 0xa4beea44)     I(a,b,c,d, X[12], 6, 0x655b59c3)
     H(d,a,b,c, X[ 4],11, 0x4bdecfa9)     I(d,a,b,c, X[ 3],10, 0x8f0ccc92)
     H(c,d,a,b, X[ 7],16, 0xf6bb4b60)     I(c,d,a,b, X[10],15, 0xffeff47d)
     H(b,c,d,a, X[10],23, 0xbebfbc70)     I(b,c,d,a, X[ 1],21, 0x85848dd1)
     H(a,b,c,d, X[13], 4, 0x289b7ec6)     I(a,b,c,d, X[ 8], 6, 0x6fa87e4f)
     H(d,a,b,c, X[ 0],11, 0xeaa127fa)     I(d,a,b,c, X[15],10, 0xfe2ce6e0)
     H(c,d,a,b, X[ 3],16, 0xd4ef3085)     I(c,d,a,b, X[ 6],15, 0xa3014314)
     H(b,c,d,a, X[ 6],23, 0x04881d05)     I(b,c,d,a, X[13],21, 0x4e0811a1)
     H(a,b,c,d, X[ 9], 4, 0xd9d4d039)     I(a,b,c,d, X[ 4], 6, 0xf7537e82)
     H(d,a,b,c, X[12],11, 0xe6db99e5)     I(d,a,b,c, X[11],10, 0xbd3af235)
     H(c,d,a,b, X[15],16, 0x1fa27cf8)     I(c,d,a,b, X[ 2],15, 0x2ad7d2bb)
     H(b,c,d,a, X[ 2],23, 0xc4ac5665)     I(b,c,d,a, X[ 9],21, 0xeb86d391)

Ao vivo e em cores

Aqui está uma ferramenta on line, escrita em JavaScript, para produzir digestos MD5. Confira.

Bateria de testes

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.

• MD5 ("") = d41d8cd98f00b204e9800998ecf8427e
• MD5 ("a") = 0cc175b9c0f1b6a831c399e269772661
• MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
• MD5 ("message digest") = f96b697d7cb7938d525a2f31aaf161d0
• MD5 ("abcdefghijklmnopqrstuvwxyz") = c3fcd3d76192e4007dfb496cca67e13b
• MD5 ("ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789") = d174ab98d277d9f5a5611c2c9f419d9f
• MD5 ("12345678901234567890123456789012345678901234567890123456789012345678901234567890") = 57edf4a22be3c955ac49da2e2107b67a

Considerações finais

Rivest melhorou a segurança do MD5 usando várias técnicas:

• Adicionou uma quarta rodada.
• Usou uma constante aditiva única em cada etapa das rodadas.
• Fez a função G menos simétrica mudando-a de (XY or XZ or YZ) para (XZ or Y not(Z))
• Promoveu um "efeito avalanche" mais rápido com cada etapa adicionando seu resultado à etapa anterior.
• Mudou a ordem da entrada dos words nas rodadas 2 e 3 para tornar seus padrões menos parecidos.
• Otimizou as rotações de cada rodada para obter um "efeito avalanche" mais rápido.

Mas a função hash MD5, um padrão mundial usado principalmente nos sistemas de senhas, é realmente segura? 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, MD5, HAVAL-128 e RIPEMD que reduz drasticamente o tempo para encontrar colisões nestes hash. Na seção de downloads da Aldeia (Criptologia/Papers) encontra-se o arquivo PDF deste trabalho.

Fontes de referência

• R. Rivest, "The MD5 Message Digest Algorithm", RFC 1321, abril 1992.
• Bruce Schneier, "Applied Cryptography".
• Xiaoyun Wang, Collisions for Some Hash Functions MD4, MD5, HAVAL-128, RIPEMD
• JavaScript do algoritmo MD5 Versão 2.1 Copyright (C) Paul Johnston 1999 - 2002.