¿Hay alguna subcadena de hash (md5, sha1) más "aleatoria" que otra?

Question

Aquí es 3 ejemplo hashes MD5

$ md5 -s "1" && md5 -s "2" && md5 -s "3" 
MD5 ("1") = c4ca4238a0b923820dcc509a6f75849b 
MD5 ("2") = c81e728d9d4c2f636f067f89cc14862c 
MD5 ("3") = eccbc87e4b5ce2fe28308fd9f2a7baf3 

dicho que quiera tomar de 8 caracteres de cualquier hash. ¿El comienzo del hash es particularmente más "aleatorio" que el final? ¿medio? ¿O todas las subcadenas son igualmente "aleatorias"?

Answer 1

Tenía curiosidad por mí mismo, así que seguí adelante y escribí un program para probar esto. Necesitará Crypto++ para compilar el código.

Descargo de responsabilidad: Cuando se trata de criptografía, o incluso solo las matemáticas en general, sé lo suficiente como para dispararme en el pie. Por lo tanto, tome los siguientes resultados con un grano de sal y tenga en cuenta que solo tengo un conocimiento superficial de las herramientas que estoy usando.

Solo muestreé tres subcadenas: los primeros 8 bytes, los 8 bytes centrales y los 8 últimos bytes. Para resumir, son igualmente aleatorios.

Sin embargo, cuando se utiliza un espacio de muestra más pequeño, parece como si los últimos 8 bits fueran un poco más aleatorios. Cuanto mayor es el espacio de muestreo, más se acercan las tres subcadenas a la aleatoriedad completa.

---

1000 iteraciones:

First: 0.995914 
Middle: 0.996546 
Last: 0.998104 

5000 iteraciones:

First: 0.998387 
Middle: 0.998624 
Last: 0.999501 

10000 iteraciones:

First: 0.999614 
Middle: 0.999457 
Last: 1 

30000 iteraciones:

First: 1 
Middle: 1 
Last: 1 

---

"aleatoriedad" se mide por MaurerRandomnessTest clase Crypto ++ 's. Como referencia, el ejecutable compilado del código anterior tiene un valor de aleatoriedad de 0.632411 y una copia de Macbeth de Shakespeare descargada del Proyecto Gutenburg tiene un valor de aleatoriedad de 0.566991.

Answer 2

Todas las subcadenas de un buen hash (y md5 es razonablemente bueno a pesar de ser criptográficamente inseguro) son igualmente aleatorias, así que sí, toma cualquier parte del hilo que te guste, deberían distribuirse equitativamente.

Answer 3

Nitpick: "al azar" es la palabra incorrecta para usar aquí, ya que las funciones hash son deterministas.

En cuanto a contestar lo que quiere decir :), una propiedad deseable de las funciones de hash es lograr la Avalanche effect: básicamente, tener todos los bits de entrada causar cambios drásticos en la salida. Por lo tanto, para un hash bien diseñado, cada subcadena debe verse afectada con la misma frecuencia ("sea como aleatorio") como cualquier otro.