Funciones HASH.
Pgina 1
TEMA
Funciones HASH.
Las funciones criptogrficas hash juegan un papel fundamental en la criptografa
moderna. Hay muchas funciones hash, comnmente usadas en aplicaciones no
criptogrficas. Nosotros nos referiremos siempre a las que admiten el adjetivo de
criptogrficas, y las llamaremos habitualmente simplemente funciones hash.
Una funcin hash, o funcin resumen, toma un mensaje como entrada y produce
una salida que llamamos cdigo hash, o resultado hash, o valor hash, o
simplemente hash. La idea bsica de las funciones criptogrficas hash es que los
valores hash obtenidos con ellas sirven como una imagen representativa y
compactada de una cadena de entrada, y pueden usarse como un posible
identificador nico de esa cadena de entrada: ese valor hash obtenido del
mensaje de entrada suele llamarse resumen del mensaje o huella digital del
mensaje.
Las funciones hash se emplean en criptografa junto con los criptosistemas de
firma digital para otorgar integridad a los datos. A la hora de firmar digitalmente
un documento o mensaje, es prctica habitual hacer la firma sobre la huella
digital del mensaje y no sobre la totalidad del mensaje a firmar.
1. FUNCIONES HASH DE USO CRIPTOGRFICO.
Entendemos por una FUNCIN HASH una aplicacin b:
-
-
n
, con n e H. Son
funciones que transforman una cadena de longitud arbitraria en una cadena de
longitud fija. Tambin se les llama en castellano funcin RESUMEN.
Un ejemplo muy sencillo de estas funciones podra ser aquella que transforma
una cadena de bits b
1
b
2
b
k
e {u,1]
-
en un nico dgito binario b
1
b
2
b
k
: es
la funcin de paridad.
Funciones HASH. Pgina 2
Las funciones Hash pueden generarse mediante funciones de compresin. Una
FUNCIN DE COMPRESIN es una transformacin b:
m
-
n
, n, m e H, m > n. Es
decir, es una aplicacin que transforma cadenas de longitud fija en cadenas de
longitud fija menor.
Sea la funcin hash b:
-
-
n
, o la funcin de compresin b:
m
-
n
. En adelante
llamaremos al conjunto de argumentos de b con el nombre de . Si b es una
funcin de hash entonces =
-
; si b es una funcin de compresin, entonces
=
m
.
Aquellas funciones b que verifiquen que el clculo de su inversa es
computacionalmente muy complicado, las llamamos FUNCIONES DE UNA VA.
Es decir, dado s e
n
es computacionalmente inasequible hallar x e tal que
b(x) = s. Realmente no queda perfilado o cuantificado el concepto inasequible;
entendemos, de forma intuitiva, que sern funciones donde el tiempo necesario
para encontrar el inverso es tal que no lo hace viable. No se sabe a ciencia cierta
si existen realmente funciones b que no sean invertibles. Se considera que una
funcin b es de una sola va cuando la dificultad computacional de su inversa sea
alta.
Toda funcin de compresin o hash tendr colisiones, porque son funciones no
inyectivas. Entendemos por COLISIN la existencia de pares (x, y) e
2
, tales que
x = y y b(x) = b(y). Una funcin b diremos que es RESISTENTE A COLISIONES si
conocido b(x) para un x e , es computacionalmente inviable hallar x' e con
b(x
i
) = b(x).
Una funcin hash diremos que es FUERTEMENTE RESISTENTE A COLISIONES si
resulta computacionalmente inviable encontrar cualquier par (x, y) e
2
, x = y
tales que b(x) = b(y).
Una vez presentamos estos conceptos previos, podemos determinar ahora
cuando una funcin hash b(x) o una funcin de compresin sern vlidas para
usos criptogrficos. Eso ocurrir si la funcin verifica las siguientes propiedades:
1. Fcil de computar para todo x e .
2. De una sola va.
3. Resistente a colisiones.
4. Fuertemente resistente a colisiones.
En el siguiente epgrafe presentamos un ataque clsico contra las funciones
hash, eficaz si sta no es fuertemente resistente a colisiones. La posibilidad de
Funciones HASH. Pgina 3
este ataque nos permitir determinar una caracterstica elemental que deben
verificar las funciones criptogrficas hash: b: -
n
no ser fuertemente
resistente a colisiones si n no es suficientemente grande. A lo largo de siguiente
epgrafe se ver qu significa aqu el adjetivo suficientemente.
2. ATAQUE DEL CUMPLEAOS.
Presentamos un ataque bastante simple contra las funciones hash, llamado
ATAQUE DEL CUMPLEAOS. Este ataque surte efecto si la funcin hash no es
fuertemente resistente a las colisiones.
El ataque del cumpleaos se basa en la PARADOJA DEL CUMPLEAOS, que queda
presentada como apndice a este tema.
Conocida ya la paradoja, veamos ahora en qu consiste la estrategia de ataque a
una funcin hash mediante la tcnica del ataque del cumpleaos. Esta estrategia
es eficaz cuando la longitud del valor hash no es suficientemente grande.
Suponemos que esa longitud es n.
Las circunstancias que concurren en este ataque son las siguientes: Alguien (A)
desea obtener una huella digital (b
m
) de un determinado mensaje suyo (m). Si la
funcin hash que emplea A no es fuertemente resistente a colisiones, entonces
un atacante (B) puede aprovechar la ocasin y sustituir el mensaje de A por otro
de igual significado (m') y de aspecto similar, con una huella (b
mi
) igual a otro
mensaje () fraudulento escrito por B, con un contenido diferente al mensaje
inicial al mensaje de A (es decir, b
mi
= b
]
). Slo queda entonces a B sustituir el
mensaje m que A deseaba enviar por el mensaje sustitutivo m': A firmar su
mensaje y guardar a buen recaudo su garanta de integridad (la huella digital) o
lo enviar con la huella a un receptor. B puede ahora sustituir el mensaje m' por
el suto fraudulento : al tener ambos la misma huella, B habr logrado burlar la
garanta de integridad de datos que en principio ofrece la huella hash: ni A, ni un
posible receptor, podrn verificar que el mensaje inicial ha sido modificado.
Veamos el procedimiento que sigue B para lograr sus fines:
1. A posee su mensaje m, del que desea calcular la huella digital o resumen.
2. El atacante B, que dispone de ese mensaje, genera 2
n 2
variaciones de l,
todos ellos sustancialmente con el mismo significado. (n es la longitud del
Funciones HASH. Pgina 4
valor hash.) entre estos mensajes est el candidato a ser el mensaje
sustituto, m
i
.
3. El atacante toma el mensaje fraudulento y prepara tambin 2
n 2
mensajes
parecidos, de similar significado al mensaje fraudulento inicial. Entre estos
mensajes est el candidato a ser el mensaje fraudulento .
4. El atacante compara los dos conjuntos de mensajes y busca un par (uno entre
las copias del mensaje de A, y otro entre los mensajes fraudulentos) que
produzcan la misma salida hash. La probabilidad de que esto ocurra, con 2
n 2
mensajes generados es, por la paradoja del cumpleaos, mayor de 0.5. Si no
consigue encontrar dos hash iguales, el atacante puede generar unos
mensajes ms en cada conjunto hasta lograrlo.
5. Slo le resta al atacante sustituir el mensaje inicial m por su versin de igual
significado m'.
Para una funcin hash que llegue a resmenes o valores hash de 64 bits, el
atacante puede sustituir un documento por otro con tan solo 2
32
pruebas. Y la
generacin de un nmero grande de versiones similares del mismo texto no es
tarea en absoluto difcil. Se requiere un software sencillo que lo realiza y cierta
capacidad de memoria.
Para prever y prevenir un ataque de este estilo ser necesario utilizar funciones
hash que realicen un resumen de cierta longitud. Normalmente n 128 es
suficiente. Habitualmente sin embargo se emplean tamaos n 16u. Es el modo
habitual de lograr funciones hash fuertemente resistentes a colisiones.
3. FUNCIONES DE COMPRESIN DESDE FUNCIONES DE CIFRADO.
No podemos afirmar con rotundidad que existan funciones hash resistentes a
colisiones. Tampoco podemos asegurar que un determinado criptosistema es
seguro y eficiente: siempre puede haber un modo de ataque desconocido.
Podemos suponer que si definimos una funcin hash como resultado de aplicar
una funcin criptogrfica, el resultado ser resistente a colisiones. Tan resistente
a colisiones como segura sea la funcin de cifrado del criptosistema. Digo que
podemos suponer esta afirmacin, pero de hecho hoy por hoy no la podemos
demostrar. Sin embargo se utilizan a veces funciones criptogrficas para hacer
hash.
Funciones HASH. Pgina 5
Supongamos que tanto el espacio de claves, como el espacio de texto plano
como el de texto cifrado es {u,1]
n
. Las funciones de cifrado son c
k
: {u,1]
n
-{u,1]
n
,
con k e {u,1]
n
. Nuestro valor hash tendr longitud n. Para protegerse del ataque
del cumpleaos, tomamos criptosistemas de cifrado con n 128: DES queda
descartado.
La funcin hash b: {u,1]
n
{u,1]
n
-{u,1]
n
puede definirse de las siguientes formas:
b(k, x) = c
k
(x) x.
b(k, x) = c
k
(x) x k.
b(k, x) = c
k
(x k) x.
b(k, x) = c
k
(x k) x k.
4. FUNCIONES HASH DESDE FUNCIONES DE COMPRESIN.
La resistencia a colisin de las funciones de compresin pueden usarse para la
construccin de funciones hash, resistentes tambin a colisiones. Se puede
demostrar que si la funcin hash resultante no es resistente a colisiones,
entonces tampoco es resistente a colisiones la funcin de compresin original.
Lamentablemente, no sabemos demostrar la afirmacin inversa.
Veamos un modo de lograr una funcin hash a partir de una funcin de
comprensin.
Sea g: {u,1]
m
-{u,1]
n
, una funcin de compresin. Y sea r = m- n.
Como g es una funcin de compresin, tendremos que r > u. Una eleccin
habitual es n = 128 y r = S12.
A partir de g queremos construir una funcin hash b: {u,1]
-
-{u,1]
n
. Sea x e
{u,1]
-
. Consideramos el caso r > 1. Realizamos los siguientes pasos:
1. Aadimos a x el nmero de ceros a la izquierda necesarios para que su
longitud sea un entero divisible por r.
2. A esa cadena le aadimos r ceros por la derecha.
3. Volvemos a tomar la cadena original x. Expresamos su longitud inicial en
cdigo binario. Aadimos a esa expresin tantos ceros como sea necesario
para que su longitud sea divisible por r - 1. Delante de esa nueva cadena
Funciones HASH. Pgina 6
aadimos un 1, y lo mismo hacemos delante de cada porcin de r - 1
caracteres.
4. Aadimos esta segunda cadena resultante a la anterior creada. Tendremos la
secuencia de palabras de longitud r: x = x
1
x
2
x
t
, donde x
e {u,1]
, 1 i t
Por ejemplo, si tenemos r = 4 y x = 111u11, los pasos indicados son:
1. x' -uu11 1u11
2. x' -uu11 1u11 uuuu
3. La longitud inicial de x es l(x) = 6, que expresada en binario es l(x) = 11u, que
ya tiene un nmero de dgitos mltiplo de r - 1, es decir, de 3. Aadimos a
esta cadena un 1 delante y llegamos as a la cadena 111u.
4. Concatenamos: x
i
-uu11 1u11 uuuu 111u.
El valor hash b(x) se calcula de forma iterativa. Inicialmente E
0
= u
n
: una cadena
de n ceros. Las siguientes iteraciones son: E
= g(E
-1
x
), para 1 i t. La
ltima iteracin la tomamos como resultado final: b(x) = E
t
. La operacin
composicin aqu indicada () es la concatenacin de cadenas: Cada E
es, por
ser imagen de g, una cadena binaria de longitud n. E
0
tambin es, por definicin
una cadena binaria de esa longitud. Cada x
es, por la propia construccin que
hemos tomado, de longitud r. Cada concatenacin E
-1
x
es, por tanto, de
longitud n + r = m, que es la longitud del conjunto inicial de la funcin g.
De todo lo dicho en los dos epgrafes anteriores, se comprende que, a partir de
cualquier criptosistema de cifrado por bloques se puede definir una funcin de
compresin, a partir de la cual a su vez se puede definir una funcin hash.
5. SHA 1.
La familia SHA (Secure Hash Algorithm) es un sistema de funciones hash
criptogrficas relacionadas de la Agencia de Seguridad Nacional de los Estados
Unidos y publicadas por el National Institute of Standards and Technology
(NIST). El primer miembro de la familia fue publicado en 1993 es oficialmente
llamado SHA. Sin embargo, hoy da, no oficialmente se le llama SHA-0 para
evitar confusiones con sus sucesores. Dos aos ms tarde el primer sucesor de
SHA fue publicado con el nombre de SHA-1. Existen cuatro variantes ms que se
han publicado desde entonces cuyas diferencias se basan en un diseo algo
Funciones HASH. Pgina 7
modificado y rangos de salida incrementados: SHA-224, SHA-256, SHA-384, y
SHA-512 (llamndose SHA-2 a todos ellos).
SHA-1 ha sido examinado muy de cerca por la comunidad criptogrfica pblica,
y no se ha encontrado ningn ataque efectivo. No obstante, en el ao 2004, un
nmero de ataques significativos fueron divulgados sobre funciones
criptogrficas de hash con una estructura similar a SHA-1; lo que ha planteado
dudas sobre la seguridad a largo plazo de SHA-1.
SHA-0 y SHA-1 producen una salida resumen de 160 bits de un mensaje que
puede tener un tamao mximo de 2
64
bits, y se basa en principios similares a
los usados por el profesor Ronald L. Rivest del MIT en el diseo de los algoritmos
de resumen de mensaje MD4 y MD5.
DESCRIPCIN DEL ALGORITMO. PREPARACIN DE LA CADENA DE ENTRADA.
Tomamos x e {u,1]
-
. Como ya ha quedado dicho, |x| < 2
64
. El valor hash se
compone mediante los siguientes pasos:
1. Aadimos un dgito 1 al final de la cadena de bits de x: x -x 1.
2. Aadimos la mnima cantidad de ceros a la derecha necesarios para que
|x| = k S12 - 64.
3. Escribimos la longitud de x como un nmero de 64 bits.
Veamos un ejemplo:
0. x <- - 0110 0001 0110 0010 0110 0011 0110 0100 0100 0101.
1. x <- - 0110 0001 0110 0010 0110 0011 0110 0100 0100 0101 1.
2. Longitud(x) = 41: hay que aadir 407 ceros a la derecha: 512 64 = 448;
tenemos ya 41, faltan 407.
En hexadecimal, tenemos:
x <- - 61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000
3. Longitud de x: 40; en hexadecimal, con 64 bits: 00000000 00000028.
4. Valor final de x:
x <- - 61626364 65800000 00000000 00000000
00000000 00000000 00000000 00000000
00000000 00000000 00000000 00000000
Funciones HASH. Pgina 8
00000000 00000000 00000000 00000028.
DESCRIPCIN DEL ALGORITMO. PROCESAMIENTO DE LA CADENA PREPARADA.
Para la computacin del valor hash empleamos las funciones:
t
: {u,1]
32
{u,1]
32
{u,1]
32
-{u,1]
32
.
Se define como sigue:
t
(B, C, ) = _
(B/C)V(-B/) poro u t 19
B C@ poro 2u t S9
(B/C)V(B/)V(C/) poro 4u t S9
B C@ poro 6u t 79
Donde A es la operacin lgica a nivel de bit AND; v es la operacin a nivel de bit
OR; es la operacin lgica a nivel de bit XOR.
Por otro lado, se emplean las siguientes constantes:
K
t
= _
SA827999 poro u t 19
6E9EBA1 poro 2u t S9
8F1BBCC poro 4u t S9
CA62C16 poro 6u t 79
Queda ver ahora cmo se calcula el Hash. Tenemos el valor de x ya
transformado segn las reglas antes indicadas. Su longitud es divisible por 512.
Tomamos x = M
1
M
2
M
3
M
n
, secuencias de palabras de 512 bits.
Comenzamos inicializando valores:
E
0
= 674S2Su1, E
1
= EFCAB89, E
2
= 98BACFE, E
3
= 1uS2S476, E
4
= CS2E1Fu.
El siguiente procedimiento se repite para i = 1, 2, , n (es decir, para cada bloque
H
de 512 bits). Definimos la operacin S
k
(w) como el desplazamiento circular a
izquierda de k bits, sobre palabras de 32 bits. Definimos tambin la suma (+)
para enteros que trabajan sobre 32 bits, es decir, suma mod 2
32
.
Los pasos que se realizan para cada H
son:
1. Escribir H
como una secuencia M
|
= W
W
1
W
15
, cada uno de 32 bits.
2. Para t = 16, 17, , 79, calcular W
t
= S
1
(W
t-3
W
t-8
W
t-14
W
t-1
).
3. Tomar A = E
0
, B = E
1
, C = E
2
, = E
3
, E = E
4
.
4. Para t = u, 1, , 79, calcular I = S
5
(A) +
t
(B, C, ) +E +w
t
+ K
t
, E = , = C,
C = S
30
(B), B = A, A = I. (I es una variable auxiliar.)
5. Calcular E
0
= E
0
+A, E
1
= E
1
+ B, E
2
= E
2
+ C, E
3
= E
3
+ , E
4
= E
4
+E.
Funciones HASH. Pgina 9
Al final de procesar todos los bloques H
de 512 bits, tendremos que el valor
hash est formado por la cadena SHA-1(x)= E
0
E
1
E
2
E
3
E
4
. (160 bits)
La codificacin hash vaca para SHA-1 corresponde a:
SHA1("") = DA39 A3EE 5E6B 4B0D 3255 BFEF 9560 1890 AFD8 0709
6. APNDICE AL TEMA. PARADOJA DEL CUMPLEAOS.
Supongamos un grupo de personas en una habitacin. Cul es la probabilidad
de que dos de ellos celebren el cumpleaos el mismo da? Otra forma de
presentar esta paradoja es: Cul es el nmero mnimo de personas k que debe
haber en la habitacin para que la probabilidad de que en el grupo al menos dos
celebren el mismo da sea mayor que 0.5? Para buscar la respuesta, ignoramos
la fecha 29 de febrero de los aos bisiestos: tomamos, pues, n = S6S. La
pregunta es, cul es el mnimo valor de k para el cual se verifica queP(S6S, k)
u.S.
De entrada es evidente que k S6S. Superado ese valor lmite la probabilidad de
hallar dos fechas duplicadas es uno, porque hay ms personas que fechas
posibles.
Para lograr tener personas todas ellas con fechas de cumpleaos diferentes,
primero dejamos entrar a una en la habitacin, sea cual sea su fecha de
cumpleaos; luego dejamos entrar a una segunda, limitando sus fechas de
cumpleaos a 364; a la siguiente le limitamos su cumpleaos a 363 das: si
alguna de las sucesivas personas que quieren entrar en la habitacin no verifica
esa exigencia, sencillamente no la dejamos entrar, y pasamos a la siguiente. As
hasta llegar a tener dentro de la habitacin a las k personas.
Nos preguntamos cuntas combinaciones de fechas de cumpleaos posibles
tendremos en nuestra habitacin. El primer hombre tendr una cualquiera de las
365, el segundo una cualquiera de las 364 restantes, el tercero una cualquiera
de las 363 restantes, y as hasta el hombre k -simo que podr tener cualquiera
de las (S6S -k +1) fechas restantes. Es decir, las diferentes combinaciones
posibles son N = S6S SS4 (SSS - k + 1) = S6S! (S6S - k)!
Si eliminramos la restriccin de que no haya fechas de cumpleaos duplicadas,
entonces cada individuo podra tener su fecha de nacimiento entre cualquiera de
Funciones HASH. Pgina 10
los 365 das del ao, y entonces el nmero de posibilidades en las fechas de los
personales de la habitacin sera una cualquiera de las combinaciones de 365
elementos tomados en grupos de k, es decir, S6S
k
combinaciones diferentes.
As las cosas, la probabilidad de que no hay duplicado alguno ((S6S, k)) es:
(S6S, k) =
S6S! (S6S - k)!
S6S
k
Y por tanto
P(S6S, k) = 1 - (S6S, k) = 1 -
S6S!
(S6S -k)! S6S
k
Esta expresin da como resultado que para k = 2S entonces P(S6S, 2S) = u.Su7.
Para k = 1uu la probabilidad de que haya dos personas con la misma fecha de
cumpleaos es de P(S6S, 1uu) = u.9999997.
La paradoja reside en que no es lo mismo preguntar por la probabilidad de que
alguien celebre el mismo da que yo, que preguntar la probabilidad de que dos
cualesquiera de los habitantes de la habitacin celebren en el mismo da.
