Se non viene inserita una lunghezza massima su una password, non si possono verificare collisioni?

Per i principianti, le funzioni di hash dovrebbero essere fondamentalmente casuali, quindi la lunghezza della stringa di input non ha importanza. La probabilità che due hash casuali di stringhe di 3 caratteri sulla stessa cosa sia uguale alla probabilità che due hash casuali di stringhe di 100 caratteri siano uguali.

Per le moderne funzioni di hash ( SHA1 , SHA2 , non MD5 ) la loro struttura è sufficientemente complessa dal punto di vista matematico che non possiamo dire molto algebricamente. Inoltre, lo spazio delle possibili stringhe di input, anche di lunghezza 32, è così grande che non possiamo verificarle sperimentalmente tutte. Quindi, in realtà non sappiamo quante collisioni ci sono nelle prime 2 stringhe ¹²⁸ (stringhe la cui rappresentazione binaria è 1 , 10 , 11 ... 2 ¹²⁸ ). In teoria ce ne dovrebbero essere alcuni, ma per quanto ne so, non ne abbiamo ancora scoperti per SHA1 o SHA2 . Quindi la tua intuizione che limitare la lunghezza delle stringhe di input a meno di 2 ¹²⁸ bit eliminerà il rischio di collisioni non del tutto corretto.

In ogni caso, supponiamo che ci siano coppie di password nelle prime 2 stringhe ¹²⁸ che hanno lo stesso hash, la probabilità che tu ne colpisca una nel tuo database è approssimativamente <number of entries in db> / 2 ¹²⁸ .

La ragione per cui

the "impact of hash collisions is non existent"?

è che 1/2 ¹²⁸ è un numero così inimmaginabile che anche se hai scritto un programma per generare password casuali fino a quando il sole ha esaurito l'energia, non ti aspetteresti di vedere un singola collisione per caso. (Se qualcuno sta attivamente cercando di fare un attacco di collisione, allora questa è una storia diversa).

Considera anche in che modo il rischio di collisione (~ 1/2 ¹²⁸ ) è paragonabile al rischio di un attacco dizionario standard. In base alla perdita di password Adobe 2013 , 1 su 68 account su Internet utilizza la password 123456 . 1/68 è un numero MOLTO più grande di 1/2 ¹²⁸ , quindi il fatto che una singola ipotesi di 123456 abbia una probabilità di 1/68 di avere ragione è una MOLTA cosa più importante di cui preoccuparsi di collisioni teoricamente possibili. Soluzione: consenti (o imponi ) le password non di dizionario lunghe, usa un salt unico per ogni hash della password e non preoccuparti delle collisioni.

Qui c'è poco da preoccuparsi, ma parliamo di questo:

Granted no collisions exist until the pingeonhole principle is satisfied

Questo non è il caso. Gli algoritmi di hashing standard sono deterministici (altrimenti non funzionerebbero.) Le password che si scontreranno (e ci sarà un numero infinito senza limite di lunghezza della password). Le collisioni non sono correlate alle dimensioni del tuo database. Ad esempio, considera il mio nuovo algoritmo di hash intero mod100. L'implementazione è che mod un intero di 100 e il resto risultante è il tuo hash. Se ho cancellato i numeri 101, 201 e 301 ho il 100% di collisione anche se il mio set è solo il 3% dello spazio hash.

Quindi c'è una possibilità astronomicamente piccola che qualcuno possa indovinare su una delle altre password che ha lo stesso hash di una vera e propria password reale. Se l'algoritmo di hashing è buono, è più probabile, tuttavia, che indovinerà la password effettiva. Non perdere il sonno su di esso.