Funciones
de hash

“Curso de Introducción a la Criptografía” by Jordi Íñigo Griera is licensed under a
Creative Commons Attribution 4.0 International License.
Project hosted at github.com/jig/crypto

Función de hash: objetivos

resume una cadena de longitud arbitraria $m$,
a un valor de tamaño fijo $r$ (el resumen):

$r = h(m)$

adicionalmente, hace falta que la función dé resumenes diferentes para mensajes diferentes...

Colisiones

...es imposible garantizar que una función genere valores diferentes para mensajes diferentes ya que el espacio de resumenes es muy inferior al espacio de mensajes:
$\|r\| \ll \|m\|$

por ejemplo si:
$\left. \begin{aligned} \|r\| & = 256\text{b} \Rightarrow |r| = 2^{256}\text{b} \\ \|m\| & \approx 10^6\text{B} \Rightarrow |m| = 2^{2^{23}}\text{b} \end{aligned} \right\} \frac{|m|}{|r|} = \frac{2^{2^{23}}}{2^{256}} = 2^{2^{23}-256} \approx 2^{8·10^6}$

Función de hash: objetivos

aunque cada resumen $r$ es compartido por una gran cantidad de mensajes (colisiones) una función de hash segura hace que sea infactible encontrar dichas duplicidades

Ataque del cumpleaños

(Birthday attack)

si tenemos un hash de tamaño $\|r\|$ la probabilidad de colisión será muy alta a medida que nos acercamos a las $\sqrt{|r|}$ operaciones

e.g para $\|r\| = 256\text{ b}$ esto son unas $\sqrt{2^{256}} = 2^\frac{256}{2} = 2^{128}$ operaciones

esto implica que para un hash hacen falta resúmenes el doble de largos de lo que hacía falta para las claves para obtener el mismo nivel de seguridad

la security strength de una función de hash de longitud $b$ bits es $b/2$

ejemplos

los hashes recomendados en la actualidad son el SHA-2 y el SHA-3

• SHA-2: longitudes de $256$ b y $512$ b (con variantes truncadas de $224$ b y $384$ b)
• SHA-3: longitudes entre $224$ b a $512$ b

longitudes aproximadamente el doble que las longitudes de claves que las claves de AES ($128$ b, $192$ b, $256$ b) para una seguridad equivalente

¿SHA-2 ó SHA-3?

los primeros están diseñados por la NSA, y los segundos escogidos por el NIST después de organizar una competición para definir el siguiente hash a utilizar

el SHA-3 se ha desarrollado teniendo en cuenta la eficiencia y como backup en caso de encontrar vulnerabilidades en el SHA-2 (diseños totalmente diferentes)

el SHA-2 hasta ahora ha sido sometido a un trabajo de
análisis muy superior al SHA-3

Protocolos basados en hash

seguridad en conjuntos de mensajes

hace falta vigilar que la seguridad con la que protegemos los mensajes individuales, debe extrapolarse a secuencias de mensajes (la sesión)

si no hacemos nada más que lo comentado hasta ahora, seríamos vulnerables a ataques:

• de réplica (replay attacks)
• de reordenado
• de eliminado

Protocolos: Sesión

por ejemplo, añadiendo un identificador de secuencia
$\{1\|\text{more}\|m_1, 2\|\text{more}\|m_2, \dots, n\|\text{last}\|m_n\}$

cada mensaje debe ir protegido por hash, HMAC o firma, cifrado, etc.

Protocolos: Merkle Hash tree

permite firmar bases de datos, discos, de forma eficiente

Protocolos: almacenamiento de contraseñas

el sistema operativo no debe guardar las contraseñas de los usuarios,
no hace falta.

podemos guardar simplemente su hash: $\text{hash}(\text{contraseña})$

pero esto tiene un problema: muchos usuarios usan palabras, nombres, etc. limitados. Las palabras, nombres conocidos són del orden de $\approx 100.000$

un atacante realizar un "diccionario" con el hash de todas las palabras, nombres, etc. (ataque de diccionario)

Contramedidas ataque de diccionario

añadir un valor aleatorio o salt y lo guardamos:
$\text{salt} \| \text{hash}(\text{salt} \| \text{contraseña})$

esto fuerza al atacante a calcular el diccionario para cada contraseña

pero sigue siendo factible realizar $\approx 100.000$ operaciones para encontrar una contraseña

contramedida adicional: realizar iteraciones
implementar un hash "costoso":
$\text{hash}(\text{hash}(\text{hash}(\cdots \text{hash}(\text{salt} \| \text{contraseña}))))$

PRNG basado en hash

también (como con cifradores de bloque) se puede generar una función PRNG basada en hash:

• Hash DRBG
• HMAC DRBG

HMAC

Hash-based Message Authentication Code

MAC: objetivo

MAC es la implementación de la firma símetrica

impide que un atacante pueda modificar el mensaje
sin que el receptor lo detecte

MAC: funcionamiento

nos hará falta una clave secreta que aplicaremos al mensaje con la función $\text{MAC}$:

$t = \text{MAC}(k, m)$

(Nota sobre el cifrado)

sólo usando un algoritmo de cifrado, un atacante puede modificar el mensaje, aunque no lo pueda leer
(incluso hay algoritmos que le permiten realizar operaciones:
e.g. $\oplus$ en cifrado de flujo)

esta funcionalidad es ortogonal con el cifrado:
cifrado y MAC se utilizan combinadas para obtener
confidencialidad y integridad

SHA2-HMAC: primer intento

$t = h(k \| m)$

concatenamos una clave $k$ (o simplemente una contraseña de longitud suficiente) al propio mensaje

Nota: esta implementación es insegura [9.64][9.65]

SHA2-HMAC

el HMAC que se utiliza habitualmente utiliza como cifrado
el propio hash y $\oplus$

$\begin{aligned} k_1 = k \oplus \text{opad} \\ k_2 = k \oplus \text{ipad} \\ \end{aligned}$

$t = \color{red}{h}( k_1 \, \| \, \color{red}{h}( k_2 \| m ) )$

Donde:

$\begin{aligned} \text{opad} &= \text{5C5C}\cdots \\ \text{ipad} &= \text{3636}\cdots \end{aligned}$

(ECBC-MAC) $\rightarrow$