Funciones hash criptográficas

En esta lección examinamos las funciones hash criptográficas, ampliamente utilizadas en la validación y autenticación rápida.

Al final de la lección habremos cubierto los siguientes temas:

• Qué son las funciones hash criptográficas
• Ejemplos de código Python para ilustrar el uso de funciones hash
• Aplicaciones del hashing criptográfico
• La seguridad del hashing criptográfico
• Amenazas a estos algoritmos por parte de computadoras clásicas y cuánticas

Introducción al hashing criptográfico

Las funciones hash representan un constructo valioso en la criptografía, ya que combinan validación con confidencialidad. Como tales, las funciones hash constituyen un componente importante de los mecanismos de autenticación e integridad de datos, como los códigos de autenticación de mensajes basados en hash (HMAC) y las firmas digitales. Este artículo explica las ideas fundamentales y las consideraciones de seguridad detrás de las funciones hash criptográficas y describe las posibles vulnerabilidades derivadas del surgimiento de la computación cuántica.

Fundamento básico y diseño de las funciones hash

Existen muchas situaciones en las que la autenticación y la verificación de integridad deben realizarse de manera económica y sin revelar información privada a la parte verificadora.

Al descargar software de un servidor remoto, por ejemplo, se necesita un mecanismo eficiente para verificar si el software descargado no ha sido alterado desde su creación por el autor original. De manera similar, al autenticar usuarios en aplicaciones web, sería deseable utilizar un mecanismo que no requiera ni el almacenamiento físico ni la transmisión de las contraseñas reales, lo que podría comprometer potencialmente su confidencialidad.

Las funciones hash criptográficas (CHF) abordan estos requisitos de manera eficiente y segura.

En esencia, una función hash criptográfica toma una entrada (o mensaje) de longitud arbitraria y produce una cadena de longitud fija de n bits. La salida de una CHF también se denomina digest.

Una CHF útil debe cumplir varias propiedades importantes:

1. Uniformidad: Los digests producidos por una CHF deben estar distribuidos uniformemente y parecer aleatorios. El objetivo es asegurar que la salida no revele información sobre la entrada.
2. Determinismo: Para una entrada dada, una CHF debe producir siempre el mismo digest, es decir, debe ser determinista.
3. Irreversibilidad: Una CHF es una función unidireccional: a partir de un digest dado, debe ser prácticamente imposible revertir el hashing y reconstruir la entrada.
4. Inyectividad aproximada: Aunque las CHF son funciones de muchos a uno, deben comportarse como funciones de uno a uno. Esto se logra mediante un conjunto de salida enormemente grande combinado con el efecto avalancha, donde pequeños cambios en la entrada producen digests muy diferentes. Esta propiedad se denomina inyectividad aproximada.

Sobre esta base, un dato puede validarse contra la versión original comparando un digest de los datos con un digest del original.

• Si los dos digests coinciden, se puede suponer con alta probabilidad que los datos son idénticos al original.
• Si los digests difieren, es seguro que los datos han sido manipulados o no son auténticos de alguna otra manera.

Dado que los digests de la CHF en sí mismos no revelan el contenido real de los datos o del original, permiten una validación que preserva la privacidad.

Descripción matemática

Una función hash $H$ puede definirse de la siguiente manera:

$H : Σ^* \rightarrow \{0,1\}^n$

donde $Σ^*$ es el conjunto de todas las cadenas posibles, que podemos considerar como cadenas binarias de longitud arbitraria.

El hecho de que el tamaño del dominio de entrada $Σ^*$ de $H$ sea ilimitado, mientras que el del codominio $\{0,1\}^n$ es limitado, significa que $H$ es necesariamente una función de muchos a uno, que mapea infinitas entradas a una cadena dada de n bits.

Las propiedades de uniformidad y determinismo están elegantemente resumidas en el modelo de oráculo aleatorio del hashing criptográfico.

Ejemplo de hashing criptográfico en Python con SHA-256

Este ejemplo sencillo demuestra el hashing criptográfico con el popular algoritmo SHA-256 de la biblioteca Python cryptography. Primero mostramos cómo una ligera diferencia en los textos planos produce una diferencia muy grande en los digests hash.

# Added by doQumentation — required packages for this notebook
!pip install -q cryptography

# Begin by importing some necessary modules
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes

# Helper function that returns the number of characters different in two strings
def char_diff(str1, str2):
    return sum(str1[i] != str2[i] for i in range(len(str1)))

# Messages to be hashed
message_1 = b"Buy 10000 shares of WXYZ stock now!"
message_2 = b"Buy 10000 shares of VXYZ stock now!"

print(f"The two messages differ by { char_diff(message_1, message_2)} characters")

The two messages differ by 1 characters

Los dos mensajes difieren en exactamente un carácter.

A continuación, instanciamos objetos hash para habilitar el proceso de hashing, que implica llamadas a dos métodos: update y finalize.

Vemos que debido al efecto avalancha en la CHF SHA-256, una diferencia de un solo carácter en los mensajes de entrada produce dos digests muy diferentes.

# Create new SHA-256 hash objects, one for each message
chf_1 = hashes.Hash(hashes.SHA256(), backend=default_backend())
chf_2 = hashes.Hash(hashes.SHA256(), backend=default_backend())

# Update each hash object with the bytes of the corresponding message
chf_1.update(message_1)
chf_2.update(message_2)

# Finalize the hash process and obtain the digests
digest_1 = chf_1.finalize()
digest_2 = chf_2.finalize()

# Convert the resulting hash to hexadecimal strings for convenient printing
digest_1_str = digest_1.hex()
digest_2_str = digest_2.hex()

# Print out the digests as strings
print(f"digest-1: {digest_1_str}")
print(f"digest-2: {digest_2_str}")

print(f"The two digests differ by { char_diff(digest_1_str, digest_2_str)} characters")

digest-1: 6e0e6261b7131bd80ffdb2a4d42f9d042636350e45e184b92fcbcc9646eaf1e7
digest-2: 6b0abb368c3a1730f935b68105e3f3ae7fd43d7e786d3ed3503dbb45c74ada46
The two digests differ by 57 characters

Aplicaciones del hashing criptográfico

Las propiedades únicas de las CHF las hacen adecuadas para una amplia variedad de aplicaciones:

• Verificaciones de integridad de datos: Las funciones hash pueden utilizarse para crear una suma de verificación para un conjunto de datos. Cualquier cambio en los datos, ya sea intencional o no, producirá una suma de verificación diferente y alertará a los sistemas o usuarios sobre la modificación. Además, la suma de verificación suele ser considerablemente más compacta que los datos originales, lo que hace que las comparaciones de sumas de verificación sean muy rápidas.

Figura 1. Hashing seguro para la integridad de datos

• Firmas digitales: Los hashes criptográficos son esenciales para el funcionamiento de las firmas digitales, ya que implican la comparación de mensajes hasheados criptográficamente para garantizar la autenticidad e integridad mientras se preserva la privacidad.

Figura 2. Firmas digitales

• Blockchain y criptomonedas: Las criptomonedas como Bitcoin dependen fuertemente de las CHF, particularmente en la garantía de la integridad de las transacciones y en la habilitación de mecanismos de consenso como la Prueba de Trabajo.

Seguridad del hashing criptográfico

La seguridad de una CHF se evalúa típicamente en función de su resistencia a dos tipos de ataques: ataques de preimagen y ataques de colisión.

Resistencia a preimagen

La resistencia a preimagen significa que, dado un digest, debería ser prácticamente imposible encontrar la entrada.

Esto está relacionado con la propiedad unidireccional de las CHF.

Una buena CHF está diseñada de modo que una parte que desee realizar un ataque de preimagen no tenga mejor opción que un enfoque de fuerza bruta, que tiene una complejidad temporal de $2^n$.

detalles matemáticos

Dada una CHF $H$ y un digest $g$, debe ser computacionalmente inviable encontrar una entrada $m$ de la preimagen de $g$ tal que $H(m) = g$.

Resistencia a colisiones

La resistencia a colisiones significa que es difícil encontrar dos entradas diferentes que produzcan el mismo digest.

Una colisión de hash criptográfico ocurre cuando dos entradas producen el mismo digest. Aunque las colisiones existen inevitablemente debido a la naturaleza de muchos a uno de las CHF, una buena CHF hace que sea impracticable encontrar una de manera deliberada.

La resistencia a colisiones es crucial para aplicaciones como firmas digitales y certificados, donde sería catastrófico si una parte malintencionada pudiera crear una falsificación que produzca el mismo valor hash.

detalles matemáticos de las colisiones de hash

$m_1, m_2$ pueden encontrarse de modo que $H(m_1) = H(m_2)$.

Longitud del hash

La resistencia a colisiones es un requisito más difícil que la resistencia a preimagen y requiere longitudes de salida que sean el doble de las necesarias para la resistencia a preimagen. Esto se debe a que un ataque de fuerza bruta, conocido como ataque de cumpleaños, que puede utilizarse para identificar colisiones de hash, tiene una complejidad temporal de $2^{n/2}$.

En ausencia de debilidades criptoanalíticas, la seguridad de una función hash está influenciada principalmente por su longitud de hash. Cuanto más largo sea el hash, más seguro será, ya que los ataques de fuerza bruta se vuelven más difíciles.

Funciones hash criptográficas de uso común

La siguiente tabla enumera algunas funciones hash criptográficas de uso común junto con sus longitudes de hash y áreas de aplicación principales:

Función hash	Longitud de salida (bits)	Aplicaciones comunes
MD5	128	Verificación de integridad de archivos, sistemas heredados, fines no criptográficos
SHA-1	160	Sistemas heredados, Git para control de versiones
SHA-256	256	Criptomoneda (Bitcoin), firmas digitales, certificados
SHA-3	Variable (hasta 512)	Diversas aplicaciones criptográficas, sucesor de SHA-2
Blake2	Variable (hasta 512)	Criptografía, reemplaza MD5/SHA-1 en algunos sistemas
Blake3	Variable (hasta 256)	Criptografía, hashing de archivos, integridad de datos

• MD5 y SHA-1, aunque todavía se encuentran en aplicaciones menos críticas para la seguridad, se consideran obsoletos en términos de resistencia a colisiones y no se recomiendan para nuevos sistemas. SHA-256, parte de la familia SHA-2, está ampliamente difundido y actualmente es seguro para la mayoría de las aplicaciones.
• SHA-3 es un estándar más reciente, seleccionado por NIST en 2015 como ganador del concurso de funciones hash de NIST. Está diseñado como un reemplazo directo de SHA-2, pero también tiene algunas otras propiedades internas y es resistente a ciertos tipos de ataques que podrían ser efectivos contra SHA-2.
• Blake2 y Blake3 son funciones hash criptográficas que son más rápidas que MD5, SHA-1, SHA-2 y SHA-3, pero al menos tan seguras como el estándar más reciente SHA-3. Se utilizan cada vez más en nuevos sistemas, especialmente donde la velocidad es importante.

Riesgos cuánticos para el hashing criptográfico tradicional

La amenaza cuántica principal para el hashing criptográfico proviene de los ataques de fuerza bruta.

Dado un digest, un atacante intenta probar entradas aleatorias hasta encontrar una que produzca el mismo digest.

Con $n$ bits en la entrada, hay $2^n$ valores posibles. Por lo tanto, el atacante debe probar aproximadamente $2^{n-1}$ entradas para tener una probabilidad de éxito superior al 50%.

Algoritmo de Grover

Para un contexto de búsqueda no estructurada de este tipo, el algoritmo de Grover puede ofrecer una aceleración cuadrática mediante una técnica llamada amplificación de amplitud cuántica y reducir la complejidad temporal de un ataque de preimagen a $2^{n/2}$.

En la práctica, esto significa que una CHF de 256 bits, que actualmente se considera segura contra ataques de preimagen por computadoras clásicas, ofrecería el mismo nivel de seguridad que una CHF de 128 bits frente a un atacante cuántico que emplee el algoritmo de Grover.

No se conoce que el algoritmo de Grover por sí solo proporcione aceleraciones cuánticas adicionales frente a ataques de colisión más allá de los límites del ataque de cumpleaños, que puede realizarse en computadoras clásicas. Dado que el ataque de cumpleaños clásico ya obliga a las CHF a usar longitudes de hash el doble de largas que las requeridas para la resistencia a preimagen, el hecho de que la búsqueda de Grover reduzca efectivamente a la mitad la longitud del hash en relación con los ataques de preimagen no representa una amenaza práctica.

Por ejemplo, realizar aproximadamente $2^{128}$ operaciones para un ataque de preimagen asistido por Grover contra SHA-256 seguiría siendo inviable en un futuro previsible.

Algoritmo BHT

Un algoritmo cuántico que combina aspectos del ataque de cumpleaños con la búsqueda de Grover fue propuesto en 1997 por Brassard, Hoyer y Tapp (BHT) y ofrece un escalamiento teórico de $O(2^{n/3})$ para encontrar colisiones de hash. Sin embargo, este escalamiento mejorado presupone la existencia de tecnología de memoria de acceso aleatorio cuántica QRAM, que actualmente no existe.

Sin QRAM, el escalamiento realizable es $\tilde{O}(2^{2n/5})$, y para las longitudes de hash actualmente en uso, esta mejora marginal en la capacidad de encontrar colisiones en comparación con el ataque de cumpleaños no representa una amenaza crítica.

Resumen

Las funciones hash criptográficas son un componente esencial para garantizar la integridad de los datos y la privacidad en los sistemas de información digital, y encuentran amplia aplicación en muchos contextos.

Los requisitos de seguridad de las CHF se entienden principalmente en términos de su resistencia a ataques de preimagen y de colisión. Para CHF bien diseñadas, la longitud del hash es un buen indicador del nivel de seguridad.

Aunque la aparición de computadoras cuánticas capaces de ejecutar los algoritmos de Grover y BHT afecta teóricamente la resistencia a preimagen y colisiones de las CHF tradicionales, las largas longitudes de hash que ya se utilizan hoy en día significan que los algoritmos modernos de hashing criptográfico como SHA-3 probablemente seguirán siendo seguros — sujeto al descubrimiento de ataques criptoanalíticos previamente desconocidos.

La relevancia de las CHF radica en su papel como bloque de construcción fundamental para los esquemas criptográficos resistentes a la cuántica, que aseguran que la información digital permanezca segura incluso frente a posibles avances futuros en algoritmos y tecnologías de computación cuántica.