Cripografía

Funciones Hash en Criptografía
(Tema 6)

Uso de las funciones hash en criptografía
Una de las aplicaciones más interesantes de la
criptografía es la posibilidad real de incluir en un
mensaje una firma digital. Todo esto comienza en el
año 1976 cuando Diffie y Hellman presentan un
modelo de cifrado asimétrico con clave pública. Con
los sistemas de clave simétrica esto era inviable.
Noobstante, dado que los sistemas de clave pública
son muy lentos, en vez de firmar digitalmente el
mensaje completo, en un sistema criptográfico se
incluirá como firma digital una operación con la clave
privada sobre un resumen o hash de dicho mensaje
representado por sólo una centena de bits.
© Jorge Ramió Aguirre

Madrid (España) 2006

Funciones hash
Mensaje = M ⇒ Función Resumen =h(M)
Firma (rúbrica): r = EdE{h(M)}
dE es la clave privada del emisor que firmará h(M)
¿Cómo se comprueba la identidad en destino?
Se descifra la rúbrica r con la clave pública del
emisor eE. Al mensaje en claro recibido M’ (se
descifra si viene cifrado) se le aplica la misma
función hash que en emisión. Si los valores son
iguales, la firma es auténtica y el mensaje íntegro:
Calcula: EeE(r)= h(M)
Compara: ¿h(M’) = h(M)?
© Jorge Ramió Aguirre

Madrid (España) 2006

¿Qué seguridad nos da
un resumen de k bits?

Seguridad asociada a una función hash
Suponga que hemos creado una función hash de forma que el resumen es
sólo de 4 bits, independientemente del tamaño del mensaje de entrada.
La pregunta es: ¿cuál es la probabilidad de que dos mensajes distintos
tengan igualfunción hash? Si esta probabilidad fuese muy baja (en este
caso 1/16: hash desde 0000 hasta 1111) podría darse el siguiente caso:
alguien modifica nuestro mensaje firmado, y envía ese mensaje falso con
la firma del primero ya que en ambos casos son los mismos 4 bits...
Mensaje 1: “Rechazamos el contrato por no interesarnos nada” hash: 1101
Mensaje 2: “Firma todo lo que te pongan porque nosinteresa” hash: 1101
Observe que ambos mensajes tienen 47 caracteres. Así, podríamos crear
una gran cantidad de mensajes diferentes que digan casi lo mismo, incluso
con igual número de caracteres... ¡hasta que los dos hash coincidan!
Por este motivo las funciones hash para que sean interesantes en
criptografía, deben cumplir un conjunto de propiedades.

© Jorge Ramió Aguirre

Madrid (España)2006

Propiedades de las funciones hash
h(M) será segura si tiene las siguientes características:
1. Unidireccionalidad. Conocido un resumen h(M), debe
ser computacionalmente imposible encontrar M a
partir de dicho resumen.
2. Compresión. A partir de un mensaje de cualquier
longitud, el resumen h(M) debe tener una longitud fija.
Lo normal es que la longitud de h(M) sea menor.
3. Facilidadde cálculo. Debe ser fácil calcular h(M) a
partir de un mensaje M.
4. Difusión. El resumen h(M) debe ser una función
compleja de todos los bits del mensaje M. Si se
modifica un bit del mensaje M, el hash h(M) debería
cambiar aproximadamente la mitad de sus bits.
© Jorge Ramió Aguirre

Madrid (España) 2006

Colusiones: resistencia débil y fuerte
5. Colusión simple. Conocido M, serácomputacionalmente imposible encontrar otro M’ tal
que h(M) = h(M’). Se conoce como resistencia débil a
las colusiones.
6. Colusión fuerte. Será computacionalmente difícil
encontrar un par (M, M’) de forma que h(M) = h(M’).
Se conoce como resistencia fuerte a las colusiones.
Ataque por la paradoja del cumpleaños
Para tener confianza en encontrar dos mensajes con el mismo
resumen h(M)-probabilidad ≥ 50%- no habrá que buscar en
2n (p.e. 2128), bastará una búsqueda en el espacio 2n/2 (264).
¡La complejidad algorítmica se reduce de forma drástica!
© Jorge Ramió Aguirre

Madrid (España) 2006

La paradoja del cumpleaños
Problema: Cuál será la confianza (probabilidad > 50%) de que en un
aula con 365 personas -no se tiene en cuenta el día 29/02 de los años
bisiestos- dos de...