Firmas basadas en hash: una cartilla ilustrada

En los últimos años he tenido el privilegio de observar dos tendencias contradictorias y fascinantes. El primero es que finalmente estamos empezando a usar la criptografía Winternitz que los investigadores han pasado los últimos cuarenta años diseñando. Vemos esto todos los días en ejemplos que van desde mensajes cifrados hasta seguridad del teléfono y criptomonedas.

La segunda tendencia es que los criptógrafos se están preparando para que terminen todos estos buenos tiempos.

Pero antes de llegar a todo eso, mucho más abajo, permítanme enfatizar que esta no es una publicación sobre el apocalipsis de la computación cuántica , ni tampoco sobre el éxito de la criptografía en el siglo XXI. En cambio, voy a hablar de algo mucho más inseguro. Este post será sobre una de las tecnologías criptográficas más simples (¡y más geniales!) Jamás desarrolladas: las firmas basadas en hash.

Los esquemas de firma basados ​​en hash fueron inventados por Leslie Lamport a finales de la década de 1970, y significativamente mejorados por Ralph Merkle y otros. Durante muchos años fueron vistos en gran medida como un remanso criptográfico interesante, sobre todo porque producen firmas relativamente grandes (entre otras complicaciones). Sin embargo, en los últimos años estas construcciones han disfrutado de algo de un renacimiento, en gran parte porque, a diferencia de las firmas basadas en RSA o la suposición del logaritmo discreto, en gran medida se consideran resistentes a los ataques cuánticos graves como el algoritmo de Shor.

Primero algunos antecedentes.

Antecedentes: funciones hash y esquemas de firma

Para comprender las firmas basadas en hash, es importante que esté familiarizado con las funciones hash criptográficas. Estas funciones toman una cadena de entrada (típicamente o una longitud arbitraria) y producen un «resumen» de tamaño fijo como salida. Las funciones hash criptográficas comunes como SHA2 , SHA3 o Blake2 producen resúmenes que varían de 256 bits a 512 bits.

Para una función H(cdot) para ser considerado un hash «criptográfico», debe alcanzar algunos requisitos de seguridad específicos. Hay varios de estos, pero aquí nos centraremos en tres comunes:

1. Resistencia de la imagen previa (a veces conocida como «unidireccional»): dado algún resultado Y = H(X) , debería llevar mucho tiempo encontrar una entrada X tal que H(X) = Y . (Hay muchas advertencias sobre esto, por supuesto, pero lo ideal sería que el mejor ataque de ese tipo requiriera un tiempo comparable a una búsqueda de fuerza bruta de cualquier distribución X es extraído de.)

2. Resistencia de segunda preimagen: esta es sutilmente diferente a la resistencia de la imagen previa. Dada una entrada X , debería ser difícil para un atacante encontrar una entrada diferente X' tal que H(X) = H(X') .

3. resistencia a la colisión : Debe ser difícil encontrar dos valores X_1, X_2 tal que H(X_1) = H(X_2) . Tenga en cuenta que esta es una suposición mucho más fuerte que la resistencia de segunda preimagen, ya que el atacante tiene total libertad para encontrar dos mensajes de su elección.

Se cree que las funciones hash de ejemplo que mencioné anteriormente proporcionan todas estas propiedades. Es decir, nadie ha articulado un ataque significativo (o incluso conceptual) que rompa cualquiera de ellos. Eso siempre podría cambiar, por supuesto, en cuyo caso casi seguro que dejaríamos de usarlos. (Discutiremos el caso especial de los ataques cuánticos un poco más adelante).

Como nuestro objetivo es usar funciones hash para construir esquemas de firma, también es útil revisar brevemente esa primitiva.

Un esquema de firma digital es una primitiva de clave pública en la que un usuario (o «firmante») genera un par de claves, denominadas clave pública y clave privada. El usuario conserva la clave privada y puede usarla para «firmar» mensajes arbitrarios, produciendo una firma digital resultante. Cualquiera que tenga la posesión de la clave pública puede verificar la corrección de un mensaje y su firma asociada.

Desde una perspectiva de seguridad, la propiedad principal que queremos de un esquema de firma es la capacidad de forzarse, o la » capacidad de recuperación existencial «. Este requisito significa que un atacante (alguien que no posee la clave privada) no debería ser capaz de falsificar una firma válida en un mensaje que usted no firmó. Para más información sobre las definiciones formales de seguridad de firmas, vea esta página .

La firma de Lamport One-Time

Los primeros esquemas de firma basados ​​en hash fueron inventados en 1979 por un matemático llamado Leslie Lamport. Lamport observó que, dada la simple función de hash, o realmente, una función de un solo sentido , era posible construir un esquema de firmas extremadamente poderoso.

¡Poderoso, siempre que solo necesites firmar un mensaje! Más sobre esto a continuación.

A los efectos de esta discusión, supongamos que tenemos el siguiente ingrediente: una función hash que admite, digamos, entradas de 256 bits y produce salidas de 256 bits. SHA256 sería un ejemplo perfecto de tal función. También necesitaremos alguna forma de generar bits aleatorios.

Imaginemos que nuestro objetivo es firmar mensajes de 256 bits. Para generar nuestra clave secreta, lo primero que debemos hacer es generar una serie de 512 bitstrings aleatorios separados, cada uno de 256 bits de longitud. Para mayor comodidad, organizaremos esas cadenas en dos listas separadas y nos referiremos a cada una por un índice de la siguiente manera:

{bf sk_0} = sk^{0}_1, sk^{0}_2, dots,  sk^{0}_{256}
{bf sk_1} = sk^{1}_1, sk^{1}_2, dots,  sk^{1}_{256}

Las listas ({bf sk_0}, {bf sk_1}) representan la clave secreta que usaremos para firmar. Para generar la clave pública, ahora simplemente hash cada una de esas cadenas aleatorias utilizando nuestra función H(cdot) . Esto produce un segundo par de listas:

{bf pk_0} = H(sk^{0}_1), H(sk^{0}_2), dots, H(sk^{0}_{256})
{bf pk_1} = H(sk^{1}_1), H(sk^{1}_2), dots, H(sk^{1}_{256})

Ahora podemos distribuir nuestra clave pública ({bf pk_0}, {bf pk_1}) a todo el mundo Por ejemplo, podemos enviarlo a nuestros amigos, insertarlo en un certificado o publicarlo en Keybase .

Ahora digamos que queremos firmar un mensaje de 256 bits M usando nuestra clave secreta Lo primero que hacemos es dividirnos y representar M como una secuencia de 256 bits individuales:

M_1, dots, M_{256} in {0,1}

El resto del algoritmo de firma es deslumbrantemente simple. Simplemente trabajamos a través del mensaje desde el primer bit hasta el último bit, y seleccionamos una cadena de una de las dos listas de claves secretas. La lista que elegimos depende del valor del bit del mensaje que estamos intentando firmar.

Concretamente, para i = 1 a 256: si el i^NO bit de mensaje M_i =0 , tomamos el i^NO cadena clave secreta (sk^NO y saca esa cadena como parte de nuestra firma. Si el mensaje es poco M_i = 1 copiamos la cadena apropiada ( (sk^NO de la segunda lista. Una vez hecho esto para cada uno de los bits de mensaje, concatenamos todas las cadenas que seleccionamos. Esto forma nuestra firma.

Aquí hay una ilustración de juguete del proceso, donde (por simplicidad) la clave secreta y el mensaje tienen solo ocho bits de longitud. Observe que cada cuadro de color a continuación representa una cadena aleatoria de 256 bits diferente :

LamportIllustration

Cuando un usuario – que ya tiene la clave pública ({bf pk_0}, {bf pk_1}) – recibe un mensaje M y una firma, ella puede verificar la firma fácilmente. Dejar s_i represente el componente $ i ^ {th} $ de la firma: para cada cadena. Ella simplemente verifica el bit del mensaje correspondiente M_i y calcula el hash H(s_i) . Si M_i = 0 el resultado debe coincidir con el elemento correspondiente de {bf pk_0} . Si M_i = 1 el resultado debe coincidir con el elemento en {bf pk_1} .

La firma es válida si cada elemento individual de la firma, cuando está codificado, coincide con la parte correcta de la clave pública. Aquí hay una (esquemáticamente) incompleta ilustración del proceso de verificación, para al menos un componente de firma:

LamportVerify

Si su impresión inicial del esquema de Lamport es que es una locura, ambos tienen razón y están un poco equivocados.

Comencemos con lo negativo. En primer lugar, es fácil ver que las firmas y claves de Lamport son bastante grandes: del orden de miles de bits. Además, y mucho más críticamente , existe una seria limitación de seguridad en este esquema: cada clave solo se puede usar para firmar un mensaje. Esto hace que el esquema de Lamport sea un ejemplo de lo que se llama una » firma única «.

Para comprender por qué existe esta restricción, recuerde que cada firma de Lamport revela exactamente uno de los dos posibles valores de clave secreta en cada posición. Si solo firmo un mensaje, el esquema de firma funciona bien. Sin embargo, si alguna vez firmo dos mensajes que difieren en cualquier posición de bit i , entonces voy a terminar distribuyendo ambos valores clave secretos para esa posición. Esto puede ser un problema.

Imagine que un atacante ve dos firmas válidas en diferentes mensajes. Es posible que pueda realizar un simple ataque de falsificación de » mezclar y combinar » que le permita firmar un tercer mensaje que en realidad nunca firmé. Así es como podría verse en nuestro ejemplo de juguete:

Falsificación

El grado en que esto duele realmente depende de cuán diferentes sean los mensajes y cuántos de ellos le hayas dado al atacante para jugar. Pero raramente son buenas noticias.

Entonces, para resumir nuestras observaciones sobre el esquema de firma de Lamport. Es sencillo. Es rápido. Y, sin embargo, por diversas razones prácticas , es una mierda. Tal vez podamos hacerlo un poco mejor.

De una sola vez a muchas firmas de tiempo: la firma basada en árboles de Merkle

Si bien el esquema de Lamport es un buen comienzo, nuestra incapacidad para firmar muchos mensajes con una sola clave es un gran inconveniente. Nadie estaba más inspirado por esto que el estudiante de Martin Hellman, Ralph Merkle. Rápidamente se le ocurrió una forma inteligente de abordar este problema.

Si bien no podemos retrazar exactamente los pasos de Merkle, veamos si podemos recuperar algunas de las ideas obvias.

Digamos que nuestro objetivo es usar la firma de Lamport para firmar muchos mensajes, digamos N de ellos. El enfoque más obvio es simplemente generar N diferentes pares de claves para el esquema Lamport original, luego concatenar todas las claves públicas juntas en una mega-clave.

(Mega-key es un término técnico que acabo de inventar).

Si el firmante se aferra a todos N componentes claves secretas, ahora puede firmar N diferentes mensajes utilizando exactamente una clave secreta de Lamport por mensaje. Esto parece resolver el problema sin requerir que vuelva a utilizar una clave secreta. El verificador tiene todas las claves públicas y puede verificar todos los mensajes recibidos. No se utilizan llaves Lamport para firmar dos veces.

Obviamente, este enfoque apesta a lo grande.

Específicamente, en este enfoque ingenuo, firmando N veces requiere que el firmante distribuya una clave pública que es $ latex N $ veces más grande que una clave pública normal de Lamport. (También necesitará aferrarse a una pila similar de claves secretas.) En algún momento la gente se cansará de esto, y probablemente N no todos llegarán a ser muy grandes Ingrese Merkle.

Lo que Merkle propuso fue una forma de conservar la capacidad de firmar N diferentes mensajes, pero sin el aumento de costo lineal de las claves públicas. La idea de Merkle funcionó así:

  1. Primero, generar N separe los pares de llaves de Lamport. Podemos llamarlos (PK_1, SK_1), dots, (PK_N, SK_N) .
  2. A continuación, coloque cada clave pública en una hoja de un árbol hash de Merkle (ver a continuación) y calcule la raíz del árbol. Esta raíz se convertirá en la clave pública «maestra» del nuevo esquema de firma de Merkle.
  3. El firmante conserva todas las claves públicas y secretas de Lamport para usar en la firma.

Merkle trees se describen aquí . En términos generales, lo que ofrecen es una forma de recopilar muchos valores diferentes, de modo que puedan representarse mediante un solo hash «raíz» (de longitud de 256 bits, utilizando la función hash en nuestro ejemplo). Dado este hash, es posible producir una simple «prueba» de que un elemento está en un árbol hash dado. Además, esta prueba tiene un tamaño que es logarítmico en el número de hojas en el árbol.

2200px-hash_tree-svg
Merkle tree, ilustración de Wikipedia. Las claves públicas de Lamport entran en las hojas de este árbol y la raíz se convierte en la clave pública maestra.

Para firmar i^NO mensaje, el firmante simplemente selecciona el i^NO clave pública del árbol, y firma el mensaje usando la clave secreta correspondiente de Lamport. A continuación, concatena la firma resultante con la clave pública de Lamport y marca una » prueba Merkle » que muestra que esta clave pública específica de Lamport está contenida dentro del árbol identificado por la raíz ( es decir, la clave pública de todo el esquema). Luego transmite toda esta colección como la firma del mensaje.

(Para verificar la firma de este formulario, el verificador simplemente desempaqueta esta «firma» como firma Lamport, clave pública Lamport y Merkle Proof. Comprueba la firma Lamport frente a la clave pública Lamport determinada, y usa la Prueba Merkle para verificar que la clave pública de Lamport está realmente en el árbol. Con estos tres objetivos logrados, puede confiar en la firma como válida).

Este enfoque tiene la desventaja de aumentar el tamaño de «firma» en más de un factor de dos. Sin embargo, la clave pública maestra para el esquema ahora es solo un valor hash único, lo que hace que este enfoque escale mucho más limpiamente que la solución ingenua anterior.

Como optimización final, los datos de la clave secreta pueden ser «comprimidos» generando todas las diversas claves secretas utilizando la salida de un generador de números pseudoaleatorios criptográficos, que permite la generación de un gran número de bits (aparentemente aleatorios) de un solo corto ‘semilla’.

Uf.

Hacer firmas y claves (un poco) más eficientes

El enfoque de Merkle permite que cualquier firma única se convierta en una N -Signatura de compás. Sin embargo, su construcción aún requiere que usemos alguna firma subyacente única como el esquema de Lamport. Lamentablemente, los costos (de ancho de banda) del esquema de Lamport siguen siendo relativamente altos.

Hay dos optimizaciones principales que pueden ayudar a reducir estos costos. El primero también fue propuesto por Merkle . Primero trataremos esta técnica simple, principalmente porque ayuda a explicar el enfoque más poderoso.

Si recuerda el esquema de Lamport, para firmar un mensaje de 256 bits necesitamos un vector que consta de 512 cadenas de bits secretas separadas (y clave pública). La firma en sí misma era una colección de 256 de las cadenas de bits secretas. (Estos números fueron motivados por el hecho de que cada bit del mensaje que se debe firmar podría ser un «0» o un «1», y por lo tanto, el elemento clave secreto apropiado debería extraerse de una de las dos listas de claves secretas diferentes .)

Pero aquí hay una idea: ¿y si no firmamos todos los bits del mensaje ?

Seamos un poco más claros. En el esquema de Lamport, firmamos cada bit del mensaje, independientemente de su valor, enviando una cadena secreta. ¿Qué sucede si, en lugar de firmar tanto valores cero como uno en el mensaje, firmamos solo que los bits del mensaje eran iguales a uno ? Esto reduciría a la mitad los tamaños de clave pública y secreta, ya que podríamos deshacernos de la {bf sk_0} lista por completo

Ahora tendríamos una sola lista de cadenas de bits sk_1, dots, sk_{256} en nuestra clave secreta Para cada posición de bit del mensaje donde M_i = 1 saldríamos una cadena sk_i . Para cada posición donde M_i = 0 saldríamoszilch . (Esto también tenderá a reducir el tamaño de las firmas, ya que muchos mensajes contienen un montón de bits cero, ¡y eso ahora nos «costaría» nada!)

Un problema obvio con este enfoque es que es tremendamente inseguro. ¡Por favor no implemente este esquema!

Como ejemplo, digamos que un atacante observa un mensaje (firmado) que comienza con «1111 …», y ella quiere editar el mensaje para que diga «0000 …» – sin romper la firma. Todo lo que tiene que hacer para lograr esto es eliminar varios componentes de la firma. En resumen, si bien es muy difícil “flip” un bit cero en una un bit, es catastróficamente fácil de hacer a la inversa.

Pero resulta que hay una solución, y es bastante elegante.

Verá, aunque no podemos evitar que un atacante edite nuestro mensaje convirtiendo uno de los bits en bits cero , podemos atraparlos . Para hacer esto, agregamos una simple «suma de verificación» al mensaje,   luego, firme la combinación del mensaje original y la suma de comprobación. El verificador de firma debe verificar la firma completa en ambos valores, y también asegurarse de que la suma de comprobación recibida sea correcta.

La suma de comprobación que utilizamos es trivial: consiste en un simple entero binario que representa el número total de cero bits en el mensaje original.

Si el atacante intenta modificar el contenido del mensaje (excluyendo la suma de comprobación) para convertir un bit en un bit cero, el esquema de firma no la detendrá. Pero este ataque tiene el efecto de aumentar el número de bits cero en el mensaje . Esto hará que la suma de comprobación sea inválida inmediatamente y el verificador rechazará la firma.

Por supuesto, un atacante inteligente podría también intentar meterse con la suma de comprobación (que también se firmó junto con el mensaje) para «arreglarlo» aumentando el valor entero de la suma de comprobación . Sin embargo, y esto es crítico, dado que la suma de comprobación es un número entero binario, con el fin de aumentar el valor de la suma de comprobación, siempre necesitaría convertir algún bit cero de la suma de comprobación en un solo bit Pero dado que la suma de comprobación también está firmada, y el esquema de firma evita este tipo de cambio, el atacante no tiene dónde ir.

 ChecksumForgery

(Si realiza un seguimiento en casa, esto de alguna manera aumenta el tamaño del «mensaje» que se debe firmar. En nuestro ejemplo de mensaje de 256 bits, la suma de comprobación requerirá ocho bits adicionales y costo de firma correspondiente. Sin embargo, si el mensaje tiene muchos bits cero, el tamaño reducido de la firma generalmente seguirá siendo una ganancia).

Winternitz: espacio comercial por tiempo

El truco anterior reduce el tamaño de la clave pública a la mitad, y reduce el tamaño de (algunas) firmas en una cantidad similar. Eso es bueno, pero no realmente revolucionario. Todavía da claves y firmas que tienen miles de bits de longitud.

Sería bueno si pudiéramos hacer un hueco más grande en esos números.

La optimización final de la que hablaremos fue propuesta por Robert Winternitz como una optimización adicional de la técnica de Merkle anterior. En el uso práctico, ofrece una reducción de 4 a 8 veces en el tamaño de las firmas y las claves públicas, a un costo que aumenta el tiempo de firma y verificación.

La idea de Winternitz es un ejemplo de una técnica llamada « compensación de tiempo-espacio «. Este término se refiere a una clase de soluciones en las que el espacio se reduce a costa de agregar más tiempo de cálculo (o viceversa). Para explicar el enfoque de Winternitz, ayuda hacer la siguiente pregunta:

¿Y si, en lugar de firmar mensajes compuestos por bits (0 o 1), tratamos nuestros mensajes como si estuvieran codificados con alfabetos de símbolos más grandes? Por ejemplo, ¿qué pasa si firmamos ‘nibbles’ de cuatro bits? ¿O bytes de ocho bits?

En el esquema original de Lamport, teníamos dos listas de cadenas de bits como parte de la clave de firma (y pública). Una era para firmar cero bits de mensaje, y la otra era para uno bits.

Ahora digamos que queremos firmar bytes en lugar de bits. Una idea obvia sería aumentar el número de listas de claves secretas (y clave pública) de dos de tales listas a 256 de tales listas , una lista para cada valor posible de un byte de mensaje. El firmante podría trabajar a través del mensaje un byte a la vez, y seleccionar desde el menú mucho más grande de valores clave.

Desafortunadamente, esta solución realmente apesta. Reduce el tamaño de la firma por un factor de ocho , a un costo de aumentar el tamaño de la clave pública y secreta por un factor de 256. Incluso esto podría estar bien si las claves públicas se pueden usar para muchas firmas, pero no pueden: cuando se trata de reutilización de claves, esta «versión de firma de bytes de Lamport» adolece de las mismas limitaciones que la firma original de Lamport.

Todo lo cual nos lleva a la idea de Winternitz.

Dado que es demasiado caro almacenar y distribuir 256 listas verdaderamente aleatorias, ¿qué pasaría si generamos esas listas programáticamente solo cuando las necesitamos?

La idea de Winternitz era generar una lista única de semillas aleatorias  { bf sk ^ 0} = (sk ^ 0_1,  dots, sk ^ 0_ {256}) para nuestra clave secreta inicial. En lugar de generar listas adicionales al azar, propuso utilizar la función hash  H () en cada elemento de esa clave secreta inicial, para derivar la próxima lista para la clave secreta:  { bf sk_1} = (sk ^ {1} _1,  dots, sk ^ {1} _ {256}) = (H (sk ^ {0} _1),  dots, H (sk ^ {1} _ {256})) . Y de forma similar, uno puede usar la función hash nuevamente en esa lista para obtener la siguiente lista  { bf sk_2} . Y así sucesivamente para muchas listas posibles.

Esto es útil ya que ahora solo necesitamos almacenar una sola lista de valores de clave secreta  { bf sk_0} , y podemos derivar todas las otras listas bajo demanda simplemente aplicando la función hash.

¿Pero qué pasa con la clave pública? Aquí es donde Winternitz se vuelve inteligente.

Específicamente, Winternitz propuso que la clave pública podría derivarse aplicando la función hash una vez más a la lista final de claves secretas. Esto produciría una sola lista de claves públicas { bf pk} . (En la práctica, solo necesitamos 255 listas de claves secretas, ya que podemos tratar la clave clave final como la clave pública). La elegancia de este enfoque es que dado cualquiera de los posibles valores clave secretos es siempre es posible verificarlo contra la clave pública, simplemente haciendo hashing hacia adelante varias veces.

Todo el proceso de generación de claves se ilustra a continuación:

 Winternitz

Para firmar el primer byte de un mensaje, seleccionamos un valor de la lista correspondiente. Por ejemplo, si el byte del mensaje era «0», obtendríamos un valor de  { bf sk_0} en nuestra firma. Si el byte del mensaje era «20», obtendríamos un valor de  { bf sk_ {20}} . Para bytes con el valor máximo «255», no podemos generar resultados, o podemos generar el elemento apropiado de  { bf pk} .

Tenga en cuenta también que, en la práctica, no es necesario almacenar cada una de estas listas de claves secretas. Podemos derivar cualquier valor de clave secreta on demand dado solo la lista original  { bf sk} _0 . El verificador solo contiene el vector de clave pública y (como se mencionó anteriormente) simplemente hash forward un número apropiado de veces, dependiendo del byte del mensaje, para ver si el resultado es igual al componente apropiado del público. clave.

Al igual que la discusión de optimización Merkle en la sección anterior, el esquema presentado hasta ahora tiene una vulnerabilidad evidente. Dado que las claves secretas están relacionadas ( es decir,  sk ^ {1} _ {1} = H (sk ^ {0} _1) ), cualquiera que vea un mensaje que firme el mensaje» 0 «puede cambiar fácilmente el byte correspondiente del mensaje a» 1 «, y actualiza la firma para que coincida. De hecho, un atacante puede incrementar el valor de cualquier byte (s) en el mensaje. Sin algún control sobre esta capacidad, esto permitiría ataques de falsificación muy poderosos.

La solución a este problema es similar a la que acabamos de analizar. Para evitar que un atacante modifique la firma, el firmante calcula y también firma una suma de comprobación de los bytes del mensaje original. La estructura de esta suma de comprobación está diseñada para evitar que el atacante incremente cualquiera de los bytes, sin invalidar la suma de comprobación. No entraré en detalles sangrientos en este momento, pero puedes encontrarlos aquí .

No hace falta decir que obtener esta suma de comprobación correcta es fundamental. Atorníllelo, aunque sea un poco, y le pueden pasar cosas muy malas. Esto sería particularmente desagradable si desplegó estas firmas en un sistema de producción.

Ilustrado en una imagen terrible, un ejemplo de juguete de 4 bytes del esquema de Winternitz se ve así:

WinternitzComp lete
Tenga en cuenta que el mensaje en este caso consiste en bytes , no en bits. Estoy bastante seguro de que calculé la suma de comprobación correctamente, pero lo hice a mano y eso no siempre funciona tan bien.

¿Para qué sirven las firmas basadas en hash?

A lo largo de todo este debate, hemos estado hablando principalmente del cómo de las firmas basadas en hash en lugar del por qué de ellas. Es hora de que nos ocupemos de esto. ¿Cuál es el sentido de estas extrañas construcciones?

Uno de los primeros argumentos a favor de las firmas basadas en hash es que son notablemente rápidos y simples. Como solo requieren solo la evaluación de una función hash y cierta copia de datos, desde una perspectiva de costo puramente computacional son altamente competitivos con esquemas como ECDSA y RSA . Esto podría ser hipotéticamente importante para dispositivos livianos. Por supuesto, esta eficiencia tiene una gran compensación en la eficiencia del ancho de banda.

Sin embargo, hay una razón más complicada para el aumento (reciente) en la atención a las construcciones de firmas basadas en hash. Esto se debe al hecho de que all de nuestro cifrado de clave pública está a punto de romperse .

Más concretamente: la inminente llegada de las computadoras cuánticas va a tener un gran impacto en la seguridad de casi todos nuestros esquemas de firma práctica, que van desde RSA hasta ECDSA, etc. Esto se debe al hecho de que el algoritmo de Shor (y sus muchas variantes) nos proporciona un polinomio Algoritmo de tiempo para resolver el logaritmo discreto y problemas de factoring , lo que probablemente haga que la mayoría de estos esquemas no sean seguros.

La mayoría de las implementaciones de firmas basadas en hash no son vulnerables al algoritmo de Shor. Eso no quiere decir que sean completamente inmunes a las computadoras cuánticas, por supuesto. Los mejores ataques cuánticos generales sobre las funciones hash se basan en una técnica de búsqueda llamada el algoritmo de Grover , que reduce el seguridad efectiva de una función hash. Sin embargo, la reducción en la seguridad efectiva no es tan grave como el algoritmo de Shor (oscila entre el raíz cuadrada y raíz cúbica), por lo que se puede retener la seguridad simplemente aumentando la capacidad interna y el tamaño de salida de la función hash. Las funciones hash como SHA3 se desarrollaron explícitamente con tamaños de resumen grandes para proporcionar resistencia contra tales ataques.

Así que, al menos en teoría, las firmas basadas en hash son interesantes porque nos proporcionan una línea de defensa contra futuras computadoras cuánticas, por el momento, de todos modos.

Epílogo: detalles de seguridad aburridos

Si recuerdas un poco antes en este artículo, pasé algún tiempo describiendo las propiedades de seguridad de las funciones hash. Esto no fue solo para mostrar. Verá, la seguridad de una firma basada en hash depende en gran medida de las propiedades que una función hash puede proporcionar.

(Y por implicación, la inseguridad de una firma basada en hash depende de qué propiedades de una función hash un atacante haya podido vencer).

La mayoría de los artículos originales que discuten firmas basadas en hash generalmente cuelgan sus argumentos de seguridad en la resistencia a las imágenes previas de la función hash. Intuitivamente, esto parece bastante sencillo. Tomemos la firma Lamport como ejemplo. Dado un elemento de clave pública  pk ^ {0} _1 = H (sk ^ {0} _1) , un atacante que puede calcular preimágenes de hash puede recuperar fácilmente una clave secreta válida para ese componente de la firma. Este ataque, obviamente, hace que el esquema sea inseguro.

Sin embargo, este argumento solo considera el caso en el que un atacante tiene la clave pública pero aún no ha visto una firma válida. En este caso, el atacante tiene un poco más de información. Ahora tienen (por ejemplo) la clave pública y una parte de la clave secreta:  pk ^ {0} _1 = H (sk ^ {0} _1) y $ latex sk ^ {0} _1 $. Si dicho atacante puede encontrar una segunda imagen previa para la clave pública  pk ^ {0} _1 ella no puede firmar un mensaje diferente. Pero ella ha producido una nueva firma. En la sólida definición de seguridad de firmas ( SUF-CMA ) esto se considera realmente un ataque válido. Por lo tanto, SUF-CMA requiere la propiedad ligeramente más fuerte de la resistencia de segunda preimagen.

Por supuesto, hay un problema final que surge en la mayoría de los usos prácticos de esquemas de firma basados ​​en hash. Notará que la descripción anterior asume que estamos firmando mensajes de 256 bits. El problema con esto es que en aplicaciones reales, muchos mensajes tienen más de 256 bits. Como consecuencia, la mayoría de las personas usa la función hash H () al primer hash del mensaje como  D = H (M) y luego el signo el valor resultante  D en lugar del mensaje.

Esto conduce a un ataque final en el esquema de firma resultante, ya que la capacidad de recuperación existencial del esquema ahora depende de la resistencia a la colisión de la función hash. Un atacante que puede encontrar dos mensajes diferentes M_1  ne M_2 tal que  H (M_1) = H (M_2) ahora ha encontrado una firma válida en dos mensajes diferentes. Esto lleva a un quiebre trivial de EUF-CMA seguridad.

Leer más

Por admin

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.