Distribuzione uniforme di md5 troncato?

Question

Possiamo dire che un hash troncato md5 è ancora uniformemente distribuito?

Per evitare equivoci: sono consapevole che la possibilità di collisioni è molto più grande nel momento in cui si inizia a incidere parti dal risultato md5; il mio caso d'uso è in realtà interessato in collisioni deliberate. Sono anche consapevole che ci sono otherhash methods che potrebbero essere più adatti a casi d'uso di un hash più corto (incluso, in effetti, il mio), e sto sicuramente esaminando quelli.

Ma mi piacerebbe anche sapere se la distribuzione uniforme di md5 si applica anche a pezzi di esso. (Considerate una curiosità ardente.)

Poiché mediawiki lo utilizza (in particolare, le due cifre esadecimali di sinistra come caratteri del risultato) per generare percorsi di file per immagini (ad esempio /4/42/The-image-name-here.png) e probabilmente sono anche interessati a almeno vicino a - distribuzione uniforme, immagino che la risposta sia "sì", ma in realtà non lo so sa.

Answer 1

Sì, non mostrare alcun bias è un requisito di progettazione per un hash crittografico. MD5 è rotto da un punto di vista crittografico, tuttavia la distribuzione dei risultati non è mai stata messa in discussione.

Se è ancora necessario essere convinti, non è un'impresa impegnativa avere un sacco di file, troncare l'output e utilizzare ent (http://www.fourmilab.ch/random/) per analizzare il risultato.

Answer 2

Ho scritto un piccolo programma php per rispondere a questa domanda. Non è molto scientifico, ma mostra la distribuzione per il primo e l'ultimo 8 bit degli hashvalues ​​usando i numeri naturali come hashtext. Dopo circa 40.000.000 di hash, la differenza tra il conteggio più alto e quello più basso scende all'1%, quindi direi che la distribuzione è ok. Spero che il codice sia più preciso nello spiegare cosa è stato calcolato :-) Btw, con un programma simile ho trovato che gli ultimi 8 bit sembrano essere distribuiti leggermente meglio del primo.

<?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"; 
} 
?>