Anatomía de una Función Hash: El Secreto de la Irreversibilidad Criptográfica

En criptografía un hash es una transformación que cambia el mensaje de entrada por otro mensaje llamado “hash”, que es una representación única de ese mensaje, es decir, “hashear” un mismo mensaje siempre nos devolverá el mismo hash. Pero a su vez, es imposible partiendo del hash encontrar cual fue el mensaje que lo generó.

El Hashing lo utilizamos sin darnos cuenta cada vez que creamos una contraseña en un sitio. El servidor nunca almacenará la contraseña en texto plano, sino un hash de ella. Si un ciber atacante roba la base de datos de contraseñas solo robará los hashes y es virtualmente imposible obtener la contraseña a partir del hash. Otro uso es la firma de documentos digitales, para autenticar la propiedad de ellos. Lo que firmamos no es un documento sino un hash del mismo. Esto se debe a que la firma digital es una “encriptación asimétrica” que es computacionalmente demandante, en especial si el documento es pesado.

Se dice que un hash es una “función de una vía” (OWF, por sus siglas en ingles). Una OWF es una definición computacional, e implica que la transformación es computacionalmente simple en un sentido (puede resolverse que es tiempo polinómico) mientras que, en el otro sentido, es computacionalmente inviable (no existe un algoritmo eficiente que pueda, dada una salida, encontrar una entrada que la genere con probabilidad no despreciable en tiempo no exponencial). En otras palabras, decimos que un hash es una función o transformación irreversible.

SHA es el algoritmo de hashing estándar adoptado por la industria. La última y más segura versión de SHA es SHA-3 y viene en 4 variantes, 224, 256, 384 y 512 bits. Esto significa que no importa cuál sea el tamaño de mensaje de entrada, podría ser un video de alta resolución de 30 GB, o un disco SSD de 2 TB o un archivo de texto de 15 bytes, todos ellos generarán un hash del mismo tamaño fijo: 224, 256, 384 o 512 bits, dependiendo de la versión de hash que usemos.

Esto tiene consecuencias importantes. Si el espacio de posibles mensajes de entrada es considerablemente mayor que el espacio de posibles mensajes de salida, entonces varios mensajes pueden generar el mismo hash. En la práctica, el número de hashes posibles es digamos 2^512 (para el caso de SHA-512) mientas que los posibles mensajes de entrada puede ser infinitos. Si varios mensajes tienen el mismo hash, a esto se lo llama colisión.

Las colisiones tienen aspectos positivos y negativos. Empecemos por los negativos. Si 2 o más mensajes de entradas generan la misma salida, nos enfrentamos a un problema matemático que se lo conoce como la “paradoja del cumpleaños”. La paradoja del cumpleaños se suele expresar así: Imaginemos que estamos en un grupo de gente. ¿Cuántas personas se necesitan para que la probabilidad de encontrar 2 personas que cumplan años el mismo día sea del 50%? Intuitivamente alguien podría decir que, habiendo un espacio de fechas de cumpleaños de 365 días, la cantidad de personas que necesitamos para que se produzca una “colisión” de cumpleaños es de 182 aproximadamente. Pues no, con 182 personas la probabilidad que se hace 50% es de que haya alguien que cumple años el mismo día que yo. Es decir, una colisión con un día específico. La pregunta era otra. La pregunta era cual es la cantidad de personas necesarias para que se produzca una colisión cualquiera, no una específica. Y sorprendentemente solo son necesarias 23 personas. Con 182 personas, la probabilidad de una colisión cualquiera es del 100%. Es más, con solo 60 personas, la probabilidad de que exista una colisión es virtualmente 100%.

Un atacante que quiere romper un sistema basado en hashes rara vez necesita atacar un hash específico. Lo que busca es un ataque de colisión, esto es, encontrar dos mensajes cualesquiera, M1 y M2, tal que HASH(M1) = HASH(M2). La paradoja del cumpleaños nos dice exactamente qué tan fácil es esto. Para un hash con una salida de n bits, hay 2^n posibles hashes. En un ataque de fuerza bruta, encontrar el mensaje original de un hash dado implica una complejidad del orden de O[2^n]. Mientras que para un ataque de colisión (Paradoja del Cumpleaños), encontrar dos mensajes cualesquiera que colisionen tiene una complejidad del orden de O[2^(n/2)]. ¡La diferencia es abismal! Reduce el espacio de ataque exponencialmente. Un hash de 128 bits se trasforma en un espacio de ataque de 2^64 operaciones. Pero, ¿por qué es esto tan peligroso en la práctica?

Imagina que un atacante prepara dos contratos: M1 (Contrato legítimo): “Yo, atacante, me comprometo a pagar a la empresa X la suma de $10.000 USD”. Y M2 (Contrato malicioso): “Yo, atacante, declaro que la empresa X me cede el control total de sus activos”. El atacante modifica sutilmente ambos documentos (añadiendo espacios invisibles, cambiando metadatos, etc.) hasta que, gracias a la paradoja del cumpleaños, encuentra una versión de M1 y M2 que producen el mismo hash. Le presenta a la empresa el contrato M1 para que lo firme digitalmente (recordemos que la firma se aplica sobre el hash). Una vez firmado, el atacante puede sustituir el contrato M1 por el M2. Como ambos tienen el mismo hash, la firma digital será válida para ambos.

Veamos ahora el aspecto positivo. El hecho de que más de una entrada pueda generar la misma salida (hash) implica que la función hash es matemáticamente irreversible. Esto se debe a que la función no es inyectiva (es una función de muchos-a-uno) y, por lo tanto, no puede tener una inversa matemática bien definida. Aunque se espera que una buena función hash sea sobreyectiva (que múltiples mensajes de entrada puedan generar todos los hashes posibles), es la falta de inyectividad la que rompe la reversibilidad. Si tenemos un hash y “supiéramos” como revertirlo, esto nos llevaría a varios posibles mensajes de entrada, en la práctica, infinitos. Y esto es una ayuda a la irreversibilidad del proceso de hashing.

A menudo se afirma que las funciones hash son irreversibles precisamente por esta razón, porque el espacio de entrada es mucho mayor que el de salida produciendo que múltiples entradas colisionen en una misma salida, y, por lo tanto, la función no tenga una inversa matemática bien definida. Esta irreversibilidad estructural es real, pero no es la única ni la más importante causa de irreversibilidad criptográfica.

Pero pensemos, por ejemplo, si aplicamos SHA-512 a un conjunto de entradas limitadas a 256 bits. El espacio de mensajes de entrada sera de 2^256, mientras que el de salida será de 2^512 posibles hashes. En ese caso, la función hashing sería matemáticamente inyectiva (no hay colisiones posibles). Y, aun así, sigue siendo considerada irreversible. Sigue siendo un OWF. ¿Por qué?

Porque el proceso de hashing (lo que el algoritmo hace internamente) implica la aplicación de operaciones matemáticamente no reversibles que causan pérdida deliberada y estructural de información. Como, por ejemplo:

• Pérdida por compresión estructural: En cada ronda de SHA, la función de compresión toma más bits de entrada que los que produce como salida. Por ejemplo, en SHA-256, cada bloque de 512 bits se comprime a un estado interno de 256 bits. Esta compresión implica que múltiples patrones de entrada diferentes deben mapearse necesariamente al mismo estado intermedio.
• Pérdida por operaciones lógicas no lineales: Las operaciones como la “función de elección (CH)” donde CH(X,Y,Z) = XOR [ AND(X,Y), AND (NOT(X),Z) ] y la “función mayoría (MAJ)” que devuelve el bit que aparece en la mayoría de las tres entradas, MAJ = XOR [ AND(X,Y), AND(X,Z), AND(Y,Z) ] combinan bits de manera no lineal, mezclando la información de tal forma que conocer el resultado no permite deducir unívocamente los valores originales de X, Y y Z.
• Pérdida por aritmética modular: Las sumas modulares (por ejemplo a + b (mod 2^32)) descartan bits de carry que contenían información sobre la magnitud real de la suma. Si el resultado es X, existen infinitas combinaciones de a y b que producen X cuando se calcula mod 2^32.
• Otras funciones, aunque técnicamente reversibles, son en la práctica irreversible debido a un efecto caótico. Las rotaciones y desplazamientos de bits crean interdependencias tan complejas entre bits distantes que hacen imposible “aislar” la contribución de cada bit individual.

Esta pérdida acumulativa hace que incluso con poder computacional infinito, no exista un camino lógico para reconstruir la entrada original. Aunque algunas etapas internas podrían ser reversibles, la composición completa del algoritmo no lo es: se transforma la información de forma tan caótica que no se puede recuperar la entrada original a partir del hash resultante, ni siquiera teóricamente, y mucho menos computacionalmente.

En este sentido, la irreversibilidad computacional no se deriva solamente de que el espacio de entrada sea mucho mayor que el espacio de salida, sino del diseño interno del algoritmo, que está pensado específicamente para impedir la trazabilidad desde la salida hacia la entrada, incluso aunque no haya colisiones.

Diferencias fundamentales entre el hashing y el cifrado.

Se dice que los algoritmos de cifrado, simétricos (como por ejemplo AES) o asimétricos (como por ejemplo RSA) son funciones reversibles. Dado el texto cifrado y la clave adecuada, se puede recuperar el mensaje original. Sin embargo, esa reversibilidad depende de tener la clave adecuada; sin ella, el proceso es computacionalmente irreversible para cualquier adversario. A estas funciones se la llama “funciones trampa de una vía”. Una función trampa de una vía es una función de una vía (OWF) que puede revertirse si disponemos de cierta información (la llave).

Podría pensarse que una función de hashing se parece a un cifrado donde no se proporciona la clave. Pero esa comparación es incorrecta. El hashing no es cifrado con clave oculta; en el hashing, no hay clave, y la irreversibilidad no se debe a una “falta de información para descifrar”, sino a que la función misma no permite el proceso inverso, ni siquiera en principio. La pérdida de información no es accidental, es parte del diseño.

En conclusión, una función hash criptográfica es irreversible no solo porque comprime grandes cantidades de información en un espacio pequeño, sino porque está construida mediante transformaciones matemáticamente no reversibles. Esa pérdida estructural y deliberada de información convierte al proceso en algo matemáticamente no invertible y, sobre todo, computacionalmente inviable de revertir, incluso en dominios donde la función podría ser inyectiva.