MD5: vulnerabilidades y evoluciones (y II)

miércoles, 27 de noviembre de 2013

Ahora que Microsoft y Google (e incluso Twitter) se han embarcado en una especie de carrera criptográfica para potenciar los algoritmos de cifrado, firma, hash y clave pública, es un buen momento para repasar y entender por qué algunos de estos algoritmos dejan de ser útiles y qué alternativas se manejan. El ejemplo más claro de algoritmo obsoleto (pero aún usado) es MD5.

Vulnerabilidades de MD5

Se pueden dar dos tipos principales de vulnerabilidades en los algoritmos de resumen y su seguridad se mide en base a los resultados de la evaluación de estas vulnerabilidades.
  • Resistencia a la preimagen o resistencia a ataques de fuerza bruta. Numéricamente, estos ataques suponen aplicaciones de la función hash 2n veces, siendo n la longitud del resumen.
  • Resistencia a colisiones o a la localización de dos mensajes de entrada que den lugar a un mismo resumen para un mismo algoritmo de cifrado hash (segunda preimagen). Teóricamente se cumple que para confiar en que podemos encontrar dos mensajes que colisionen, no hay que realizar 2n operaciones, sino sólo 2n/2
Esta segunda vulnerabilidad da lugar a cuatro tipos de ataques, con un índice de peligrosidad incremental. El Tipo1 se aplica cuando el atacante es capaz de encontrar colisiones pero no de forma sistemática. El Tipo4 cuando el atacante es capaz de crear un mensaje con sentido cuyo hash colisiona con el hash del mensaje verdadero.
La vulnerabilidad frente a la preimagen no fue la mayor debilidad de MD4, pero en todo caso la longitud de resumen de ambos (128 bits) resulta baja en la actualidad. Es en el aspecto de colisiones y segunda preimagen donde MD4 tuvo mayores problemas, y donde se ha demostrado que MD5 también los presenta.

El origen de la determinación del algoritmo de cifrado MD5 como vulnerable o "oficialmente roto" data de 2004, cuando Xiaoyun Wang y su equipo anunciaron el descubrimiento de colisiones de hash para MD5. En función de este artículo, quedó demostrado que era posible encontrar una colisión a partir de dos mensajes de 1024 bits con un determinado valor inicial. De ahí en adelante, han surgido numerosas publicaciones en esta línea. Destacar entre ellas la realizada en 2007 por Arjen Lenstra de Bell Laboratories. Basándose en el trabajo de Wang desarrolló un método para construir colisiones en 224.8 procesados (unos 10 segundos). El objetivo de todas estas técnicas es el de conseguir multicolisiones, algunas de las cuales surgen a partir de la demostración de la posibilidad de generar nuevos pares de colisiones a partir de una dada. Este hecho quedó probado tras la comprobación matemática de la siguiente enunciación:

Esto se debe al uso de la construcción de Merkle-Damgård, que permite trabajar con números ilimitados de bloques de entrada, pero también la aparición de esta vulnerabilidad.

Teniendo en cuenta que el algoritmo de cifrado MD5 presenta debilidades en la tarea de resistencia a la colisión y que la resistencia a la segunda preimagen queda más que comprometida tras los resultados de los estudios citados, se puede efectivamente concluir que el algoritmo MD5 está "roto".

MD5 roto en la vida real

Desde 1996 se empezaron a conocer "indicios" sobre la debilidad del algoritmo. En 2004 se consiguió crear dos certificados  X.509 distintos con igual hash MD5. En verano de 2005, un australiano consiguió anular una multa de tráfico. El abogado que representaba al amonestado recurrió una denuncia,  argumentando que no se había probado que la imagen obtenida por  la cámara asociada al radar no hubiese sido modificada de ninguna forma. Las autoridades australianas de tráfico respondieron que se utilizaba el algoritmo MD5 para obtener el hash de las imágenes obtenidas. No encontraron a ningún perito que demostrase ante el tribunal la validez de este algoritmo, y por tanto se libró de la multa.

A finales de 2008, Alexander Sotirov, Marc Stevens y otros investigadores consiguieron (usado la potencia de 200 consolas PlayStation3) hacer que cualquier certificado SSL pareciese válido usando certificados que basaban su confianza en MD5. Pero en cierta forma, todo fueron ataques de laboratorio hasta que llegó TheFlame, y usó varias debilidades (entre ellas de MD5) para conseguir un certificado de Microsoft válido. Los problemas hasta entonces más o menos "teóricos" estaban siendo usados por atacantes.

Además de las colisiones, MD5 tiene otros problemas. Para una firma o hash debe ser matemáticamente muy complicado realizar el proceso contrario: calcular los datos que produjeron el hash. Por esta razón, muchos programas almacenan el MD5 de las contraseñas de usuarios en las bases de datos. Hace algunos años se popularizaron las tablas rainbow con información preprocesada sobre hashes MD5. Esto, en teoría, permite a alguien que tenga acceso a esos resúmenes, realizar el proceso inverso en tiempo razonable. Se ha popularizado como método eficaz de "crackeo" para contraseñas de este tipo, con lo que el almacenamiento de credenciales en este formato también se considera ya inseguro.

Conclusión: Evolución hacia SHA-1, SHA-3 y Whirlpool

La resistencia del algoritmo SHA-1 se ha puesto en duda últimamente, por lo que resulta una solución temporal. Aunque su diseño resulta más robusto que el de MD5 con un mayor tamaño de hash code (160 bits), presenta ciertas similaridades con MD4 y MD5 que lo hacen vulnerable al igual que los son éstos. Microsoft ya ha declarado que no lo quiere en sus certificados.

A pesar de que las demostraciones presentadas consiguen superar la seguridad del algoritmo en 263 operaciones, relativamente más rápido que un ataque de fuerza bruta (que requeriría 280 operaciones), todavía son muchas operaciones. Aunque en el futuro es cada vez más probable que romper esta función sea trivial, al aumentar las capacidades de los sistemas de cálculo y, previsiblemente, al centrarse los ataques y estudios en SHA-1 ahora que MD5 ya está "roto".

Actualmente, ya se contemplan y utilizan funciones de SHA de mayor tamaño (por ejemplo, SHA‑512, de 512 bits de longitud es muy usada en certificados). Sin embargo, se busca ya una nueva función hash estandarizada que permita sustituir a SHA-1. Entre las candidatas, SHA-3 (originalmente Keccak, elegido a finales de 2012) y Whirlpool (adoptado como parte del estándar ISO/IEC 10118-3).

 * MD5: vulnerabilidades y evoluciones (I)


Julia Llanos

5 comentarios:

  1. Excelente par de entrada, me ha gustado mucho.

    ResponderEliminar
  2. Hola Julia,

    ¿ no habría que poner h3 = MD5 (m1 + x) y h4 = MD5(m2 + x) ?

    Un saludo.

    ResponderEliminar
  3. Corregido en la imagen. ¡Muchas gracias!

    ResponderEliminar
  4. necesit los tipos de ataque de canal colateral al MD5

    ResponderEliminar