PBKDF2-HMAC Collisioni

Question

Cercando di capire la proprietà ben nota di queste collisioni quando usate con SHA1, SHA256, ecc. Dove una data chiave è maggiore della dimensione del blocco della funzione digest. In questi casi la più piccola delle collisioni avrà una dimensione di 20 caratteri per SHA1 e 32 per SHA256 (metà della lunghezza del digest esadecimale), quindi questo significa che per forzare un PBKDF2-HMAC-SHA1 un attaccante deve solo prendere in considerazione passphrase di 20 caratteri o meno? E quindi 32 o meno se si utilizza SHA256? Le passphrase più lunghe sono effettivamente inutili? Grazie.

Answer 1

"forza bruta a PBKDF2-HMAC-SHA1" non riguarda le collisioni (almeno, se viene preso di mira un singolo hash o se c'è del sale all'ingresso dell'hash della password). È un attacco preimmagine .

L'output hash di SHA-1 è di 160 bit. Sono 20 byte (non caratteri; queste sono nozioni diverse e perché abbiamo codifiche dei caratteri ). Può volerci$2^{160}$valori. L'output di PBKDF2-HMAC-SHA-1 ha una dimensione parametrizzabile che può essere minore (per troncamento) o maggiore (essenzialmente aggregando risultati di 20 byte), ma il parametro è spesso impostato su 20 byte e supponiamo che .

Questo significa che per forzare un PBKDF2-HMAC-SHA-1 un utente malintenzionato deve considerare solo passphrase di 20 caratteri o meno?

No . Implica che un valore casuale della dimensione dell'hash abbia probabilità$2^{-160}$per abbinare un dato hash. La conseguenza pratica è che provare a caso è senza speranza.

Le password sono spesso limitate a un sottoinsieme di ASCII con circa 95 caratteri, quindi ci sono circa $2^{131.714}$password di 20 caratteri o meno (la maggior parte esattamente di 20 caratteri). Se PBKDF2 è parametrizzato per eseguire 1000 hash SHA-1 per PBKDF2 (che è la parametrizzazione più bassa mai considerata dalla sua definizione ed è diventata grossolanamente insufficiente), l'hashing di metà di queste password richiederebbe più di$2^{140}$ hash, questo è finito $2^{40}$(un milione di milioni) volte più di quanto sprecato finora dall'umanità per l'estrazione di bitcoin. Non è solo un'opzione.

La ricerca con password in genere non prova tutte le password possibili su più di pochi caratteri; comunemente ≈6 su ≈70 caratteri (solo gli attaccanti molto potenti possono prendere di mira tutte le combinazioni di 10 caratteri quando c'è anche un leggero allungamento di password / chiavi ). Quello che fa la ricerca delle password è provare le password che le persone potrebbero plausibilmente scegliere, approssimativamente in diminuzione della probabilità di essere scelte.