Non tutti gli hash si scontrano dopo un numero sufficiente di iterazioni con un sale statico?

Quando si itera una funzione hash, si verifica la riduzione dello spazio, ma non fino a un singolo punto. Per una funzione scelta a caso (che si suppone che il tuo "amazing_hash" si avvicini), con un output n -bit, potresti aspettarti di raggiungere un ciclo di dimensioni 2 ^{n / 2} o così, cioè ancora abbastanza grande se si utilizza una dimensione di output decente (per esempio, n = 256 ).

Vedi questa risposta per ulteriori spiegazioni dettagliate. Riporto qui lo schema di quella risposta, perché è un bel colpo d'occhio:

Naturalmente , un "sale statico" non è un sale; significa solo che stai usando una funzione hash personalizzata. Il sale è pensato per dissuadere gli attacchi paralleli: quando l'aggressore tenta di decifrare 10 password, gli costa 10 volte il costo di crearne uno. Con un "sale statico", crackare 10 password non costa più di cracking 1, cioè un fallimento totale della salatura.

I sali non servono per evitare le collisioni, in particolare perché le collisioni non sono un problema per l'hashing delle password. È una resistenza di preimage di cui dovresti preoccuparti.

Non la penso così, solo perché l'hash avrebbe quasi certamente raggiunto "common_thing" in diversi punti. Una password potrebbe essere "common_thing" al passo 10.000 e un'altra al passo 100.000. Le catene si seguiranno l'un l'altra in parallelo, ma non si troveranno necessariamente nello stesso punto al termine dell'algoritmo.

Se i cicli sono grandi o piccoli, la probabilità è ancora bassa. Se ci sono molti piccoli cicli, è meno probabile che un valore finisca in uno qualsiasi di essi; se ci sono alcuni cicli di grandi dimensioni, è meno probabile che il valore finisca la catena nello stesso punto.

Come altre persone hanno detto, il motivo per cui non si usa un sale statico è impedire agli attaccanti di creare tavoli arcobaleno. Non sono sicuro che il sale statico abbia alcun effetto sul numero di collisioni nel tempo, a parte ovviamente che valori identici avranno lo stesso valore.

Prendi tutto questo con un pizzico di sale, però; Sono un criptico appassionato, ma non un esperto. Mi piacerebbe saperne di più sui cicli degli algoritmi hash se altre persone sono più informate in questo settore.

Il problema relativo al sale statico, non è che ci sono maggiori possibilità di collisione (non c'è). L'esecuzione ripetuta dello stesso algoritmo non determinerà un aumento delle collisioni (con una buona funzione di hashing) purché tutte le password abbiano lo stesso numero di iterazioni.

Il vero problema è un gioco di probabilità.

Se un utente malintenzionato conosce il codice utilizzato per generare la password hash (il meccanismo utilizzato per iniettare il sale e il numero di iterazioni tramite il ciclo hash), l'utente malintenzionato può riprodurre l'algoritmo. Supponiamo che l'hacker conosca anche il tuo reale risultato dell'hash. Possono elaborare la tua password attuale?

Con l'algoritmo, l'utente malintenzionato può quindi inserire nell'algoritmo un dizionario di password comuni e cercare corrispondenze con il risultato dell'hash. Certo, potrebbe volerci molto tempo, ma alla fine l'hacker potrebbe indovinare la tua password.

Il fatto è che potresti avere una password "difficile da indovinare" ... ma, per quanto riguarda tutti gli altri nel sistema. La tua password hash è solo una delle tante. Se il sito è 'stack exchange', allora ci sono migliaia di utenti. Se tutti usano lo stesso sale, quindi, un attacco del dizionario come questo può verificare la corrispondenza con tutte le password hash degli utenti. Se ottengono una corrispondenza, hanno anche indovinato la password dell'utente. È un gioco di numeri. Se ci sono 10.000 utenti in un sistema, allora le probabilità di trovare una password facile sono migliorate di 10.000, probabilmente molto di più.

Ora, se usi un salt unico per ogni utente, ottenere un hash di corrispondenza per un utente è inutile a meno che quell'utente non abbia lo stesso sale che hai nell'algoritmo.

In altre parole, con un unico sale, puoi attaccare un solo account utente alla volta. Con un sale statico, puoi attaccarli tutti contemporaneamente ... e le probabilità di un colpo sono molto più grandi.

In teoria, sì, ciò avverrà sicuramente, per le definizioni sufficienti di "un intero lotto" e "molti". In pratica no, non succederà mai. Il punto di una funzione hash crittografica sicura è che "un intero lotto" e "molti" sono numeri ridicolmente grandi che non possono essere raggiunti. Se riesci a raggiungerli, c'è un grave attacco all'algoritmo, e non dovresti usarlo, o non è abbastanza grande, e non dovresti usarlo.

Ad esempio, prendi MD5. Un hash è lungo 128 bit. Idealmente, in media dovresti trovare una collisione con 2 tentativi ⁶⁴ , o circa 18 quintilioni. Questo sarebbe molto costoso, ma è possibile farlo con abbastanza hardware. Tuttavia, MD5 ha sofferto in modo catastrofico dalla crittanalisi, e ci sono attacchi che possono trovare collisioni in pochi momenti.

D'altra parte, c'è SHA-256. È 256 bit - non è possibile calcolare 2 hash ¹²⁸ e non ci sono attacchi significativi contro di esso.

Quindi questo non è un problema se usi un hash decente come SHA-256 o SHA-512. Inoltre non dovrebbe essere una preoccupazione anche se non lo sei. Non riesco a pensare al motivo per cui un utente proverà a creare una password che causa intenzionalmente una collisione e non è pratico utilizzare un numero significativo di iterazioni, a meno che non si desideri eseguire decenni di calcolo per consentire agli utenti di accedere. Questo a parte le considerazioni menzionate nelle altre risposte).

Essentially, my question is: With a non-randomized-per-password salt, does the chance of a collision go up with every iteration added?

Sì, da "così vicino a zero non succederà mai" a "ancora così vicino allo zero che non accadrà mai".

Per quanto riguarda la teoria, ogni output della funzione amazing_hash ha una dimensione fissa, ed è mappato su un altro output della funzione hash, e un altro, e così via.

Quindi, lasciando da parte il primissimo input, hai una funzione da un insieme finito a se stesso. La funzione può o non può essere biettiva, ma non è una proprietà richiesta di una funzione di hash che è. Il dominio della funzione necessariamente è diviso in:

• uno o più cicli, più
• zero o più "code", cioè sequenze che portano in uno dei cicli o in un'altra coda. Quando due code si uniscono consideriamo arbitrario quale si sta portando nell'altra, ma userò il numero di code più tardi, quindi deve essere definito in questo modo :-) Definire anche la "fine" di una coda per essere il punto in cui unisce un'altra coda o un ciclo.

Ogni punto, quando è iterato, fa parte o meno di un ciclo, oppure segue una coda e le code che la coda unisce, finché non si unisce a un ciclo. Questa è una proprietà necessaria di una funzione da un insieme finito a se stesso. Un percorso non può funzionare per sempre senza entrare in un ciclo, perché ci sono solo un numero finito di valori e quindi alla fine deve ripeterne uno. È quindi possibile immaginare la funzione visivamente come un sacco di cerchi, con rami sporgenti dai lati di essi. I rami portano tutti nelle cerchie.

Con una singola iterazione (ovvero un ulteriore hash dopo l'hash iniziale), quante collisioni ci sono? Bene, è legato al numero di code, poiché la fine di una coda è un luogo in cui due valori non uguali hanno lo stesso hash. Ogni punto di unione implica che ci sia un numero di valori di collisione uguale al numero di strutture che si uniscono in quel punto. Ogni coda termina con un join, quindi se definiamo attentamente "code" e "collisioni", il numero di collisioni è solo il numero di code.

Dopo due iterazioni, quante collisioni ci sono? È il numero di code (dato che una volta che i due valori sono entrati in collisione rimangono in collisione), più il numero di nuove collisioni causate dall'iterazione extra. L'iterazione aggiuntiva provoca una collisione se "entrambi i lati" di un punto di unione sono lunghi almeno 2 nodi. Quindi, quando si uniscono due code, devono essere entrambi lunghi almeno 2 nodi e dove una coda si unisce a un ciclo deve essere almeno un 2 cicli.

Dopo n iterazioni, ulteriori collisioni vengono generate da code almeno n nodi lunghi e n cicli.

Nel caso estremo, una funzione di hash che è biiettiva non ha code. Questo è un teorema di funzioni finite: ogni permutazione divide il suo dominio in cicli. Quindi dovrebbe essere facile vedere che non importa quante iterazioni fai, ci sono collisioni no (diverse da quelle causate dall'hash iniziale, ovviamente). Ogni punto si muove attorno al suo ciclo. Spostando ogni punto un numero uguale di passaggi attorno a un ciclo, sono ancora tutti in posizioni diverse.

Altrimenti, per iniziare con più iterazioni che fai, più collisioni vengono generate quando le code si uniscono nei cicli. Tuttavia, c'è un limite superiore a questo processo, perché ogni coda e ogni ciclo ha una lunghezza finita. Alla fine non causerai più collisioni quando fai più iterazioni. Ciò non accadrà finché non avrai raggiunto la lunghezza della coda più lunga nella tua funzione.

Questo è tutto in teoria: in pratica la coda più lunga potrebbe essere ancora più grande di quanto tu abbia tempo per iterare. Se è così, continuerai ad aumentare il numero di collisioni per tutto il tempo che puoi praticamente eseguire.

Tuttavia , il numero di collisioni introdotte da ciascuna iterazione è ancora molto piccolo rispetto allo spazio hash, così piccolo che è incredibilmente improbabile che si verifichi una collisione in questo modo. Come facciamo a saperlo? Perché se non lo fosse, allora l'algoritmo di ricerca del ciclo di Floyd sarebbe un mezzo efficace per trovare le collisioni nella funzione di hash. La funzione di hash non sarebbe "sorprendente" secondo le ipotesi della domanda, sarebbe risaputo essere infranta: -)

Would, in theory, many passwords collide?

Nel tuo esempio, ciò che stai guardando è quanto è facile per due input ottenere lo stesso output, noto come collisioni . Questa è un'area importante in crittografia, viene utilizzata per valutare la forza degli algoritmi e varia per ogni algoritmo.

Il numero di iterazioni non ha importanza, anche nel tuo esempio, perché tutto ciò che è interessante è il seguente:

hash(n,mznxc,mnzxc)     > common_thing 
hash(ioasjdknckauyieuh) > common_thing 

Dato che stai prendendo l'output di un hash e poi lo spingo indietro come input, l'input e l'output hanno la stessa dimensione (eccetto per il primo input).

Algoritmi, come MD5 , è noto che sono stati mostrati alcuni vulnerabilità di collisione . Anche le collisioni MD5 sono state sfruttate nei Flame virus , anche se MD5 è stato inventato come sostituto sicuro di MD4 . E così, la crittografia si basa sulla revisione e la ricerca di un gran numero di crittografi per capire quali algoritmi non hanno ancora mostrato alcun punto debole.

Quindi, in qualsiasi momento, è necessario considerare quali funzioni hash non hanno vulnerabilità note e progettare il sistema in modo tale che in futuro sia possibile eseguire il rollover della funzione hash (cioè essere criptato-agile).

With a non-randomized-per-password salt, does the chance of a collision go up with every iteration added?

I sali non randomizzati non risolvono questo problema. Risolvono il problema delle tabelle rainbow e delle collisioni con password (cioè se due utenti hanno lo stesso sale, la stessa password e lo stesso numero di iterazioni, ottieni lo stesso hash.) Dal punto di vista del design, devi presupporre che il sale e il numero di iterazioni siano pubblicamente noti (anche se riesci a nasconderli).

Dato che molti utenti condividono le stesse password ("123456", "password", "abcdefgh", ecc.), con sali e iterazioni non randomizzati, la previsione delle password diventa molto più semplice utilizzando analisi di frequenza a causa degli stessi hash risultanti dalle stesse password.

Quindi, in parole semplici: quali sono le probabilità dell'ingresso A e dell'input B di hashing sulla stessa cosa dopo N iterazioni? (Il sale non cambia nulla al riguardo.) Poiché H (A) e H (B) dovrebbero essere distribuiti uniformemente in modo casuale per una buona funzione di hash, questo è all'incirca lo stesso delle probabilità di H (A) e H (B ) non scontrandosi moltiplicato per le probabilità che H (A) e H (B) non collidano dopo N - 1 round. Per SHA-256 con 2 ²⁵⁶ possibili output (idealmente), cioè 1 - ((2 ²⁵⁶ - 1) / 2 ²⁵⁶ ) ^N &; 2.59 × 10 ^-59 per 3 quintilioni di iterazioni.

Non è molto probabile.

Puoi anche stimare la probabilità di entrare nel ciclo che altre risposte hanno menzionato con l'approssimazione del problema del compleanno, sebbene, come altre risposte hanno anche detto, che non causerà una collisione a meno che i due input non siano sincronizzati in questo ciclo .

Di nuovo per le iterazioni SHA-256 e 3 × 10 ¹⁸ , cioè 1 - e ^{- (3 × 10 18 ) 2 / (2 × 2 256 )} e circa; 3.89 × 10 ^-41 .

Inoltre, non molto probabile.

Non ci sono.

Si tratta di entropia.

Dato una funzione di hash crittografica "non-broken", produce N bit di output pseudocasuale per qualsiasi input di lunghezza M , che non è altro che estraendo N bit di entropia da quelli M bit. ¹ Ovviamente questo funziona solo in modo ragionevole se M >= N , dal momento che puoi difficilmente estrarre N bit di entropia se l'input non contiene più di tanto.

La probabilità di collisioni è descritta dal famoso paradosso del compleanno (che per ironia della sorte non funziona affatto con i compleanni attuali , poiché questi sono distribuiti in modo molto disuguale!).
La probabilità che gli utenti di che scelgono password identiche sia molto, molto più alta di così. In altre parole, l'entropia contenuta in una password utente (anche se relativamente buona) è abissale.

Il sale aggiunge entropia all'input. Il che significa che la prima iterazione con una statica (presumo che "statico" significhi ancora "per utente"!) Riduce effettivamente la probabilità di una collisione rispetto alla password semplice.

Ora cosa succede nella seconda, terza e con iterazione? La funzione di hash prende come input l'output del round precedente, che contiene N bit di entropia (che include già l'entropia nel sale statico, quindi l'aggiunta di sale lo lascia ancora a N ) e produce% outputN bit di entropia.
La CPU gira, i bit girano, i numeri appaiono diversi, ma nulla cambia per quanto riguarda l'entropia o la probabilità di collisione. N bit in, N bit out.

Quindi no, non peggiora (ma anche, non migliora).