MD5

El algoritmo de resumen de mensajes MD5 es una función hash ampliamente utilizada que produce un valor hash de 128 bits. MD5 fue diseñado por Ronald Rivest en 1991 para reemplazar una función hash anterior MD4 y se especificó en 1992 como RFC 1321.

MD5 se puede usar como una suma de verificación para verificar la integridad de los datos contra la corrupción no intencional. Históricamente, se usó ampliamente como una función hash criptográfica; sin embargo, se ha encontrado que sufre de amplias vulnerabilidades. Sigue siendo adecuado para otros fines no criptográficos, por ejemplo, para determinar la partición de una clave particular en una base de datos particionada, y puede preferirse debido a los requisitos computacionales más bajos que los algoritmos hash seguros más recientes.

Historia y criptoanálisis

MD5 es uno de una serie de algoritmos de resumen de mensajes diseñados por el profesor Ronald Rivest del MIT (Rivest, 1992). Cuando el trabajo analítico indicó que era probable que el predecesor de MD5, MD4, no fuera seguro, Rivest diseñó MD5 en 1991 como un reemplazo seguro. (De hecho, Hans Dobbertin luego encontró debilidades en MD4).

En 1993, Den Boer y Bosselaers dieron un resultado temprano, aunque limitado, de encontrar una "pseudo-colisión" de la función de compresión MD5; es decir, dos vectores de inicialización diferentes que producen un resumen idéntico.

En 1996, Dobbertin anunció una colisión de la función de compresión de MD5 (Dobbertin, 1996). Si bien esto no fue un ataque a la función hash MD5 completa, estuvo lo suficientemente cerca como para que los criptógrafos recomendaran cambiar a un reemplazo, como SHA-1 (también comprometido) o RIPEMD-160.

El tamaño del valor hash (128 bits) es lo suficientemente pequeño como para contemplar un ataque de cumpleaños. MD5CRK fue un proyecto distribuido iniciado en marzo de 2004 para demostrar que MD5 es prácticamente inseguro al encontrar una colisión mediante un ataque de cumpleaños.

MD5CRK terminó poco después del 17 de agosto de 2004, cuando Xiaoyun Wang, Dengguo Feng, Xuejia Lai y Hongbo Yu anunciaron colisiones para el MD5 completo. Se informó que su ataque analítico tomó solo una hora en un clúster IBM p690.

El 1 de marzo de 2005, Arjen Lenstra, Xiaoyun Wang y Benne de Weger demostraron la construcción de dos certificados X.509 con diferentes claves públicas y el mismo valor hash MD5, una colisión demostrablemente práctica. La construcción incluía claves privadas para ambas claves públicas. Unos días más tarde, Vlastimil Klima describió un algoritmo mejorado, capaz de construir colisiones MD5 en unas pocas horas en una sola computadora portátil. El 18 de marzo de 2006, Klima publicó un algoritmo que podía encontrar una colisión en un minuto en una sola computadora portátil, utilizando un método que él llama tunelización.

Se han publicado varias erratas de RFC relacionadas con MD5. En 2009, el Comando Cibernético de los Estados Unidos utilizó un valor hash MD5 de su declaración de misión como parte de su emblema oficial.

El 24 de diciembre de 2010, Tao Xie y Dengguo Feng anunciaron la primera colisión MD5 de bloque único (512 bits) publicada. (Los descubrimientos de colisiones anteriores se habían basado en ataques de bloques múltiples). Por "razones de seguridad", Xie y Feng no revelaron el nuevo método de ataque. Lanzaron un desafío a la comunidad criptográfica, ofreciendo una recompensa de US $ 10,000 al primer buscador de una colisión diferente de 64 bytes antes del 1 de enero de 2013. Marc Stevens respondió al desafío y publicó mensajes de un solo bloque en colisión, así como el algoritmo de construcción y fuentes.

En 2011, se aprobó un RFC 6151 informativo para actualizar las consideraciones de seguridad en MD5 y HMAC-MD5.

Seguridad

Un requisito básico de cualquier función hash criptográfica es que debe ser computacionalmente inviable encontrar dos mensajes distintos que tengan el mismo valor. MD5 falla catastróficamente en este requisito; tales colisiones se pueden encontrar en segundos en una computadora doméstica común. El 31 de diciembre de 2008, el Instituto de Ingeniería de Software de CMU concluyó que MD5 estaba esencialmente "criptográficamente roto y no era adecuado para su uso posterior". Las debilidades de MD5 han sido explotadas en el campo, de manera más infame por el malware Flame en 2012. A partir de 2019, MD5 continúa siendo ampliamente utilizado, a pesar de sus debilidades bien documentadas y la desaprobación de los expertos en seguridad.

La seguridad de la función hash MD5 está gravemente comprometida. Existe un ataque de colisión que puede encontrar colisiones en segundos en una computadora con un procesador Pentium 4 de 2,6 GHz (complejidad de 2^24,1). Además, también hay un ataque de colisión de prefijo elegido que puede producir una colisión para dos entradas con prefijos específicos en cuestión de segundos, utilizando hardware informático estándar (complejidad 2³⁹). La capacidad de encontrar colisiones se ha visto favorecida en gran medida por el uso de GPU disponibles en el mercado. En un procesador de gráficos NVIDIA GeForce 8400GS, se pueden calcular entre 16 y 18 millones de hashes por segundo. Una NVIDIA GeForce 8800 Ultra puede calcular más de 200 millones de hashes por segundo.

Estos ataques hash y de colisión se han demostrado en el público en varias situaciones, incluida la colisión de archivos de documentos y certificados digitales. A partir de 2015, se demostró que MD5 todavía se usa bastante, sobre todo por parte de las empresas de investigación de seguridad y antivirus.

A partir de 2019, se informó que una cuarta parte de los sistemas de administración de contenido ampliamente utilizados todavía usan MD5 para el cifrado de contraseñas.

Resumen de problemas de seguridad

En 1996, se encontró una falla en el diseño de MD5. Si bien no se consideró una debilidad fatal en ese momento, los criptógrafos comenzaron a recomendar el uso de otros algoritmos, como SHA-1, que desde entonces también se ha descubierto que es vulnerable. En 2004 se demostró que MD5 no es resistente a colisiones. Como tal, MD5 no es adecuado para aplicaciones como certificados SSL o firmas digitales que dependen de esta propiedad para la seguridad digital. Los investigadores también descubrieron fallas más graves en MD5 y describieron un ataque de colisión factible: un método para crear un par de entradas para las cuales MD5 produce sumas de verificación idénticas. Se lograron más avances para descifrar MD5 en 2005, 2006 y 2007. En diciembre de 2008, un grupo de investigadores utilizó esta técnica para falsificar la validez del certificado SSL.

A partir de 2010, el Instituto de Ingeniería de Software de la CMU considera que MD5 está "criptográficamente roto y no es adecuado para su uso posterior", y la mayoría de las aplicaciones del gobierno de EE. UU. ahora requieren la familia de funciones hash SHA-2. En 2012, el malware Flame aprovechó las debilidades de MD5 para falsificar una firma digital de Microsoft.

Vulnerabilidades de colisión

En 1996, se encontraron colisiones en la función de compresión de MD5, y Hans Dobbertin escribió en el boletín técnico de RSA Laboratories, "El ataque presentado aún no amenaza las aplicaciones prácticas de MD5, pero se acerca bastante... En el futuro, MD5 ya no debería implementarse... donde se requiera una función hash resistente a colisiones."

En 2005, los investigadores pudieron crear pares de documentos PostScript y certificados X.509 con el mismo hash. Más tarde ese año, el diseñador de MD5, Ron Rivest, escribió que "md5 y sha1 están claramente rotos (en términos de resistencia a colisiones)".

El 30 de diciembre de 2008, un grupo de investigadores anunció en el 25.º Congreso de Comunicación del Caos cómo habían utilizado las colisiones MD5 para crear un certificado de autoridad certificadora intermedia que parecía ser legítimo cuando se comprobaba mediante su hash MD5. Los investigadores usaron un clúster de PS3 en la EPFL en Lausana, Suiza, para cambiar un certificado SSL normal emitido por RapidSSL en un certificado de CA funcional para ese emisor, que luego podría usarse para crear otros certificados que parecerían ser legítimos y emitidos por RapidSSL.. VeriSign, los emisores de certificados RapidSSL, dijeron que dejaron de emitir nuevos certificados usando MD5 como su algoritmo de suma de verificación para RapidSSL una vez que se anunció la vulnerabilidad. Aunque Verisign se negó a revocar los certificados existentes firmados con MD5, los autores del exploit (Alexander Sotirov, Marc Stevens, Jacob Appelbaum, Arjen Lenstra, David Molnar, Dag Arne Osvik y Benne de Weger) consideraron adecuada su respuesta. Bruce Schneier escribió sobre el ataque que "ya sabíamos que MD5 es una función hash rota". y que "nadie debería seguir usando MD5". Los investigadores de SSL escribieron: "Nuestro impacto deseado es que las autoridades de certificación dejen de usar MD5 para emitir nuevos certificados". También esperamos que se reconsidere el uso de MD5 en otras aplicaciones."

En 2012, según Microsoft, los autores del malware Flame utilizaron una colisión MD5 para falsificar un certificado de firma de código de Windows.

MD5 usa la construcción Merkle-Damgård, por lo que si se pueden construir dos prefijos con el mismo hash, se puede agregar un sufijo común a ambos para que sea más probable que la aplicación acepte la colisión como datos válidos. Además, las técnicas actuales de detección de colisiones permiten especificar un prefijo arbitrario: un atacante puede crear dos archivos en colisión que comiencen con el mismo contenido. Todo lo que el atacante necesita para generar dos archivos en colisión es un archivo de plantilla con un bloque de datos de 128 bytes, alineado en un límite de 64 bytes, que el algoritmo de detección de colisiones puede cambiar libremente. Un ejemplo de colisión MD5, con los dos mensajes que difieren en 6 bits, es:

d131dd02c5e6eec4 693d9a0698aff95c 2fcab58712467eab 4004583eb8fb7f89
55ad340609f4b302 83e488832571415a 085125e8f7cdc99f d91dbdf280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e2b487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080a80d1e c69821bcb6a88393 96f9652b6ff72a70

d131dd02c5e6eec4 693d9a0698aff95c 2fcab50712467eab 4004583eb8fb7f89
55ad340609f4b302 83e4888325f1415a 085125e8f7cdc99f d91dbd7280373c5b
d8823e3156348f5b ae6dacd436c919c6 dd53e23487da03fd 02396306d248cda0
e99f33420f577ee8 ce54b67080280d1e c69821bcb6a88393 96f965ab6ff72a70

Ambos producen el hash MD5 79054025255fb1a26e4bc422aef54eb4. La diferencia entre las dos muestras es que se ha invertido el bit inicial de cada nibble. Por ejemplo, el vigésimo byte (compensación 0x13) en la muestra superior, 0x87, es 10000111 en binario. El bit inicial del byte (también el bit inicial del primer cuarteto) se invierte para hacer 00000111, que es 0x07, como se muestra en el ejemplo inferior.

Más tarde también se descubrió que era posible construir colisiones entre dos archivos con prefijos elegidos por separado. Esta técnica se utilizó en la creación del certificado de CA no autorizado en 2008. Anton Kuznetsov propuso en 2014 una nueva variante de búsqueda de colisiones en paralelo mediante MPI, que permitía encontrar una colisión en 11 horas en un clúster informático.

Vulnerabilidad de preimagen

En abril de 2009, se publicó un ataque contra MD5 que rompe la resistencia de preimagen de MD5. Este ataque es solo teórico, con una complejidad computacional de 2^123.4 para una preimagen completa.

Aplicaciones

Los resúmenes MD5 se han utilizado ampliamente en el mundo del software para garantizar que un archivo transferido haya llegado intacto. Por ejemplo, los servidores de archivos a menudo proporcionan una suma de verificación MD5 (conocida como md5sum) precalculada para los archivos, de modo que un usuario pueda comparar la suma de verificación del archivo descargado con ella. La mayoría de los sistemas operativos basados en Unix incluyen utilidades de suma MD5 en sus paquetes de distribución; Los usuarios de Windows pueden usar la función "Get-FileHash" de PowerShell incluida, instalar una utilidad de Microsoft o usar aplicaciones de terceros. Las ROM de Android también utilizan este tipo de suma de comprobación.

Como es fácil generar colisiones MD5, es posible que la persona que creó el archivo cree un segundo archivo con la misma suma de verificación, por lo que esta técnica no puede proteger contra algunas formas de manipulación maliciosa. En algunos casos, no se puede confiar en la suma de verificación (por ejemplo, si se obtuvo a través del mismo canal que el archivo descargado), en cuyo caso MD5 solo puede proporcionar la funcionalidad de verificación de errores: reconocerá una descarga corrupta o incompleta, que se convierte en más probable al descargar archivos más grandes.

Históricamente, MD5 se ha utilizado para almacenar un hash unidireccional de una contraseña, a menudo con extensión de clave. NIST no incluye MD5 en su lista de hashes recomendados para el almacenamiento de contraseñas.

MD5 también se usa en el campo del descubrimiento electrónico, para proporcionar un identificador único para cada documento que se intercambia durante el proceso de descubrimiento legal. Este método se puede usar para reemplazar el sistema de numeración de sellos de Bates que se ha usado durante décadas durante el intercambio de documentos en papel. Como se indicó anteriormente, este uso debe desaconsejarse debido a la facilidad de los ataques de colisión.

Algoritmo

Gráfico 1. Una operación MD5. MD5 consiste en 64 de estas operaciones, agrupadas en cuatro rondas de 16 operaciones. F es una función no lineal; una función se utiliza en cada ronda. M_i denota un bloque de 32 bits de la entrada del mensaje, y K_i denota una constante de 32 bits, diferente para cada operación. c)._s denota un bit rotación izquierda por s lugares; s varía para cada operación. ⊞ ⊞ {displaystyle boxplus } denotes addition modulo 2³².

MD5 procesa un mensaje de longitud variable en una salida de longitud fija de 128 bits. El mensaje de entrada se divide en fragmentos de bloques de 512 bits (dieciséis palabras de 32 bits); el mensaje se rellena para que su longitud sea divisible por 512. El relleno funciona de la siguiente manera: primero, se añade un solo bit, 1, al final del mensaje. A esto le siguen tantos ceros como sean necesarios para aumentar la longitud del mensaje hasta 64 bits menos que un múltiplo de 512. Los bits restantes se rellenan con 64 bits que representan la longitud del mensaje original, módulo 2 ⁶⁴.

El algoritmo MD5 principal opera en un estado de 128 bits, dividido en cuatro palabras de 32 bits, denominadas A, B, C, y D. Estos se inicializan a ciertas constantes fijas. El algoritmo principal luego usa cada bloque de mensaje de 512 bits para modificar el estado. El procesamiento de un bloque de mensajes consta de cuatro etapas similares, denominadas rondas; cada ronda se compone de 16 operaciones similares basadas en una función no lineal F, adición modular y rotación a la izquierda. La Figura 1 ilustra una operación dentro de una ronda. Hay cuatro funciones posibles; se utiliza uno diferente en cada ronda:

F()B,C,D)=()B∧ ∧ C)Alternativa Alternativa ()¬ ¬ B∧ ∧ D)G()B,C,D)=()B∧ ∧ D)Alternativa Alternativa ()C∧ ∧ ¬ ¬ D)H()B,C,D)=B⊕ ⊕ C⊕ ⊕ DI()B,C,D)=C⊕ ⊕ ()BAlternativa Alternativa ¬ ¬ D){begin{aligned}F(B,C,D) limit=(Bwedge {C})vee (neg {B}wedge {D})G(B,C,D) limit=(Bwedge {D})vee (Cwedgeneg {D})H(B,CoBplus] (Bvee neg {D}end{aligned}}

⊕ ⊕ ,∧ ∧ ,Alternativa Alternativa ,¬ ¬ {displaystyle opluswedgeveeneg } denota las operaciones XOR, AND, OR y NO respectivamente.

Pseudocódigo

El hash MD5 se calcula de acuerdo con este algoritmo. Todos los valores están en little-endian.

// : Todas las variables no se firman 32 bits y envolver modulo 2^32 al calcularVar int s[64], K[64]
Var int i

// s especifica las cantidades de cambio por rondas[ 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, 23, 16, 23 }
s[48..63]:= { 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 }

// Use la parte de entero binario de los pecados de los enteros (Radians) como constantes:para i desde 0 a 63 doK[i]:= floor(2)32 × abdominales (sin(i + 1)))
final for// (O simplemente use la siguiente tabla precomputada):K[ 0. 3]:= { 0xd76aa478, 0xe8c7b756, 0x242070db, 0xc1bdceee }
K[ 4.. 7]:= { 0xf57c0faf, 0x4787c62a, 0xa8304613, 0xfd469501 }
K[ 8..11]:= { 0x698098d8, 0x8b44f7af, 0xff5bb1, 0x895cd7be }
K[12..15]:= { 0x6b901122, 0xfd987193, 0xa679438e, 0x49b40821 }
K[16..19]:= { 0xf61e2562, 0xc040b340, 0x265e5a51, 0xe9b6c7aaa }
K[20.23]:= { 0xd62f105d, 0x02441453, 0xd8a1e681, 0xe7d3fbc8 }
K[24.27]:= { 0x21e1cde6, 0xc33707d6, 0xf4d50d87, 0x455a14ed }
K[28.31]:= { 0xa9e3e905, 0xfcefa3f8, 0x676f02d9, 0x8d2a4c8a }
K[32.35]:= { 0xfffa3942, 0x8771f681, 0x6d9d6122, 0xfde5380c }
K[36..39]:= { 0xa4beea44, 0x4bdecfa9, 0xf6bb4b60, 0xbebfbc70 }
K[40.43]:= { 0x289b7ec6, 0xeaa127fa, 0xd4ef3085, 0x04881d05 }
K[44..47]:= { 0xd9d4d039, 0xe6db99e5, 0x1fa27cf8, 0xc4ac5665 }
K[48..51]:= { 0xf4292244, 0x432aff97, 0xab9423a7, 0xfc93a039 }
K[52.55]:= { 0x655b59c3, 0x8f0ccc92, 0xffeff47d, 0x85845dd1 }
K[56..59]:= { 0x6fa87e4f, 0xfe2ce6e0, 0xa3014314, 0x4e0811a1 }
K[60..63]:= { 0xf7537e82, 0xbd3af235, 0x2ad7d2bb, 0xeb86d391 }

// Inicializar variables:Var int a0:= 0x67452301 / AVar int b0:= 0xefcdab89 / BVar int c0:= 0x98badcfe / CVar int d0:= 0x10325476 / D// Pre-procesamiento: añadir un solo 1 bitapéndice "1" bit a Mensaje // Aviso: los bytes de entrada se consideran como cadenas de bits,
// donde la primera parte es la parte más significativa del byte.// Pre-procesamiento: relleno con cerosapéndice "0" bit hasta longitud del mensaje en bits ≡ 448 (mod 512)

// Aviso: los dos pasos anteriores se implementan de una manera más simple
// en implementaciones que solo funcionan con bytes completos: apéndice 0x80
// y almohadilla con 0x00 bytes para que la longitud del mensaje en bytes  56 56 (mod 64).apéndice longitud original en bits mod 264 a Mensaje

// Procesar el mensaje en sucesivos pedazos de 512 bits:para cada uno 512-bit gorro de mensaje acolchado doromperse en dieciséis palabras de 32 bits M[j], 0 ≤ 15
 // Iniciar el valor de hash para este trozo: Var int A:= a0
 Var int B:= b0
 Var int C:= c0
 Var int D:= ♪
 // Loop principal: para i desde 0 a 63 do Var int F, g
 si 0 ≤ 15 entoncesF:= (B) y C) o ()no B) y D)
g:= i
 si 16 ≤ ≤ 31 entoncesF:= (D y B) o ()no D) y C)
g:= (5×i + 1) mod 16
 si 32 ≤ ≤ 47 entoncesF:= B xor C xor D
g:= (3×i + 5) mod 16
 si 48 ≤ ≤ 63 entoncesF:= C xor (B) o ()no D))
g:= (7×i) mod 16
 // Tenga cuidado de las definiciones siguientes de a,b,c,dF:= F + A + K[i] + M[g]  // M[g] debe ser un bloque de 32 bitsA:= D
D:= C
C:= B
B:= B + izquierda(F, s[i])
 final for // Agregue el hash de este pedazo para resultar hasta ahora:a0:= a0 + A
b0:= b0 + B
c0:= c0 + C
d0:= d0 + D
final forVar char digest[16]:= a0 apéndice b0 apéndice c0 apéndice ♪ // (La salida está en poco fin)

En lugar de la formulación del RFC 1321 original que se muestra, se puede usar lo siguiente para mejorar la eficiencia (útil si se usa lenguaje ensamblador; de lo contrario, el compilador generalmente optimizará el código anterior. Dado que cada cálculo depende de otro en estas formulaciones, esto es a menudo más lento que el método anterior donde el nand/and se puede paralelizar):

(0 ≤ ≤ 15): F:= D xor (B) y (C) xor D))
(16 ≤ i ≤ 31): F:= C xor (D y (B) xor C))

Hashes MD5

Los hashes MD5 de 128 bits (16 bytes) (también denominados resúmenes de mensajes) suelen representarse como una secuencia de 32 dígitos hexadecimales. A continuación se muestra una entrada ASCII de 43 bytes y el hash MD5 correspondiente:

MD5("El zorro marrón rápido salta sobre el perrito perezoso") =
9e107d9d372bb6826bd81d3542a419d6

Incluso un pequeño cambio en el mensaje dará como resultado (con una probabilidad abrumadora) un hash mayormente diferente, debido al efecto de avalancha. Por ejemplo, agregando un punto al final de la oración:

MD5("El zorro marrón rápido salta sobre el perrito perezoso.") =
e4d909c290d0fb1ca068ffaddf22cbd0

El hash de la cadena de longitud cero es:

MD5(") =
d41d8cd98f00b204e9800998ecf8427e

El algoritmo MD5 se especifica para mensajes que constan de cualquier número de bits; no se limita a múltiplos de ocho bits (octetos, bytes). Algunas implementaciones de MD5, como md5sum, pueden estar limitadas a octetos o es posible que no admitan transmisión para mensajes de una longitud inicialmente indeterminada.

Implementaciones

A continuación se muestra una lista de bibliotecas de criptografía compatibles con MD5:

• Botan
• Bouncy Castle
• cryptlib
• Crypto+
• Libgcrypt
• Nettle
• OpenSSL
• wolfSSL