Firma de Lamport - Lamport signature

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 .

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 = 65536 bits = 8 KiB. 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 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.

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 números aleatorios de 2 × 256 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

Sea un número entero positivo y sea ​​el conjunto de mensajes. Sea una función unidireccional . ${\ Displaystyle k}$${\ Displaystyle P = \ {0,1 \} ^ {k}}$${\ Displaystyle f: \, Y \ rightarrow Z}$

Para y el firmante elige aleatoriamente y calcula . ${\ Displaystyle 1 \ leq i \ leq k}$${\ Displaystyle j \ in \ {0,1 \}}$${\ Displaystyle y_ {i, j} \ in Y}$${\ Displaystyle z_ {i, j} = f (y_ {i, j})}$

La clave privada , consta de valores . La clave pública consta de los valores . ${\ Displaystyle K}$${\ displaystyle 2k}$${\ Displaystyle y_ {i, j}}$${\ displaystyle 2k}$${\ Displaystyle z_ {i, j}}$

Firmar un mensaje

Sea un mensaje. ${\ Displaystyle m = m_ {1} \ ldots m_ {k} \ in \ {0,1 \} ^ {k}}$

La firma del mensaje es

${\ Displaystyle \ operatorname {sig} (m_ {1} \ ldots m_ {k}) = (y_ {1, m_ {1}}, \ ldots, y_ {k, m_ {k}}) = (s_ {1 }, \ ldots, s_ {k})}$.

Verificando una firma

El verificador valida una firma comprobando eso para todos . ${\ Displaystyle f (s_ {i}) = z_ {i, m_ {i}}}$${\ Displaystyle 1 \ leq i \ leq k}$

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. ${\ Displaystyle f}$

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 ⁿ 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} , la longitud de la clave privada debe seleccionarse 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} tenía solo 16 bits de longitud, es trivial buscar exhaustivamente las 2 ¹⁶ combinaciones posibles de clave privada en 2 ¹⁶ 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 asegura 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} . Seleccionar el tamaño de elemento óptimo teniendo en cuenta la recopilació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 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 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 del tamaño. Es decir, se deben incluir los valores para todos . ${\ displaystyle 2k}$${\ Displaystyle z_ {ij}}$${\ Displaystyle (z_ {ij})}$${\ Displaystyle j \ neq m_ {i}}$

Los hash no utilizados no necesitan incluirse en la firma si se usa un acumulador criptográfico en lugar de una lista de hash. 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 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. ${\ displaystyle 2 \ langle {\ text {tamaño del fragmento en bits}} \ rangle}$${\ displaystyle 2 ^ {\ langle {\ text {tamaño del fragmento en bits}} \ rangle} / \ langle {\ text {tamaño del fragmento en bits}} \ rangle}$

También se podría emplear una lista hash para acortar la clave pública a un solo valor 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

• S / LLAVE

Referencias

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)