Funciones hash criptográficas (Parte 1)
Una función hash es una función de programación que se utiliza para asignar datos de tamaño aleatorio a datos de una longitud fija. Un ejemplo de esta función se ve así:
68bef6f86606449ebbd07fa7deb02845a1ba84a3d49b06f6d2d8d287aae13bf9Las funciones hash se originaron de la necesidad de comprimir información y así reducir la cantidad de memoria requerida para almacenar archivos grandes. También ayudan a minimizar las etiquetas de archivos como textos, mp3, PDF o imágenes para que la manipulación de estos archivos de gran tamaño sean manejables. Un requisito clave de las funciones hash es que generan una serie de caracteres alfanuméricos de longitud fija y eso hace que se pueden utilizar como "huella digital" de archivos (en inglés se utiliza la palabra ‘digest’).
Un uso y beneficio secundario que apareció es el uso de los "hashes" como identificadores únicos y singulares. Cuando se “hashean” diferentes archivos, hay una poca probabilidad que dos terminen resultando en un hash idéntico, entonces decimos que hubo una colisión. Si una función hash es elegida con ciertas propiedades entonces, los mensajes diferentes dan como resultado hashes de salida diferente. Desde la perspectiva de una base de datos, una colisión significa que dos objetos diferentes terminan siendo almacenados en la misma celda, lo que no es bueno si uno busca crear identificadores singulares.
Para que una función hash sea útil necesitamos que posea tres propiedades:
- Que su entrada puede ser cualquier cadena de cualquier tamaño.
- Que produzca salidas de tamaño fijo.
- Que sea eficientemente computable.
Esas propiedades son las que definen a las funciones hash en general, y gracias a estas las funciones se pueden usar para construir estructuras de datos como tablas hash, árboles de Merkle o blockchains (cadenas de bloques), que analizaremos en siguientes artículos.
También requerimos que las funciones hash sean criptográficamente seguras, eso significa que requerimos propiedades adicionales como:
- Resiste a colisiones
- Ocultar la informacion original
- Amigables para construir rompecabezas criptográficos
Haremos foco en estas últimas tres propiedades ya que son parte parte de las tecnologías que se usan en la criptografía que usamos en Signatura, en Bitcoin y en la mayoría las criptomonedas.
Propiedad 1: Resistente a colisiones
Nota: Una cadena (string) de información genérica se expresa como “x” y la función hash asociada a esa cadena como H(x).
Una colisión se produce cuando dos entradas distintas nos dan como resultado la misma salida. Una función hash H(x) es resistente a colisiones si nadie puede encontrar una colisión.
Para todos los “x” e “y” que sean distintos es imposible encontrar un par de “x” e “y” que al aplicarles la función hash se obtengan los mismos valores de salida.
Resistente a colisiones no significa que las colisiones no existan, significa que las colisiones existen pero que es extremadamente difícil encontrarlas. Vamos a demostrarlo con un ejemplo muy muy muy sencillo.
Vamos a crear la función hash más sencilla que puede existir, la función SHA 1bit (las siglas SHA viene del acrónimo en inglés “Secure Hash Algoritm”, en español Algoritmo Hash Seguro). Nuestra función va tener como parámetro de entrada data y va a tener como salida 1 bit (recordemos que un bit es la menor unidad de información en una computadora y posee un valor binario: 0 ó 1)
Si de todas las posibles entradas elijo el abecedario {a,b,c,d,……}, cuando ingrese la letra {a} a la función hash voy a obtener el 0 de mi único bit y cuando ingrese la letra {b} obtendré el valor 1 de mi bit. Ahora, ¿que es lo que va a suceder cuando quiera ingresar la letra {c}?. La función hash me va a devolver ó un 0 ó un 1, efectuando así la primera colisión, y como existe una colisión existen infinitas colisiones. Como conclusión sacamos que la función de 1 sólo bit es insegura por la alta incidencia de las colisiones.
Nosotros utilizamos el estándar criptográfico SHA256 cuya salida tiene 256 bits, si tenemos en cuenta que cada bit tiene dos posibilidades hace que la salida de esta función sean 2^256 posibilidades distintas. Si traducimos ese número a notación decimal lo que obtenemos es astronómico:
Es prácticamente imposible encontrar una colisión en este espacio, pero las colisiones existen simplemente por el hecho de que el espacio de entrada es infinito y el espacio de salida es finito.
Si una computadora calcula 10.000 hashes por segundo, se necesitarán más de un octillón (10^27) años para calcular la mitad de las posibilidades.
Aplicación: Digestor de mensajes
La pregunta que emerge de todo lo que hablamos es, ¿para qué sirve esto?
Si sabemos que una función hash H(x) es resistente a colisiones, entonces es aceptable asumir que “x” e “y” son diferentes.
Este argumento nos permite usar salidas hash como un resumen del mensaje. Imaginemos un sistema de almacenamiento de archivos online que permite a los usuarios subir archivos y garantizar su integridad cuando los descarguen. Las funciones hash libres de colisiones nos permiten una solución eficiente a este problema. Sólo se necesita recordar el hash del archivo original. Cuando se descarga nuevamente el archivo se calcula su hash y lo comparamos con el hash almacenado. Si los valores hash son iguales, se puede asumir que el archivo es exactamente el mismo, pero si son diferentes, entonces se asume que el archivo sufrió una modificación.
En Signatura utilizamos la función SHA256 de dos formas. La primera como resumen de mensaje para garantizar su inmutabilidad y la segunda como parte del protocolo de firmas digitales ECDSA.
Dentro del recibo de Signatura que explicamos en el artículo anterior, encontramos el Digest (SHA256) entre la información sobre el documento. De esa forma podremos saber si estamos mirando el archivo original o un archivo alterado.
El algoritmo de firma digital ECDSA no se realiza sobre el archivo sino sobre el hash del archivo. La elección de la función hash depende del usuario. También la red de Bitcoin utiliza esta función como parte de su mecanismo de seguridad.
Continuación
En la parte dos de este articulo vamos a explorar las dos propiedades que nos faltan de las funciones hash: la de ocultar y la de construir rompecabezas criptográficos. También veremos como también un pequeño script de python para crear hashes.
Signatura ofrece una plataforma para firma y certificación blockchain de documentos.
