Definición
Criptográficamente, entendemos por funcion hash
una aplicación de cifrado en la que el mensaje no se puede recuperar. Más ampliamente, las funciones hash son funciones
de resumen de contenido y reciben, en criptografía, también el
nombre de digest.
Una función hash perfecta es aquella que mapea diferentes
valores de origen en diferentes valores destino. Claro está que
no puede ser perfecta una función cuyo espacio de imágenes
sea más pequeño que el de actuación.
Las funciones hash utilizan habitualmente una serie de operaciones
combinadas y aplicadas reiteradamente sobre el valor de entrada:
- truncamiento o extracción: elimnando una serie de bits
del principio o el final del mensaje
- modúlo: actuación en un grupo finito de las operaciones
para conseguir el hash
- selección: tomcar una serie de posiciones fijas del
mensaje, despreciando el resto
- cambio de base: representación del mensaje en una
base diferente a la original.
- doblamiento: división del mensaje en varias partes de igual
tamaño y aplicación de determinada operación entre las partes
para obtener como resultado algo de igual tamaño que los
fragmentos tomados.
- multiplicación: multiplicar el valor del mensaje truncándolo
o reduciéndolo módulo una constante.
Esta lista está más bien obtenida a partir de los más representativos
mecanismos de cálculo de hashes; es decir, no excluyen que haya
algoritmos de hashing que no utilicen estos elementos.
Utilizaciones
El más elemental de los usos es para el almacenamiento y
localización de objetos:
- arrays asociativos
- buscadores en redes P2P: DHT
Para estas aplicaciones cuestiones tales como el número de
colisiones o el conocimiento o no de la inversa de la función hash
no son tan relevantes en tanto en cuanto no es la seguridad
el objetivo buscado.
En criptografía, hay ocasiones en las que cifrar el mensaje
entero es sumamente pesado y realmente innecesario. En estos
casos se utilizan funciones hash que convierten un mensaje de
tamaño ilimitado a priori en un valor acotado. Es importante
en este caso que no sea factible encontrar una inversa para la
función hash y que la probabilidad de colisiones se lo más baja
posible. También, para evitar reconstruir la inversa de la
función por fuerza bruta, las funciones hash utilizadas con esta
finalidad han de ser pesadas, es decir, que el tiempo empleado
en calcular no sea muy poco y no pueda ser reducido.
Para almacenar claves, en conformidad con los preceptos
expresados en la LOPD (artículo 93.3, BOE núm 17 de
19 de enero de 2008), por ejemplo, se requiere que no
puedan ser descubiertas aunque se acceda a lugar donde se guardan éstas. Aunque existen varias maneras, la forma más simplificada consiste en recordar el hash de la clave del
usuario. En este caso buscamos la minimización de colisiones
y una gran dispersión de valores próximos, frente a otras
caracterísitcas como reducción del espacio ocupado por
el valor hash frente al valor original o la velocidad
de cómputo.
La aplciación a criptografía para verificar la autenticida
d de un
mensaje se conoce con el nombre de HMAC (del inglés
keyed-Hash Message Authentication Code). Una HMAC utiliza una
clave privada y una función hash para demostrar que el mensaje
no ha sido alterado desde que lo generara el propietario de la clave privada.
Matemáticamente, un HMAC es
HMACk(msg) = h((K ^ opad) | (K ^ ipad) | msg)
siendo
ipad=0x36363636...36 y
opad=0x5c5c5c...5c (secuencia de bits impares y pares),
h una función hash criptográfica y
K la clave privada.
Características deseables
Ante todo, la función hash de estar bien definida, es decir
el valor del hash ha de estar completamente determinado a partir de
los datos a resumir. Es la única manera de que la función hash
pueda ser utilizada para comprobar la integridad de los datos
resumidos.
La función hash ha de utilizar completamente todos los
datos de entrada. La pretensión es que no haya colisiones a
priori definidas por la propia función hash.
La distribución de valores sobre el espacio de imagen ha de ser
uniforme. Si siguiera alguna distribución no uniforme,
habría una mayor probabilidad de colisionar para determinados
valores de entrada.
Ha de generar valores suficientemente diferentes para
valores de entrada muy similares. Lo que sería característico
de un problema mal puesto en mecánica es algo deseable
por tanto en cuanto desviamos las probabilidades de encontrar
colisiones.
En general, cualquier función que cumpla estas caracterísitcas
podemos encuadrarlas en el conjunto de funciones hash. Por las
particulares características pedidas a las funciones hash y
dada la dificultad de demostrar que se cumplen es habitual
utilizar algoritmos ya implementados y probados.
Por ejemplo, a modo de muestra de la infinidad de lista de funciones
hash tenemos:
- Unix ELF hash:
unsigned long hash(char *text) {
unsigned long h = 0, g;
while(*name) {
h = (h<<4) + *name;
*name++;
g = h & 0xF0000000;
if(g!=0) h^=g > 24;
h &= ~g;
}
return h;
}
- Hash XOR:
char XORhash(char *text, int len) {
char hash;
int i;
for(hash=0, i=0; i<len; i++) hash=hash^key[i];
return hash % 101;
}
El espacio destino de estas funciones es muy reducido (8 bits en un
caso y 32 en el otro), lo que hace que para firmado sea poco
útiles. Sin embargo, para comprobar la integridad de contenidos
pequeños, o para su utilización en tablas hash y cuando hay
restricciones de cómputo son perfectamente
utilizables, cumpliendo las caracterísitcas pedidas (es un
interesante ejercicio demostrarlo).
Colisión
Se llama así, para una función hash dada, a la situación en la
que dos valores diferentes tienen el mismo valor hash.
Evidentemente, como el objetivo de las funciones hash es el
resumen de contenidos, el espacio imagen es menor que el espacio
de origen de la función. Incluso, en el caso más general,
el espacio inicial es ilimitadamente grande (por ejemplo, todas
los posibles secuencias de caracteres) mientras que el
destino está acotado (por ejemplo, el espacio de valores de
160 bits). Así que es trivial que habrá colisiones
inevitablemente. La cuestión es si las colisiones son predecibles
y hasta que punto. Cuando, dada una función hash, se
descubre un mecanismo para provocar las colisiones, se
dice que el sistema hash ha sido vulnerado.
Aleatoriedad
Los algoritmos de hash son, por definición predecibles. Es decir,
para la misma entrada, producen la misma salida.
Sin embargo, a la hora de utilizarlos para el firmado de documentos
o para almacenamiento seguro de contraseñas, conviene provocar la
dispersión aleatoria del hash generado, añadiendo al contenido
original un valor o valores aleatorios.
Si el generador de números aleatorios es predecible en algún sentido,
como ha ocurrido con el generador de OpenSSL de Debian
en mayo de 2008, el almacenamiento de claves y generación de
valores para identificadores de sesión con los que cifrar
queda seriamente comprometido.
