¿Por qué un hash de n bits no se puede romper con un hash en cada texto simple de n bits?

Navega tus respuestas
0

Me pregunto por qué es tan difícil encontrar colisiones para hashes criptográficos.

Tomemos, por ejemplo, una función hash que genera un hash 64 bit.

Para encontrar colisiones, si alimenta la función cada cadena de bits 65 posible, ¿no tiene la garantía de encontrar una colisión? La función hash tiene que convertir los bits 65 en bits 64 por lo que tiene que encontrar algunas colisiones.

¿No se puede encontrar una colisión de una manera bastante directa usando esta técnica?

Entiendo que la computación todos tomará mucho tiempo, pero parece bastante razonable hacerlo y crear un índice de base de datos para almacenarlos de modo que se puedan romper los hashes.

    
pregunta CodyBugstein 25.10.2015 - 15:31
fuente

2 respuestas

6

Sí, tienes razón. Aunque esperaría (estadísticamente) encontrar una colisión después de aproximadamente 2 ^ 32 intentos.

Si tiene un hash de 160 bits de longitud, tendría que probar 2 ^ 80 combinaciones (en promedio) para encontrar una colisión. Pero aún así, con el poder de computación de hoy, las combinaciones de 2 ^ 80 pueden demorar mucho para que tenga la edad suficiente para ver la colisión :-)

Eso es prácticamente todo. Haciendo que los bits sean tantos que solo se demora mucho en probar todas las combinaciones necesarias.

    
respondido por el fr00tyl00p 25.10.2015 - 16:11
fuente
4

fr00tyl00p lo explicó muy bien, así que simplemente descargaré algunos números para aclarar cuánta información sería.

Permite permanecer con tu ejemplo (cada valor de 65 bits se ha cifrado a 64 bits). 65 bits pueden contener 2 ^ 65 valores diferentes = 36.893.488.147.419.103.232. Así que necesitarías guardar al menos 2 ^ 65 * 64 bits. También es posible que necesites algún tipo de índice, pero ignoremos eso por ahora.

Esto requeriría unos 256 pebibyte, o 262144 datos de petabyte. Y esto es solo para hashes de 64 bits y sin ningún tipo de índice.

    
respondido por el SleepProgger 25.10.2015 - 20:13
fuente

Lea otras preguntas en las etiquetas

¿Por qué se considera que SHA-3 (keccak) es más seguro que DES cuando puede intentar romperlo 3 veces más rápido? [cerrado] ¿Es una amenaza para la seguridad tener comida o bebida al lado de las computadoras [cerrado]