Attacchi di compromissione della memoria temporale

" Scambio di memoria tempo " è la terminologia generica per un algoritmo che migliora (abbrevia) il tempo di esecuzione usando più spazio (memoria); o, analogamente, che migliora l'utilizzo della memoria (cioè utilizzando meno RAM o disco, o usandolo "meglio", ad esempio con accesso sequenziale invece di accesso casuale) a spese di più tempo di calcolo.

In caso di hashing della password , l'algoritmo TMTO principale è dovuto a Hellman nel lontano 1980; un certo numero di miglioramenti locali sono stati successivamente scoperti, dando luogo a ciò che è colloquialmente noto come tavole arcobaleno . Possiamo ottenere una visione concettuale delle tabelle arcobaleno considerando i due endpoint dello spettro:

• Ricerca esauriente riguarda il provare tutte le potenziali password, eseguirne l'hashing e confrontare il valore con quello da decifrare. Questo ha il più alto costo computazionale (hash N / 2 medi per calcolare N password potenziali con probabilità uniforme) ma utilizza solo RAM trascurabile.

• Una tabella precomputa contiene gli hash delle password potenziali N e deve essere eseguita una singola ricerca. Non contiamo lo sforzo di costruire la tabella perché può presumibilmente essere riutilizzato per attacchi multipli, probabilmente da più aggressori. La dimensione della tabella è proporzionale a N , ma lo sforzo computazionale è trascurabile (beh, su O ( log N) , che è piccolo ).

Le tabelle arcobaleno si adatteranno in mezzo. Quando la tabella è costruita, scegli un parametro t chiamato "lunghezza media della catena". La dimensione della tabella sarà proporzionale a N / t : viene ridotta di un fattore t , rispetto alla tabella precalcata. D'altra parte, ogni attacco implicherà uno sforzo computazionale proporzionale ai calcoli di hash t ² e t . A seconda delle condizioni operative, la ricerca o i calcoli costituiranno il collo di bottiglia (ad esempio dipende molto dal fatto che la tabella si trovi nella RAM, su un SSD o su un set di dischi rigidi meccanici).

I Sali completamente neutralizzano le tabelle precalcolate, comprese le tabelle arcobaleno . La creazione di una tabella precalcata per le password N è costata N ; la creazione di una tabella arcobaleno per le stesse password N ha costi ancora più elevati (su 1,7 * N ). Ciò vale lo sforzo solo se la tabella può essere utilizzata almeno due volte, per attaccare due distinti valori hash; una tabella one-shot (arcobaleno o meno) non è competitiva con una ricerca esaustiva. Ma il punto sali è che non esiste una funzione one ; infatti, esiste una grande famiglia di funzioni e il valore di sale indica quale viene effettivamente utilizzato. Una tabella creata per un sale specifico non ha assolutamente alcun valore nel rompere un valore hash per qualsiasi altro sale.

Bcrypt utilizza i sali, quindi nessuna tabella e nessun TMTO. Gli aggressori sono tornati alla ricerca esaustiva. Bcrypt ha anche armi contro ricerche esaurienti, vale a dire una lentezza configurabile, ottenuta attraverso un numero enorme di iterazioni interne: dal punto di vista dell'utente, non c'è molta differenza tra un calcolo hash che richiede 1 microsecondo e uno che richiede 100 millisecondi ; ma per l'attaccante, quest'ultimo significa 100000 volte lo sforzo per la sua ricerca esauriente.

Vedi questa risposta per ulteriori informazioni sull'hash della password sicura . Breve riassunto: se la tua password è strong (cioè ha un'alta entropia), allora anche le agenzie più potenti non saranno in grado di ottenerlo rompendo l'hash bcrypt in anticipo (lo otterranno rompendo le tue rotazioni, ma questa è un'altra storia).

Bcrypt utilizza un "fattore lavoro"; fattori di lavoro più elevati portano a una maggiore elaborazione richiesta per un determinato spazio delle chiavi.

Per quanto riguarda la stima del "tempo", quali risorse si prevede che l'attaccante abbia? Se la stima si basa su N risorse e l'utente malintenzionato genera 1000N di risorse, l'utente malintenzionato può esaurire lo spazio delle chiavi o eseguire l'attacco del dizionario basato su regole in 1/1000 del tempo.

Per quanto riguarda i compromessi tempo / memoria effettivi, se si dispone di un lungo salt random, non esiste un modo ragionevole per generare elenchi precompilati per ogni possibile valore di salt, quindi è tutto il lavoro di runtime. Gli elenchi WPA possono essere generati perché il sale è l'SSID, che è raramente casuale.

Nota anche che se la tua password non è veramente casuale, allora gli attacchi del dizionario basati su regole sono il peggiore pericolo, non pura forza bruta o persino catene di Markov.

Inoltre, questa stima della forza tiene conto della Legge di Moore (o qualche altro fattore di aumento esponenziale)? Tutte le stime della "durata del sole" non riescono a spiegare che gli hacker acquistano nuovo hardware dopo che è migliorato.

Bcrypt accetta due parametri: una password e un fattore di lavoro. Il fattore lavoro indica quanto tempo impiegare per risolvere il problema.

Diversi fattori di lavoro danno risultati diversi, quindi il fattore lavoro agisce come una sorta di sale secondario. Normalmente non la si pensa in questo modo, ma fa parte del motivo per cui raramente si vede bcrypt nei database hash. Per abbinare l'hash, hai bisogno sia della password che del fattore di lavoro corretto. Quindi il tuo database ha bisogno di un set separato di hash di bcrypt per ogni potenziale fattore di lavoro.

Per quanto riguarda il fatto che la NSA sarà mai in grado di decifrare gli hash di bcrypt di 10 caratteri, si trova sul lato più lontano della probabilità, ma non del tutto alla fine della possibilità. Salta fino a 14 caratteri e praticamente ce l'hai.