12

Gostaria de entender como funciona o algoritmo de hash MD5 (Message-Digest algorithm 5). Ele é considerado seguro?

Procuro respostas didáticas, que me façam compreender os processos utilizados por este algoritmo passo-a-passo, dando ênfase a parte lógica e matemática, e se possível, as operações com bits.

Note que não peço exemplos de código, embora sejam válidos para a explicação.

9
  • 1
    Se ele é seguro ou não, depende da aplicação. Ele é vulnerável a colisões (tanto via ataque de aniversário quanto via prefixos comuns) - inviabilizando seu uso em diversos cenários - e é bastante rápido - inviabilizando seu uso para proteger senhas. Entretanto, ele continua até hoje resistente a pré-imagem (1ª e 2ª), de modo que ainda existem aplicações práticas pra ele. Seu uso sozinho é limitado, mas combinado com outros algoritmos (ex.: HMAC-MD5) ele ainda possui utilidade.
    – mgibsonbr
    Commented 10/12/2014 às 5:31
  • 1
    Seu comentário é bastante pertinente, mas, por ora, manterei a pergunta desta forma para causar este tipo de discussão nas respostas. Se julgar que ela pode ser editada ou reformulada, sinta-se livre para fazê-lo. :)
    – Avelino
    Commented 10/12/2014 às 5:50
  • 1
    Ok, só coloquei como comentário porque não tenho conhecimento suficiente para dar uma resposta, mesmo que parcial. Se a comunidade achar que assim fica muito amplo, é só tirar, mas por ora não tenho nada contra manter como está.
    – mgibsonbr
    Commented 10/12/2014 às 5:52
  • 2
    Ao invés de perguntar sobre cada tipo de hash, poderia perguntar sobre todos eles numa pergunta só. Commented 10/12/2014 às 10:41
  • 1
    Relacionado: pt.stackoverflow.com/questions/2402/…
    – bfavaretto
    Commented 10/12/2014 às 14:16

1 Resposta 1

13

Como definido no RFC1321 o MD5 (Message-Digest algorithm 5) é um algoritmo de resumo de mensagem. Ele recebe como entrada uma mensagem de um comprimento arbitrário e produz como saída uma "impressão digital" de 128-bits.

Descrição do algoritmo MD5

Nós começamos supondo que temos uma mensagem de b bits como entrada e que queremos obter seu resumo. Nesse caso b é um inteiro arbitrário não negativo; b pode ser zero, ele não precisa ser um múltiplo de oito, e pode ser arbitrariamente grande. Imaginemos os bits dessa mensagem escritos como segue:

m0 m1 ... mb-1

The following five steps are performed to compute the message digest of the message.

Primeiro Passo: Adicionar Bits de Padding

A mensagem é extendida para que seu comprimento (em bits) seja côngruo a 448 módulo 512. Ou seja, a mensagem é extendida até que faltem apenas 64 bits para que seu comprimento seja múltiplo de 512. A operação de padding sempre é realizada, mesmo que o comprimento da mensagem já seja côngruo a 448 (mod. 512).

O padding ocorre da seguinte forma:

  1. Um bit 1 é adicionado ao fim da mensagem;

  2. Bits 0 são adicionados até que o comprimento (em bits) da mensagem após o padding seja côngruo a 448 (mod. 512).

Ou seja: Ao todo ao menos um bit será adicionado e no máximo 512 bits serão.

Segundo Passo: Anexando o Comprimento

Uma representação de 64-bits de b (o comprimento da mensagem antes da adição dos bits de padding) é anexado ao resultado do passo anterior. No caso (pouco provável) de b ser maior que 264 então somente os 64 bits menos significativos de b são usados. (Esses bits são anexados como duas palavras de 32-bits e anexados começando pela menos significativa (little-endian)).

Nesse ponto a mensagem resultante possui um comprimento é que um múltiplo de 512 bits. Ou seja, o comprimento da mensagem é um múltiplo de 16 palavras (de 32-bits). Sejam M[0 ... N-1] as palavras da mensagem resultante, onde N é um múltiplo de 16.

Terceiro Passo: Inicializar o Buffer MD

Um buffer de 4 palavras (A,B,C,D) é usado para computar o resumo da mensagem. Nesse caso cada um de A, B, C, D é um registrador de 32-bits. Esses registradores são inicializados com os valores que seguem em hexadecimal. Os bytes menos significativos primeiro:

word A: 01 23 45 67

word B: 89 ab cd ef

word C: fe dc ba 98

word D: 76 54 32 10

Quarto Passo: Processar a Mensagem em Blocos de 16 Palavras

Primeiro é necessário definir quatro funções auxiliares que recebem como entrada 3 palavras de 32-bits e produzem como saída uma palavra de 32-bits.

F(X,Y,Z) = XY v not(X) Z
G(X,Y,Z) = XZ v Y not(Z)
H(X,Y,Z) = X xor Y xor Z
I(X,Y,Z) = Y xor (X v not(Z))

Onde

  • not(X) é o complemento bit-wise de X,

  • X v Y é o OU bit-wise de X e Y,

  • X xor Y é o OU EXCLUSIVO bit-wise de X e Y,

  • XY é o E bit-wise de X e Y.

Esse passo usa uma tabela de 64 elementos T[1 ... 64] construída a partir da função seno. Seja T[i] igual ao i-ésimo elemento da tabela, que é iqual a parte inteira de 4294967296 vezes abs(sin(i)), onde i está em radianos.

Considere que + denota a adição de palavras) e X <<< s o valor obtido pelo deslocamento circular (rotação) de X a esquerda em s posições de bit.

Faça o seguinte:

/* Processa cada bloco de 16 palavras. */
For i = 0 to N/16-1 do

/* Copia o bloco i para X. */
For j = 0 to 15 do
Set X[j] to M[i*16+j].
end /* fim do loop em j */

/* Salva A como AA, B como BB, C como CC e D como DD. */
AA = A
BB = B

CC = C
DD = D

/* Round 1. */
/* Seja [abcd k s i] a operação
 a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Faça as 16 operações que seguem. */
[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]

/* Round 2. */
/* Seja [abcd k s i] a operação
 a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Faça as 16 operações que seguem. */
[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]

/* Round 3. */
/* Seja [abcd k s t] a operação
 a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Faça as 16 operações que seguem. */
[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]

/* Round 4. */
/* Seja [abcd k s t] a operação
 a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Faça as 16 operações que seguem. */
[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]

/* Então faça as seguintes adições.(Adicione a cada um dos quatro registradores o valor que eles tinham antes desse bloco começar.)*. */
A = A + AA
B = B + BB
C = C + CC
D = D + DD

end /* fim do loop em i */

Este passo pode ser implementado de uma maneira mais didática como se encontra no artigo da Wikipedia sobre MD5:

//Processar a mensagem em pedaços sucessivos de 512-bits:
for each 512-bit chunk of message
    break chunk into sixteen 32-bit little-endian words w(i), 0 ≤ i ≤ 15

    //Inicializar o valor do hash para este pedaço

    //Loop principal:
    for i from 0 to 63
        if 0 ≤ i ≤ 15 then
            f := (b and c) or ((not b) and d)
            g := i
            //há uma palavra referenciada por w(i)
        else if 16 ≤ i ≤ 31
            f := (d and b) or ((not d) and c)
            g := (5×i + 1) mod 16
            //não há uma palavra referenciada por w(i), logo fazemos 5i+1 %16
        else if 32 ≤ i ≤ 47
            f := b xor c xor d
            g := (3×i + 5) mod 16
            //não há uma palavra referenciada por w(i), logo fazemos 3i+5 %16
        else if 48 ≤ i ≤ 63
            f := c xor (b or (not d))
            g := (7×i) mod 16
            //não há uma palavra referenciada por w(i), logo fazemos 7i %16

        temp := d
        d := c
        c := b
        b := ((a + f + k[i] + w(g)) leftrotate r[i]) + b
        a := temp

    //Adicionar este pedaço do hash ao resultado:
    h0 := h0 + a
    h1 := h1 + b 
    h2 := h2 + c
    h3 := h3 + d

Considero a implementação mais didática pois cada bloco de cada uma das 16 palavras do bloco é processada usando um loop (em quanto o RFC lista as 16 operações). Além disso ela não usa funções auxiliares e deixa bem claro o que ocorrerá em cada passo. Podemos também perceber o espalhamento que ocorre dentro das quatro faixas de valores de i.

Quinto Passo: Saída

O resumo da mensagem produzido como saída é A, B, C, D, ou seja, começando pelo byte menos significativo de A, e terminando com o byte mais significativo de D.

Uma implementação de referência em JavaScript pode ser vista aqui.


Ele é considerado seguro?

De uma olhada em colisões e rainbow tables.

Usando MD5 para senhas

Usar MD5 para senhas não é uma ideia muito boa pois a função é muito rápida, ou seja, é muito fácil para um atacante tentar bilhões de possíveis senhas por segundo. Além disso há diversas vulnerabilidades (e casos famosos em que elas foram exploradas) que são conhecidas em MD5.

Sem querer generalizar: não use MD5 para senhas (nem com salt).

Para mais informações sobre como fazer hashing de senhas de maneira segura veja essa pergunta do Information Security.

Usando MD5 para checar integridade de arquivos

Baseado nessa resposta do Information Security:

Depende do cenário. Os ataques contra MD5 são de colisão, ou seja, um atacante pode fazer dois arquivos com o mesmo hash se ele tiver controle dos dois arquivos (divirta-se!), mas ele não consegue criar um arquivo que tenha um hash igual a de um arquivo que não foi influenciado por ele.

Nota: essa resposta é em grande parte uma tradução do RFC1321.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .