- OroyFinanzas.com - https://www.oroyfinanzas.com -

Aplicación de funciones de Hash con funciones unidireccionales – Conceptos Bitcoin (V)

(OroyFinanzas.com) – En los anteriores artículos hemos explicado el funcionamiento de la criptográfica simétrica [1] y asimétrica [2] que son funciones unidireccionales. En este artículo explicaremos como se utilizan las funciones hash en combinación con las funciones unidireccionales y los requisitos que deben cumplir. Así habremos cubierto las tres grandes familias de algoritmos criptográficos: simétricos, asimétricos y las funciones hash.

Habitualmente los algoritmos criptográficos se basan en procedimientos que son fáciles de calcular en una dirección pero muy difíciles de invertir si no se conoce una trampa.

En criptografía de clave privada (simétrica) [1] el emisor puede generar un texto cifrado a partir de un texto en claro porque conoce la clave de cifrado, mientras que un atacante no puede invertir el proceso fácilmente y recuperar el texto en claro o la clave partiendo sólo del texto cifrado.

En criptografía de clave pública (asimétrica) [2] se generan un par de claves, pública y privada, pero dada la clave pública resulta computacionalmente muy costoso obtener la clave privada sin más o trampa. Del mismo modo, en la firma digital es muy fácil verificar una firma, pero resulta computacionalmente complejo falsificarla sin conocer la clave privada del firmante.

Este paradigma de “fácil de calcular, difícil de invertir” es tan común en criptografía que las funciones que tienen esta propiedad son denominadas funciones unidireccionales o de una sola dirección. La criptografía simétrica o de clave secreta y la criptografía asimétrica o de clave pública son funciones unidireccionales.

Una función unidireccional es una función matemática en la cual se conoce un procedimiento de cálculo eficiente y rápido para computar esa función, mientras que no se conoce un procedimiento eficiente para realizar ese mismo cálculo pero a la inversa.

Existen muchos ejemplos de funciones unidireccionales. Uno famoso es el problema de la factorización de números enteros: multiplicar dos primos grandes de centenas o miles de bits es viable y fácil para los ordenadores actuales como explicamos en nuestro ejemplo del algoritmo RSA de clave pública [3]; sin embargo, no se conoce un algoritmo eficiente para invertir esta multiplicación, es decir, recuperar los dos primos partiendo exclusivamente de su producto.

El tema de las funciones unidireccionales es una de las preguntas abiertas más importantes en computación teórica y una ciencia muy práctica en el campo de la criptografía. De momento, no se tienen pruebas matemáticas de la existencia de funciones de una dirección, pero los criptógrafos“entienden” que tales funciones existen y usan algunos candidatos razonables en la construcción de algoritmos criptográficos.

Video funciones unidireccionales y funciones hash (Intypedia)

Ejemplos reales donde las funciones unidireccionales tienen utilidad

La protección de claves bancarias

Cuando enviamos una clave a una máquina remota, por ejemplo a nuestro banco, ¿cómo cree que hace el banco para verificar su clave? El banco tiene almacenada una copia de su clave.

Pero el banco no almacena una copia en claro de la clave sino el resultado de aplicar una función unidireccional a la misma, una especie de huella llamada resumen o hash [4]. Más tarde, cuando el usuario envía su clave, el banco aplica esta función a la información recibida y la valida respecto a la almacenada.

Esto es mejor porque si alguien accede a esa base de datos, sólo podrá encontrar ese hash que es difícil de invertir y no tiene utilidad directa.

Envío de documentos

Imagine que un amigo suyo quiere enviarle a través de Internet un fichero enorme, el cual es demasiado grande para adjuntarlo por mail. En su lugar, él lo sube a alguna Web pública. Sin embargo, existe el riesgo que alguien cambie el fichero sin que nos demos cuenta.

Para evitar eso pediríamos a nuestro amigo que lo firmara; si tenemos su clave pública, podemos verificar que es de él.

Pero existen soluciones todavía más sencillas. Por ejemplo, nuestro amigo podría tomar ese fichero grande que quiere enviar y utilizando una función hash, calcular un valor basado en él, por ejemplo de 20 caracteres alfanuméricos, al que nosotros llamaremos resumen del fichero. A continuación nuestro amigo nos enviaría por email o por conversación telefónica este valor. Con esta información, únicamente tendríamos que comprobar que el resumen del fichero descargado coincide con el que nos envió nuestro amigo. De esta forma reducimos el problema de verificar la integridad de millones de bits a la integridad de sólo unos cientos de ellos. De hecho, este método se usa en ocasiones para distribuir claves públicas largas, actualizaciones de software, entre otras.

Así que si alguien quiere reemplazar el fichero de mi amigo por otro diferente y no ser detectado, necesitaría encontrar un fichero cuyo resumen coincida con el del fichero original, pero como la función resumen es de una sola dirección, no podría encontrar ese segundo fichero.

Requisitos de una función Hash

En criptografía a este tipo de funciones que generan resúmenes se les denomina funciones hash. Son funciones que convierten una cantidad de bits de tamaño arbitrario a un conjunto reducido de bits denominado resumen, típicamente 128 ó 160 bits [5].

Resistencia a pre-imagen – Colisiones

Por tanto, como la salida es reducida y la entrada puede ser muy grande, existen muchas entradas diferentes que darán el mismo resumen. En criptografía, a estas entradas que dan el mismo resumen se les denomina pre-imágenes. Una buena función hash debe ser resistente a pre-imagen, es decir, debe ser computacionalmente inviable que un atacante deduzca fácilmente las diferentes entradas que producen una misma salida. Esto también se llama resistente a colisión.

Resistente a segunda pre-imagen – Colisiones

Pero no sólo eso, sino que además deben ser resistentes a ataques de segunda pre-imagen, es decir, debe ser computacionalmente inabordable que, partiendo de un mensaje, sea posible encontrar otro que sea modificación del primero y cuyos resúmenes coincidan.

Por tanto, si una función hash es resistente a una segunda pre-imagen entonces la función unidireccional lo seguirá siendo incluso aunque se conozca la relación de que un mensaje deriva en un resumen concreto. Esto es exactamente la medida de seguridad que se necesita en la aplicación que mencioné anteriormente, en la cual nuestro amigo enviaba un fichero a través de una web pública.

Por ejemplo, la idea de generar resúmenes de ficheros es muy útil criptográficamente para firmar ficheros o mensajes, y por tanto garantizar la autoría de ese contenido. En la práctica, por eficiencia en lugar de aplicar la firma digital al mensaje completo se realiza sólo al resumen generado. Como el atacante no es capaz de encontrar diferentes mensajes que den el mismo resumen, entonces firmar el resumen es tan válido como firmar el documento entero.

La utilidad de que las funciones hash sean resistentes a segunda pre-imagen facilita firmas en documentos de tamaño arbitrario.

Ejemplo de colisión

Supongamos que contratamos a un amigo para hacer un trabajo y firmamos un documento en el que dice que le pagaré 5.000 Euros. Misteriosamente, al mes siguiente, nuestro amigo vuelve con el contrato firmado por nosotros en el que se indica que le pagaremos 50.000 Euros por ese mismo trabajo. Ahora la pregunta: ¿cómo es esto posible?

Sólo sería posible si el contrato original y el modificado tienen el mismo resumen. Pero, ¿no se suponía que un atacante no puede hacer esto si la función hash implementa las medidas oportunas?

Si nuestro amigo ha generado los dos contratos, antes de que los firmáramos, y ambos tienen el mismo resumen se haría posible esta situación. Lo que tenemos que evitar es que sea computacionalmente factible calcular dos mensajes que generen el mismo resumen (es decir, una colisión) para la misma función hash.

Video Funciones criptográficas de Hash (en inglés)

Consideraciones prácticas: Procedimientos, criptoanálisis y consecuencias

En la práctica criptográfica se reutiliza mucho del conocimiento existente en la construcción de algoritmos criptográficos y, en particular, de la construcción de algoritmos de cifrado en bloque. Por ejemplo, aquí también se persiguen que entradas muy parecidas a nivel de bits generen salidas completamente diferentes y no correlacionadas. Por ejemplo, en cifradores de bloque de n vueltas, modificar un solo bit puede hacer que en una pasada del algoritmo cambien el 50% de los bits resultantes.

Sin embargo, hay una gran diferencia entre funciones hash y funciones de cifrado como la secreta o de clave pública. El objetivo de las primeras no es proteger un secreto o la confidencialidad. Además lo habitual es que las funciones hash no necesiten del uso de claves secretas. Esta es una de las características que hacen que su diseño sea más difícil. No obstante, sí comparten la filosofía de que los algoritmos actuales son públicos y por tanto el atacante intentará vencer al algoritmo por este hecho.

De hecho, el diseño de funciones hash se ha ido renovando gracias a las propuestas de ataque de criptoanalistas. Por ejemplo, los algoritmos estándar de funciones hash desarrollados y utilizados desde la década de los 90, como MD5 o SHA-1, hoy en día o están rotos o significativamente amenazados. Bitcoin no se basa en ninguno de ellos porque utiliza SHA-256 [6] como función hash principal y ECDSA [7] junto a RIPEMD-160 [8] en el proceso de creación de direcciones [9].

¿Qué quiere decir que una función hash esté rota?

Pues básicamente que cuando se descubre una pareja de mensajes que generan el mismo resumen, la función hash ya no es resistente a colisiones. Esto le sucedió al algoritmo MD5 en 2004. Incluso esto es peor cuando se demuestran métodos para producir muchas colisiones de este tipo.

Dado que una utilidad importante de las funciones hash está en las firmas digitales, encontrar colisiones puede facilitar falsificar firmas digitales. Es decir, dos mensajes distintos que tengan un mismo resumen, tienen además la misma firma y un atacante puede reemplazar un mensaje por el otro. Un ejemplo de este ataque fue demostrado en 2008 por un grupo de investigadores en Amsterdam los cuales falsificaron un certificado raíz mediante el uso de un ataque de colisión contra el algoritmo MD5.

En nuestro próximo artículo explicaremos el funcionamiento de las curvas elípticas y el algoritmo ECDSA [7] como parte fundamental para la creación de claves privadas y públicas en el protocolo Bitcoin [9].

© OroyFinanzas.