Tabella arcobaleno
In crittografia una tabella arcobaleno, nota anche con il termine inglese di rainbow table, è una tabella di associazione che offre un compromesso tempo-memoria usato per il recupero delle chiavi di cifratura in chiaro partendo da chiavi in formato hash generate da una funzione crittografica di hash. Un'applicazione comune di una tabella arcobaleno è quella di rendere flessibili gli attacchi contro le password in formato hash. Spesso viene impiegato un nonce in abbinamento ad una password in formato hash per rendere questo tipo di attacco più difficile.
Martin Hellman, informatico e crittografo, fondò la sua teoria basandosi su una tecnica chiamata compromesso tempo-memoria. La considerazione che Hellman fece fu quella di creare un archivio di password dove memorizzare tutti i possibili hash. Non considerò però che ci sarebbe voluto troppo tempo e spazio (decine di terabyte) per rendere fattibile l'operazione; L'idea di Hellman fu ripresa da Philippe Oechslin, un esperto in sicurezza, che perfezionò il concetto espresso da Hellman. La soluzione che trovò Oechslin, fu di creare una tabella che possiede come righe le Rainbow Tables e come colonne gli hash. Ogni tabella è composta da catene, che vanno da un hash fino al successivo memorizzato nella tabella. In quest'ultima si applicano funzioni di riduzioni diverse per ogni colonna ma medesime funzioni hash. Inoltre per ogni Rainbow table si memorizzano solo la password iniziale e quella finale.
Indice |
[modifica] Funzione Hash e funzione di Riduzione
Le funzioni che gestiscono le tabelle sono le seguenti:
- Funzione Hash. Prende come argomento una password per poi restituire un hash generalmente composto da 15 caratteri alfanumerici, indipendentemente dalla lunghezza della password.
- Funzione di Riduzione. Prende come argomento l'hash prodotto dalla precedente funzione e genera una password (questa è rigorosamente diversa da quella di partenza).
Ecco perché le due funzioni hanno la particolarità di essere irreversibili (non restituiscono il valore iniziale). Questa caratteristica è fondamentale, perché se così non fosse, sarebbe molto semplice risalire ad una password attraverso il solo hash connesso.
[modifica] Funzionamento dell'algoritmo
Data una password, viene generato l'hash corrispondente; subito dopo viene applicato a questo, l'ultima funzione di riduzione della catena; Il valore ottenuto dall'applicazione della funzione all'hash, viene confrontato con l'ultimo di ogni catena nella tabella; da qui si possono avere due diversi casi:
- L'hash non compare nelle catene. A questo punto, partendo dalla tabella più in basso; all'hashcode verrà applicata la k-esima funzione di riduzione (dove k è ottenuta dalla sottrazione tra il numero delle colonne della tabella e il numero di iterazioni eseguite fin ora nella tabella). Poi si applicano alternativamente funzioni di hash e di riduzione e, ogni volta che si trova un hash,si confronta l'hash trovato con quello presente nella chiave di registro. Non appena si giunge all'inizio della tabella, si itera il procedimento per la tabella sovrastante. L'algoritmo termina se si trova l'hash oppure se si esaurisce lo spazio di ricerca.
- L'hash viene trovato in una catena. In questo caso viene individuata la catena in cui esso si trova. A questo punto, è molto facile ricostruire la catena, avendo memorizzato la password iniziale.
La computazione che l'algoritmo esegue, come si può notare, fa guadagnare tempo nella ricerca; infatti, viene considerata di volta in volta una catena della tabella. Quindi non appena troviamo la password l'algoritmo termina.
[modifica] Efficienza
L'algoritmo pensato da Hellman, venne in seguito riformulato, introducendo un nuovo criterio di memorizzazione degli hash delle password, attraverso tabelle. Le Rainbow Tables prendono dunque questo nome per il fatto che vengono utilizzate funzioni di riduzioni diverse per ogni colonna di ogni tabella , un po' come i colori dell'arcobaleno,con argomenti diversi per ognuna di esse. Le principali migliorie apportate col nuovo metodo sono:
- Riduzione del numero di merge (fusioni) rispetto ai metodi precedenti basati sul compromesso tempo-memoria;
- Le collisioni (il caso in cui esistono due hash uguali per password diverse), che si hanno a livelli differenti, non comportano il merge e quindi le catene restano invariate;
- Le catene sono prive di cicli (ogni funzione di riduzione è unica nella catena);
- Catene di lunghezza fissa (per esempio si memorizzano uno ogni 10000 hash).
[modifica] Prestazioni
La ricerca attraverso le tabelle Arcobaleno risulta essere circa sette volte più veloce dei precedenti metodi basati sul compromesso tempo-memoria, in quanto durante la computazione dell'algoritmo viene considerata di volta in volta una catena della tabella e quando troviamo la password l'algoritmo termina. Una volta avviata la ricerca sulle tabelle, la probabilità di successo di rinvenire la password è molto vicina al 100%. Bisogna sottolineare che la generazione delle tabelle Arcobaleno richiede una potenza di calcolo non alla portata di qualsiasi calcolatore. È inoltre possibile reperirle sul web.
[modifica] Metodi analoghi
L'uso di potenti mezzi di ricerca per il recupero di informazioni perse, quali le Rainbow Tables, non sono gli unici ad esistere. È infatti possibile che vengano utilizzati altri algoritmi per rintracciare informazioni di questo tipo. I più noti sono:
- Metodo forza bruta. È un algoritmo che ricerca la chiave di un sistema, provandone tutte le possibili combinazioni. Nella pratica un lavoro del genere richiede parecchio tempo, spesso anche anni, cosa che però può essere ridotta attraverso il lavoro in pipeline da parte di più processori.
- Attacco a dizionario. È un algoritmo che si basa appunto su un dizionario, ovvero un file contenente parole candidate ad essere le probabili password (wordlist). L'attacco che viene sferrato si incentra su una serie di tentativi di inserimento della chiave memorizzata sul dizionario, effettuato in modo del tutto automatico. La caratteristica di questo metodo è quella che le parole memorizzate all'interno dell'elenco sono per lo più voci di uso frequente utilizzate dalle persone durante la scelta della loro password.
Il vantaggio di usare un dizionario rispetto a un normale attacco col metodo a forza bruta è dato dal fatto che vengono evitate sequenze prive di senso, del tipo dhskfler. Quindi un attacco a dizionario é efficace solo nel caso la password sia presente nel file dizionario che usiamo, mentre un attacco con metodo a forza bruta, anche se richiede tempi di gran lunga maggiori, ha una probabilità di riuscita del 100%.
[modifica] Impedimenti
Le Rainbow Tables consentono a qualsiasi persona di risalire alle parole chiavi corrispondenti ad un dato hash. Tuttavia sono state trovate soluzioni molto efficaci nell'impedire a metodi potenti come le tabelle, di ottenere i risultati sperati. Il procedimento adottato è noto come salting e consiste nell'aumentare la lunghezza e la complessità della password. Questa tecnica, consente di avere successo se la lunghezza delle Rainbow Tables è minore rispetto a quella delle password comprensive di salt. Altra caratteristica del salting è quella di fare distinzione fra utenti che hanno la stessa password. Questo perché le due chiavi hanno un salt diverso che le contraddistingue. Il salting è quindi un'ottima difesa per coloro che vogliono ottenere la massima sicurezza per le loro informazioni.
