¿Qué es la criptografía basada en hash?

Definición: La criptografía basada en hash fue desarrollada por primera vez por Leslie Lamport y Ralph Merkle a finales de los años setenta. La criptografía basada en hash crea algoritmos de firma digital cuya seguridad se basa matemáticamente en la seguridad de una función hash criptográfica seleccionada.

Explicación de la criptografía basada en hash

Una función hash es un identificador único para cualquier contenido. También es un proceso que toma datos de texto plano de cualquier tamaño y los convierte en un texto cifrado único de una longitud específica. Las funciones hash toman una cadena de entrada (normalmente de longitud arbitraria) y devuelven un "resumen" de tamaño fijo como salida. Las funciones hash criptográficas más comunes, como SHA2, SHA3 o Blake2, producen compendios de entre 256 y 512 bits.

Un esquema de firma basado en hash parte de un esquema de firma de un solo uso (OTS), es decir, un esquema de firma en el que un par de claves sólo debe utilizarse para firmar un mensaje. Si un par de claves OTS se utiliza para firmar dos mensajes diferentes, un atacante puede falsificar fácilmente las firmas.

Sin embargo, lo que Merkle propuso fue una forma de conservar la capacidad de firmar N mensajes diferentes que funciona de la siguiente manera:

1. En primer lugar, se crean N pares de claves Lamport distintos. Un ejemplo podría ser (PK_1, SK_1), \dots, (PK_N, SK_N)

2. A continuación, asigne cada clave pública a una hoja de un árbol hash Merkle (véase más abajo) y calcule la raíz del árbol. Esta raíz servirá como clave pública "maestra" del nuevo esquema de firma Merkle.

3. El firmante conserva todas las claves pública y secreta de Lamport para utilizarlas en la firma.

Un árbol Merkle (o árbol hash) es una estructura de datos que se representa como un árbol en el que cada nodo hoja está etiquetado con el valor hash criptográfico de un bloque de datos y cada nodo no hoja está etiquetado con el hash criptográfico de las etiquetas de sus nodos hijos. Los árboles hash permiten verificar de forma eficaz y segura el contenido de grandes estructuras de datos.

Cada nivel de bloque en el árbol Merkle anterior refleja un orden superior de hash derivado de una transacción (T0-T7). El valor hash sucesivo (H) se pasa a través de una función hash para cada nivel de bloque por encima de la transacción inicial hasta que alcanza el nivel de bloque más alto representado como la suma de todos los hashes precedentes (H01234567).

Los valores hash de nivel inferior se denominan hojas y contienen el valor hash de la transacción (T) asociada a la hoja. Los niveles 3 y 4 son los resultados de los hashes de las hojas y sus hashes subsiguientes (o nodos). Por último, la raíz Merkle, el nivel de bloque más alto, contiene el resumen de todos los datos de la transacción en un único valor.

Desde el enfoque inicial de Merkle se han inventado numerosos esquemas de firma basados en hash con un rendimiento mejorado. Los esquemas XMSS, Leighton-Micali (LMS), SPHINCS y BPQS son ejemplos recientes. A diferencia de las técnicas típicas de firma digital, la mayoría de los esquemas de firma basados en hash son de estado, lo que significa que la firma requiere la actualización de la clave secreta.

Para firmar con técnicas de firma basadas en hash con estado es necesario hacer un seguimiento de las claves de un solo uso utilizadas y asegurarse de que nunca se repiten. Los esquemas XMSS, LMS y BPQS son con estado, pero el esquema SPHINCS es sin estado. Las firmas de SPHINCS son mayores que las de XMSS y LMS. BPQS se creó pensando en los sistemas Blockchain. Además de la técnica de firma de un solo uso WOTS+, SPHINCS emplea el mecanismo de firma de un solo uso HORST (basado en hash). HORST es una mejora de una antigua técnica de firma de pocas veces (Hash to Obtain Random Subset).

Los tres algoritmos de firma digital*, que serán normalizados por el NIST (basados en celosías estructuradas) para firmas digitales de seguridad cuántica son: