Criptografía (LXXIV): El algoritmo MD5

En este post comparto lo que voy aprendiendo sobre el algoritmo MD5 (Message Digest 5), una función resumen que produce un valor hash de 128 bits.

Este Algoritmo fue diseñado en 1991 por Ronald Rivest, uno de los inventores del cifrado RSA, para reemplazar a su función hash predecesora, MD4.

MD5 procesa un mensaje de longitud variable dando como resultado un hash o resumen con una longitud fija de 128 bits.

Veamos como funciona este algoritmo, si lo he entendido bien, poniendo un ejemplo:

Mensaje de entrada "Mikel":

01001101 01101001 01101011 01100101

01101100
Longitud = 40 bits.

1.-  El mensaje de entrada se extiende de la siguiente manera:

1.1.- Se añade un bit "1" al final del mensaje.

01001101 01101001 01101011 01100101

01101100 1
Longitud = 41 bits.

1.2.- Se añaden bits "0" hasta que la longitud del mensaje sea de 64 bits menos que un múltiplo de 512 (en nuestro caso hasta 448).

01001101 01101001 01101011 01100101
01101100 10000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
Longitud = 448 bits.

Según lo que he entendido, hay que tener en cuenta que en cada byte los bits se sitúan, de izquierda a derecha, del más significativo al menos significativo, mientras en cada palabra de 32 bits los bytes se sitúan, de derecha a izquierda, del menos significativo al más significativo, es decir:

01100101 01101011 01101001 01001101
00000000 00000000 10000000 01101100
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
Longitud = 448 bits.

2.- Los 64 bits restantes hasta completar una longitud de un múltiplo de 512 (en nuestro caso hasta 512) se rellenan con la longitud del mensaje de entrada original módulo 2⁶⁴ (en nuestro caso tiene una longitud de 40 bits = 00101000). Es decir, la longitud se añade en dos palabras de 32 bits cada una de ellas, primero la palabra menos significativa:

01100101 01101011 01101001 01001101
00000000 00000000 10000000 01101100
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00101000
00000000 00000000 00000000 00000000
Longitud = 512 bits.

3.- Se utilizan cuatro palabras (A, B, C y D) de 32 bits cada una de ellas para calcular el hash o resumen del mensaje y que se inicializan con las siguientes constates fijas (en cada palabra, de izquierda a derecha, del byte menos significativo al más significativo):

A = 01 23 45 67 = 00000001 00100011 01000101 01100111
B = 89 ab cd ef  = 10001001 10101011 11001101  11101111
C = fe dc ba 98  = 11111110  11011100  10111010 10011000
D = 76 54 32 10 = 01110110 01010100 00110010 00010000

4.- A continuación, el algoritmo emplea cada uno de los bloques de 512 bits del mensaje, después de que el mensaje de entrada original haya sido extendido y se haya completado con la longitud del mismo, para modificar esas cuatro palabras y obtener el hash o resumen.

El procesamiento de cada bloque del mensaje (en nuestro caso sólo 1) se realiza en cuatro rondas o vueltas compuestas de 16 operaciones cada una de ellas. En la figura siguiente se representa de forma gráfica una de las 64 operaciones de las que consta el procesamiento de cada bloque:

Donde:

F: función no lineal. Se utiliza una diferente para cada ronda o vuelta:

1ª ronda o vuelta (0 ≤ i ≤ 15):    F(B, C, D) = (B and C) or ((not B) and D).
2ª ronda o vuelta (16 ≤ i ≤ 31):  G(B, C, D) = (B and D) or (C and (not D)).
3ª ronda o vuelta (32 ≤ i ≤ 47):  H(B, C, D) = (B xor C xor D).
4ª ronda o vuelta (48 ≤ i ≤ 63):   I(B, C, D) = C xor (B or (not D)).

M_g: una palabra de 32 bits del bloque de 512 bits que se está procesando:

1ª ronda o vuelta (0 ≤ i ≤ 15):    g = i.
2ª ronda o vuelta (16 ≤ i ≤ 31):  g = (5 x i + 1) mod 16.
3ª ronda o vuelta (32 ≤ i ≤ 47):  g = (3 x i + 5) mod 16.
4ª ronda o vuelta (48 ≤ i ≤ 63):  g = (7 x i) mod 16.

K_i: constante de 32 bits . Se utiliza una diferente para cada una de las 64 operaciones:

K [0 .. 3]:   = {d76aa478, e8c7b756, 242070db, c1bdceee}

K [4 .. 7]:   = {f57c0faf, 4787c62a, a8304613, fd469501}

K [8..11]:   = {698098d8, 8b44f7af, ffff5bb1, 895cd7be}

K [12..15]: = {6b901122, fd987193, a679438e, 49b40821}

K [16..19]: = {f61e2562, c040b340, 265e5a51, e9b6c7aa}

K [20..23]: = {d62f105d, 02441453, d8a1e681, e7d3fbc8}

K [24..27]: = {21e1cde6, c33707d6, f4d50d87, 455a14ed}

K [28..31]: = {a9e3e905, fcefa3f8, 676f02d9, 8d2a4c8a}

K [32..35]: = {fffa3942, 8771f681, 6d9d6122, fde5380c}

K [36..39]: = {a4beea44, 4bdecfa9, f6bb4b60, bebfbc70}

K [40..43]: = {289b7ec6, eaa127fa, d4ef3085, 04881d05}

K [44..47]: = {d9d4d039, e6db99e5, 1fa27cf8, c4ac5665}

K [48..51]: = {f4292244, 432aff97, ab9423a7, fc93a039}

K [52..55]: = {655b59c3, 8f0ccc92, ffeff47d, 85845dd1}

K [56..59]: = {6fa87e4f, fe2ce6e0, a3014314, 4e0811a1}

K [60..63]: = {f7537e82, bd3af235, 2ad7d2bb, eb86d391}

S_i: número de bits a rotar circularmente a la izquierda:

S [0..15]:   = {7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22}

S [16..31]: = {5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20}

S [32..47]: = {4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23}

S [48..63]: = {6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21}

Finalmente, espero no equivocarme mucho, completo algunas de las operaciones por ronda o vuelta hasta obtener el hash o resumen de nuestro ejemplo (mensaje de entrada "Mikel"):

- Valores iniciales de A, B, C y D (de izquierda a derecha, del byte más significativo al menos significativo):

A = 67452301 = 01100111  01000101 00100011 00000001
B = efcdab89  =  11101111  11001101 10101011 10001001
C = 98badcfe  = 10011000 10111010 11011100  11111110
D = 10325476 = 00010000 00110010 01010100 01110110

- Procesamiento del primer y único bloque de 512 bits del mensaje:

Palabra 0 (M₀):    01100101 01101011 01101001 01001101
Palabra 1 (M₁):    00000000 00000000 10000000 01101100
Palabra 2 (M₂):    00000000 00000000 00000000 00000000
Palabra 3 (M₃):    00000000 00000000 00000000 00000000
Palabra 4 (M₄):    00000000 00000000 00000000 00000000
Palabra 5 (M5):    00000000 00000000 00000000 00000000
Palabra 6 (M6):    00000000 00000000 00000000 00000000
Palabra 7 (M7):    00000000 00000000 00000000 00000000
Palabra 8 (M8):    00000000 00000000 00000000 00000000
Palabra 9 (M9):    00000000 00000000 00000000 00000000
Palabra 10 (M10): 00000000 00000000 00000000 00000000
Palabra 11 (M11): 00000000 00000000 00000000 00000000
Palabra 12 (M12): 00000000 00000000 00000000 00000000
Palabra 13 (M13): 00000000 00000000 00000000 00000000
Palabra 14 (M14): 00000000 00000000 00000000 00101000
Palabra 15 (M15): 00000000 00000000 00000000 00000000

Primera ronda o vuelta:

i = 0

       11101111110011011010101110001001      (B)
and 10011000101110101101110011111110      (C)
------------------------------------------------------
       10001000100010001000100010001000    (B and C)                                     
or    00010000001100100101010001110110    ((not B) and D)
------------------------------------------------------
        10011000101110101101110011111110     F(B, C, D) = (B and C) or ((not B) and D)
        01100111010001010010001100000001    (A)
        01100101011010110110100101001101    (g = i = 0: M₀).
+      11010111011010101010010001111000    (K_{0 =} d76aa478)
------------------------------------------------------
        00111100110101100000110111000100
------------------------------------------------------
        01101011000001101110001000011110     (S₀ = 7: Rotación circular 7 bits a izq.)
+      11101111110011011010101110001001     (B)
------------------------------------------------------
        01011010110101001000110110100111     (B')
------------------------------------------------------
        00010000001100100101010001110110     (A = D: La palabra D pasa a ser la A)
        10011000101110101101110011111110      (D = C: La palabra C pasa a ser la D)
        11101111110011011010101110001001      (C = B: La palabra B pasa a ser la C)
        01011010110101001000110110100111     (B = B': B' pasa a ser la palabra B)

i = 1

       01011010110101001000110110100111     (B)
and  11101111110011011010101110001001     (C)
------------------------------------------------------
       01001010110001001000100110000001    (B and C)                                   
or    10000000001010100101000001011000    ((not B) and D)
------------------------------------------------------
        11001010111011101101100111011001     F(B, C, D) = (B and C) or ((not B) and D)
        00010000001100100101010001110110    (A)
        00000000000000001000000001101100    (g = i = 1: M₁)
+      11101000110001111011011101010110     (K_{1 =} e8c7b756)
------------------------------------------------------
        11000011111010010110011000010001
------------------------------------------------------
        10010110011000010001110000111110     (S₁ = 12: Rotación circular 12 bits a izq.)
+      01011010110101001000110110100111     (B)
------------------------------------------------------
        11110001001101011010100111100101      (B')
------------------------------------------------------
        10011000101110101101110011111110      (A = D: La palabra D pasa a ser la A)
        11101111110011011010101110001001      (D = C: La palabra C pasa a ser la D)
        01011010110101001000110110100111     (C = B: La palabra B pasa a ser la C)
        11110001001101011010100111100101     (B = B': B' pasa a ser la palabra B)

i = ...

         ...

i = 15

       00000001100000000000110001010100    (B)
and  01100010110000001011100101011110    (C)
------------------------------------------------------
       00000000100000000000100001010100    (B and C)                                   
or    00001100011000010001001000101001    ((not B) and D)
------------------------------------------------------
        00001100111000010001101001111101     F(B, C, D) = (B and C) or ((not B) and D)
        00000011110100100100111010101101     (A)
        00000000000000000000000000000000    (g = i = 15: M₁₅)
+      01001001101101000000100000100001    (K_{15 =} 49b40821)
------------------------------------------------------
        01011010011001110111000101001011
------------------------------------------------------
        01010010110101101001100111011100     (S₁₅ = 22: Rotación circular 22 bits a izq.)
+     00000001100000000000110001010100     (B)
------------------------------------------------------
        01010100010101101010011000110000    (B')
------------------------------------------------------
        00001101011000010001011001101001    (A = D: La palabra D pasa a ser la A)
        01100010110000001011100101011110     (D = C: La palabra C pasa a ser la D)
        00000001100000000000110001010100    (C = B: La palabra B pasa a ser la C)
        01010100010101101010011000110000    (B = B': B' pasa a ser la palabra B)

Segunda ronda o vuelta:

i = 16

         ...

i = ...

         ...

i = 31

Tercera ronda o vuelta:

i = 32

         ...

i = ...

         ...

i = 47

Cuarta ronda o vuelta:

i = 48

         ...

i = ...

         ...

i = 63

        11100100110101100010001010001101   (C)
xor   00110111111011101111111111001101     (B or (not D))
------------------------------------------------------
        11010011001110001101110101000000    I(B, C, D) = C xor (B or (not D)
        11010111111000010001000001110110    (A)
        00000000000000000000000000000000   (g = (7 x i) mod 16 = 9: M₉)
+      11101011100001101101001110010001    (K_{63 =} eb86d391)
------------------------------------------------------
        10010110101000001100000101000111
------------------------------------------------------
        00101000111100101101010000011000    (S₆₃ = 21: Rotación circular 21 bits a izq.)
+      00000111111010100110011110000100    (B)
------------------------------------------------------
        00110000110111010011101110011100     (B')
------------------------------------------------------
        11001000000100010110010100110010    (A = D: La palabra D pasa a ser la A)
        11100100110101100010001010001101    (D = C: La palabra C pasa a ser la D)
        00000111111010100110011110000100     (C = B: La palabra B pasa a ser la C)
        00110000110111010011101110011100     (B = B': B' pasa a ser la palabra B)

Actualización final A, B, C y D del bloque de 512 bits procesado
------------------------------------------------------
     67452301 efcdab89  98badcfe 10325476      Valores iniciales A, B, C y D
+   c8116532 30dd3b9c 07ea6784 e4d6228d     Valores finales (i= 63) A, B, C y D
------------------------------------------------------
     2f568833 20aae725  a0a54482 f5087703

Valor hash o resumen del bloque de 512 bits procesado

En cada palabra de 32 bits, de izquierda a derecha, del byte menos significativo al más significativo:

      3388562f 25e7aa20 8244a5a0 037708f5

Como en nuestro ejemplo tenemos un único bloque de 512 bits, éste será el valor hash o resumen del mensaje de entrada: 3388562f25e7aa208244a5a0037708f5.