Funciones resumen

Matemáticamente podemos definir las funciones resumen (hash functions) como proyecciones de un conjunto, generalmente con un número elevado de elementos (incluso infinitos), sobre un conjunto de tamaño fijo y mucho más pequeño que el anterior; por ejemplo, podemos definir la siguiente función resumen, que va de un conjunto con un número infinito de elementos a otro con únicamente 10:

, ,

Sin embargo, aunque la anterior sea una función resumen en sentido estricto, no es especialmente interesante en aplicaciones criptográficas; para serlo, habría de cumplir los siguientes requisitos:

• La entrada puede ser de un tamaño indeterminado.
• La salida es de un tamaño fijo, varios órdenes de magnitud más pequeño que el anterior.
• Para un cierto , calcular es computacionalmente barato.
• es de un solo sentido.
• no presenta colisiones.

El que una función hash sea de un solo sentido (lo que se denomina One-Way hash function) no implica más que a partir del valor de no puedo obtener el de : no existe , o su cálculo es computacionalmente difícil. Las colisiones en una función resumen se producen cuando para dos entradas diferentes e , , y se habla de funciones hash débilmente libres de colisiones (weakly collision free) cuando es computacionalmente imposible encontrar dos elementos e tales que cumplan ; si aparte de computacionalmente imposible también lo es matemátimamente, se habla de funciones resumen fuertemente libres de colisiones (strongly collision-free).

Una de las aplicaciones criptográficas más importante de las funciones resumen es sin duda la verificación de integridad de archivos; aunque ya hemos hablado de los verificadores de integridad tipo Tripwire en el capítulo dedicado a los sistemas de detección de intrusos, la idea es sencilla: en un sistema del que tengamos constancia que está `limpio' (esto es, que no ha sido troyanizado o modificado de cualquier forma por un pirata) podemos generar resúmenes de todos los ficheros que consideremos clave para el correcto funcionamiento de la máquina y guardar dichos resúmenes - como ya indica su nombre, mucho más cortos que los archivos originales - en un dispositivo de sólo lectura como un CD-ROM. Periódicamente, o cuando sospechemos que la integridad de nuestro entorno ha sido violada, podemos volver a generar los resúmenes y comparar su resultado con el almacenado previamente: si no coinciden, podemos estar seguros (o casi seguros) de que el fichero ha sido modificado.

Para este tipo de aplicaciones se suele utilizar la función resumen MD5, diseñada por Ronald Rivest y que viene implementada `de serie' en muchos clones de Unix, como Solaris o Linux (órdenes `md5' o `md5sum'):

luisa:~$ echo "Esto es una prueba" >/tmp/salida
sluisa:~$ md5sum /tmp/salida 
3f8a62a7db3b276342d4c65dba2a5adf  /tmp/salida
luisa:~$ echo "Ahora modifico el fichero" >>/tmp/salida
luisa:~$ md5sum /tmp/salida 
1f523e767e470d8f23d4378d74817825  /tmp/salida
luisa:~$

Otra aplicación importante de las funciones resumen es la firma digital de mensajes - documentos - y su timestamping; en el primer caso, como los algoritmos de firma digital suelen ser lentos, o al menos más lentos que las funciones hash, es habitual calcular la firma digital de un resumen del fichero original, en lugar de hacer el cálculo sobre el propio fichero (evidentemente, de tamaño mayor que su resumen). Con respecto al timestamping, las funciones hash son útiles porque permiten publicar un resumen de un documento sin publicar su contenido, lo cual permite a una parte obtener un timestamp de un documento sin que la autoridad de timestamp conozca el contenido del mismo, pero asegurándose la validez del procedimiento en caso de repudio; en ambos casos, tanto en la firma digital como en el timestamping, trabajar con el resumen es completamente equivalente a trabajar con el archivo original.