Qué ha pasado con SHA-1 y el nuevo ataque. Una explicación sencilla

Se ha anunciado “otro clavo en la tumba de SHA-1” en forma de estudio que demuestra, de otra manera y una vez más, su debilidad. Aunque suene complejo, no es tan complicado. Cada cierto tiempo se vienen oyendo noticias sobre la debilidad de los algoritmos de hash, pero no siempre somos conscientes de qué significa y si son ataques teóricos prácticos. Vamos a intentar aclararlo.

Pequeña introducción
Una colisión en un algoritmo de hash es conseguir que dos flujos de datos diferentes tengan el mismo hash. SHA-1 son 160 bits y por tanto “solo” 2^160 combinaciones finitas. Pero el flujo de entrada de datos es infinito, así que teóricamente las colisiones son posibles, y de hecho necesitarías en 2^80 combinaciones de media por fuerza bruta para encontrarlas, algo que hoy por hoy es computacionalmente muy complejo. Las colisiones a su vez pueden ser de dos tipos, de prefijos “Idénticos” (o “clásico”) y de “Prefijos elegidos”.

Prefijos idénticos y prefijos elegidos
En las idénticas, digamos que el atacante no tiene control sobre los mensajes en los que se encuentra la colisión, sino que los elige el algoritmo. Por tanto es menos útil desde el punto de vista práctico (para un atacante). Se tiene que partir de la base de que existe un prefijo con mismo hash,y a partir de ahí se le añaden payloads diferentes para que todo el conjunto tenga el mismo hash, aunque el contenido sea diferente.

Esto es muy útil para crear documentos con un mismo hash y diferente contenido. Como un documento o binario con un formato compartido contiene muchas partes idénticas por esa misma razón, es bastante habitual realizar pruebas de concepto de este tipo.

Esto se popularizó con el algoritmo de Xiaoyun Wang y Yu en 2004. Diseñó un código para crear ficheros que podían llegar a ser diferentes en hasta 128 bytes, pero compartir un mismo hash MD5. Un año más tarde se publicó el famoso artículo «Attacking Hash Functions by Poisoned Messages – The Story of Alice and her Boss«, donde se mostraban dos ficheros PS (PostScript) con idéntico MD5. Lo consiguieron Magnus Daum y Stefan Lucks. Recordemos que MD5 son 128 bits y SHA-1, 160. Google no se consiguió lo mismo con SHA-1 hasta doce años más tarde y un coste más elevado.

Esto se mejoró sustancialmente en 2007 cuando Marc Stevens, Arjen K. Lenstra, y Benne de Wege pudieron crear dos binarios ejecutables completamente diferentes con mismo MD5, gracias a los prefijos «elegidos». Con los prefijos elegidos se abría una nueva fórmula, en la que se ponían en peligro los certificados, por ejemplo, con firmas digitales completamente diferentes pero que se podía simular que disponían del mismo hash, puesto que en un certificado solo se firma el hash de su información.

Por tanto, tenemos por un lado los ataques clásicos de Wang y demás con prefijo idéntico y por otro lado, Stevens y demás con sus prefijos elegidos. Uno más sencillo computacionalmente que el otro, y el segundo también más potente.

Y ahora, la carrera por reducir la potencia en cada modalidad
Una vez establecidas las bases de la teoría, tenemos una carrera para reducir la potencia necesaria para su cálculo, porque no olvidemos que todo esto se trata al final de fuerza bruta. No es lo mismo computar 2^80 que 2^60. Uno puede marcar la diferencia con respecto al otro sobre qué es factible hoy en día. Si reducimos el número, puede que se haya conseguido un logro, sin duda, pero quizás siga sin ser factible para la computación actual. Por tanto, tenemos ataques teóricos, donde con algoritmos en papel, reduce la potencia pero pueden ser imposibles hoy. Por otro lado, tenemos ataques prácticos con la computación actual. Por supuesto, con el tiempo los teóricos pueden volverse prácticos.

Para entender qué ha pasado con SHA-1 y por qué debemos preocuparnos, se puede realizar un paralelismo con MD5.

• 1992: se publica MD5 y en teoría se debería poder romper en 2^64 con fuerza bruta (se le suele llamar ataque cumpleaños).
• 1993: ya se habla de pseudo colisiones, pero nada preocupante para la época (vectores de inicialización diferentes que ofrecían el mismo digest).
• 2004: como hemos mencionado, colisiones de prefijo idéntico conseguidas en 2^40. Algo ya «práctico» en una hora.
• 2005: ficheros diferentes, mismo MD5 con prefijos elegidos. Crean dos certificados con mismo MD5.
• Curiosidad: 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.
• 2006: colisiones de prefijo elegido en 2^49.
• 2009: se perfeccionan los ataques hasta unos 2^16 los idénticos y 2^39 los elegidos. Se crea una autoridad de certificación falsa con mismo MD5 gracias a 200 consolas PlayStation calculando colisiones. Cualquier certificado puede aparecer como válido ante una CA que use MD5. Muere definitivamente en la práctica y en la teoría.

Por otro lado, la historia de SHA-1 va más o menos así.

• 1995: se publica SHA-1. En teoría se debería romper en 2^80 (la mitad de 160) con fuerza bruta.
• 2005: SHA-1, se publica un primer ataque de colisión con prefijos idénticos en 2^69, algo computacionalmente costoso para el momento y por tanto complejo en la práctica. Aun así ya el NIST recomendó ir migrando. Lo consideraría obsoleto en 2011.
• 2012: se consigue mejorar los ataques de prefijo idéntico en 2^61. Algo posible, pero muy caro. Ese mismo año se consiguen que los ataques de prefijo elegido caigan a 2^77.1.
• 2017: Google consigue dos PDF diferentes con mismo hash. Utiliza ataques de prefijo idéntico, que en teoría estaban en 2^61, pero ellos lo consiguen en 2^63 tras varios meses de computación y un coste de más de 100.000 dólares (en GPU).
• 2019: Se consigue reducir la complejidad del algoritmo de colisión de prefijos elegidos hasta entre 2^66 y 2^69. Esto hoy por hoy requeriría bastante computación, pero… ¿y mañana?

Por tanto el paralelismo el claro, muy pronto podremos ver ataques prácticos de colisión de prefijos elegidos en SHA-1, bien porque se mejore aún más el algoritmo, bien porque la capacidad de computación lo permita. Como pasó con MD5, el siguiente paso será crear un certificado o entidad certificadora falsa con mismo SHA-1. Para entonces, más nos vale haber dejado de usar SHA-1 para siempre.