Prendiamo ad esempio MD5:
Emette un hash a 128 bit. Ha senso (in teoria) scegliere un input (password) che è esso stesso più lungo di 128 bit?
Aumenta in qualche modo la probabilità di una collisione?
So che MD5 è rotto, quindi che dire di algoritmi più moderni come bcrypt o scrypt?
Se consideri un insieme di potenziali password di dimensioni P , con una funzione hash con N possibili valori di output, allora la probabilità che esista em> almeno una collisione in questo set è piuttosto bassa quando P è inferiore alla radice quadrata di N , e piuttosto in alto. Vedi il problema di compleanno . Come dice la pagina di Wikipedia, quella probabilità è approssimativamente uguale a 1-e -P 2 / 2 · N .
Con figure: se usi password composte da 10 caratteri (lettere maiuscole, lettere minuscole e cifre), allora P = 62 10 = 839299365868340224 ; con una funzione hash a 128 bit, N = 2 128 . La formula sopra indica che può esistere almeno una coppia in collisione tra tutte queste password con probabilità prossima allo 0,1%. D'altra parte, se aggiungi un carattere alle tue password (vale a dire che le potenziali password hanno lunghezza 11, non 10), allora la probabilità che esista almeno una collisione sale al 98,1%.
Ora tutto ciò riguarda la probabilità di esistenza di una collisione; non probabilità di colpire una collisione.
Le collisioni non sono rilevanti per l'hashing della password . L'hashing della password funziona su preimage resistance : dato l'hash, quanto difficile o facile è indovinare una password corrispondente. Nota che ho detto "a", non "il": per l'attaccante, non importa se trova la stessa password che l'utente ha scelto; vuole solo una password che dia accesso, e qualsiasi password che corrisponda all'output dell'hash farà il trucco.
Si noti che mentre MD5 è "rotto" per le collisioni, non è così per le pre-immagini (beh, per le pre-immagini è "leggermente ammaccato", ma non significativamente ai fini di questa domanda).
Ci sono due modi per rompere la resistenza di pre-immagine:
Indovina la password. Ciò significa provare tutte le potenziali password finché non viene trovato / corretto. Se ci sono P password possibili con probabilità uniforme, allora questo è costato al massimo P / 2 perché l'utente ha scelto una delle password, e l'attaccante dovrà, in media, provarne la metà prima di colpire quella password esatta.
Sii fortunato. Prova le password (casuali, consecutive ... non importa) finché non viene trovato un valore di hash corrispondente. Questo ha un costo medio N / 2 .
La forza di hashing della password non sarà superiore a inferiore dei due. In questo senso , utilizzando un set di password possibili che è maggiore dell'output della funzione hash (ad esempio P > 2 128 per un Funzione hash a 128 bit) non offre ulteriore sicurezza, perché oltre quel punto, l'attacco "get lucky" diventa un affare migliore per l'attaccante rispetto all'attacco "guess the password", e l'attacco "get lucky" non dipende da come l'utente sceglie effettivamente la sua password. Si prega di notare che dico "dimensione del set di password" e NON "lunghezza della password". Tutte le analisi sopra riportate si basano su quanti valori di password potrebbero essere stati scelti, con probabilità uniforme. Se si utilizzano solo password di 200 lettere, ma è possibile selezionarne solo dieci migliaia (ad es. Perché ogni "password" è una frase del tuo libro preferito e l'hacker conosce quel libro), quindi la dimensione del set di potenziali password è 10000, non 62 200 .
In pratica , P è limitato dal cervello dell'utente (l'utente deve ricordare la password) ed è invariabilmente inferiore a N . Una password "molto strong" è una password da un processo di selezione che utilizza un P di 2 80 o più; questo è sufficiente per la sicurezza, e tuttavia molto al di sotto del 2 128 di MD5 o del 2 192 di bcrypt. Ma sembra poco realistico aspettarsi che gli utenti medi scelgano mediamente password molto forti. Invece, dobbiamo far fronte a password deboli, con P circa 2 30 o giù di lì (nel senso: prova un miliardo di password possibili e avrai infranto le password di metà tuo utenti). Le misure di mitigazione sono quindi hashing lento (rendere ogni ipotesi costosa) e sali (non consentire all'aggressore di attaccare parallelamente più password a costi ridotti). Vedi questa risposta .
L'hashing riduce uno spazio infinito, cioè i possibili input di dati, in uno spazio finito, ovvero possibili hash. Pertanto ci saranno sempre collisioni.
Tecnicamente, se limiti l'input impostato a una dimensione inferiore a 2 h , dove h è la dimensione dell'output hash in bit, allora diminuisci la tua possibilità di collisione. Infatti, poiché len (m) tende a h , la probabilità di una collisione quando si esegue un hashing esaustivo di tutti i valori nell'insieme M tende a 1 .
Detto questo, dato un valore abbastanza grande di h , l'hashing esaustivo di tutti M è altamente poco pratico - per SHA256 devi eseguire 2 255 prima di colpire il 50% di possibilità di collisione con un valore preselezionato.
La cosa importante da ricordare è che, per una stringa più lunga di h , la tua sicurezza non è mai inferiore a un messaggio h , assumendo che non ci siano vulnerabilità specifiche nell'hash che causa la minore sicurezza dei messaggi multi-blocco.
Quindi, per essere sinceri: sì, un messaggio più breve della lunghezza dell'output hash, statisticamente, ha una minore probabilità di collisione, ma il numero di operazioni necessarie per trovare la collisione si ridimensiona con la lunghezza.
Sì, ha assolutamente senso scegliere password più lunghe della dimensione dell'hash di output. Perché?
Ciò che ti dice è che l'entropia di una tipica n -byte password è molto, molto inferiore all'entropia che può essere codificata in un n -byte tag della password. In termini più semplici, le password in chiaro sono molto prevedibili e quindi un database reale di password in chiaro n -byte può essere facilmente compresso a meno di n byte per password. Quindi, in un certo senso, le password n -byte non utilizzano tutta la capacità fornita dall'hash n -byte.