¿Se sabe de qué tamaño de mensaje son las funciones hash estándar inyectivas?

Question

¿Se sabe de qué tamaño de mensaje son las funciones hash estándar inyectivas?

#1 de cloudfeet (3 votos)
#2 de DRF (2 votos)

1

Este sencillo script de Python verifica que todos los mensajes de longitud 1 tienen hashes SHA-1 diferentes:

import hashlib
s = set()
for i in range(256):
    s.add(hashlib.sha1(chr(i)).hexdigest())
print len(s)

¿Se sabe hasta qué tamaño de los mensajes son funciones hash criptográficas como SHA-1, SHA-2 o MD5 inyectivo? En otras palabras (para cada función hash):

¿Cuáles son los dos mensajes más cortos con el mismo hash?
¿Cuál es el n más pequeño de manera que existen dos mensajes de longitud n con el mismo hash?

hash md5 sha

pregunta Petr Pudlák 31.03.2015 - 10:16

fuente

2 respuestas

Lea otras preguntas en las etiquetas hash md5 sha

¿Cómo se puede saber si la base de datos de contraseñas en el servidor es robada o no? problema de seguridad del comando bash enviado por el usuario

score 3 · Answer 1

Según Wikipedia (barra de resumen en la RHS), "SHA-1 no ha producido aún colisiones reales". Lo mejor que hemos hecho es encontrar algoritmos que "deberían" encontrar colisiones eventualmente.

Dado que el punto de una función hash es que cualquier cambio (incluso un solo bit) debería cambiar el resultado completo de una manera básicamente pseudoaleatoria, esencialmente estás mirando a problema de cumpleaños .

La tabla en esta página de Wikipedia enumera la relación entre cuántas entradas tiene y qué tan preocupado debería estar. sobre una colisión. Esta otra tabla aquí enumera la "seguridad" de cada hash (en bits).

Un ejemplo de cálculo: para SHA-512 , con 256 bits de seguridad, debe mirar 10 ^ 32 antes de comenzar a tener problemas. log2(10^32) tiene aproximadamente 106 bits, lo que significa que debería comenzar a preocuparse por las colisiones después de unos 13 bytes . Sin embargo, es posible que tenga otros problemas en ese momento, como su factura de electricidad y la muerte del Sol.

score 2 · Answer 2

Esto es algo que también he pasado un tiempo tratando de averiguar. La respuesta es mucho más difícil de lo que parece, pero parece ser bastante consistente "No tenemos idea".

Esto puede parecer extraño, pero en realidad es bastante razonable si consideras lo que estás buscando. Esencialmente, le estás pidiendo a alguien que encuentre una colisión en una función hash. Se supone que eso es MUY duro. Tanto el SHA-1 como el SHA-2 y, en menor medida, el MD-5 (que está roto) se diseñaron no solo para que encontrar preimágenes y colisiones fueran difíciles, sino incluso más. Una buena función hash debe ser indistinguible de un oráculo aleatorio.

Si pudiéramos descubrir cosas como las que está pidiendo, sabríamos mucho más sobre las funciones que lo que deberíamos poder decir.

Obviamente, puede estar seguro de que hay dos mensajes de longitud < = n + 1 que chocan, donde n es la longitud de bloque de la función hash. Espero que la duración de las colisiones más pequeñas sea casi máxima, pero para ser honesto, no puedo respaldar eso con las matemáticas.