En criptografía , una firma Lamport o un esquema de firma única Lamport es un método para construir una firma digital . Las firmas Lamport se pueden crear desde cualquier función unidireccional criptográficamente segura ; normalmente se utiliza una función hash criptográfica .
Aunque el desarrollo potencial de las computadoras cuánticas amenaza la seguridad de muchas formas comunes de criptografía como RSA , se cree que las firmas Lamport con grandes funciones hash seguirían siendo seguras en ese caso. Cada clave Lamport solo se puede utilizar para firmar un único mensaje. Sin embargo, muchas firmas Lamport pueden ser manejadas por un árbol hash Merkle , por lo que se puede usar una única clave de árbol hash para muchos mensajes, lo que lo convierte en un esquema de firma digital bastante eficiente.
El criptosistema de firma Lamport fue inventado en 1979 y lleva el nombre de su inventora, Leslie Lamport . [1]
Alice tiene una función hash criptográfica de 256 bits y algún tipo de generador de números aleatorios seguro . Quiere crear y utilizar un par de claves Lamport, es decir, una clave privada y una clave pública correspondiente.
Para crear la clave privada, Alice utiliza el generador de números aleatorios para producir 256 pares de números aleatorios (2×256 números en total), cada número tiene un tamaño de 256 bits, es decir, un total de 2×256×256 bits = 128 Kibit. en total. Esta es su clave privada y la guardará en un lugar seguro para su uso posterior.
Para crear la clave pública, aplica un hash a cada uno de los 512 números aleatorios de la clave privada, creando así 512 hashes, cada uno de 256 bits de tamaño. (También 128 Kbits en total). Estos 512 hashes forman su clave pública, que compartirá con el mundo.
Más tarde Alice quiere firmar un mensaje. Primero, convierte el mensaje en una suma hash de 256 bits. Luego, para cada bit en el hash, basándose en el valor del bit, elige un número de los pares de números correspondientes que componen su clave privada (es decir, si el bit es 0, se elige el primer número, y si el bit es 1, se elige el segundo). Esto produce una secuencia de 256 números. Como cada número tiene una longitud de 256 bits, el tamaño total de su firma será 256 × 256 bits = 65536 bits = 64 Kibit. Estos números (originalmente elegidos al azar) son su firma y los publica junto con el mensaje.
Tenga en cuenta que ahora que se utiliza la clave privada de Alice, no debería volver a utilizarse nunca más. Debe destruir los otros 256 números que no utilizó para la firma. De lo contrario, cada firma adicional que reutiliza la clave privada reduce el nivel de seguridad contra adversarios que luego podrían crear firmas falsas a partir de ellas. [2]
Entonces Bob quiere verificar la firma del mensaje de Alice. También procesa el mensaje para obtener una suma hash de 256 bits. Luego usa los bits de la suma hash para seleccionar 256 de los hashes en la clave pública de Alice. Elige los hashes de la misma manera que Alice eligió los números aleatorios para la firma. Es decir, si el primer bit del hash del mensaje es 0, elige el primer hash del primer par, y así sucesivamente.
Luego Bob procesa cada uno de los 256 números aleatorios en la firma de Alice. Esto le da 256 hashes. Si estos 256 hashes coinciden exactamente con los 256 hashes que acaba de seleccionar de la clave pública de Alice, entonces la firma está bien. Si no, entonces la firma es incorrecta.
Tenga en cuenta que antes de que Alice publique la firma del mensaje, nadie más conoce los 2 × 256 números aleatorios en la clave privada. Por tanto, nadie más puede crear la lista adecuada de 256 números aleatorios para la firma. Y después de que Alice haya publicado la firma, otros todavía no conocen los otros 256 números aleatorios y, por lo tanto, no pueden crear firmas que se ajusten a otros hashes de mensajes.
A continuación se muestra una breve descripción de cómo funcionan las firmas Lamport, escrita en notación matemática . Tenga en cuenta que el "mensaje" en esta descripción es un bloque de tamaño fijo de tamaño razonable, posiblemente (pero no necesariamente) el resultado hash de un mensaje arbitrariamente largo firmado.
Sea un número entero positivo y sea el conjunto de mensajes. Sea una función unidireccional .
Para y el firmante elige aleatoriamente y calcula .
La clave privada, consta de valores . La clave pública consta de los valores .
Sea un mensaje.
La firma del mensaje es
El verificador valida una firma comprobándola para todos .
Para falsificar un mensaje, Eva tendría que invertir la función unidireccional . Se supone que esto es intratable para insumos y productos de tamaño adecuado.
La seguridad de las firmas Lamport se basa en la seguridad de la función hash unidireccional y la longitud de su salida.
Para una función hash que genera un resumen de mensaje de n bits, la resistencia ideal a la preimagen y a la segunda preimagen en una única invocación de función hash implica del orden de 2 n operaciones para encontrar una colisión bajo un modelo informático clásico. Según el algoritmo de Grover , encontrar una colisión de preimagen en una única invocación de una función hash ideal es el límite superior de las operaciones O(2 n /2 ) en un modelo de computación cuántica. En las firmas Lamport, cada bit de la clave pública y la firma se basa en mensajes cortos que requieren solo una invocación única a una función hash.
Para cada clave privada y i,j y su correspondiente par de claves públicas z i,j, se debe seleccionar la longitud de la clave privada de modo que realizar un ataque de preimagen en la longitud de la entrada no sea más rápido que realizar un ataque de preimagen en la longitud de la producción. Por ejemplo, en un caso degenerado, si cada elemento de clave privada y i,j tuviera solo 16 bits de longitud, es trivial buscar exhaustivamente las 2 16 combinaciones posibles de clave privada en 2 16 operaciones para encontrar una coincidencia con la salida, independientemente de la longitud del resumen del mensaje. Por lo tanto, un diseño de sistema equilibrado garantiza que ambas longitudes sean aproximadamente iguales.
Basado en el algoritmo de Grover, un sistema cuántico seguro, la longitud de los elementos de clave pública z i,j , los elementos de clave privada y i,j y los elementos de firma si ,j deben ser al menos 2 veces mayores que la clasificación de seguridad. del sistema. Eso es:
Sin embargo, se debe tener precaución ya que las estimaciones de trabajo idealistas anteriores asumen una función hash ideal (perfecta) y se limitan a ataques que apuntan solo a una preimagen a la vez. Se sabe mediante un modelo informático convencional que si se buscan 2 3 n /5 preimágenes, el coste total por preimagen disminuye de 2 n /2 a 2 2 n /5 . [3] Seleccionar el tamaño de elemento óptimo teniendo en cuenta la colección de múltiples resúmenes de mensajes es un problema abierto. La selección de tamaños de elementos más grandes y funciones hash más potentes, como elementos de 512 bits y SHA-512, garantiza mayores márgenes de seguridad para gestionar estas incógnitas.
En lugar de crear y almacenar todos los números aleatorios de la clave privada, se puede almacenar una única clave de tamaño suficiente. (Por lo general, tiene el mismo tamaño que uno de los números aleatorios de la clave privada). Luego, la clave única se puede utilizar como semilla para un generador de números pseudoaleatorios criptográficamente seguro (CSPRNG) para crear todos los números aleatorios en la clave privada cuando sea necesario. Tenga en cuenta que no se puede utilizar un hash criptográficamente seguro (o al menos cuya salida no esté sometida a XOR con la semilla) en lugar de CSPRNG porque firmar un mensaje revelaría valores aleatorios adicionales de la clave privada. Si el adversario puede acceder a la firma antes que los destinatarios previstos, entonces puede falsificar una firma con una reducción a la mitad del nivel de seguridad por cada duplicación de los valores aleatorios revelados de la clave privada.
De la misma manera, se puede usar una sola clave junto con un CSPRNG para crear muchas claves Lamport. Preferiblemente, entonces se debería utilizar algún tipo de CSPRNG de acceso aleatorio seguro poscuántico . En particular, no se deben utilizar CSPRNG clásicos como BBS .
Una firma Lamport se puede combinar con una lista hash , lo que permite publicar solo el hash superior en lugar de todos los hashes de la clave pública. Es decir, en lugar de los valores . Para verificar con el hash superior único, la firma debe incluir los números aleatorios y los hash no utilizados de la lista de hash de la clave pública, lo que da como resultado firmas de aproximadamente el doble de tamaño. Es decir, es necesario incluir los valores para todos .
No es necesario incluir los hashes no utilizados en la firma si se utiliza un acumulador criptográfico en lugar de una lista de hash. [4]
La compresión de firmas de Winternitz reduce el tamaño de la clave privada y la clave pública en un poco menos de un factor de y la mitad de ese factor para la firma. El cálculo aumenta en poco más de un factor de . Un hash criptográficamente seguro es suficiente en lugar del requisito de un CSPRNG. [5]
También se podría emplear una lista hash para acortar la clave pública a un valor único a costa de duplicar el tamaño de la firma, como se explica en la sección anterior.
Cada clave pública de Lamport solo se puede utilizar para firmar un único mensaje, lo que significa que se deben publicar muchas claves si se quieren firmar muchos mensajes. Pero se puede usar un árbol hash en esas claves públicas, publicando en su lugar el hash superior del árbol hash. Esto aumenta el tamaño de la firma resultante, ya que se debe incluir una rama del árbol hash en la firma, pero permite publicar un único hash que luego puede usarse para verificar una gran cantidad de firmas futuras.
