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:
Um bit 1
é adicionado ao fim da mensagem;
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.