En criptografía , una firma Lamport o un esquema de firma única Lamport es un método para construir una firma digital . Las firmas de Lamport se pueden construir a partir de 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 de Lamport con grandes funciones hash seguirían siendo seguras en ese caso. Desafortunadamente, cada clave de Lamport solo se puede usar para firmar un solo mensaje. Sin embargo, combinado con árboles hash , se podría usar una sola clave para muchos mensajes, lo que lo convierte en un esquema de firma digital bastante eficiente.
El criptosistema característico de Lamport se inventó en 1979 y recibió el nombre de su inventor, Leslie Lamport . [1]
Ejemplo
Alice tiene una función hash criptográfica de 256 bits y algún tipo de generador seguro de números aleatorios . Quiere crear y utilizar un par de claves Lamport, es decir, una clave privada y una clave pública correspondiente.
Haciendo el par de llaves
Para crear la clave privada, Alice usa 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, utiliza el hash de 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 números forman su clave pública, que compartirá con el mundo.
Firmando el mensaje
Más tarde, Alice quiere firmar un mensaje. Primero, convierte el mensaje en una suma hash de 256 bits. Luego, para cada bit del hash, según 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 256 bits de longitud, el tamaño total de su firma será de 256 × 256 bits = 64 KiB. Estos números (originalmente seleccionados 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 usó para la firma. De lo contrario, cada firma adicional que reutilice la clave privada reduce el nivel de seguridad contra los adversarios que luego podrían crear firmas falsas a partir de ellos. [2]
Verificando la firma
Entonces Bob quiere verificar la firma del mensaje de Alice. También aplica un hash al mensaje para obtener una suma hash de 256 bits. Luego usa los bits en la suma hash para seleccionar 256 de los hash en la clave pública de Alice. Elige los valores hash 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 un 0, elige el primer hash del primer par, y así sucesivamente.
Luego Bob hace un hash de 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 es así, 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 lo tanto, nadie más puede crear la lista adecuada de 256 números aleatorios para la firma. Y después de que Alice ha publicado la firma, otros aún no conocen los otros 256 números aleatorios y, por lo tanto, no pueden crear firmas que se ajusten a otros hashes de mensajes.
Descripción formal
A continuación se muestra una breve descripción de cómo funcionan las firmas de Lamport, escritas 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 largo arbitrario firmado.
Llaves
Dejar ser un entero positivo y dejar ser el conjunto de mensajes. Dejarser una función unidireccional .
Para y el firmante elige aleatoriamente y calcula .
La clave privada , consiste en valores . La clave pública consta de la valores .
Firmar un mensaje
Dejar ser un mensaje.
La firma del mensaje es
- .
Verificando una firma
El verificador valida una firma comprobando que para todos .
Para falsificar un mensaje, Eva tendría que invertir la función unidireccional. Se supone que esto es intratable para entradas y salidas de tamaño adecuado.
Parámetros de seguridad
La seguridad de las firmas de 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 mensajes de n bits, la preimagen ideal y la resistencia de la segunda preimagen en una única invocación de la función hash implica del orden de 2 n operaciones para encontrar una colisión en un modelo informático clásico. Según el algoritmo de Grover , encontrar una colisión de preimagen en una sola 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 de Lamport, cada bit de la clave pública y la firma se basa en mensajes cortos que solo requieren una única invocación 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 del producción. Por ejemplo, en un caso degenerado, si cada elemento de clave privada y i, j tenía 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 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 de seguridad cuántica, 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 s i, j no deben ser menos de 2 veces mayores que la clasificación de seguridad. del sistema. Es decir:
- Un sistema seguro de 80 bits utiliza longitudes de elementos de no menos de 160 bits;
- Un sistema seguro de 128 bits utiliza longitudes de elementos de no menos de 256 bits;
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 tienen como objetivo solo una preimagen a la vez. Se sabe bajo un modelo de computación convencional que si se buscan 2 3 n / 5 preimágenes, el costo 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 recopilación de resúmenes de mensajes múltiples es un problema abierto. La selección de tamaños de elementos más grandes y funciones hash más fuertes, como elementos de 512 bits y SHA-512, garantiza mayores márgenes de seguridad para gestionar estas incógnitas.
Optimizaciones y variantes
Clave privada corta
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, del mismo tamaño que uno de los números aleatorios en la clave privada). La clave única se puede usar 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 un hash criptográficamente seguro (o al menos cuya salida no se XORed con la semilla) no se puede usar 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, debería usarse algún tipo de CSPRNG de acceso aleatorio , como BBS .
Clave pública corta
Una firma de Lamport se puede combinar con una lista de hash , lo que hace posible publicar solo el hash superior único en lugar de todos los hash de la clave pública. Es decir, en lugar del 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 del tamaño. Es decir, los valores para todos necesita ser incluido.
Los hash no utilizados no necesitan incluirse en la firma si se usa un acumulador criptográfico en lugar de una lista de hash. [4] Sin embargo, si el acumulador se basa en supuestos teóricos de números, esto probablemente anula el beneficio de emplear firmas de Lamport, por ejemplo, la resistencia a la computación cuántica.
Claves cortas y firma
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 la y la mitad de ese factor para la firma. El cálculo aumenta en un 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 expensas de duplicar el tamaño de la firma como se explica en la sección anterior.
Clave pública para varios mensajes
Cada clave pública de Lamport solo se puede usar para firmar un solo mensaje, lo que significa que se deben publicar muchas claves si se van a firmar muchos mensajes. Pero se puede usar un árbol hash en esas claves públicas, publicando el hash superior del árbol hash en su lugar. Esto aumenta el tamaño de la firma resultante, ya que partes del árbol hash deben incluirse en la firma, pero permite publicar un solo hash que luego se puede usar para verificar cualquier número dado de firmas futuras.
Ver también
Referencias
- ^ Lamport, Leslie (octubre de 1979). "Construcción de firmas digitales a partir de una función unidireccional" . SRI Internacional (CSL-98) . Consultado el 17 de febrero de 2021 .
- ^ "Firma de Lamport: ¿Cuántas firmas se necesitan para falsificar una firma?" .
- ^ Bart Preneel, "Principios de diseño para funciones hash iteradas revisadas"
- ^ "¿Se puede usar un acumulador criptográfico para almacenar de manera eficiente las claves públicas de Lamport sin la necesidad de un árbol Merkle?" .
- ^ "Esquema de firma única de Winternitz" .
Otras lecturas
- L. Lamport , Construcción de firmas digitales a partir de una función unidireccional , Informe técnico SRI-CSL-98, SRI International Computer Science Laboratory, octubre de 1979.
- Uso eficiente de los árboles Merkle : explicación de RSA Labs del propósito original de los árboles Merkle + firmas de Lamport, como un esquema eficiente de firma de una sola vez.
- Una introducción a las firmas basadas en hash y firmas Merkle por Adam Langley.
- Implementación de referencia del esquema Lamport sobre BLAKE2b (C ++)
- Implementación de referencia de firmas de Lamport sobre SHA256, SHA512 o Blake2b (Rust)