hash - password - Distribución uniforme de md5 truncado?

md5 value

Question

¿Podemos decir que un hash md5 truncado todavía está distribuido uniformemente?

Para evitar interpretaciones erróneas: soy consciente de que la probabilidad de colisiones es mucho mayor en el momento en que comienzas a piratear partes del resultado md5 ; mi caso de uso está realmente interesado en colisiones deliberadas . También sé que hay other métodos hash que pueden ser más adecuados para el uso, casos de un hash más corto (incluido, de hecho, el mío), y definitivamente los estoy buscando.

Pero también me gustaría saber si la distribución uniforme de md5 también se aplica a partes de ella. (Considéralo una curiosidad ardiente)

Dado que mediawiki lo usa (específicamente, los dos dígitos hexadecimales más a la izquierda como caracteres del resultado) para generar /4/42/The-image-name-here.png para imágenes (por ejemplo, /4/42/The-image-name-here.png ) y probablemente también estén interesados en una distribución al menos cercana a la normal, me imagino que la respuesta es ''sí'', pero en realidad no lo sé .

Answer 1

Escribí un pequeño programa php para responder esta pregunta. No es muy científico, pero muestra la distribución de los primeros y los últimos 8 bits de los valores hash usando los números naturales como hashtext. Después de aproximadamente 40,000,000 hashes, la diferencia entre el recuento más alto y el más bajo se reduce al 1%, por lo que diría que la distribución es correcta. Espero que el código sea más preciso al explicar lo que se calculó :-) Por cierto, con un programa similar encontré que los últimos 8 bits parecen estar distribuidos un poco mejor que el primero.

<?php
// Setup count-array:
for ($y=0; $y<16; $y++) {
for ($x=0; $x<16; $x++) {
$count[dechex($x).dechex($y)] = 0;
}
}
$text = 1; // The text we will hash.
$hashCount = 0;
$steps = 10000;
while (1) {
// Calculate & count a bunch of hashes:
for ($i=0; $i<$steps; $i++) {
$hash = md5($text);
$count[substr($hash, 0, 2)]++;
$count[substr($hash, -2)]++;
$text++;
}
$hashCount += $steps;
// Output result so far:
system("clear");
$min = PHP_INT_MAX; $max = 0;
for ($y=0; $y<16; $y++) {
for ($x=0; $x<16; $x++) {
$n = $count[dechex($x).dechex($y)];
if ($n < $min) $min = $n;
if ($n > $max) $max = $n;
print $n."/t";
}
print "/n";
}
print "Hashes: $hashCount, Min: $min, Max: $max, Delta: ".((($max-$min)*100)/$max)."%/n";
}
?>

Answer 2

Sí, no mostrar ningún sesgo es un requisito de diseño para un hash criptográfico. MD5 está roto desde un punto de vista criptográfico, sin embargo, la distribución de los resultados nunca estuvo en duda.

Si todavía necesita que lo convenzan, no es una gran tarea agrupar un montón de archivos, truncar el resultado y usar ent ( http://www.fourmilab.ch/random/ ) para analizar el resultado.