Picadillo digital

Por Manuel Lucena

Hace unos meses saltó la liebre. El rumor se propagó rápidamente por foros y listas de correo. SHA-1, junto con otras funciones "hash" criptográficas había sido roto, al menos parcialmente. Como muchos de ustedes sabrán, las funciones "hash" forman el corazón de la práctica totalidad de los esquemas de firma digital usados por el gran público. La gran pregunta estaba servida, ¿en qué medida afectará este descubrimiento a los usuarios de a pie? A la vista de la escasa repercusión posterior del asunto, parece que poco. Sin embargo, parece sensato analizar la cuestión con algo de rigor, e ir considerando posibles sustitutos para un futuro quizás no muy lejano...

Las funciones "hash" (la palabra "hash" viene a significar en inglés algo así como "picadillo", así que permítanme llamarlas a partir de ahora "funciones resumen") permiten obtener, a partir de un mensaje cualquiera, una secuencia de bits de longitud fija (habitualmente entre 128 y 256), que hace el papel de "huella digital" (o signatura) del mensaje, en el sentido de que, dado el valor de la función resumen de un mensaje, resulta muy difícil encontrar otro mensaje distinto que dé lugar al mismo valor que el primero. Estas funciones, combinadas con algoritmos de cifrado asimétricos, permiten firmar digitalmente cualquier trozo de información.

Puesto que el conjunto de posibles mensajes de longitud arbitraria es infinito, el conjunto de posibles secuencias de bits de una longitud determinada es finito, y la función resumen siempre asocia una signatura a cualquier mensaje, deberá existir al menos un valor de signatura que corresponda a infinitos posibles mensajes, aunque, en general, todos los posibles valores de la signatura tendrán esta propiedad. Si llamamos colisión a una pareja de mensajes que dan lugar a la misma signatura, podemos deducir que todas las funciones resumen tienen (infinitas) colisiones, por definición.

Lo que es realmente malo no es que las colisiones se den o no, sino que sea fácil encontrarlas. No obstante, existen diferentes grados de compromiso de una función resumen, en función del tipo de colisiones que se encuentren. Los comentaremos de menor a mayor gravedad:

• Alguien encuentra dos mensajes que tienen la misma signatura, pero no tiene un método sistemático para encontrar más. Esta situación es difícilmente explotable, a no ser que el mensaje que queremos falsificar sea exactamente uno de los que tienen la colisión.
• Mediante un algoritmo, se pueden generar dos mensajes tales que sus signaturas coincidan, si bien se desconoce a priori qué valor van a tener. Usualmente, los mensajes obtenidos carecerán de sentido, por lo que el compromiso, aun siendo mportante, no será demasiado grave.
• Dado un mensaje, se puede calcular otro con la misma signatura. Esta situación es bastante más delicada, ya que podremos sustituir un mensaje determinado por otro que, aunque no tenga sentido, pase por auténtico. Esto podría usarse para, por ejemplo, intoxicar las redes p2p que usen funciones resumen para validar los archivos que se descargan, sustituyendo los mismos por basura. También podría servir para negar la autoría sobre una firma digital, alegando que lo que realmente se firmó fue el mensaje falso.
• Dado un mensaje, se puede calcular otro con la misma signatura, y con una estructura determinada. El término estructura hace aquí alusión a la posibilidad de forzar que el mensaje falso tenga algún sentido, cosa que podríamos lograr buscando a partir de manipulaciones del original que no alteren su significado. Pensemos, por ejemplo, en un archivo html en el que añadimos o quitamos espacios, tabuladores o retornos de carro superfluos.

Una vez disipados los rumores y el revuelo inicial, parece que la verdadera noticia era, en realidad, un ataque del segundo tipo sobre los algoritmos SHA-0, MD4, MD5, HAVAL-128 y RIPEMD, y que SHA-1 permanece a salvo por ahora. Para los que no lo sepan, la NSA (Agencia Nacional de Seguridad de los EE.UU.) desarrolló inicialmente el algoritmo SHA, y al poco tiempo le introdujo una modificación para protegerlo de un posible ataque sobre el que no se dieron detalles, dando lugar así a SHA-1 (y pasando el algoritmo original a llamarse SHA-0). Teniendo en cuenta que SHA-0 data de 1993, y SHA-1 de 1995, no parece tan descabellado pensar que todavía quedan aspectos en los que los criptólogos militares llevan diez años de adelanto a los criptólogos civiles.

Manuel Lucena