¿Cómo puedo saber cuántos bits de seguridad tiene una función hash segura?

Pregunta:

¿Cómo puedo saber cuántos bits de seguridad tiene una función hash segura?

Por ejemplo, ¿cómo calcularía o diría cuántos bits de seguridad tendría una función hash segura con una salida de 160 bits? Suponiendo que no hay debilidades conocidas …

Respuesta:

Bueno, la resistencia al ataque dependerá de las propiedades de seguridad que necesite de él.

Hay tres suposiciones estándar que podemos hacer sobre una función hash:

  • Dado un valor hash, es difícil encontrar una imagen que tenga ese valor; esto se conoce como resistencia a la preimagen

  • Dada una imagen que tiene un valor hash específico, es difícil encontrar otra imagen que tenga ese mismo valor; esto se conoce como resistencia a la segunda preimagen . Esto se considera una suposición más fuerte que la resistencia a la preimagen, porque puede ser posible modificar la imagen y no cambiar el valor de salida.

  • Es difícil encontrar dos imágenes diferentes que tengan el mismo valor; esto se conoce como resistencia a colisiones .

A veces nos interesa la resistencia a colisiones, a veces no. Un ejemplo en el que nos puede interesar es si usamos el hash como parte de un esquema de firma. Por ejemplo, suponga que encontramos dos imágenes que tienen el mismo valor; uno dice "Me gusta el helado" y el otro dice "Estoy de acuerdo en darle a Bob un millón de dólares". Luego hacemos que Alice firme el mensaje que indica que le gusta el helado; Debido a que lo que firma el sistema de clave pública es en realidad el hash, Bob ahora escribe un mensaje firmado de Alice dándole un millón de dólares.

Ahora, hay otras ocasiones en las que realmente no nos preocupamos por la resistencia a las colisiones.

Entonces, ¿cuál es el problema de la resistencia a colisiones frente a la resistencia a la preimagen? Bueno, resulta que, si no asumimos ninguna debilidad criptográfica dentro de la función hash, es mucho más fácil romper la resistencia a colisiones que romper la resistencia de preimagen (o segunda preimagen).

Para romper la resistencia a las colisiones, una forma sería que el atacante aplicara un hash a una gran cantidad de variantes del mensaje "Me gusta el helado" y un gran número de variantes del mensaje "Estoy de acuerdo en darle a Bob un millón de dólares", y revise las listas y vea si hay un valor en común. Para un hash de 160 bits, necesitamos alrededor de $ 2 ^ {80} $ mensajes en ambas listas (debido a la paradoja del cumpleaños, es probable que sea suficiente); resulta que esto es lo mejor que podemos hacer (asumiendo que no hay debilidades criptográficas dentro del hash), y por lo tanto tenemos alrededor de 80 bits de seguridad contra este ataque.

Por otro lado, para romper la resistencia de la preimagen (o la segunda preimagen), no podemos usar la paradoja del cumpleaños. En cambio, lo mejor que podemos hacer (salvo una debilidad dentro de la función hash) es hash de muchos mensajes, y esperamos obtener uno que tenga el valor hash del valor objetivo. Para un hash de 160 bits, esperamos revisar alrededor de $ 2 ^ {160} $ mensajes antes de encontrarnos con uno, y por lo tanto tenemos alrededor de 160 bits de seguridad contra estos.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top

web tasarım