Anomolies de salida de la función criptográfica hash

Question

Cualquiera sabe si MD5, Whirlpool, Sha [N], etc., tienen alguna entrada "especial" que pueda obtener una salida hexdigest para alinearse en:

• Todos los personajes numéricos
• Todos los personajes alfa
• Todo el mismo carácter/patrón se repite de manera consistente o total

Ejemplo en Python:

>>> from hashlib import sha1
>>> hash = sha1('magic_word').hexdigest()
>>> hash
4040404040404040404040404040404040404040
>>> hash = sha1('^3&#b d   *#"').hexdigest()
aedefeebadcdccebefadcedddcbeadaedcbdeadc

¿Es esto incluso posible? Mi conocimiento de las funciones de hash se limita al alcance de aplicarlas en bases de datos para almacenar contraseñas, lo cual es esencialmente ninguno.

Pero a veces me pregunto, al probar las colisiones, que este tipo de casos pueden surgir ...

Answer 1

Una función hash modela un oráculo al azar: Para cada entrada, si aún no se había consultado antes, arrojamos algunos dados para encontrar una salida, luego lo anotamos a algún libro. Si se consulta nuevamente una entrada, simplemente devuelva este valor anterior.

Al lanzar un dados de 16 lados 40 veces (para cada entrada), obtenemos suficiente salida para un SHA-1 como Oracle. (Para MD5, solo necesitamos 32 veces).

Entonces, podemos calcular la probabilidad de "40 veces solo letras" como (6/16)^40 ≈ 9.15 · 10^-18, "40 veces solo dígitos" tiene probabilidad (10/16)^40 ≈ 6.8 · 10^^ -9.

Como "número de intentos necesarios hasta el primer éxito" se distribuye geométricamente, necesitamos 1/P intentos en promedio, es decir, alrededor de 10^17 intentos para "solo letras" y 1.5 · 10^8 intentos para "solo dígitos".

(Ahora, Sha-1 no es un oráculo aleatorio real, pero no se sabe la debilidad que diría que SHA-1 tendría mejores o peores probabilidades para uno de estos. Y por ahora, la fuerza bruta realmente parece ser la mejor forma de hacer esto.)

Answer 2

Estoy seguro de que con la entrada correcta, ese tipo de salidas son posibles. ¿Por qué eso importa? ¿Sólo curioso?

Answer 3

Sí, es posible. Dada la entrada correcta, se puede emitir cualquier patrón de bits deseado. Sin embargo, puede tomar unos pocos millones de años encontrar el aporte correcto.

Para un objetivo razonablemente amplio, como todo Hex 0-9 o todo Hex AF, debería ser relativamente fácil. Calculando la proporción de salidas aceptables, en todas las salidas posibles lo ayudará a obtener una estimación del tiempo de ejecución. La fuerza bruta o la búsqueda aleatoria eventualmente encontrarán algo que llegue al objetivo. Para un hash roto, como MD4, es posible que pueda afeitarse algo del tiempo esperado.