Tabella arcobaleno

Tabelle arcobaleno semplificate con tre funzioni di riduzione

In crittografia una tabella arcobaleno (in inglese rainbow table) è una tabella di associazione che offre un compromesso tempo-memoria usata per il recupero delle chiavi di cifratura in chiaro partendo da chiavi in formato hash generate da una funzione crittografica di hash. L'idea è di usare una grossa quantità di memoria per contenere informazioni calcolate una volta per tutte invece di usare il tempo di CPU. Un'applicazione comune di una tabella arcobaleno è quella di attaccare protezioni basate su password memorizzate col loro hash. Spesso prima di generare l'hash di una password quest'ultima viene «salata» mediante l'aggiunta di un salt 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 fece Hellman fu quella di creare un archivio di password dove memorizzare tutti i possibili hash. Non considerava 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 trovata da Oechslin fu di creare una tabella che possiede come righe le tabelle arcobaleno 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 tabella arcobaleno si memorizzano solo la password iniziale e quella finale.

Funzione di hash e funzione di riduzione

Le funzioni che gestiscono le tabelle sono le seguenti:

• funzione di hash: prende come argomento una password e restituisce 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, rigorosamente diversa da quella di partenza.

Le funzioni di hash sono costruite in modo che sia estremamente difficile risalire alla password originale, quindi la funzione di riduzione non restituisce la password originale, ma ne genera un'altra. Una possibile sequenza di passaggi è la seguente:

password originale -> hash -> altra password -> altro hash -> e così via

per esempio:

${\displaystyle \mathbf {aaaaaa} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {281DAF40} \,{\xrightarrow[{\;R\;}]{}}\,\mathrm {sgfnyd} \,{\xrightarrow[{\;H\;}]{}}\,\mathrm {920ECF10} \,{\xrightarrow[{\;R\;}]{}}\,\mathbf {kiebgt} }$

Funzionamento dell'algoritmo

1. Partendo dall'hash re3xes nell'immagine sottostante, si calcola l'ultima riduzione usata nella tabella e si verifica se la password è presente nell'ultima colonna della tabella.
2. Se la verifica fallisce (rambo non è presente nella tabella), si calcola la catena con le ultime 2 riduzioni. Si continua con riduzioni successive fino a trovare la password o raggiungere la fine della catena. Se la password non viene trovata, l'attacco ha fallito.
3. Se la verifica ha esito positivo (linux23 è presente in tabella e alla fine della catena), la password viene recuperata dall'inizio della catena che produce linux23.
4. All'inizio della catena corrispondente troviamo passwd. A questo punto si genera una catena e si compara ad ogni iterazione l'hash con l'hash iniziale (re3xes). Il test ha successo perché troviamo l'hash re3xes nella catena e la password corrente (culture) è quella che ha prodotto tutta la catena. L'attacco ha successo.

La sequenza di calcoli che l'algoritmo esegue fa guadagnare tempo nella ricerca. Infatti viene calcolata di volta in volta una sola catena, quella dell'hash, e l'algoritmo termina non appena si trova la password.

Efficienza

L'algoritmo pensato da Hellman venne in seguito riformulato introducendo un nuovo criterio di memorizzazione degli hash delle password in tabelle. Le tabelle arcobaleno 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 (casi 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);
• le catene hanno lunghezza fissa (per esempio si memorizza un hash ogni 10 000).

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 l'esecuzione dell'algoritmo viene considerata di volta in volta una catena della tabella e quando la password viene trovata 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 grandissima potenza di calcolo. Normalmente è possibile reperire le tabelle sul web.

Metodi analoghi

Le tabelle arcobaleno non sono l'unico mezzo di ricerca per ricostruire le password. Tra i più noti algoritmi di questo tipo ci sono:

• il metodo forza bruta. È un algoritmo che ricerca la chiave di un sistema provando tutte le possibili combinazioni. Nella pratica un lavoro del genere richiede parecchio tempo, anche anni. Il tempo può essere ridotto attraverso il lavoro in pipeline da parte di più processori se non ci sono colli di bottiglia come un intervallo prefissato tra tentativi successivi;
• l'attacco a dizionario. È un algoritmo che si basa su un file chiamato dizionario perché contenente un enorme numero di 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 viene utilizzato, mentre un attacco con metodo a forza bruta, anche se richiede tempi di gran lunga maggiori, ha una probabilità di riuscita del 100%.

Impedimenti

Le tabelle arcobaleno consentono a qualsiasi persona di risalire alle parole chiave 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, informazione che può essere generata casualmente prima dell'utilizzo di una funzione di hash non reversibile: in questo modo password uguali, ma che sono state codificate con 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 che non lo memorizzano affatto. Un attacco con le tabelle arcobaleno sarebbe impraticabile per valori sufficientemente grandi della quantità di informazione aggiunte tramite il sale, in quanto lo spazio richiesto aumenta linearmente con il numero di salt possibili: ad esempio per un sale di 16 bit, l'attaccante dovrebbe avere spazio sufficiente per memorizzare 2^16 = 65 536 tabelle. L'addizionale tempo di ricerca (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 sale utilizzato è uguale) per velocizzare la ricerca.

Un altro procedimento è noto come key stretching ed è un'estensione del salting: consiste nell'utilizzare come algoritmo di hash un'iterazione di funzioni di hash, ciascuna delle quali utilizza sia l'output della precedente sia un sale costante. In questo modo non solo l'attaccante avrà bisogno di maggior spazio per le tabelle, ma dovrà impiegare anche più tempo. Ad esempio, MD5-Crypt utilizza 1 000 iterazioni della funzione di hash MD-5.

Voci correlate

• Metodo forza bruta
• Attacco a dizionario