Qual è il limite pratico per la bruteforce basata su rainbow-table?

Diciamo che hanno scelto in modo alfanumerico (A-Za-z0-9 senza simboli) sia per il sale che per la password; ad esempio, lo spazio campione è (62) ^ M possibili sali e (62) ^ N password.

Supponiamo di avere un milione di GPU in una farm a loro disposizione in grado di generare un miliardo di hash al secondo (supponendo un semplice hash di tipo MD5 o SHA - gli hash basati su bcrypt o PBKDF sono molto più lenti). Quindi, per un dato sale, possono crackare una password di 8 caratteri in 0,2 secondi (200.000 GPU-secondi), una password di 10 caratteri in 14 minuti (26 GPU-anni), una password di 12 caratteri in 37 giorni (100.000 GPU -anni), una password di 16 caratteri in 1.5 milioni di anni (1.5 trilioni di anni GPU).

O un altro modo di pensarci; una tipica GPU per estrarre un miliardo di hash al secondo utilizza ~ 200 W. Quindi se l'elettricità costa $ 0,10 per kWHr e trascurando i costi di avvio, una GPU-ora costa $ 0,02. Quindi una password di 8 caratteri costa ~ $ 1, 10 caratteri $ 4600, 12 caratteri $ 18 milioni, caratteri 16 - $ 260 trilioni (l'offerta di moneta mondiale è dell'ordine di $ 10 trilioni). (E questo trascura il costo di acquisto / mantenimento di un milione di GPU - solo elettricità)

Come per un tavolo arcobaleno - a un certo punto deve essere costruito. Quindi vuoi una tabella arcobaleno completa per tutti i prefissi di 4 caratteri; e vogliono coprire tutte le password fino a 8 caratteri (ad esempio, un totale di 12 caratteri password) impiega 100.000 GPU (37 giorni su un milione di GPU) e costa circa $ 18 milioni in bolletta elettrica.

Fondamentalmente quando M + N > ~ 12 per alfanumerici casuali inizia a diventare non fattibile (ad esempio, non è fattibile a M + N = 16).

EDIT: Nuova tabella di riepilogo, dove elenco lunghezza e tipo di password (ad esempio, 8 A-Za-z0-9 significa 8 caratteri maiuscoli + minuscoli + password numerica).
È inoltre inclusa una password specifica per l'applicazione google ( 16 lettere minuscole casuali) anche se ovviamente la password di tipo google in genere dovrebbe essere attaccata online (non come un hash offline attaccato da una farm GPU).

  PW Length  | # of PW | PW Entropy |       GPU-time | Electricity Cost at $0.10/kW-hr
-------------------------------------------------------------------------------------------
 8 A-Za-z0-9 | 2x10^14 | 47.6 bits  |       60 hours |                  $1
10 A-Za-z0-9 | 8x10^17 | 59.5 bits  |       26 years |              $4 600
12 A-Za-z0-9 | 3x10^21 | 71.4 bits  |   100 000 years|         $18 000 000 ($18 million)
14 A-Za-z0-9 | 1x10^25 | 83.4 bits  | 390 million yrs|     $69 000 000 000 ($69 billion)
16 A-Za-z0-9 | 5x10^28 | 95.2 bits  |1500 billion yrs|$260 000 000 000 000 ($260 trillion)
-------------------------------------------------------------------------------------------
16 a-z       | 4x10^22 | 75.2 bits  | 1.4 million yrs|        $242 000 000 ($242 million)

Mi scuso in anticipo perché questa risposta non sarà una risposta diretta alla tua domanda, ma ho voluto postarla in modo che le persone sappiano che la domanda che stai ponendo è davvero solo accademica. La vera risposta a questa domanda è: non usare sha1, usa bcrypt . Gli sha1 e md5 del mondo sono stati progettati per essere veloci e veloci non è una buona qualità per le password di hashing. Bcrypt è progettato per consentire la configurazione della quantità di tempo necessaria per eseguire l'hash di una password, in modo da poter rallentare il processo di hashing in modo tale che gli utenti non notino la differenza, ma per gli hacker saranno necessari più ordini di grandezza genera una tabella arcobaleno o forza bruta una password. Per ulteriori informazioni su bcrypt e sul motivo per cui dovresti utilizzarlo, consulta questa domanda .

Oltre a tutto questo, bcrypt include anche uno schema di salatura. Per le ragioni sopra menzionate, puoi essere abbastanza sicuro che i sali da 20 byte menzionati da woliveirajr saranno validi anche in futuro.

Ci sono tavoli arcobaleno e c'è forza bruta ... sono due cose distinte.

Una tabella arcobaleno è un caso speciale di una grande tabella precomputed di password con hash. In quanto tale, una tabella arcobaleno può "invertire" un hash, cioè recuperare una password corrispondente, solo se, ad un certo punto durante la costruzione della tabella, tale password è stata considerata ed hash. Corrispondentemente, se una password può essere trovata con una tabella arcobaleno, allora potrebbe essere stata trovata con un semplice attacco dizionario che non sono costati più della costruzione della tabella. L'arcobaleno non cambia questo; infatti, la cosa arcobaleno rende effettivamente la tabella più costosa da costruire, di un fattore circa 1,7 (perché la costruzione della tabella tende a considerare e hash più volte le stesse password, e ciò è piuttosto inevitabile).

Una conseguenza è che nessuna tabella arcobaleno vale lo sforzo a meno che non possa essere applicata almeno due volte . Usiamo sali proprio per evitare che ciò accada. Il sale può essere visto come una variante della funzione hash, ogni nuovo sale implica una nuova variante. Una tabella precalcolata vale qualcosa solo se è stata precalcata con la stessa variante (lo stesso sale) del valore di hash che deve essere attaccato. Se non viene usato alcun valore di sale più di una volta, l'attaccante intelligente non sprecherà il suo tempo a costruire tavoli arcobaleno Kleenex; lui semplicemente scapperà un attacco di dizionario.

Consideriamo che l'attaccante conosce il sale. Perché ? Perché il server lo sa e il modello di attacco è che l'utente malintenzionato potrebbe ottenere un dump del database del server. Qualunque cosa sappia il server, anche l'hacker sa. Pertanto, quando si attacca una password con hash, la lunghezza del sale o il contenuto non contano (l'attaccante deve includere il valore di sale nei suoi calcoli, ma nessuna lunghezza di sale renderà il suo compito più facile o più difficile).

Quindi, abbiamo solo la password come linea di difesa. Se vogliamo sapere quanto costa l'attacco, allora questo diventa economia e, come tale, sorge una certa complessità. In particolare, vogliamo sapere se stiamo parlando di un utente malintenzionato che sta cercando one una password molto preziosa (ad esempio, la password che protegge il computer principale della forza aliena che sta per obliterare la Terra), o un aggressore che si guadagna da vivere rompendo le molte password. In quest'ultimo caso, i costi dell'hardware diventano trascurabili per quanto riguarda il consumo di energia.

Se prendiamo le stime di @jimbob, l'hardware che calcola 10 ⁹ hash al secondo utilizza 200W di potenza e la potenza arriva a $ 0,1 per kWh (nota che il costo dell'energia include il raffreddamento: ogni Watt speso per il calcolo diventa anche calore, che deve essere in qualche modo dissipato). Questo ci dà valori di hash di 1,8 * 10 ¹⁴ per dollaro. Da ciò otteniamo quanto segue:

• Con $ 10K, un utente malintenzionato può provare i valori hash 1.8 * 10 ¹⁸ , che è più o meno il numero di possibili password di 10 caratteri alfanumerici (maiuscolo, minuscolo e cifre).

• Con 683,7 miliardi di dollari (ovvero il budget militare totale degli Stati Uniti nel 2010 ), un utente malintenzionato potrebbe provare circa 1.23 * 10 ²⁶ valori di hash, corrispondenti a circa 14,5 caratteri alfanumerici. Permettetemi di aggiungere che questa cifra corrisponde alla produzione annua di circa un centinaio di centrali nucleari, quindi lo sforzo di cracking difficilmente potrebbe essere poco appariscente.

Conclusione: con 15 caratteri alfanumerici casuali, le tue password resisteranno anche a nemici non plausibili, anche se hai completamente distrutto l'hashing utilizzando una singola invocazione di SHA-1, invece di usare bcrypt o PBKDF2 con un alto conteggio iterazione, come si dovrebbe fare . Nota che questo è valido solo per i caratteri casuali , non del tutto per il tipo di personaggi che potresti trovare nella privacy del tuo cervello. I cervelli umani non sono affatto bravi a caso.

Le tabelle arcobaleno rappresentano un compromesso tra tempo di CPU e archiviazione, quindi in teoria la risposta a questa domanda è inconoscibile. Dipende da quale lato del trade-off il tuo aggressore preferisce: se hanno un sacco di tempo CPU disponibile, dopo aver incontrato un nuovo valore di sale, l'attaccante può iniziare a calcolare un nuovo tavolo, quindi è effettivamente inutile (questo estremo equivale a l'attaccante può forzare una chiave senza usare le tabelle precalcolate). Se hanno un sacco di spazio di archiviazione, possono precompilare le tabelle per qualsiasi valore del sale, ma impiegheranno molto tempo, tanto più grande è, meglio è.

Naturalmente, le cose che non funzionano in teoria spesso funzionano molto bene nella pratica. Il mondo reale si inietta a questo punto e ci dice che per molti attaccanti, sia la memoria che il tempo di CPU sono limitati. Più lungo è il sale, più aggressori non hanno le risorse per montare un attacco riuscito. Accettando questa relazione, c'è una disuguaglianza che fornisce un limite superiore alla tua scelta della dimensione del sale:

Le risorse totali da parte tua necessarie per lavorare con gli hash salati devono essere inferiori alle risorse richieste per soddisfare gli altri requisiti della tua applicazione.

Questa è la mia comprensione, mi scuso se ciò non è corretto in ogni caso.

L'uso di un sale con password rende le tabelle arcobaleno quasi inutili per gli attacchi nella maggior parte dei casi. Con la lunghezza della password P e una lunghezza salt di S avresti bisogno dello spazio P * S con ingenue forze di ricerca brute (aggiungendo un salt casuale devi creare S tabelle per ogni password). Le tabelle Rainbow riducono lo spazio richiesto per archiviare le ricerche per la password ma non eliminano la moltiplicazione di S (il mio Uni Math non è abbastanza buono da darti il Notazione Big O , che può essere un esercizio per il lettore: P).

Il calcolo può quindi essere considerato come la lunghezza del set di caratteri accettato ( c ) elevato alla potenza della lunghezza della password ( p ) moltiplicato per il numero di possibili sali ( s ).

(c^p) * s

Inutile dire che questo può diventare un numero molto grande molto rapidamente.

Scenario 1

Un governo potrebbe costruire un sistema sufficientemente grande da infrangere una password + schema di sale usando le tabelle arcobaleno? Questo dipende dalla dimensione delle password, dal set di caratteri disponibile e dalla dimensione del sale. Al di sopra di una certa dimensione inizi a colpire i limiti fisici (puoi effettivamente codificare tutte le permutazioni su un dispositivo usando la materia / energia a portata di mano?). I governi hanno spesso maggiori risorse rispetto alla maggior parte delle istituzioni, ma nemmeno loro possono esaurire questi limiti fisici.

L'unico modo per aggirare questo sarebbe cercare di usare intuizione o conoscenza precedente per ridurre lo spazio di ricerca. Per un sistema comunemente utilizzato, le password delle persone saranno al di sotto di una certa lunghezza, quindi limitatevi a controllarle. Probabilmente useranno anche solo un sottoinsieme del set di caratteri disponibile. Puoi usarli per concentrare gli hash utilizzati per popolare la tua tabella arcobaleno ( p e c ). Ma sarai sempre contrariato dal fatto che tu moltiplichi per il sale casuale ( s ).

Hai un casuale sale vero ?! Questo è dove le persone iniziano a preoccuparsi per l'entropia dei numeri casuali. È piuttosto difficile da sfruttare quando vengono utilizzati dati non casuali in cui sono necessari dati casuali reali, ma questa è una di quelle situazioni in cui entra in gioco. Considera il problema precedente in cui sei riuscito a ridurre (p ^ c) facendo intuizioni sulla natura della password. Se sappiamo qualcosa su come "random" i sali sono (o possono influenzarli in qualche modo) possiamo iniziare a ridurre le dimensioni di s . Potremmo sapere (o poter influenzare) il s tra un certo insieme di valori e quindi ridurre drasticamente le permutazioni sulle tabelle arcobaleno. Se un attaccante può ottenere questo sotto limiti fisici ragionevoli, allora un governo (che era così incline) potrebbe usare le tabelle arcobaleno per violare le password.

(spero che questo abbia risposto anche alla tua domanda correlata)

Scenario 2

Ai livelli attuali del 2012 direi che, a meno che tu non sia stato incredibilmente fortunato, la probabilità che tu sia in grado di crackare password + hash salt (ignorando le debolezze tecniche nella tua implementazione) è incredibilmente sottile. Questo presuppone che tu usi lunghezze ragionevoli per p , c e s .

Vedi link e link per una lettura interessante su questo argomento (che quasi sicuramente ho usato e abusato in modo errato).