Publicado el 6 de Septiembre del 2018
526 visualizaciones desde el 6 de Septiembre del 2018
187,4 KB
17 paginas
Creado hace 18a (07/03/2006)
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 15
Funciones Hash en Criptografía
Seguridad Informática y Criptografía
Ultima actualización del archivo: 01/03/06
Este archivo tiene: 34 diapositivas
v 4.1
Material Docente de
Libre Distribución
Dr. Jorge Ramió Aguirre
Universidad Politécnica de Madrid
Este archivo forma parte de un curso completo sobre Seguridad Informática y Criptografía. Se autoriza el uso,
reproducción en computador y su impresión en papel, sólo con fines docentes y/o personales, respetando los
créditos del autor. Queda prohibida su comercialización, excepto la edición en venta en el Departamento de
Publicaciones de la Escuela Universitaria de Informática de la Universidad Politécnica de Madrid, España.
Curso de Seguridad Informática y Criptografía © JRA
Capítulo 15: Funciones Hash en Criptografía
Página 711
Uso de las funciones hash en criptografía
Una de las aplicaciones más interesantes de la actual
criptografía es la posibilidad real de añadir en un
mensaje una firma digital: la autenticación completa.
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 antiguos sistemas de cifra de clave
simétrica esto era inviable o bien muy complejo.
No obstante, 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 de cifra con la clave privada
del emisor sobre un resumen o hash de dicho mensaje,
representado por sólo una centena de bits.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 15: Funciones Hash en Criptografía
Página 712
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’ (si
viniese cifrado, se descifra) 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)?
¿Qué seguridad nos da
un resumen de k bits?
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Página 713
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 igual funció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 nos interesa” hash: 1101
Observe que ambos mensajes tienen 47 caracteres. Así, podríamos crear
una gran cantidad de mensajes diferentes que digan cosas distintas incluso
con igual número de caracteres... ¡hasta que los dos hash coincidan!
Por este motivo, para que las funciones hash sean interesantes en
criptografía deben cumplir un conjunto de propiedades.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 15: Funciones Hash en Criptografía
Página 714
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 que el mensaje M.
3. Facilidad de 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 solo bit
del mensaje M, el hash h(M) debería cambiar la mitad de
sus bits aproximadamente.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Página 715
Colisiones: resistencia débil y fuerte
5. Colisión simple: será computacionalmente imposible
conocido M, encontrar otro M’ tal que h(M) = h(M’). Esto
se conoce como resistencia débil a las colisiones.
6. Colisión fuerte: será computacionalmente difícil encontrar
un par (M, M’) de forma que h(M) = h(M’). Esto se
conoce como resistencia fuerte a las colisiones.
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
Capítulo 15: Funciones Hash en Criptografía
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 15: Funciones Hash en Criptografía
Página 716
Repaso de la paradoja del cumpleaños
En el capítulo de criptosistemas asimétricos ya se presentaba este
problema matemático, consistente en que exista confianza, es decir una
probabilidad mayor que el 50%, de que en un aula con 365 personas, dos
de ellas al azar cumplan años en la misma fecha.
En realidad no se trata de una paradoja, pero parece serlo dado que ese
número que buscamos es sólo de 23 personas.
Explicación: si éstos entran en el aula de uno en uno y van borrando de
una pizarra su cumpleaños, el primero tendrá una probabilidad de que su
número no esté borrado igual a n/n = 1, el segundo de (n-1)/n, etc. La
probabilidad de no coincidencia es pNC = n!/(n-k)!nk. Si k = 23, se tiene
pNC = 0,493 y la probabilidad de coincidencia es pC = 0,507.
En un hash, esto sería equivalente a sacar dos mensajes de dos conjuntos
disjuntos y comparar sus valores; si los hash son distintos sacamos un nuevo
mensaje y lo comparamos con los anteriores,... hasta que haya una colisión.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Página 717
Algoritmos de resumen en criptografía
• MD5: Ron Rivest 1992. Mejoras al MD4 y MD2 (1990), es más lento
pero con mayor nivel de seguridad. Resumen de 128 bits.
SHA-1: Del NIST, National Institute of Standards and Technology,
1994. Similar a MD5 pero con resumen de 160 bits. Existen otras
propuestas conocidas como SHA-256 y SHA-512, posibles estándares.
•
• RIPEMD: Comunidad Europea, RACE, 1992. Resumen de 160 bits.
• N-Hash: Nippon Telephone and Telegraph, 1990. Resumen: 128 bits.
Snefru: Ralph Merkle, 1990. Resúmenes entre 128 y 256 bits. Ha sido
•
criptoanalizado y es lento.
• Tiger: Ross Anderson, Eli Biham, 1996. Resúmenes de hasta 192 bits.
Optimizado para máquinas de 64 bits (Alpha).
Panama: John Daemen, Craig Clapp, 1998. Resúmenes de 256 bits de
longitud. Trabaja en modo función hash o como cifrador de flujo.
• Haval: Yuliang Zheng, Josef Pieprzyk y Jennifer Seberry, 1992.
•
e
t
n
e
m
l
a
u
t
c
a
s
o
d
a
s
u
s
á
m
s
o
L
Admite 15 configuraciones diferentes. Hasta 256 bits.
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 15: Funciones Hash en Criptografía
Página 718
Función resumen MD5
Esta función ya está obsoleta desde mediados de 2005. No obstante, es
interesante su estudio dada la sencillez del algoritmo y su generalidad.
Algoritmo básico de Message Digest 5
a) Un mensaje M se convierte en un bloque múltiplo de 512 bits,
añadiendo bits si es necesario al final del mismo.
b) Con los 128 bits de cuatro vectores iniciales ABCD de 32 bits cada uno
y el primer bloque del mensaje de 512 bits, se realizan diversas
operaciones lógicas entre ambos bloques.
c) La salida de esta operación (128 bits) se convierte en el nuevo conjunto
de 4 vectores A’B’C’D’ y se realiza la misma función con el segundo
bloque de 512 bits del mensaje, y así hasta el último bloque del
mensaje. Al terminar, el algoritmo entrega un resumen que corresponde
a los últimos 128 bits de estas operaciones.
http://userpages.umbc.edu/~mabzug1/cs/md5/md5.html
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Página 719
Etapas de MD5
Bloques funcionales de MD5
a) Añadir bits para congruencia módulo 512, reservando los
últimos 64 bits para un indicador de longitud.
b) Añadir indicación de la longitud del mensaje en los 64 bits
c)
reservados para ello.
Inicializar el vector ABCD de claves con un valor que no
es secreto.
d) Procesar bloques de 512 bits, entregando una salida de 128
bits que formarán nuevamente el vector ABCD.
e) Obtener el resumen de los últimos 128 bits.
http://www.faqs.org/rfcs/rfc1321.html
© Jorge Ramió Aguirre Madrid (España) 2006
Capítulo 15: Funciones Hash en Criptografía
Libro Electrónico de Seguridad Informática y Criptografía v4.1
Capítulo 15: Funciones Hash en Criptografía
Página 720
Esquema de la función MD5
Mensaje de K bits
Relleno de 1 a 448 bits
K mod 264
(64 bits)
MENSAJE
1000... K
L∗512 bits = N∗ 32 bits
N palabras de 32 bits
512 bits
Y1
Y2
ABCD
HMD5 HMD5
Primer resumen
© Jorge Ramió Aguirre Madrid (España) 2006
Yq
HMD5
A16 = 01234567
B16 = 89ABCDEF
C16 = FEDCBA98
D16 = 76543210
YL-1
HMD5
RESUMEN
de 128 bits
Capítulo 15: Funciones Hash en Criptografía
Página 721
Bloque principal de MD5
Bloque principal
Comentarios de: Capítulo 15 Funciones Hash en Criptografía (0)
No hay comentarios