MD5: vulnerabilidades y evoluciones (y II)

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 2ⁿ 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 2ⁿ operaciones,
sino sólo 2^n/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 2^24.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 2⁶³ operaciones,
relativamente más rápido que un ataque de fuerza bruta (que requeriría 2⁸⁰ 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

julia.llanos@11paths.com

MD5: vulnerabilidades y evoluciones (I)La publicidad en las apps de Google Play. Más que una «molestia»