it-swarm-eu.dev

Cosa sono i tavoli Rainbow e come vengono utilizzati?

Dove posso trovarne uno? C'è una pentola d'oro alla fine?
Come posso proteggerli?


Dalla proposta Area51

Questa domanda era Domanda sulla sicurezza IT della settimana.
Leggi il 09 settembre 2011 post di blog per maggiori dettagli o invia il tuo Domanda della settimana.

149
AviD

Le tabelle arcobaleno sono comunemente confuse con un'altra tecnica più semplice che sfrutta un compromesso di archiviazione dei tempi di calcolo nel recupero della password: tabelle hash.

Le tabelle hash sono costruite con l'hash di ogni parola in un dizionario di password. Le coppie password-hash sono memorizzate in una tabella, ordinate per valore hash. Per utilizzare una tabella hash, basta prendere l'hash ed eseguire una ricerca binaria nella tabella per trovare la password originale, se presente.

Le tabelle arcobaleno sono più complesse. Costruire una tabella Rainbow richiede due cose: una funzione di hashing e una funzione di riduzione. La funzione di hashing per un determinato set di tabelle Rainbow deve corrispondere alla password con hash che si desidera ripristinare. La funzione di riduzione deve trasformare un hash in qualcosa utilizzabile come password. Una semplice funzione di riduzione consiste nel codificare Base64 l'hash, quindi troncarlo a un determinato numero di caratteri.

I tavoli arcobaleno sono costruiti con "catene" di una certa lunghezza: ad esempio 100.000. Per costruire la catena, scegli un valore seme casuale. Quindi applica le funzioni di hashing e riduzione a questo seed e al suo output e continua a ripetere 100.000 volte. Vengono memorizzati solo il seme e il valore finale. Ripeti questo processo per creare tutte le catene che desideri.

Per recuperare una password utilizzando Rainbow Tables, l'hash della password viene sottoposto alla procedura sopra descritta per la stessa lunghezza: in questo caso 100.000 ma ogni collegamento nella catena viene mantenuto. Ogni anello della catena viene confrontato con il valore finale di ogni catena. Se esiste una corrispondenza, la catena può essere ricostruita, mantenendo sia l'output di ciascuna funzione di hashing sia l'output di ciascuna funzione di riduzione. La catena ricostruita conterrà l'hash della password in questione e la password che l'ha prodotta.

I punti di forza di una tabella hash sono che il recupero di una password è velocissimo (ricerca binaria) e la persona che crea la tabella hash può scegliere cosa inserire, come le prime 10.000 password. Il punto debole rispetto a Rainbow Tables è che le tabelle hash devono memorizzare ogni singola coppia hash-password.

Le tabelle Rainbow hanno il vantaggio che la persona che costruisce quelle tabelle può scegliere la quantità di memoria richiesta selezionando il numero di collegamenti in ciascuna catena. Più collegamenti tra il seme e il valore finale, più password vengono acquisite. Uno dei punti deboli è che la persona che costruisce le catene non sceglie le password che acquisisce, quindi Rainbow Table non può essere ottimizzato per le password comuni. Inoltre, il recupero della password comporta il calcolo di lunghe catene di hash, rendendo il ripristino un'operazione costosa. Più lunghe sono le catene, più password vengono catturate in esse, ma è necessario più tempo per trovare una password all'interno.

Le tabelle hash sono buone per le password comuni, le tabelle Rainbow sono buone per le password difficili. L'approccio migliore sarebbe recuperare quante più password possibile usando le tabelle hash e/o il cracking convenzionale con un dizionario delle prime N password. Per quelli che rimangono, usa Rainbow Tabelle.

180
Crunge

Ci sono molte buone spiegazioni di cosa siano le tabelle Rainbow, questa Come funzionano le tabelle Rainbow è particolarmente buona. Anche articolo di Wikipedia ha anche un'ottima spiegazione. Per un po 'più approfondito, la lettura del documento definitivo sull'argomento è Fare un più rapido scambio crittanalitico di memoria-tempo .

Una semplice spiegazione di Rainbow Tables è che fanno uso di una tecnica di compromesso della memoria temporale. Significa invece di prendere un valore di hash di destinazione e un dizionario di parole, quindi eseguire l'hashing di ogni parola e fare il confronto al volo (approccio della forza bruta usando qualcosa come John ), invece hai tutti i valori nel dizionario in anticipo (ciò potrebbe richiedere molto tempo a seconda della dimensione del dizionario). Ma una volta fatto puoi confrontare tutti gli hash che vuoi con i valori pre-hash nelle tabelle Rainbow, questo è significativamente più veloce rispetto al calcolo di nuovo degli hash.

La spiegazione che ho scritto qui in precedenza nel tentativo di essere breve era fuorviante, dal momento che non spiegava l'uso di riduzioni che utilizzano i tavoli Rainbow. Per una spiegazione migliore fino a quando non riscrivo questo bit, vedi @ risposta Crunge .

Puoi generare tu stesso le tabelle Rainbow usando un'applicazione come RainbowCrack oppure puoi scaricarle da fonti come The Shmoo Group , Free Rainbow Tables project sito web, Ophcrack progetto e molti altri luoghi a seconda del tipo di hash di cui hai bisogno per le tabelle.

Per proteggere da un attacco basato su Rainbow Table il metodo più efficace per combatterlo è assicurarsi che ogni hash all'interno di un sistema sia salato . Ciò rende inutili le tabelle Rainbow pre-generate e significherebbe che un utente malintenzionato dovrebbe generare un set personalizzato di tabelle da utilizzare contro gli hash target, il che sarebbe possibile solo se conoscessero il sale.

15
Mark Davidson

Scopo e pertinenza

Le tabelle Rainbow aiutano a decifrare password difficili, vale a dire quelle che non si trovano nemmeno in un dizionario di grandi dimensioni. Le password sono state storicamente archiviate come semplici hash nei database, ed è per questo che le tabelle Rainbow sono efficaci contro: creare una singola tabella Rainbow (lenta) ed eseguire un numero qualsiasi di database pieni di hash (veloce).

Al giorno d'oggi, sempre più sistemi utilizzano algoritmi di archiviazione password adeguati come Bcrypt, Scrypt o Argon2. Vedi: Come archiviare in modo sicuro le password? Questi algoritmi non sono più "vulnerabili" alle tabelle Rainbow: poiché ogni hash è unico, anche se le password sono uguali, le tabelle Rainbow non funzionano più.

Ecco perché oggi i tavoli Rainbow sono impopolari. Anche se non viene utilizzato qualcosa di moderno come Argon2, oggi gli sviluppatori di solito sanno che dovrebbero almeno usare un sale. Questo è già abbastanza per rendere inutile un tavolo Rainbow.

Come funzionano

Creazione di una tabella

Immagina di creare una tabella Rainbow con solo due catene, ciascuna della lunghezza 5. La tabella Rainbow è per la funzione di hash fittizia MD48, che genera 48 bit (solo 12 caratteri esadecimali). Quando costruiamo la catena, vediamo questo:

Chain 0: 0=cfcd208495d5 => z=fbade9e36a3f => renjaj820=7668b2810262 => aL=8289e8a805d7 => ieioB=2958b80e4a3a => WLgOSj
Chain 1: 1=c4ca4238a0b9 => ykI4oLkj=140eda4296ac => Dtp=1b59a00b7dbe => W=61e9c06ea9a8 => 6cBuqaha=d4d2e5280034 => 0uUoAD

Iniziamo con 0 perché è la prima catena (abbiamo solo bisogno di un valore per iniziare). Quando lo hash con MD48, si trasforma in cfcd208495d5. Ora applichiamo una funzione "riduci" che sostanzialmente formatta questo hash in una password e finiamo con "z". Quando lo hash di nuovo, otteniamo fbade9e36a3f, quindi ridurlo di nuovo e ottenere renjaj820. Ci sono altri cicli e il risultato finale è WLgOSj.

Lo stesso vale per la seconda catena. Iniziamo con un altro valore e facciamo la stessa cosa. Questo termina in 0uUoAD.

Il nostro tavolo Rainbow completo è ora questo:

WLgOSj => 0
0uUoAD => 1

Questo è tutto ciò che devi conservare.

Ricerca di un hash

Supponiamo di aver trovato un hash online, 7668b2810262. Facciamo crack usando il nostro tavolo!

Looking for hash '7668b2810262', reduced to 'aL'.
hashed=>reduced 'aL' to ieioB
hashed=>reduced 'ieioB' to WLgOSj
Found a match, 'WLgOSj' is in our Rainbow table:
    WLgOSj => 0
The chain starts with '0'. Let's walk that chain and look for the hash.
hashed '0' to cfcd208495d5
hashed 'z' to fbade9e36a3f
hashed 'renjaj820' to 7668b2810262
That hash matches! Found the password: renjaj820

Per giocarci da soli, gli esempi sopra sono stati creati usando questo Python: https://Gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Proprietà di ridimensionamento

In breve:

  • Le ricerche rapide significano tabelle più grandi, supponendo che la copertura rimanga invariata.
  • Una migliore copertura significa ricerche più lente o tabelle più grandi.
  • Tabelle più piccole significano ricerche più lente o copertura peggiore.

Le seguenti sezioni presuppongono che il tempo per riduzione hash + sia 1µs e non riesca a tenere conto delle collisioni. Questi sono tutti numeri di baseball, intesi come esempi e non valori esatti.

Tempo di ricerca

Se un'operazione di riduzione hash + richiede un microsecondo, la generazione di una tabella con un milione di catene e 10 000 riduzioni per catena richiederebbero circa 3 ore:
chain_length × chain_count / reductions_per_second / seconds_per_hour
= 10 000 × 1 000 000 / 1 000 000 / 3600 = 2,8 ore.

Effettuare una ricerca in quella tabella richiede in media 10 millisecondi. Questo perché in genere dovremo passare attraverso chain_length/2 riduzioni prima di trovare quale catena contiene l'hash. Ad esempio, potremmo dover fare 3000 riduzioni su un hash prima di trovare un valore nella tabella. Successivamente, dobbiamo ripetere quella catena dall'inizio fino a quando non troviamo il valore corrispondente. Se abbiamo dovuto fare 3000 per trovarlo nella nostra tabella, allora dobbiamo fare 7000 riduzioni dall'inizio per arrivare al punto giusto della catena. Fondamentalmente, eseguiamo tutte le operazioni quando guardiamo in alto come quando generiamo una singola catena. Pertanto, il tempo di ricerca è 10.000 volte un microsecondo, che è di dieci millisecondi (o un centisecondo, se lo si desidera).

Requisiti di archiviazione

Quando vuoi creare una tabella di ricerca completa e veloce per una funzione hash, anche MD5, avrai comunque bisogno di cento miliardi di miliardi di terabyte di spazio di archiviazione. Non è molto utile. E se volessimo coprire solo password minuscole fino a 10 caratteri?

Se vogliamo dedicare al massimo 30 secondi alla ricerca di un hash e supponendo che abbiamo bisogno di 1 microsecondo (un milionesimo di secondo) per hash + ciclo di riduzione, allora possiamo avere una lunghezza della catena di: 1 million × 30 = 30 milioni. Ce ne sono 2610 (o 1014) possibili password minuscole di 10 caratteri e per catena copriamo 30 milioni di valori. Questo ci lascia con 4 milioni di catene. Sappiamo che ogni catena ha solo un valore iniziale e finale memorizzato e che i valori sono ciascuno di 10 caratteri. Così 2 × 10 × 4 million = 76 dati MiB.

Generare la tabella ripetendo tutte le password di 10 caratteri richiede molto tempo: 30 secondi per catena, volte 4 milioni di catene è di circa 91 anni. Molte persone sarebbero interessate a una tabella del genere, tuttavia, quindi mettendo in comune 1092 CPU (= 91 × 12), ci vuole solo 1 mese. Questo mostra quanto una tabella di questo tipo possa essere paragonata allo spazio delle password che copre: le ricerche richiedono solo 30 secondi e devi archiviare solo 76 MiB di dati.

Conclusione

Le tabelle arcobaleno possono essere considerate trade-off di memoria del tempo : si memorizza solo una piccola parte della tabella e la recupera attraverso un calcolo aggiuntivo in fase di ricerca. Questo è uno dei motivi per cui i sali, o meglio, un buon algoritmo di archiviazione delle password come Scrypt o Argon2 sono importanti per proteggere le password. Una tabella Rainbow può recuperare una password salata solo se la tabella contiene una voce abbastanza grande da contenere sia il salt sia la password, che sarebbe estremamente inefficiente e vanifica l'intero scopo.

Si noti che una cosa simile si applica alla crittografia: quando le persone crittografano i file con una password, è possibile creare una tabella Rainbow per decifrare i file. Supponiamo che il software utilizzi AES e che il primo blocco del file debba essere decrittografato in "password corretto" utilizzando la password fornita dall'utente, quindi una tabella Rainbow utilizzerà AES invece di una funzione hash.

Ogni volta che gestisci una password (un segreto di forza sconosciuta, e soprattutto se l'utente potrebbe riutilizzarla), eseguila sempre attraverso un algoritmo di archiviazione password (lento) per renderla lenta e unica da decifrare.

7
Luc