La criptografía basada en hash es el término genérico para las construcciones de primitivas criptográficas basadas en la seguridad de las funciones hash . Es interesante como un tipo de criptografía poscuántica .
Hasta ahora, la criptografía basada en hash se utiliza para construir esquemas de firmas digitales como el esquema de firma Merkle , pruebas de conocimiento cero y de integridad computacional, como el sistema de prueba zk-STARK [1] y pruebas de rango sobre credenciales emitidas a través del protocolo HashWires [2] . Los esquemas de firma basados en hash combinan un esquema de firma de un solo uso, como una firma Lamport , con una estructura de árbol Merkle . Dado que una clave de esquema de firma de un solo uso solo puede firmar un solo mensaje de forma segura, es práctico combinar muchas de estas claves dentro de una única estructura más grande. Una estructura de árbol Merkle se utiliza para este fin. En esta estructura de datos jerárquica, una función hash y la concatenación se utilizan repetidamente para calcular los nodos del árbol.
Una consideración que se debe tener en cuenta con los esquemas de firma basados en hash es que solo pueden firmar de forma segura una cantidad limitada de mensajes, debido a que utilizan esquemas de firma de un solo uso. El Instituto Nacional de Estándares y Tecnología (NIST) de Estados Unidos especificó que los algoritmos de su concurso de criptografía postcuántica admiten un mínimo de 2 64 firmas de forma segura. [3]
En 2022, el NIST anunció que SPHINCS+ sería uno de los tres algoritmos que se estandarizarían para las firmas digitales. [4] El NIST estandarizó la criptografía basada en hash con estado basada en el esquema de firma de Merkle ampliado (XMSS) y las firmas Leighton-Micali (LMS), [5] que son aplicables en diferentes circunstancias, en 2020, pero señaló que el requisito de mantener el estado al usarlos hace que sea más difícil implementarlos de una manera que evite el mal uso. [6] [7] [8]
En 2024, el NIST anunció el estándar de firma digital basada en hash sin estado. [9]
Leslie Lamport inventó las firmas basadas en hash en 1979. Los esquemas de firma basados en hash XMSS (eXtended Merkle Signature Scheme) [10] y SPHINCS [11] [12] se introdujeron en 2011 y 2015, respectivamente. XMSS fue desarrollado por un equipo de investigadores bajo la dirección de Johannes Buchmann y se basa tanto en el esquema seminal de Merkle como en el Generalized Merkle Signature Scheme (GMSS) de 2007. [13] Una variante de múltiples árboles de XMSS, XMSS MT , se describió en 2013. [14]
Los esquemas de firma basados en hash utilizan esquemas de firma de un solo uso como su bloque de construcción. Una clave de firma de un solo uso determinada solo se puede utilizar para firmar un único mensaje de forma segura. De hecho, las firmas revelan parte de la clave de firma. La seguridad de los esquemas de firma de un solo uso (basados en hash) depende exclusivamente de la seguridad de una función hash subyacente.
Los esquemas de firma de un solo uso más comunes incluyen el esquema Lamport–Diffie , el esquema Winternitz [15] y sus mejoras, como el esquema W-OTS + . [16] A diferencia del esquema seminal Lamport–Diffie, el esquema Winternitz y sus variantes pueden firmar muchos bits a la vez. La cantidad de bits que se firmarán a la vez está determinada por un valor: el parámetro Winternitz. La existencia de este parámetro proporciona un equilibrio entre tamaño y velocidad. Valores grandes del parámetro Winternitz producen firmas y claves cortas, al precio de una firma y verificación más lentas. En la práctica, un valor típico para este parámetro es 16.
En el caso de firmas basadas en hash sin estado, se utilizan esquemas de firma de pocas veces. Dichos esquemas permiten que la seguridad disminuya gradualmente en caso de que una clave de pocas veces se use más de una vez. HORST es un ejemplo de un esquema de firma de pocas veces.
La idea central de los esquemas de firma basados en hash es combinar un mayor número de pares de claves de un solo uso en una única estructura para obtener una forma práctica de firmar más de una vez (pero un número limitado de veces). Esto se hace utilizando una estructura de árbol de Merkle, con posibles variaciones. Se construyen una clave pública y una privada a partir de las numerosas claves públicas y privadas del esquema de un solo uso subyacente. La clave pública global es el nodo único en la parte superior del árbol de Merkle. Su valor es una salida de la función hash seleccionada, por lo que un tamaño típico de clave pública es de 32 bytes. La validez de esta clave pública global está relacionada con la validez de una clave pública de un solo uso dada utilizando una secuencia de nodos del árbol. Esta secuencia se llama ruta de autenticación. Se almacena como parte de la firma y permite que un verificador reconstruya la ruta del nodo entre esas dos claves públicas.
La clave privada global se maneja generalmente mediante un generador de números pseudoaleatorios. En ese caso, basta con almacenar un valor inicial. Las claves secretas de un solo uso se derivan sucesivamente del valor inicial mediante el generador. Con este enfoque, la clave privada global también es muy pequeña, por ejemplo, normalmente de 32 bytes.
El problema de atravesar el árbol es crítico para el rendimiento de la firma. Se han introducido enfoques cada vez más eficientes que aceleran drásticamente el tiempo de firma.
Algunos esquemas de firma basados en hash utilizan múltiples capas de árboles, lo que ofrece una firma más rápida a costa de firmas más grandes. En dichos esquemas, solo se utiliza la capa más baja de árboles para firmar mensajes, mientras que todos los demás árboles firman los valores raíz de los árboles inferiores.
El trabajo de Naor-Yung [17] muestra el patrón mediante el cual se puede transferir una firma de tiempo limitada de la familia de tipos Merkle a un esquema de firma ilimitada (regular).
Los esquemas de firma basados en hash se basan en suposiciones de seguridad sobre la función hash subyacente, pero se puede utilizar cualquier función hash que cumpla con estas suposiciones. En consecuencia, cada función hash adecuada produce un esquema de firma basado en hash correspondiente diferente. Incluso si una función hash dada se vuelve insegura, es suficiente reemplazarla por una diferente y segura para obtener una instancia segura del esquema de firma basado en hash en consideración. Algunos esquemas de firma basados en hash (como XMSS con generación de claves pseudoaleatorias) son seguros hacia adelante, lo que significa que las firmas anteriores siguen siendo válidas si se compromete una clave secreta.
La minimización de los supuestos de seguridad es otra característica de los esquemas de firma basados en hash. Por lo general, estos esquemas solo requieren una función hash criptográfica segura (por ejemplo, en el sentido de resistencia a la segunda preimagen ) para garantizar la seguridad general del esquema. Este tipo de supuesto es necesario para cualquier esquema de firma digital; sin embargo, otros esquemas de firma requieren supuestos de seguridad adicionales , lo que no es el caso aquí.
Debido a que dependen de un esquema de firma única subyacente, los esquemas de firma basados en hash solo pueden firmar de forma segura una cantidad fija de mensajes. En el caso de los esquemas Merkle y XMSS, se puede firmar de forma segura una cantidad máxima de mensajes, con la altura total del árbol Merkle.
Desde el esquema inicial de Merkle, se han introducido numerosos esquemas de firma basados en hash con mejoras de rendimiento. Los más recientes incluyen los esquemas XMSS, Leighton–Micali (LMS), SPHINCS y BPQS. La mayoría de los esquemas de firma basados en hash son con estado , lo que significa que la firma requiere actualizar la clave secreta, a diferencia de los esquemas de firma digital convencionales. Para los esquemas de firma basados en hash con estado, la firma requiere mantener el estado de las claves de un solo uso utilizadas y asegurarse de que nunca se reutilicen. Los esquemas XMSS, LMS y BPQS [18] son con estado, mientras que el esquema SPHINCS no tiene estado. Las firmas SPHINCS son más grandes que las firmas XMSS y LMS. BPQS ha sido diseñado específicamente para sistemas de cadena de bloques. Además del esquema de firma de un solo uso WOTS+, [16] SPHINCS también utiliza un esquema de firma de pocas veces (basado en hash) llamado HORST. HORST es una mejora de un esquema más antiguo de pocas firmas de tiempo, HORS (Hash para obtener un subconjunto aleatorio). [19]
Los esquemas basados en hash con estado XMSS y XMSS MT se especifican en RFC 8391 (XMSS: eXtended Merkle Signature Scheme). [20] Las firmas basadas en hash Leighton–Micali se especifican en RFC 8554. [5] Se han propuesto mejoras prácticas en la literatura que alivian las preocupaciones introducidas por los esquemas con estado. [21] Las funciones hash apropiadas para estos esquemas incluyen SHA-2 , SHA-3 y BLAKE .
Los esquemas XMSS, GMSS y SPHINCS están disponibles en las API criptográficas de Java Bouncy Castle . [22] Los esquemas LMS [23] y XMSS están disponibles en las API criptográficas de wolfSSL . [24] SPHINCS está implementado en el kit de herramientas de evaluación comparativa SUPERCOP. [25] Existen implementaciones de referencia optimizadas [26] y no optimizadas [27] del RFC XMSS. El esquema LMS se ha implementado en Python [28] y en C [29] siguiendo su borrador de Internet.
