Tabella arcobaleno

Da Wikipedia, l'enciclopedia libera.
Tabelle arcobaleno semplificate con tre funzioni di riduzione

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 fattibili 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.

Funzione Hash e funzione di Riduzione[modifica | modifica wikitesto]

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.

Funzionamento dell'algoritmo[modifica | modifica wikitesto]

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.

Efficienza[modifica | modifica wikitesto]

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 10 000 hash).

Prestazioni[modifica | modifica wikitesto]

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.

Metodi analoghi[modifica | modifica wikitesto]

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%.

Impedimenti[modifica | modifica wikitesto]

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.

Un procedimento adottato è noto come salting e consiste nella aggiunta di una quantità di informazione addizionale alla password, che può anche essere generato casualmente, prima dell'utilizzo di una funzione di hashing non reversibile: in questo modo, password uguali ma che sono state codificate secondo salt diversi, hanno codifiche criptate diverse. I salt sono solitamente conservati in chiaro sul sistema che provvede all'hashing, anche se sono disponibili implementazioni che utilizzano una funzione di codifica reversibile, o non memorizzano affatto il salt. Un attacco con le tabelle arcobaleno, sarebbe non pratico per valori sufficientemente grandi della quantità di informazioni aggiunte tramite il salt, in quanto lo spazio richiesto aumenta linearmente con il numero di salt possibili: ad esempio per un salt di 16 bit, l'attaccante dovrebbe avere spazio sufficiente per memorizzare 65.536 = 2^16 tabelle. L'addizionale tempo di lookup su tali tabelle, è trascurabile rispetto alle risorse necessarie per compilarle e memorizzarle, tantopiù che l'analisi potrebbe sfruttare le collisioni tra salt (casi in cui il salt utilizzato è uguale) per velocizzare la ricerca.

Un altro procedimento è noto come Key Stretching, ed è una estensione del salting: consiste nell'utilizzare come algoritmo di hashing, una iterazione di funzioni di hashing, ciascuna delle quali utilizza sia l'output del precedente, che un salt costante. In questo modo, non solo l'attaccante ha requisiti addizionali in termini di spazio, ma anche di tempo. Ad esempio, MD5-Crypt utilizza 1000 iterazione della funzione di hash MD-5.

Voci correlate[modifica | modifica wikitesto]