SHA-1 y las "colisiones de cumpleaños"

Saludos a todos los kriptopoleros. Soy Arturo Quirantes, y llevo una temporada siguiendo el nuevo Kriptópolis, aunque todavía no había intervenido (cuestiones de agenda, que dirían los políticos).

Imagino que habréis seguido el debate sobre el SHA-1 y el nuevo ataque chino. Hace unos días escribí un artículo para mi Boletín ENIGMA que os puede resultar de interés. No está disponible en la red, así que -aparte mis suscriptores- sois los primeros en leerlo. Espero que os guste...

(con mis disculpas por si resulta un rollo demasiado largo o pesado).

----

En los últimos meses se han descubierto vulnerabilidades en las funciones hash más habitualmente utilizadas; la última en sufrir ataques ha sido la conocida como SHA-1. Las funciones hash son uno de los elementos menos "glamurosos" del batiburrillo criptográfico actual. El tema es bastante técnico, pero en este Boletín vamos a intentar digerirlo, y siguiendo la filosofía didáctica que nos caracteriza, vamos a tratarlos dejando de lado la terminología matemática farragosa. Aprovecharemos que pasamos por allí para "abrir el motor" y enterarnos de lo que realmente es una firma digital.

Bien, seguro que la expresión "firma digital" os suena. Es el nuevo grial que, según los políticos, nos traerá confianza, seguridad y todo eso a la red; por supuesto, los usuarios de PGP llevamos bastantes años al tanto del asunto. Se llama "firma" porque, a semejanza de las firmas manuscritas tradicionales, relaciona un documento con la persona que lo suscribe. Es, a fin de cuentas, una representación de la voluntad de dicha persona. Escribir "el Taller de Criptografía es una birria" es algo que cualquiera puede hacer; pero firmarlo representa, además, un acto de adhesión hacia dicha afirmación (lo que puede conllevar consecuencias de todo tipo, como por ejemplo que yo le retire el saludo al firmante).

En el caso digital, la voluntad de "firmar" se plasma mediante el uso de la clave privada del firmante. Ya os supondré al tanto de los principios de la criptografía de clave pública (PKC), donde el usuario tiene dos claves, una pública (conocida por todos) para poder cifrar y verificar una firma, y una privada (solamente conocida por su dueño) para poder descifrar y firmar. La idea es que, puesto que solamente el dueño de una clave privada puede activarla, bien pudiera usarse para el acto personal e intransferible de firmar. De modo que, en principio, bastaría con aplicar la clave privada sobre un documento para "firmarlo" digitalmente.

Por supuesto, esto resulta muy inconveniente en la práctica. En primer lugar, la aplicación de una clave asimétrica (sea pública o privada) sobre un archivo es un proceso lento y que produce un segundo archivo de mucho mayor tamaño. En segundo lugar, se supone que clave pública y clave privada son complementarias, y lo que hace una la deshace la otra. Eso quiere decir que, si firmamos y ciframos un documento, lo que estamos haciendo es aplicarle la clave privada y después la clave pública, !con lo que obtenemos el documento original!

Por este y otros motivos, la firma digital se modifica ligeramente. En lugar de aplicar la clave privada sobre todo el documento, se aplica sobre un "destilado" del mensaje. Con "destilado" quiero decir una ristra corta de bits que representan dicho mensaje. En inglés se denomina "hash", palabra curiosa que puede traducirse por revoltillo o picadillo. En lo que sigue, llamaremos M al mensaje y h=H(M) al valor de la función hash.

El lector fiel a mis escritos podrá recordar (y el que no, ya tarda) algunas explicaciones sobre hash y firma digital en el Curso Sencillo de PGP, capítulo 2 y en el Informe "Los entresijos del firmado digital" del año 1997 (caray, cómo pasa el tiempo): ).

Una buena función hash tendrá que cumplir ciertas características. En primer lugar, la discreción: conocido el hash h, debe ser difícil, si no imposible, obtener el valor del mensaje M. También debemos exigir que cualquier alteración, por pequeña que sea, cambie el valor de h de forma significativa. Idealmente, un cambio de un solo bit en el mensaje debería cambiar al menos la mitad de los bits en h. Esto no es muy difícil, si se sabe mezclar bien los bits.

Para empezar, queremos que sea única. Es decir, que dos valores hash diferentes correspondan a firmas diferentes. En realidad, nunca podremos obtener esto, ya que si la función hash es de, digamos 64 bits, solamente habrá 2^64 posibles valores de hash, así que si tenemos 2^64 mensajes mas uno, será inevitable que dos de ellos tengan el mismo hash. En la práctica, lo que hacemos es que el número de bits de la función hash sea lo bastante alto que la probabilidad de hacer dos mensajes con el mismo hash sea ínfima. En general, para un hash de n bits, la probabilidad de encontrar otro mensaje con el mismo hash que el primero ha de ser el que marca la probabilidad pura y dura: 2^(-n). Con n=128, un atacante necesitaría probar con 2^128 mensajes para encontrar un hash igual al de otro mensaje dado. Esto es lo que se conoce como RESISTENCIA DÉBIL A LAS COLISIONES: Para un mensaje M dado, ha de ser imposible (o al menos muy difícil) encontrar otro mensaje M' con el mismo resumen. Es decir, no ha de darse H(M)=H(M').

Sin embargo, existe otra condición más restrictiva, conocida como RESISTENCIA A LAS COLISIONES: Ha de ser difícil hallar al azar dos mensajes M, M' tales que H(M)=H(M'). Parece que son muy parecidas, pero ambas condiciones son diferentes. La diferencia es que en el primer caso M es un mensaje determinado, en tanto que en el segundo caso M y M' son dos mensajes cualesquiera.

Para ilustrar esta diferencia, alguien inventó el concepto de "ataque de cumpleaños". Imagine que entra usted en una habitación llena de gente. ¿Cuántas personas ha de haber para que exista una probabilidad del 50% de que al menos una de ellas tenga un cumpleaños el mismo día que usted?. Asumiendo que todas las fechas de cumpleaños son equiprobables (gemelos y nacidos el 29 de Febrero, abstenerse), la probabilidad de que eso suceda para una reunión de n personas es

P = 1-(364/365)^n

con lo que P>50% se da para n=253. Ahora bien, supongamos que queremos saber cuántas personal hacen falta para que CUALESQUIERA DOS DE ELLAS cumplan años el mismo día. Puesto que ahora no hay que fijarse en un cumpleaños determinado sino en una cualquiera, el cálculo cambia. Ahora la probabilidad viene dada por

P = 1- [365!/(365^n*(365-1)!)]

nos dice que, para P>50% ha de cumplirse n> 22. ¿No se lo cree?. Pues créaselo, es cierto. Esto, en la práctica, significa que una clave de n bits puede producir una colisión débil (h=h' para M dado) una vez de cada 2^n, pero producirá una colisión (h=h' para M, M' cualesquiera) una vez de cada 2^(n/2).

Existen diversas funciones hash con longitud de 128 bits. Un atacante que quisiese hacer un ataque necesitaría probar con 2^128 valores para obtener una colisión débil. Pero para una colisión de cumpleaños (permítaseme llamarla de este modo) le bastaría con probar 2^64 valores, un número grande pero al alcance de un adversario con grandes medios a su alcance. Por eso, las funciones hash se construyen con una longitud mayor. Funciones como MD2, MD4 y MD5 tenían longitud de 128 bits. Ya no se usan mucho, aunque el protocolo de cifrado usado antiguamente en los navegadores (SSL v2.0) usaba MD5 como función hash; también se empleó en las primeras versiones de PGP.

El algoritmo hash más usado en la actualidad es el Secure Hash Standard, SHA-1. Los amantes del ... er... intercambio creativo de archivos en Internet habrán notado que se usa como autenticador, permitiendo detectar si un archivo ha sido modificado. Las transacciones electrónicas por navegador usan SHA-1, así como nuestro conocido programa de cifrado PGP.

SHA-1 es una modificación del SHA, y fue desarrollado por la Agencia de Seguridad Nacional (NSA). Se supone que eso la convierte en un algoritmo muy seguro, ya que esa gente tiene la mayor concentración de matemáticos del mundo y lleva medio siglo largo en el negocio. Por supuesto, habrá quien piense que seguro que han incluido alguna puerta trasera. Hay que tener en cuenta, sin embargo, que si la NSA tiene un lógico interés en trastear con un algoritmo usado para cifrar, le resulta poco útil diseñar un algoritmo usado para la firma digital. A fin de cuentas, SHA-1 forma parte de un algoritmo federal de firma, así que el gobierno de EEUU estaría tirando piedras contra su propio tejado.

Por supuesto, la comunidad científica no se ha limitado a creerse lo que la NSA dice, y han probado todo tipo de ataques contra SHA-1. Ninguno de ellos consiguió nada. Otras funciones como la anteriormente mencionada MD5 cayeron en el camino, pero SHA-1 se reía de ellas.

Hasta ahora.

Lo que un grupo de criptólogos chinos han descubierto es un sistema de búsqueda de colisiones "de cumpleaños" que permite obtener dos hash iguales para dos mensajes con un esfuerzo menor que el de fuerza bruta. Es decir, si un algoritmo hash perfecto de 160 bits permite obtener una "colisión de cumpleaños" con un esfuerzo computacional equivalente a 2^80 operaciones hash, ellos pueden encontrar dicha colisión en SHA-1 con un esfuerzo equivalente a probar 2^69 veces. También han conseguido obtener colisiones de cumpleaños en la versión antigua, SHA, con un esfuerzo de 2^39 operaciones, lo que significa nada y menos. Resulta curioso que en 1995, dos años de crear la función SHA, la NSA la retiró y la sustituyó por la SHA-1, casi idéntica a la anterior salvo por cambios muy sutiles. En su momento se negaron a explicar el porqué de dicho cambio, pero parece que algo se olían.

Aunque un ataque de cumpleaños contra SHA-1 se ha hecho dos mil veces más rápido, sigue siendo del orden de diez mil veces más difícil que un ataque contra DES. Y los ataques que requieran colisiones débiles (por ejemplo, encontrar otro mensaje con igual hash que un mensaje dado) no sufren por ello. En la práctica, al menos, la cosa no parece tan grave.

Sin embargo, las implicaciones son preocupantes. Existen casos en los que un ataque de cumpleaños es posible. Para fijar conceptos, supongamos una función hash de 64 bits. Imagínese, lector, que usted va a firmarme un documento digital M que diga lo guapo y listo que soy. Yo redacto el documento y usted la firma. Ahora bien, lo que no sabe es que yo he preparado un segundo documento M' por el que usted me cede su casa, su coche, su cuenta bancaria y su encantadora sobrinita. Es muy poco probable que ambos documentos tengan el mismo valor de función hash, ¿verdad?. Sin embargo, yo puedo tomar ambos documentos y crear múltiples versiones de ambos. Los procedimientos son muchos: añadir espacios diferentes entre palabra y palabra, añadir un punto o una coma extra aquí y allá. De esa forma creo 2^32 variantes de M y otras 2^32 variantes de M'. Cuando encuentre una variante de M que tenga el mismo hash que una variante de M' (es decir, cuando obtenga una colisión de cumpleaños), no tengo más que hacerle firmar a usted la variante de M, en tanto que yo me guardo la variante de M'. Como ambas tienen el mismo hash, al día siguiente cambio M por M', lo llevo a los tribunales y lo echo de su casa. Para hacerlo con SHA-1, antes necesitaba probar 2^80 variantes de M y M', pero gracias a esos simpáticos chinos ahora me basta con 2^69. Este ataque puede frustrarse si usted cambia un carácter cualquiera antes de firmarlo, pero un firmante ignorante de este problema puede aprovecharse impunemente.

Y lo peor es que los ataques criptoanalíticos no hacen sino mejorar. Si hoy tenemos una colisión de cumpleaños en SHA-1 con 2^69 operaciones, ¿cómo estar seguros de que pasado mañana, o el año que viene, no vendrá alguien con un segundo ataque más devastador, o incluso con un ataque que utilice colisiones débiles?. La respuesta es que no lo sabemos. Esto es como una grieta en una presa. No importa que sea microscópica y sólo suelte una gota al día. El mero hecho de que exista implica una brecha a todo lo grueso de la pared, y si mañana sigue en pie eso no garantiza que siga allí pasado mañana.

Lo más curioso es que se levantó la liebre antes incluso de saber en qué consiste el ataque criptoanalítico de Wang, Yin y Yu (que así se llaman los chinos en cuestión). Bruce Schneier lo anunció en su blog, y al par de días solamente teníamos un artículo de tres páginas (fechado el 13 de Febrero), y que se limitaba a dar los resultados parciales. Es decir, se mostraban dos mensajes breves con sus hash,!y ni siquiera se referían a SHA-1! Un ejemplo se refería a SHA, el otro a una versión simplificada (no la completa) de SHA-1.

A pesar de ello, el ataque tri-chino ha sacudido a la comunidad criptográfica. PGP ya ha anunciado que cambiará su función hash por otra más segura, y ha sugerido variantes de longitud mayor como SHA-256 y SHA-512. En palabras de Jon Callas, de PGP, "es hora de caminar hacia la salida anti-incendios, pero sin correr". Las alarmas suenan y no se ve todavía el humo, pero es de sabios levantarse ahora que hay tiempo en lugar de esperar a que tengamos un nuevo edificio Windsor entre manos.

En España, las autoridades responsables del tan cacareado DNI digital tendrán que afrontar este nuevo problema. El lanzamiento de dicho documento electrónico ha sido pospuesto una y otra vez, y aunque nunca se han dado motivos sospecho que se debe a las dificultades inherentes a esa tarea (véase p. ej. "Tarjetas no tan inteligentes" en el Boletín ENIGMA nº 1). La Guarcia Civil, cuyos miembros ya tienen tarjetas de identificación digital, tendrá que replantearse las cosas, y el Ministerio de Defensa español -que prepara su propia infraestructura de clave pública- hará bien en pensárselo dos veces.

A corto plazo, podremos apañárnoslas con algoritmos tipo SHA-256, que PGP se ha apresurado a abrazar. Más adelante, la idea de Bruce Schneier de organizar un concurso internacional para escoger un nuevo estándar de hash (similar al que se organizó para jubilar al DES, y que desembocó en la elección de Rijndael como Estandar Avanzado de Cifra, AES) parece el mejor camino a seguir.

Paradójicamente, este tropiezo puede ser beneficioso para la comunidad criptográfica en su conjunto. Cada ataque conlleva su contraataque, y los nuevos algoritmos hash que surjan serán más fuertes que los anteriores. También sirve para que los criptólogos no se duerman en los laureles pensando que ya está hecho todo. Muy por el contrario, la lucha entre cifra y contracifra sigue tan en boga como en tiempos de las ciudades-estado italianas. Martin Gardner, el mítico columnista de la revista Investigación y Ciencia, no podía haberse equivocado más cuando escribió en 1977 lo que sigue:

"Los computadores y la teoría de complejidad están llevando a la criptografía a una etapa excitante, que quizás adquiera tintes tristes. Repartidos por todo el mundo se encuentran hombres y mujeres de gran inteligencia, algunos de ellos geniales, que han dedicado sus vidas al dominio del análisis criptográfico moderno. A partir de la Segunda Guerra Mundial, incluso aquellas claves gubernamentales y militares que no son de uso único se han hecho tan difíciles de descifrar que el talento de estos expertos va siendo cada vez menos útil. Estas personas se encuentran ahora encima de trampillas a punto de abrirse y sumirlos en las profundidades del olvido."

Esto escribió en 1977, poco después de la presentación en sociedad del algoritmo de clave pública RSA. Pues lamento contradecirle, maestro Gardner, pero esas trampillas llevan tres décadas sin abrirse. Y, a juicio de lo que vemos, todavía tardaremos mucho en verlo. Las profundidades del olvido siguen esperando.

Arturo Quirantes