Ir al contenido principal

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 264 (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)).

Mg: 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.

Ki: 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}

Si: 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 (M0):    01100101 01101011 01101001 01001101
Palabra 1 (M1):    00000000 00000000 10000000 01101100
Palabra 2 (M2):    00000000 00000000 00000000 00000000
Palabra 3 (M3):    00000000 00000000 00000000 00000000
Palabra 4 (M4):    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: M0).
+      11010111011010101010010001111000    (K0 = d76aa478)
------------------------------------------------------
        00111100110101100000110111000100
------------------------------------------------------
        01101011000001101110001000011110     (S0 = 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: M1)
+      11101000110001111011011101010110     (K1 = e8c7b756)
------------------------------------------------------
        11000011111010010110011000010001
------------------------------------------------------
        10010110011000010001110000111110     (S1 = 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: M15)
+      01001001101101000000100000100001    (K15 = 49b40821)
------------------------------------------------------
        01011010011001110111000101001011
------------------------------------------------------
        01010010110101101001100111011100     (S15 = 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: M9)
+      11101011100001101101001110010001    (K63 = eb86d391)
------------------------------------------------------
        10010110101000001100000101000111
------------------------------------------------------
        00101000111100101101010000011000    (S63 = 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.

Comentarios

Entradas populares de este blog

Criptografía (I): cifrado Vigenère y criptoanálisis Kasiski

Hace unos días mi amigo Iñaki Regidor ( @Inaki_Regidor ), a quien dedico esta entrada :), compartió en las redes sociales un post titulado "Criptografía: el arte de esconder mensajes"  publicado en uno de los blogs de EiTB . En ese post se explican ciertos métodos clásicos para cifrar mensajes , entre ellos el cifrado de Vigenère , y , al final del mismo, se propone un reto consistente en descifrar un mensaje , lo que me ha animado a escribir este post sobre el método Kasiski  para atacar un cifrado polialfabético ( conociendo la clave descifrar el mensaje es muy fácil, pero lo que contaré en este post es la forma de hacerlo sin saberla ). El mensaje a descifrar es el siguiente: LNUDVMUYRMUDVLLPXAFZUEFAIOVWVMUOVMUEVMUEZCUDVSYWCIVCFGUCUNYCGALLGRCYTIJTRNNPJQOPJEMZITYLIAYYKRYEFDUDCAMAVRMZEAMBLEXPJCCQIEHPJTYXVNMLAEZTIMUOFRUFC Como ya he dicho el método de Vigenère es un sistema de sustitución polialfabético , lo que significa que, al contrario que en un sistema de

Criptografía (XXIII): cifrado de Hill (I)

En este post me propongo explicar de forma comprensible lo que he entendido sobre el cifrado de Hill , propuesto por el matemático Lester S. Hill , en 1929, y que se basa en emplear una matriz como clave  para cifrar un texto en claro y su inversa para descifrar el criptograma correspondiente . Hay tres cosas que me gustan de la criptografía clásica, además de que considero que ésta es muy didáctica a la hora de comprender los sistemas criptográficos modernos: la primera de ellas es que me "obliga" a repasar conceptos de matemáticas aprendidos hace mucho tiempo y, desgraciadamente, olvidados también hace demasiado tiempo, y, por consiguiente, que, como dice  Dani , amigo y coautor de este blog, me "obliga" a hacer "gimnasia mental"; la segunda es que, en la mayoría de las ocasiones, pueden cifrarse y descifrase los mensajes, e incluso realizarse el criptoanálisis de los criptogramas, sin más que un simple lápiz y papel, es decir, para mi es como un pasat

¿Qué significa el emblema de la profesión informática? (I)

Todas o muchas profesiones tienen un emblema que las representa simbólicamente y en el caso de la  informática: " es el establecido en la resolución de 11 de noviembre de 1977  para las titulaciones universitarias superiores de informática, y  está constituido por una figura representando en su parte central  un  núcleo toroidal de ferrita , atravesado por  hilos de lectura,  escritura e inhibición . El núcleo está rodeado por  dos ramas : una  de  laurel , como símbolo de recompensa, y la otra, de  olivo , como  símbolo de sabiduría. La  corona  será la  de la casa real  española,  y bajo el escudo se inscribirá el acrónimo de la organización. ". Veamos los diferentes elementos tomando como ejemplo el emblema del COIIE/EIIEO (Colegio Oficial de Ingenieros en Informática del País Vasco/ Euskadiko Informatikako Ingeniarien Elkargo Ofiziala ) . Pero no sólo el COIIE/EIIEO adopta el emblema establecido en dicha resolución, sino que éste se adopta también como im