¿Qué esquema asimétrico proporciona la firma más corta, a la vez que seguro?

16

He visto varios esquemas de firmas (DSA, ECDSA para los más comunes) y me pregunto si existe un esquema que tenga las siguientes propiedades:

  • Sea asimétrico (se necesita una clave privada para firmar, se puede verificar con una clave pública)
  • Tiene un tamaño de firma muy corto (menos de 50 bits)
  • Manténgase seguro para los estándares de hoy (es difícil encontrar la clave privada con una firma y el texto firmado)

Ni siquiera me importaría si varias firmas fueran válidas para un texto, siempre y cuando sean verificables con la clave pública.

Mi intuición es que "estar" seguro está inherentemente vinculado al tamaño de la clave de cifrado, lo que a su vez tiene un impacto en el tamaño de la firma. Por lo que pude ver, ECDSA ofrece firmas más cortas que DSA con el mismo nivel de seguridad, pero las firmas siguen siendo demasiado grandes para mi uso ...

Todos los pensamientos / enlaces a esquemas de firmas son bienvenidos.

editar: También leí acerca de BLS en algún momento, pero realmente no pude averiguar si es posible obtener un esquema lo suficientemente seguro con una firma de menos de 50 bits.

edit2: Debo agregar que el objetivo es usar eso para un esquema OTP, por lo que el tamaño de los mensajes que se firmarán sería pequeño (< 512 bytes), y las colisiones no serían un gran problema: suponiendo que los dos las partes conocen el mensaje, me gustaría que una de ellas verifique que la otra tiene una clave privada, con una firma muy corta.

    
pregunta Wam 22.03.2013 - 13:58
fuente

4 respuestas

19

No puede tener un esquema de firma seguro en menos de 50 bits. Demostración: el atacante puede simplemente enumerar todas las secuencias de 50 bits hasta que se encuentre una coincidencia. De hecho, un punto de las firmas digitales es que el algoritmo de verificación puede ser calculado por todos, ya que usa solo la clave pública (que, por definición, es pública).

Lo mejor que puedes esperar, teóricamente, es una firma de n bits para una seguridad de 2n . El umbral tradicional de inviabilidad era de bits n = 80 , pero el avance implacable de la tecnología tiende a elevarlo. Los criptógrafos modernos tienden a saltar a 128 bits, porque esa es una potencia de dos, por lo tanto hermosa (a pesar de Kant, la mayoría de los juicios estéticos son relativos). Sin embargo, 100 bits deberían ser seguros durante bastante tiempo.

Entre los algoritmos de firma conocidos que se consideran seguros, BLS es en este momento el mejor de su clase ; producirá firmas de tamaño 2n para un nivel de seguridad de 2n , por lo que está contemplando firmas de tamaño de 160 a 200 bits por lo menos . Hay algoritmos que pueden ir por debajo (hasta aproximadamente 1.4 * n ) pero tienen una historia bastante larga de roturas, reparaciones y roturas de nuevo (estoy hablando de SFLASH y su ilk), por lo que su uso Realmente no se recomienda, y no hay un estándar directamente utilizable.

Otra posibilidad es usar RSA con relleno ISO / IEC 9796-2 . Como muestra el artículo vinculado, hay algunas sutilezas con respecto a su uso. Este esquema de firma es un esquema "con recuperación", lo que significa que si bien la firma es bastante voluminosa (1024 bits si usa una clave RSA de 1024 bits), también puede incrustar algunos de los datos que se firman; Por lo tanto, si su problema es agregar una firma a un mensaje, este esquema generará una sobrecarga relativamente baja. Como lo explica el artículo, obtiene la protección 261 para una sobrecarga de firma de 22 bytes, también conocida como 176 bits; para obtener una buena seguridad, tendría que usar una función hash con un tamaño de salida de, digamos, 224 bits, lo que lleva a una sobrecarga de firma de 240 bits, no tan buena como la de 200 bits de un BLS de potencia equivalente, pero mejor que los 400 bits de DSA o ECDSA (para aún el mismo nivel de potencia).

    
respondido por el Thomas Pornin 22.03.2013 - 14:25
fuente
4

El problema con una firma corta es que facilita la colisión. Tampoco puede hacer que su ejecución sea prohibitivamente tan larga (utilizando un hash lento o incrementando las iteraciones), ya que el tamaño del archivo puede diferir en órdenes de magnitud. Si lo hace lo suficientemente lento como para firmar de forma segura "hola", entonces será muy difícil firmar un lanzamiento de 50 gigabytes de bluray. Por lo tanto, la opción más fácil que nos queda es aumentar el número de bits y, por lo tanto, aumentar el número de intentos necesarios para obtener una colisión si el algoritmo no se rompe de otra manera.

También vale la pena señalar que el tamaño de la clave no tiene nada que ver con el tamaño de la firma. El tamaño del hash es lo que determina el tamaño de la firma, ya que una firma es un hash del archivo que luego se cifra con la clave privada, de modo que la clave pública puede descifrarla y compararla con su propio cálculo del hash. Siempre que no utilice un esquema de cifrado que requiera relleno, la longitud de la firma es completamente independiente del tamaño de la clave.

Edit: Ok, para la pregunta actualizada parece que no estás buscando una firma. Una firma toma un hash de un archivo y luego lo cifra con la clave privada, por lo que a) otros pueden verificar que el archivo no ha cambiado yb) otros pueden verificar que usted atestigua el archivo. Esto funciona porque alguien no puede crear otro archivo que se ajuste al mismo valor hash.

Lo que está buscando es un desafío / respuesta que pueda verificar que la persona que está tratando de ingresar posee la clave. Esto generalmente se realiza con una clave simétrica en lugar de una clave asimétrica, y se encripta una marca de tiempo. Hash para reducir la longitud. El problema es que el hash para reducir la longitud eliminará un sistema público / privado porque ambas partes tienen que poder realizar la acción. Supongo que un resultado corto podría derivarse de una firma de clave privada, pero tengo la sensación de que sería significativamente más débil (sin ninguna razón demostrable, pero no se ha hecho, según mi conocimiento) que utilizar una clave simétrica.

    
respondido por el AJ Henderson 22.03.2013 - 14:19
fuente
1

El resultado más reciente en esta dirección es el documento titulado " Las firmas más cortas de la historia " (ePrint: 2016 / 911), que utiliza criptografía multivariada. Pretende lograr firmas de 110 bits en el nivel de seguridad de 80 bits. Sin embargo, el esquema tiene los siguientes inconvenientes:

  • Supuesto de seguridad relativamente no probado (comparado con (EC) DSA / BLS)
  • Los rendimientos decrecientes en niveles de seguridad más altos (por ejemplo, la seguridad de 100 bits requiere 171 bits)
  • Tiempo de verificación lento para las firmas más pequeñas (~ 1 segundo)
  • Clave pública relativamente grande (25 a 100 kilobytes)

Una ventaja potencial, aparte de los tamaños de firmas cortas, es:

  • Se cree que la criptografía multivariable es más resistente a los ataques cuánticos que (EC) DSA / BLS

Si realmente necesita firmas muy cortas y puede vivir con los inconvenientes, entonces podría intentarlo. Tenga en cuenta sin embargo que la criptografía, por naturaleza, es un tema conservador; es mejor que te limites a seguir un esquema comprobado a menos que realmente necesites lo contrario.

    
respondido por el djao 28.07.2017 - 07:31
fuente
0

Una alternativa a DSA (EC) es el esquema de firma de Schnoor, que en su forma original reduce el tamaño de la firma de 4t-bit a 3t-bit para conjeturas 2 t -bit security y como máximo 2 t / 2 firmas por clave. Por ejemplo, en el nivel de seguridad de 96 bits, una firma requiere 36 bytes.

La descripción de referencia es: Claus-Peter Schnorr, Efficient Signature Generation por tarjetas inteligentes , en Journal of cryptology, 1991 . Se considera que el esquema es aplicable a cualquier grupo de orden $ q $ donde el problema de DL sea difícil.

Analizo algunas posibles variantes en esta pregunta :

  • deshacerse del RNG utilizado para la firma, que es una debilidad probada y comprobada de DSA (EC) y similares, reemplazándolo por un MAC determinista, como en Ed25519 ;
  • utilizando hashes salted con la clave pública / ID de usuario;
  • volver a aplicar hash al hash t-bit a 2t-bit antes de usarlo.

Los dos últimos cambios apuntan a argumentos de seguridad más fuertes (el hash público estrecho de t-bit se encuentra entre dos hashes salados); no pretenden eliminar una debilidad en una configuración específica.

    
respondido por el fgrieu 23.06.2017 - 19:37
fuente

Lea otras preguntas en las etiquetas