¿Cantidad mínima de bits para evitar colisiones hash? [cerrado]

0

Hay una serie de funciones hash en uso generalizado ahora. Parece que el rango general de bits es de 128 (MD5) a 512 (SHA-2).

Para evitar diferentes tipos de colisiones hash, ¿cuáles son las recomendaciones & número mínimo de bits?

Colisiones:

  • Identificadores (claves PGP, direcciones de bitcoin, etc.)
  • Archivos (controles de integridad)
  • HMAC (integridad de transmisión)
  • ?
pregunta Xeoncross 22.03.2018 - 18:12
fuente

2 respuestas

2

Un algoritmo de hashing perfecto generará bits aleatorios para cualquier entrada única. Suponiendo un algoritmo de hashing perfecto y una cantidad infinita de memoria, la cantidad de hashes que puede generar antes de que observe (en promedio) un duplicado, es alrededor de 1.2*sqrt(2^bits) . Un algoritmo de hash con una longitud de resumen de 32 bits, probablemente producirá un duplicado después de 77000 hashes. O, si desea tener una probabilidad de solo un 0,0001% de encontrar un duplicado, solo puede generar 93 hashes usando ese algoritmo. Eso es definitivamente posible con el hardware actual.

Ya se puede usar un algoritmo con salida de 64 bits para más de 6 millones de salidas antes de que tenga una probabilidad superior al 0.0001% de que se produzca un duplicado. Pero aún así, 6 millones podemos hacer.

Para tener un alto nivel de confianza y poder generar tantos hashes como desee, necesita un cierto número de bits. Pero la cantidad de bits que necesita depende del nivel de confianza que desea alcanzar. 128 bits es un buen nivel para casi cualquier cosa.

Otra consideración es la resistencia contra los ataques. A menudo, un algoritmo no se rompe por completo, sino que se debilita cada vez más, hasta que es factible realizar ataques realistas en tiempo real (si es que lo hay). Si su algoritmo de hash está debilitado, aún querrá que le quede suficiente confianza. Es por eso que la mayoría de los protocolos producen un poco más de lo necesario, como 256 bits.

Más información sobre las matemáticas: enlace

    
respondido por el Luc 23.03.2018 - 10:54
fuente
2

Cualquier función de hash criptográfica n -bit ininterrumpida tiene una resistencia de colisión de 2 n / 2 . Esto significa que, si desea tener una resistencia de colisión 2 128 , debe utilizar, como mínimo, una función hash de 256 bits. Como se pueden realizar 2 operaciones 64 , no querrá usar un hash de 128 bits. Un hash de 160 bits (es decir, un nivel de seguridad de 2 80 ) está en el límite. El uso de un hash de 256 bits le dará un nivel de seguridad de 2 128 , que debería estar completamente bien en el futuro inmediato. A veces, las debilidades en la función hash en sí misma hacen que sea más fácil de romper que lo que sugiere el resumen de salida. La familia de hashes SHA-2 es un ejemplo que actualmente no está roto. SHA-1, por otra parte, está roto . Tiene una salida de 160 bits pero "solo" un nivel de seguridad 2 63 contra colisiones, en lugar de 2 80 .

Sospecho que puedes estar mezclando ataques de colisión con otros tipos de ataques. Un ataque de colisión no permitirá que un atacante encuentre información que haga hashes a un valor arbitrario. Las definiciones formales:

  • Ataque Preimage : dado h donde f (m) = h , encuentra cualquier m ' tal que f (m ') = h .
    "Busque información que haga hashes a un valor arbitrario".

  • 2do ataque de preimagen - Dado f (m) = h , encuentra cualquier m ' tal que m ≠ m ' y f (m') = h .
    "Modificar una entrada sin cambiar el hash resultante".

  • Ataque de colisión : encuentre cualquier par de m y m ' de manera que m ≠ m' y f (m) = f (m ') .
    "Encuentra dos entradas que tengan el mismo hash".

Cada ataque tiene diferentes implicaciones. Un ataque de colisión es problemático para los certificados, ya que se pueden usar en firmas que son válidas para versiones benignas y maliciosas del mismo software. Un ataque de preimagen es problemático para la verificación. Imagínese si un atacante pudiera modificar un ejecutable sin cambiar su hash. Claramente, un ataque de pre-imagen es mucho más severo que un ataque de colisión, pero afortunadamente también es mucho más difícil de lograr. El infame algoritmo MD4 inseguro, por ejemplo, es tan malo en la resistencia a la colisión que es más barato encontrar una colisión que ejecutar la función hash dos veces. Sin embargo, por más roto que esté, los ataques de preimagen contra él son altamente teóricos.

Si, por otro lado, simplemente desea verificar la corrupción accidental y no tiene la intención de proteger contra un atacante activo, entonces lo ideal sería un CRC con un polinomio correctamente seleccionado. Un CRC puede en realidad garantizar la detección de errores hasta cierto punto.

    
respondido por el forest 23.03.2018 - 10:49
fuente

Lea otras preguntas en las etiquetas