MD5
| MD5 | |
 | |
| Fecha de creación: |
1991
|
En Criptografía, MD5 (acrónimo de Message-Digest Algorithm 5, Algoritmo de Resumen del Mensaje 5) es un Algoritmo de reducción criptográfico de 128 Bits ampliamente usado. El código MD5 fue diseñado por Ronald Rivest en 1991. Durante el año 2004 fueron divulgados ciertos defectos de seguridad, lo que hará que en un futuro cercano se cambie de este sistema a otro más seguro.
Sumario
Historia
MD5 es uno de los algoritmos de reducción criptográficos diseñados por el profesor Ronald Rivest del MIT (Massachussets Institute of Technology, Instituto Tecnológico de Masachusets). Cuando un análisis analítico indicó que el algoritmo MD4 era inseguro, se decidió a programar el MD5 para sustituirlo en 1991. Las debilidades en MD4 fueron descubiertas por Hans Dobbertin.
En 1996 Dobbertin anunció una colisión de Hash de la función de compresión del MD5. Esto no era una ataque contra la función de hash del MD5, pero hizo que los criptógrafos empezasen a recomendar el reemplazo de la codificación MD5 a otras como SHA-1 o RIPEMD-160. En Agosto de 2004 unos investigadores chinos encontraron también colisiones hash en el MD5. Actualmente el uso de MD5 es muy amplio y se desconoce cómo afectarán estos problemas a su uso y a su futuro.
Codificación
La codificación del MD5 de 128 bits es representada típicamente como un número de 32 dígitos hexadecimal. El siguiente código de 28 bytes ASCII será tratado con MD5 y veremos su correspondiente hash de salida:
MD5("Esto si es una prueba de MD5") = e07186fbff6107d0274af02b8b930b65
Un simple cambio en el mensaje nos da un cambio total en la codificación hash, en este caso cambiamos dos letras, el "si" por un "no".
MD5("Esto no es una prueba de MD5") = dd21d99a468f3bb52a136ef5beef5034
Otro ejemplo sería la codificación de un campo vacío:
MD5("") = d41d8cd98f00b204e9800998ecf8427e
Algoritmo
- Terminologías y notaciones
En este documento "palabra" es una entidad de 32 bits y byte es una entidad de 8 bits. Una secuencia de bits puede ser interpretada de manera natural como una secuencia de bytes, donde cada grupo consecutivo de ocho bits se interpreta como un byte con el bit más significativo al principio. Similarmente, una secuencia de bytes puede ser interpretada como una secuencia de 32 bits (palabra), donde cada grupo consecutivo de cuatro bytes se intepreta como una palabra en la que el bit menos significativo está al principio.
El símbolo "+" significa suma de palabras. X <<< s se interpreta por una rotación a la izquierda 's' posiciones not(x) se entiende como el complemento de x
- Descripción del algoritmo MD5
Empezamos suponiendo que tenemos un mensaje de 'b' bits de entrada, y que nos gustaría encontrar su resumen. Aquí 'b' es un valor arbitrario entero no negativo, pero puede ser cero, no tiene por qué ser múltiplo de ocho, y puede ser muy largo. Imaginemos los bits del mensaje escritos así:
m0 m1 ... m{b-1}
Los siguientes cinco pasos son efectuados para calcular el resumen del mensaje.
Paso 1. Añadiendo bits
El mensaje será extendido hasta que su longitud en bits sea congruente con 448, módulo 512. Esto es, el mensaje se extenderá hasta que se forme el menor número múltiplo de 512 bits. Esta extensión se realiza siempre, incluso si la longitud del mensaje es ya congruente con 448, módulo 512.
La extensión se realiza como sigue: un sólo bit "1" se añade al mensaje, y después bits "0" se añaden hasta que la longitud en bits del mensaje es congruente con 448, módulo 512. En todos los mensajes se añade al menos un bit y como máximo 512.
Paso 2. Longitud del mensaje
Una representación de 64 bits de 'b' (la longitud del mensaje antes de añadir los bits) se añade al resultado del paso anterior. En el supuesto no deseado de que 'b' sea mayor que 2^64, entonces sólo los 64 bits de menor peso de 'b' se usarán.
En este punto el mensaje resultante (después de rellenar con los bits y con 'b') se tiene una longitud que es un múltiplo exacto de 512 bits. A su vez, la longitud del mensaje es múltiplo de 16 palabras (32 bits por palabra). Con M[0 ... N-1] denotaremos las palabras del mensaje resultante, donde N es múltiplo de 16.
Paso 3. Inicializar el búfer MD
Un búfer de cuatro palabras (A, B, C, D) se usa para calcular el resúmen del mensaje. Aquí cada una de las letras A, B, C, D representa un registro de 32 bits. Estos registros se inicializan con los siguientes valores hexadecimales, los bits de menor peso primero:
palabra A: 01 23 45 67 palabra B: 89 ab cd ef palabra C: fe dc ba 98 palabra D: 76 54 32 10
Paso 4. Procesado del mensaje en bloques de 16 palabras
Primero definimos cuatro funciones auxiliares que toman como entrada tres palabras de 32 bits y su salida es una palabra de 32 bits.
- <math>F(X,Y,Z) = (X\wedge{Y}) \vee (\neg{X} \wedge{Z})</math>
- <math>G(X,Y,Z) = (X\wedge{Z}) \vee (Y \wedge \neg{Z})</math>
- <math>H(X,Y,Z) = X \oplus Y \oplus Z</math>
- <math>I(X,Y,Z) = Y \oplus (X \vee \neg{Z})</math>
Los operadores <math>\oplus, \wedge, \vee, \neg</math> son las funciones XOR, AND, OR y NOT respectivamente.
En cada posición de cada bit F actúa como un condicional: si X, entonces Y sino Z. La función F podría haber sido definida usando + en lugar de v ya que XY y not(x)Z nunca tendrán unos ('1') en la misma posición de bit. Es interesante resaltar que si los bits de X, Y y Z son independientes y no sesgados, cada uno de los bits de F(X,Y,Z) será independiente y no sesgados.
Las funciones G, H e I son similares a la función F, ya que actúan "bit a bit en paralelo" para producir sus salidas de los bits de X, Y y Z, en la medida que si cada bit correspondiente de X, Y y Z son independientes y no sesgados, entonces cada bit de G(X,Y,Z), H(X,Y,Z) e I(X,Y,Z) serán independientes y no sesgados. Nótese que la funcion H es la comparación bit a bit "xor" o función "paridad" de sus entradas.
Este paso usa una tabla de 64 elementos T[1 ... 64] construida con la función seno. Denotaremos por T[i] el elemento i-ésimo de esta tabla, que será igual a la parte entera del valor absoluto del seno de 'i' 4294967296 veces, donde 'i' está en radianes.
Código del MD5:
/* Procesar cada bloque de 16 palabras. */ para i = 0 hasta N/16-1 hacer
/* Copiar el bloque 'i' en X. */
para j = 0 hasta 15 hacer
hacer X[j] de M[i*16+j].
fin para /* del bucle 'j' */
/* Guardar A como AA, B como BB, C como CC, y D como DD. */ AA = A BB = B CC = C DD = D
/* Ronda 1. */
/* [abcd k s i] denotarán la operación
a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
/* Hacer las siguientes 16 operaciones. */
[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]
/* Ronda 2. */
/* [abcd k s i] denotarán la operación
a = b + ((a + G(b,c,d) + X[k] + T[i]) <<< s). */
/* Hacer las siguientes 16 operaciones. */
[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]
/* Ronda 3. */
/* [abcd k s t] denotarán la operación
a = b + ((a + H(b,c,d) + X[k] + T[i]) <<< s). */
/* Hacer las siguientes 16 operaciones. */
[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]
/* Ronda 4. */
/* [abcd k s t] denotarán la operación
a = b + ((a + I(b,c,d) + X[k] + T[i]) <<< s). */
/* Hacer las siguientes 16 operaciones. */
[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]
/* Ahora realizar las siguientes sumas. (Este es el incremento de cada
uno de los cuatro registros por el valor que tenían antes de que
este bloque fuera inicializado.) */
A = A + AA
B = B + BB
C = C + CC
D = D + DD
fin para /* del bucle en 'i' */
Paso 5. Salida
El resumen del mensaje es la salida producida por A, B, C y D. Esto es, se comienza el byte de menor peso de A y se acaba con el byte de mayor peso de D.
Seguridad
MD5 ha sido ampliamente usado, y originalmente se pensaba que era criptográficamente seguro. No obstante, ciertas investigaciones han destapado vulnerabilidades que hacen cuestionable un futuro uso del MD5. El 17 de Agosto del año 2004 Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hongbo Yu anunciaron que habían descubierto colisiones de hash para MD5. Su ataque sólo llevó una hora de cálculo con un clúster IBM P690.
Aunque el ataque de Wang era analítico, el tamaño del hash (128 bits) es suficientemente pequeño para poder contemplar ataques de 'fuerza bruta' tipo 'cumpleaños'. MD5CRK era un proyecto distribuido que comenzó en Marzo del 2004 con el propósito de demostrar que MD5 es inseguro encontrando una colisión usando un ataque de 'fuerza bruta', aunque acabó poco después del aviso de Wang.
Debido al descubrimiento de un método fácil para generar colisiones de hash, muchos investigadores recomiendan otros algoritmos tales como SHA-1 o RIPEMD-160, para ser usados en lugar de MD5.
Aplicaciones
Los resúmenes MD5 se utilizan extensamente en el mundo del software para proporcionar la seguridad de que un archivo descargado de internet no se ha alterado. Comparando una suma MD5 publicada con la suma de comprobación del archivo descargado, un usuario puede tener la confianza suficiente de que el archivo es igual que el publicado por los desarrolladores. Esto protege al usuario contra los 'Caballos de Troya' o 'Troyanos' y virus que algún otro usuario malicioso pudiera incluir en el software. La comprobación de un archivo descargado contra su suma MD5 no detecta solamente los archivos alterados de una manera maliciosa, también reconoce una descarga corrupta o incompleta.
Para comprobar la integridad de un archivo descargado de Internet se puede utilizar una herramienta MD5 para comparar la suma MD5 de dicho archivo con un archivo MD5SUM con el resumen MD5 del primer archivo. En los sistemas UNIX, el comando de md5sum es un ejemplo de tal herramienta. Además, también está implementado en el lenguaje de scripting PHP como MD5("") entre otros.
En sistemas UNIX y GNU/Linux se utiliza el algoritmo MD5 para encriptar las claves de los usuarios. En el disco se guarda el resultado del MD5 de la clave que se introduce al dar de alta un usuario, y cuando éste quiere entrar en el sistema se compara la entrada con la que hay guardada en el disco duro, si coinciden, es la misma clave y el usuario será autenticado. He ahí el problema de encontrar y generar colisiones de hash a voluntad.
El MD5 también se puede usar para comprobar que los correos electrónicos no han sido alterados usando llaves públicas y privadas.
Véase también
Enlaces externos
- Implementación en múltiples lenguajes del MD5
- 1 Tb de RainbowTables para MD5/LM/NTLM
- Bibliografía de ataques contra el MD5
- Página que proporciona las salidas MD5, SHA1 y MySQL de una enrada
- RFC del MD5
- Página que da la salida MD5 y SHA-1 de una entrada
- Base de datos en línea de la contraseña MD5 (cerca de 6 millones de entradas)
- Base de datos en línea de la contraseña MD5 (cerca de 70 millones de entradas)
- Online MD5 Reverser | Hash cracker.
