signature – ¿Por qué EdDSA es resistente a colisiones con SHA-512?

Pregunta:

En el Bernstein et al. artículo sobre EdDSA , los autores afirman que EdDSA es resistente contra colisiones (es decir, puede ser seguro incluso si la función hash utilizada no es resistente a colisiones), basándose en un resultado de Neven et al. que dice que las firmas de Schnorr son seguras cuando se utilizan con una función hash que es resistente a preimagen de prefijo aleatorio y resistente a segunda preimagen de prefijo aleatorio. Bernstein dice que

Neven, Smart y Warinschi en [60] propusieron aprovechar la resistencia a colisiones eligiendo $ H $ para generar solo $ b / 2 $ bits, reduciendo el tamaño de las firmas comprimidas en un 25%.

y luego hace la siguiente afirmación:

Nuestra ecuación de verificación es la misma que la ecuación de verificación de Schnorr con hash de tamaño doble en lugar de hash de tamaño medio, con $ \ underline {A} $ insertado como una entrada de hash adicional y sin la compresión de Schnorr de $ \ underline {R} $. Evidentemente, estas modificaciones no comprometen la seguridad.

Sin embargo: en Neven, una mención de reducir a la mitad la longitud del hash ocurre en la página 8, donde señalan que el ataque de manada de Kelsey y Kohno le permite a uno usar una falta de resistencia a la colisión para las funciones hash Merkle-Damgård para romper el aleatorio- prefijar los requisitos de resistencia de preimagen y segunda preimagen, por lo que recomendamos no utilizar una función hash Merkle-Damgård tal cual, sino truncarla. Presentan esto no como una cuestión de conveniencia, sino de seguridad (de modo que incluso si la resistencia a colisiones se ve comprometida, las dos propiedades necesarias para que las firmas de Schnorr sean seguras no necesariamente se vean comprometidas por el ataque de manada). SHA-512, por supuesto, es una función hash Merkle-Damgård.

Aquí está mi pregunta: estoy bastante seguro de que no entendí algo que los autores del artículo de EdDSA de alguna manera pasaron por alto. Probablemente hay algo que me estoy perdiendo aquí. ¿Qué es?

Respuesta:

La parte relevante de Neven et al es esta:

Lo que esto significa para la práctica es que no se debe crear una instancia de la función hash con una iteración Merkle-Damgård de una función de compresión de $ n $ -bit. En su lugar, probablemente se debería simplemente truncar la salida de una función hash de $ 2n $ -bit a $ n $ bits. (En nuestra situación, tal método recordaría el hash de tubo ancho [Luc05] de Lucks). Por lo tanto, usar, por ejemplo, los primeros 128 bits del hash SHA-256 debería proporcionar en la práctica un nivel de seguridad de 128 bits.

Ed25519 usa SHA-512, una función hash de 512 bits. Si se aplica el ataque de manada pero la función hash en sí es segura, su nivel de seguridad debe ser de al menos 256 bits (la resistencia a la colisión de la función hash). Eso es mucho más que la seguridad del algoritmo general y, por lo tanto, no es relevante aquí.

Incluso si algún ataque de colisión en el número de ~ 256 bits que resulta de la multiplicación (después de la reducción módulo $ 1 $) permitiera romper el esquema de firma, eso aún no rompería el nivel de seguridad de ~ 128 bits reclamado.

Es decir, en lugar de tener problemas debido al uso de un hash Merkle-Damgård de media longitud, Ed25519 utiliza un hash conservador de doble longitud y no debería verse afectado.

Leave a Comment

Your email address will not be published.

Scroll to Top

istanbul avukat

-

web tasarım