Distribución uniforme de md5 truncado?

Question

¿Podemos decir que un hash truncado md5 todavía se distribuye uniformemente?

Para evitar interpretaciones erróneas: soy consciente de que la probabilidad de colisiones es mucho mayor en el momento en que empiezas a piratear partes del resultado md5; mi caso de uso es realmente interesado en deliberadas colisiones. También sé que hay otherhash methods que pueden ser más adecuados para los casos de uso 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 trozos de ella. (Considéralo una curiosidad ardiente)

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

Answer 1

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 tiene que estar convencido, no es una gran tarea tachar un montón de archivos, truncar la salida y usar ent (http://www.fourmilab.ch/random/) para analizar el resultado.

Answer 2

Escribí un pequeño programa php para responder a 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"; 
} 
?>