Entre colisiones

Por: Marcelo Mayorga (Fortinet) - Febrero de 2009

Leyendo un artículo sobre el concurso que se está llevando a cabo en busca de un nuevo algoritmo de hashing (An Algorithm with No Secrets) llamó mi atención la frase “… es imposible evitar las colisiones”. Algo muy cierto, pero que no siempre es expresado correctamente. En varias ocasiones he leído que un algoritmo de hashing para ser seguro no debe conducir a colisiones. Incluso, en un libro de redes muy reconocido podemos encontrar la frase “Nadie puede generar dos mensajes que den como resultado un mismo valor hash” y añade “…para que se cumpla esto, el resultado de la operación (el valor hash) debe ser de 128 bits, preferentemente mayor.” (¿?).

Lo cierto es que las colisiones son inherentes a todas las funciones de hashing. Esta afirmación, que puede parecer obvia para muchos, no lo fue para mi, y les propongo que intentemos demostrarla aunque más no sea de una forma un tanto informal.

Empecemos por definir qué es una función hashing y qué es una colisión.

Función hashing: Es una función que de forma eficiente procesa una cadena de cantidad arbitraria de bits, dando como resultado otra cadena de bits de tamaño fijo (llamado valor hash, fingerprint, message digest, etc.). Algunas acotaciones a esta definición:

• Tienen la particularidad que el más mínimo cambioen la cadena de origen, incluso un bit,  produce un cambio “radical” en la cadena de salida.
• La función es de una vía, es decir irreversible por definición. No se puede calcular el mensaje original a partir del valor hash.

Colisión: Colisión se llama cuando dos cadenas de tamaño arbitrario distintas dan como resultado un mismo valor hash al ser procesados por una misma función de hashing.

De acuerdo a estas definiciones, estamos en presencia de dos conjuntos y una relación entre ellos; 

1. El conjunto de los mensajes planos posibles
2. El conjunto de los valores hash posibles 
3. La relación que es la función de hashing en si.

Sabemos en principio que la cantidad de elementos del conjunto de mensajes planos es infinita ya que es imposible cuantificar la cantidad de mensajes planos posibles. 

Por otro lado sabemos que la cantidad de elementos del conjunto de valores hash es finito por naturaleza. Los hashes son de tamaño fijo, es decir que si hablamos de MD5, nuestro conjunto de hashes tendrá un cardinal de 2¹²⁸, para SHA-1 será de 2¹⁶⁰, etc. 

En cuánto a la relación entre los conjuntos, conocemos de forma tácita datos muy importante. Sabemos que todo mensaje plano al ser procesado por una función de hashing da como resultado un único valor hash. Pareciera una obviedad, ¿no?. Expresado de otra forma; no existen mensajes planos que al ser procesador por una función de hashing no den como resultado un valor hash o den como resultado más de uno. 

Con esto hemos demostrado (muy informalmente) que toda función de hashing producirá eventualmente colisiones. Va de nuevo: Si todos los mensajes planos tienen como resultado un único valor hash (al ser procesados por una función de hashing) y el cardinal del conjunto de valores hash es menor al cardinal del conjunto de mensajes planos, entonces inevitablemente habrá casos en que asignaremos más de un mensaje plano a un mismo valor hash… o sea una colisión. Es más, puede parecer extraño, pero tendremos a lo sumo 2ⁿ elementos que no colisionan e infinitos que sí lo hacen. Esto es cierto para todos las funciones hashing existentes.

Ahora, sabiendo que para todas las funciones de hashing existen infinitas colisiones, sería bueno saber qué determina que una función de este tipo sea considerada robusta. De nuevo con bastante informalidad, podemos decir que las funciones de hashing deben:

• Ser resistente a pre-imagen: Dado un valor hash, es computacionalmente impracticable encontrar el mensaje en texto plano que lo produce. Esto es; conocer el valor hash no ayuda a inferir qué lo produjo (no se puede utilizar ingeniería inversa).
• Ser resistente a segunda pre-imagen: Dado un valor hash y su correspondiente mensaje en texto plano, es computacionalmente impracticable encontrar un segundo mensaje que dé como resultado el mismo valor hash. Es decir, conocer el valor hash y conocer el mensaje que lo produjo no aporta nada para encontrar un segundo mensaje que lleve al mismo resultado.
• Resistencia a colisiones: Es computacionalmente impracticable encontrar dos textos planos cuales quiera que den como resultado un mismo hash. Es decir, que incluso teniendo la posibilidad de elegir los textos planos, no es tarea sencilla elegir dos que produzcan un mismo resultado.

En fin, en no mucho tiempo tendremos un nuevo algoritmo para funciones hashing como resultado de un concurso (lo mismo que sucediera con AES). De antemano sabemos que esa función seguramente no estará exenta de colisiones, pero también sabemos que no por eso será insegura.