MD5: vulnerabilidades y evoluciones (y II)

ElevenPaths    27 noviembre, 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 2
    n operaciones,
    sino sólo 2
    n/2

Esta segunda vulnerabilidad da lugar a cuatro tipos
de ataques, con un índice de peligrosidad incremental
. El T
ipo1 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

Comentarios

Deja un comentario

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *