Si verifica una riduzione dello spazio, ma non così.
Si suppone che le funzioni di hash sicure si comportino come ciò che una funzione casuale farebbe in media (cioè una funzione scelta in modo uniforme tra l'insieme di funzioni possibili con le stesse lunghezze di input e di output). MD5 e SHA-1 sono noti per non essere alla fine sicuri (perché possiamo trovare collisioni per loro in modo più efficiente di una funzione casuale), ma sono ancora abbastanza approssimazioni qui (ancora, non dovresti usarli se non per l'interoperabilità con implementazioni legacy, dovresti davvero usare una funzione più moderna e sicura come SHA-256).
Quindi, supponendo un output n -bit, se hai tutte e 2 le stringhe n dei bit n , puoi aspettarti che tutte le uscite coprano circa il 63,21% dello spazio di 2 n possibili valori di output (ovvero 1- (1 / e )). Si perde un po 'più di un terzo dello spazio. Tuttavia , se riporti di nuovo tutti questi valori ottenuti, perderai molto meno di un terzo di essi. Il fattore di riduzione non è costante per ogni round. Dopo pochi round, la riduzione extra per round è molto piccola.
Quando hai hash un determinato valore molti volte in successione, stai effettivamente camminando su una "struttura rho", come nella figura seguente:
Questastrutturaècosìdenominataperchésembraapprossimativamentelaletteragrecaρ,"rho". Ogni punto è un valore n -bit e ogni freccia rappresenta l'applicazione della funzione di hash. Il punto blu è il tuo punto di partenza. Quindi l'idea è che applicando la funzione sufficientemente molte volte, finisci in un ciclo. Una volta sul ciclo, le successive applicazioni della funzione hash non riducono più lo spazio dei valori possibili: basta camminare per il ciclo, indefinitamente. La lunghezza del ciclo è quindi la dimensione minima dello spazio che è possibile raggiungere.
Le lunghezze sia della "coda" (i valori che attraversi prima di entrare nel ciclo) che del "ciclo" stesso sono, in media, 2 n / 2 . Quindi, per una funzione di hash con uscita a 128 bit, le applicazioni successive non ridurranno lo spazio al di sotto di 2 64 , un valore abbastanza grande; raggiungere uno spazio minimo richiede in media 2 64 valutazioni della funzione hash, che è costoso.
Trovare il ciclo camminando sulla struttura rho è in realtà la base per l'algoritmo di ricerca del ciclo di Floyd , che è uno degli algoritmi generici che possono essere usati per costruire collisioni per una funzione hash: nella struttura rho, nel punto in cui la coda è attaccata al ciclo, c'è una collisione (due valori distinti che hanno lo stesso valore). Per una funzione hash crittograficamente sicura, trovare le collisioni dovrebbe essere difficile; in particolare, l'algoritmo di Floyd dovrebbe essere computazionalmente non fattibile, il che si ottiene rendendo n abbastanza grande (ad esempio, n = 256 per SHA-256: questo aumenta il costo dell'algoritmo di Floyd a 2 128 , cioè, non realisticamente fattibile sulla Terra).
In altre parole: se selezioni una funzione di hash sicura, con un output sufficientemente ampio (un prerequisito per essere sicuro), quindi non sarai in grado di raggiungere il ciclo e / o camminarlo, e la tua sicurezza non soffrirà di alcuna "riduzione dello spazio". Corollario: se hai un problema di riduzione dello spazio, non stai utilizzando una funzione di hash sicura e che è il problema che devi risolvere. Quindi, usa SHA-256.