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