Cosa sono i tavoli arcobaleno e come vengono utilizzati?

Le Rainbow Tables sono comunemente confuse con unaltra tecnica più semplice che sfrutta i tempi di calcolo torage compromesso nel recupero della password: tabelle hash.

Le tabelle hash sono costruite hashing ogni parola in un dizionario delle password. Le coppie password-hash sono archiviate in una tabella, ordinate per valore hash. Per utilizzare una tabella hash, è sufficiente prendere lhash ed eseguire una ricerca binaria nella tabella per trovare la password originale, se presente.

Le tabelle arcobaleno sono più complesse. La costruzione di una tabella arcobaleno richiede due cose : una funzione di hashing e una funzione di riduzione. La funzione di hashing per un dato insieme di Rainbow Tables deve corrispondere alla password con hash che desideri recuperare. La funzione di riduzione deve trasformare un hash in qualcosa utilizzabile come password. Una semplice funzione di riduzione è Base64 codificare lhash, quindi troncarlo a un certo numero di caratteri.

Le tabelle arcobaleno sono costituite da “catene” di una certa lunghezza: 100.000 ad esempio. Per costruire la catena, scegli un valore iniziale casuale. Quindi applica le funzioni di hashing e di riduzione a questo seed e al suo output e continua a ripetere 100.000 volte. Vengono memorizzati solo il seed e il valore finale. Ripeti questo processo per creare tutte le catene desiderate.

Per ripristinare un password utilizzando Rainbow Tables, lhash della password subisce il processo sopra per la stessa lunghezza: in questo caso 100.000 ma ogni anello della catena viene mantenuto. Ogni anello della catena viene confrontato con il valore finale di ciascuna catena. Se cè una corrispondenza, la catena può essere ricostruita, mantenendo sia loutput di ciascuna funzione di hashing che loutput di ciascuna funzione di riduzione. Quella catena ricostruita conterrà lhash della password in questione e la password che lha prodotta.

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

I Rainbow Tables hanno il vantaggio che la persona che costruisce quelle tabelle può scegliere la quantità di spazio di archiviazione necessaria selezionando il numero di collegamenti in ogni catena. Più collegamenti tra il seme e il valore finale, più password vengono acquisite. Un punto debole è che la persona che costruisce le catene non sceglie le password che acquisisce, quindi Rainbow Tables non può essere ottimizzato per password comuni. Inoltre, il ripristino della password implica lelaborazione di lunghe catene di hash, rendendo il ripristino unoperazione costosa. Più lunghe sono le catene, più password vengono catturate al loro interno, ma più tempo è necessario per trovare una password allinterno.

Le tabelle hash sono buone per le password comuni, le tabelle Rainbow sono buone per le password difficili. Lapproccio migliore sarebbe quello di recuperare quante più password possibile utilizzando tabelle hash e / o cracking convenzionale con un dizionario delle prime N password. Per quelli che rimangono, usa i tavoli Rainbow.

Commenti

• Oh mio Dio, ammetto di essere scioccato – discuto e spiego tutti i tavoli Rainbow tempo, e per tutto questo tempo sembra che io sia stato uno dei ” comunemente confusi “! Lo farei totalmente +1000 volte, ho davvero imparato qualcosa di nuovo qui (e pensavo di conoscere la risposta). Sono contento di aver fatto la domanda dopotutto … Grazie!
• Anche se per essere precisi (ora che hai aperto gli occhi ho fatto qualche ricerca in più :)), i Rainbow Tables si differenziano dalle Hellman Hash Chains usando diverse diverse funzioni di riduzione. Più complessa in effetti … ma davvero unidea davvero bella (Ah! È questo perché ‘ si chiama ” Rainbow ” tabelle?)
• Sono daccordo che questa sia unottima spiegazione. Nella mia risposta lho spiegato in modo semplice e anche davvero sbagliato essendo semplice.La bellezza delle tabelle Rainbow è il fatto che ‘ non memorizzano ogni valore hash. Modificherò il mio ma voterò anche questo in quanto è sicuramente una spiegazione migliore.
• Hmm … Anche se più ci penso, nei sistemi della vita reale i Rainbow Tables non sono neanche lontanamente utili quanto tabelle hash. Come hai affermato, per le password comuni le tabelle hash sono molto migliori (poiché sono più veloci dellordine di grandezza e le dimensioni richieste per un dizionario delle password sono ovviamente molto più piccole dellintero intervallo possibile di password). E chi ‘ stiamo prendendo in giro? La maggior parte delle password rientra in questa categoria, è molto raro (e lo sarà per un po di tempo) che tu debba chiamare in RT.
• Sfortunatamente, mi hai perso qui: ” Per recuperare una password utilizzando Rainbow Tables, la password viene sottoposta alla procedura precedente per la stessa lunghezza. ” In che modo la password può essere sottoposta al processo quando ‘ non è nemmeno noto? Intendevi lhash della password? Inoltre, ‘ è questo: ” Ogni anello della catena viene confrontato con il valore finale di ciascuna catena. ” Non riesco a vedere una situazione in cui un collegamento nella catena corrisponderebbe al valore finale della catena, poiché il valore del collegamento verrebbe continuamente sottoposto ad hashing e ridotto.

Ci sono molte buone spiegazioni di cosa sono le tabelle arcobaleno, questa Come funzionano le tabelle arcobaleno è particolarmente buono. Anche l articolo di Wikipedia ha unottima spiegazione. Per una lettura un po più approfondita, larticolo definitivo sullargomento è Fare un compromesso crittoanalitico più veloce tra tempo e memoria .

Una semplice spiegazione dei Rainbow Tables è che fanno uso di una tecnica di scambio della memoria temporale. Significato invece di prendere un valore hash di destinazione e un dizionario di parole, quindi eseguire lhashing di ogni parola ed eseguire il confronto al volo (approccio di forza bruta utilizzando qualcosa come John ), si esegue invece lhash di tutti i valori nel dizionario in anticipo (ciò potrebbe richiedere molto tempo a seconda delle dimensioni del dizionario). Ma una volta fatto, puoi confrontare quanti hash vuoi con i valori pre-hash nelle tabelle arcobaleno, questo è significativamente più veloce che calcolare di nuovo gli hash.

La spiegazione che ho scritto qui in precedenza in uno sforzo per essere brevi era fuorviante, poiché non spiegava luso delle riduzioni di cui fanno uso le tabelle arcobaleno. Per una spiegazione migliore fino a quando non riscrivo questo bit, vedi @Crunge answer .

Puoi generare tu stesso le tabelle arcobaleno usando unapplicazione come RainbowCrack oppure puoi scaricarli da fonti come The Shmoo Group , Free Rainbow Tables , progetto Ophcrack e molti altri posti a seconda del tipo di hash per cui hai bisogno di tabelle.

Per proteggersi da un attacco basato su Rainbow Table, il metodo più efficace per combatterlo è garantire che ogni hash allinterno di un sistema sia salato . Ciò rende inutili le tabelle arcobaleno pre-generate e un utente malintenzionato dovrebbe generare un set personalizzato di tabelle da utilizzare contro gli hash mirati, il che sarebbe possibile solo se conoscesse il sale.

Commenti

• Inoltre (considera di modificarlo in), se usi un salt diverso per ogni password, registrandola in chiaro nel database, allora il attaccato avrebbe bisogno di generare un set personalizzato di tabelle per ogni hash, che sconfiggerebbe loggetto dellesercizio: lo scopo della tabella arcobaleno è di forzare lintero spazio della password e quindi ottenere tutte le password per una forza bruta sforzo; se ‘ stai ottenendo solo una password per tabella arcobaleno, potresti anche forzare direttamente lhash.

Scopo e pertinenza

Le tabelle arcobaleno aiutano a decifrare password difficili, cioè quelle che non si trovano nemmeno in un grande dizionario. Le password sono state storicamente memorizzate come semplici hash nei database, e questo è ciò contro cui le tabelle arcobaleno sono efficaci: creare una singola tabella arcobaleno (lento) ed eseguire un numero qualsiasi di database pieni di hash contro di essa (veloce).

Oggigiorno sempre più sistemi utilizzano algoritmi di memorizzazione delle password appropriati come Bcrypt, Scrypt o Argon2. Vedi: Come [memorizzare] le password in modo sicuro? Questi algoritmi sono non più “vulnerabile” alle tabelle arcobaleno: poiché ogni hash è unico, anche se le password sono uguali, le tabelle arcobaleno non funzionano più.

Ecco perché le tabelle arcobaleno sono oggi impopolari.Anche se non viene utilizzato qualcosa di moderno come Argon2, gli sviluppatori oggigiorno di solito sanno che dovrebbero almeno usare un sale. Già questo è sufficiente per rendere inutile una tabella arcobaleno.

Come funzionano

Creazione di una tabella

Immagina di creare una tabella arcobaleno con solo due catene, ciascuna di lunghezza 5. La tabella arcobaleno è per la funzione hash fittizia MD48, che emette 48 bit (solo 12 caratteri esadecimali). Durante la creazione della 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 con cui iniziare). Quando lo abbiamo hash con MD48, si trasforma in cfcd208495d5. Ora applichiamo una funzione “reduce” che fondamentalmente formatta questo hash in un password e finiamo con “z”. Quando lo cancelliamo di nuovo, otteniamo fbade9e36a3f, quindi lo riduciamo di nuovo e otteniamo renjaj820 Ci sono altri cicli e il risultato finale è WLgOSj.

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

La nostra tabella arcobaleno completa ora è questa:

WLgOSj => 0 0uUoAD => 1 

Questo è tutto ciò che devi memorizzare.

Cercare un hash

Supponiamo di aver trovato un hash online, 7668b2810262. Rompiamolo usando la nostra tabella!

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 solo, gli esempi precedenti sono stati creati utilizzando questo script Python: https://gist.github.com/lgommans/83cbb74a077742be3b31d33658f65adb

Proprietà di ridimensionamento

In breve:

• Ricerche veloci significano tabelle più grandi, supponendo che la copertura rimanga la stessa.
• Una copertura migliore significa ricerche più lente o tabelle più grandi.
• Tabelle più piccole significa ricerche più lente o una copertura peggiore.

Le sezioni seguenti presumono che il tempo per hash + riduzione sia 1 µs e non tengono conto delle collisioni. Questi sono tutti numeri approssimativi, intesi come esempi e non come valori esatti.

Tempo di ricerca

Se unoperazione di riduzione hash + richiede un microsecondo, la generazione di una tabella con un milione di catene e 10.000 riduzioni per catena richiederebbe 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.

Lesecuzione di una ricerca in quella tabella richiede in media 10 millisecondi. Questo perché in genere dovremo eseguire riduzioni chain_length/2 prima di trovare quale catena contiene lhash. Ad esempio, potremmo dover fare 3000 riduzioni su un hash prima di trovare un valore che è nella tabella. Successivamente, dobbiamo ripetere quella catena dallinizio fino a trovare il valore corrispondente. Se dovessimo solo fare 3000 per trovarlo nella nostra tabella, allora dobbiamo fare 7000 riduzioni dallinizio per arrivare al punto giusto della catena. Fondamentalmente, eseguiamo tante operazioni quando guardiamo in alto quante quando generiamo una singola catena. Pertanto, il tempo di ricerca è di 10.000 volte un microsecondo, ovvero dieci millisecondi (o un centisecondo, se vuoi).

Requisiti di archiviazione

Quando vuoi creare una tabella di ricerca rapida e completa per una funzione hash, anche MD5, “avresti ancora bisogno di cento miliardi di miliardi di terabyte di spazio di archiviazione. Quello” non è molto utile. Ma cosa succede se vogliamo coprire solo le password minuscole fino a 10 caratteri?

Se vogliamo spendere al massimo 30 secondi alla ricerca di un hash e supponendo di aver bisogno di 1 microsecondo (un milionesimo di secondo) per hash + ridurre il ciclo, quindi possiamo avere una lunghezza della catena di: 1 million × 30 = 30 milioni. Sono disponibili 26 ¹⁰ (o 10 ¹⁴ ) 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 uno finale memorizzati e che i valori sono di 10 caratteri ciascuno. Quindi 2 × 10 × 4 million = 76 MiB di dati.

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

Conclusione

Le tabelle arcobaleno possono essere considerato un compromesso tempo-memoria : si memorizza solo una piccola parte della tabella e la si recupera attraverso alcuni calcoli extra sul tempo di ricerca. Questo è uno dei motivi per cui i sali, o meglio, un buon algoritmo di memorizzazione delle password come Scrypt o Argon2 sono importanti per mantenere le password al sicuro.Una tabella arcobaleno può recuperare una password salata solo se la tabella contiene una voce abbastanza grande da contenere sia il sale che la password, il che sarebbe estremamente inefficiente e vanifica lintero scopo.

Nota che una cosa simile si applica con la crittografia: quando le persone crittografano i file con una password, è possibile creare una tabella arcobaleno per decifrare i file. Supponiamo che il software utilizzi AES e che il primo blocco del file debba essere decrittografato in “passwordcorrect” utilizzando la password fornita dallutente, quindi una tabella arcobaleno userebbe AES invece di una funzione hash.

Ogni volta che gestisci una password (un segreto di forza sconosciuta, e soprattutto se lutente potrebbe riutilizzarla), eseguila sempre attraverso un algoritmo di memorizzazione della password appropriato (lento) per renderlo lento e unico da decifrare. >

Commenti

• Buona spiegazione. Se ho capito bene, il potere delle tabelle arcobaleno sta nellavere una buona funzione di riduzione, giusto? Come ne trovo uno buono? E come faccio a evitare le collisioni per tutti i candidati delle catene?
• @ Kyu96 Buone domande! Non ‘ non conosco la risposta ma sarei interessato se ne trovassi una. Questa pagina riguarda solo la questione generale di cosa sia una tabella arcobaleno, non le specifiche come progettare un algoritmo. Dovresti aprire una nuova domanda , ma questo sito web riguarda la ” protezione delle risorse dalle minacce digitali ” (iirc ). Penso che sarebbe in tema per il nostro sito gemello, crypto.stackexchange.com , che riguarda ” la matematica e le proprietà dei sistemi crittografici, la loro analisi (” cryptanalysis “) e argomenti sussidiari che generalmente costituiscono la crittoologia, come il numero casuale generazione. ”