Criptografía basada en hash - Hash-based cryptography
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 de interés como un tipo de criptografía post-cuántica .
Hasta ahora, la criptografía basada en hash se utiliza para construir esquemas de firmas digitales como el esquema de firma Merkle , conocimiento cero y pruebas de integridad computacional, como el sistema de prueba zk-STARK y pruebas de rango sobre credenciales emitidas a través del protocolo HashWires. Los esquemas de firma basados en hash combinan un esquema de firma de una sola vez con una estructura de árbol Merkle . Dado que una clave de esquema de firma de una sola vez solo puede firmar un único mensaje de forma segura, es práctico combinar muchas de estas claves en una única estructura más grande. Para ello se utiliza una estructura de árbol Merkle. En esta estructura de datos jerárquica, una función hash y una concatenación se utilizan repetidamente para calcular los nodos del árbol. Las firmas de Lamport son un ejemplo de un esquema de firma de una sola vez que se puede combinar con una estructura de árbol Merkle.
En 2019, el Instituto Nacional de Estándares y Tecnología de EE. UU. Anunció su intención de promulgar estándares para la criptografía basada en hash con estado basados en el Esquema de firma eXtended Merkle (XMSS) y las Firmas Leighton-Micali (LMS), que son aplicables en diferentes circunstancias.
Historia
Leslie Lamport inventó las firmas basadas en hash en 1979. Los esquemas de firma basados en hash XMSS (eXtended Merkle Signature Scheme) y SPHINCS 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 Esquema de firma de Merkle generalizado de 2007 (GMSS). En 2013 se describió una variante de varios árboles de XMSS, XMSS MT .
Esquemas de firma de una sola vez
Los esquemas de firma basados en hash utilizan esquemas de firma de una sola vez como componente básico. Una clave de firma de una sola vez 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 única (basados en hash) se basa exclusivamente en la seguridad de una función hash subyacente.
Los esquemas de firma de una sola vez comúnmente utilizados incluyen el esquema Lamport-Diffie , el esquema Winternitz y sus mejoras, como el esquema W-OTS + . A diferencia del esquema seminal de Lamport-Diffie, el esquema de Winternitz y las variantes pueden firmar muchos bits a la vez. El número de bits a firmar a la vez está determinado por un valor: el parámetro Winternitz. La existencia de este parámetro proporciona una compensación entre tamaño y velocidad. Los valores altos del parámetro de 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 se use una clave de pocas veces más de una vez. HORST es un ejemplo de un esquema de firma de pocas veces.
Combinar muchos pares de claves de una sola vez en un esquema de firma basado en hash
La idea central de los esquemas de firma basados en hash es combinar una mayor cantidad de pares de claves de una sola vez en una sola estructura para obtener una forma práctica de firmar más de una vez (aunque un número limitado de veces). Esto se hace utilizando una estructura de árbol Merkle, con posibles variaciones. Una clave pública y una privada se construyen a partir de las numerosas claves públicas y privadas del esquema subyacente de una sola vez. La clave pública global es el nodo único en la parte superior del árbol Merkle. Su valor es una salida de la función hash seleccionada, por lo que un tamaño de clave pública típico es de 32 bytes. La validez de esta clave pública global está relacionada con la validez de una determinada clave pública de un solo uso utilizando una secuencia de nodos de árbol. Esta secuencia se denomina 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. Entonces es suficiente almacenar un valor semilla. 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, típicamente 32 bytes.
El problema del cruce de árboles es fundamental para el rendimiento de la firma. Se han introducido enfoques cada vez más eficientes, lo que acelera drásticamente el tiempo de firma.
Algunos esquemas de firma basados en hash utilizan múltiples capas de árbol, lo que ofrece una firma más rápida al precio de firmas más grandes. En tales esquemas, solo la capa más baja de árboles se usa para firmar mensajes, mientras que todos los demás árboles firman valores de raíz de árboles más bajos.
El trabajo de Naor-Yung muestra el patrón mediante el cual transferir una firma de tiempo limitado de la familia tipográfica Merkle a un esquema de firma ilimitado (regular).
Propiedades de los esquemas de firma basados en hash
Los esquemas de firma basados en hash se basan en supuestos de seguridad sobre la función hash subyacente, pero se puede utilizar cualquier función hash que cumpla con estos supuestos. Como consecuencia, cada función hash adecuada produce un esquema de firma basado en hash correspondiente diferente. Incluso si una función hash determinada se vuelve insegura, es suficiente reemplazarla por otra diferente y segura para obtener una instanciación segura del esquema de firma basado en hash que se está considerando. Algunos esquemas de firma basados en hash (como XMSS con generación de clave pseudoaleatoria) son seguros hacia adelante, lo que significa que las firmas anteriores siguen siendo válidas si una clave secreta se ve comprometida.
La minimidad de los supuestos de seguridad es otra característica de los esquemas de firma basados en hash. Generalmente, estos esquemas solo requieren una función de hash criptográfica segura (por ejemplo, en el sentido de la resistencia de la segunda preimagen ) para garantizar la seguridad general del esquema. Este tipo de suposición es necesaria para cualquier esquema de firma digital; sin embargo, otros esquemas de firmas requieren supuestos de seguridad adicionales , lo cual no es el caso aquí.
Debido a su dependencia de un esquema de firma de una sola vez subyacente, los esquemas de firma basados en hash solo pueden firmar un número fijo de mensajes de forma segura. En el caso de los esquemas Merkle y XMSS, se puede firmar un máximo de mensajes de forma segura, con la altura total del árbol Merkle.
Ejemplos de esquemas de firma basados en hash
Desde el esquema inicial de Merkle, se han introducido numerosos esquemas de firmas 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 tienen 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 tienen estado, mientras que el esquema SPHINCS no tiene estado. Las firmas SPHINCS son más grandes que las firmas XMSS, LMS, mientras que BPQS ha sido diseñado específicamente para sistemas blockchain. Además del esquema de firma única de WOTS + , SPHINCS también usa un esquema de firma de pocas veces (basado en hash) llamado HORST. HORST es una mejora de un antiguo esquema de firma de pocas veces, HORS (Hash para obtener subconjunto aleatorio).
Los esquemas basados en hash con estado XMSS y XMSS MT se especifican en RFC 8391 (XMSS: eXtended Merkle Signature Scheme). Las firmas basadas en Hash de Leighton-Micali se especifican en RFC 8554. Se han propuesto mejoras prácticas en la literatura que alivian las preocupaciones introducidas por los esquemas con estado. Las funciones hash apropiadas para estos esquemas incluyen SHA-2 , SHA-3 y BLAKE .
Implementaciones
A diferencia de otras redes de cadenas de bloques y criptomonedas populares que utilizan algoritmos de firma digital de curva elíptica ( ECDSA ) estandarizados por el NIST , Quantum Resistant Ledger (QRL) es la primera red de código abierto en implementar eXtended Merkle Signature Scheme. En contraste con las firmas ECDSA tradicionales, este esquema de firma con estado es demostrablemente resistente a una computadora cuántica lo suficientemente poderosa que ejecuta el algoritmo de Shor .
Los esquemas XMSS, GMSS y SPHINCS están disponibles en las API criptográficas de Java Bouncy Castle . SPHINCS se implementa en el kit de herramientas de evaluación comparativa SUPERCOP. Existen implementaciones de referencia optimizadas y no optimizadas del XMSS RFC. El esquema LMS se ha implementado en Python y en C siguiendo su Internet-Draft.
Referencias
- T. Lange. "Firmas basadas en hash". Enciclopedia de criptografía y seguridad, Springer EE. UU., 2011. [2]
- FT Leighton, S. Micali. "Grandes esquemas de firma digital demostrablemente rápidos y seguros basados en funciones hash seguras". Patente de Estados Unidos 5.432.852, [3] 1995.
- G. Becker. "Esquemas de firma de Merkle, árboles de Merkle y su criptoanálisis", seminario 'Criptología postcuántica' en la Universidad de Ruhr en Bochum, Alemania, 2008. [4]
- E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, LC Coronado García. "CMSS - un esquema de firma Merkle mejorado". Progreso en criptología - Indocrypt 2006. [5]
- R. Merkle. "Secreto, autenticación y sistemas de clave pública / Una firma digital certificada". Doctor. disertación, Departamento de Ingeniería Eléctrica, Universidad de Stanford, 1979. [6]
- S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Representación y recorrido del árbol Fractal Merkle". RSA-CT 03. [7]
- P. Kampanakis, S. Fluhrer. "LMS vs XMSS: una comparación de los estándares propuestos de firmas basadas en hash de estado". Archivo de Cryptology ePrint, Informe 2017/349. [8]
- D. Naor, A. Shenhav, A. Wool. "Firmas de una sola vez revisadas: firmas rápidas prácticas utilizando el cruce del árbol Fractal Merkle". 24ª Convención de Ingenieros Eléctricos y Electrónicos de IEEE en Israel, 2006. [9]