This post was written for the italian cybersecurity blog Cyberment and published here.
For this reason it is written in italian.

Rainbow Table Attack

L’avvento della crittografia e, in particolare, dell’hashing, ha innovato notevolmente le politiche di protezione dei dati sensibili all’interno dei sistemi. Queste tecnologie costituiscono uno strumento fondamentale per garantire la sicurezza delle password all’interno dei database, e diventano sempre più cruciali all’aumentare dell’innovazione digitale e, naturalmente, delle minacce informatiche.

Tuttavia, come ben sappiamo, nel campo della cybersecurity non esistono rimedi universali e infallibili. Le rainbow table rappresentano la principale minaccia per le soluzioni offerte da questo tipo di strumenti. È evidente, quindi, la necessità di studiare e comprendere le implicazioni che queste tabelle hanno per la sicurezza dei nostri dati e quali accorgimenti adottare di conseguenza.

Cos’è una Rainbow Table?

Le rainbow table vengono utilizzate dagli attaccanti per decifrare le password salvate all’interno di un sistema. Nei sistemi moderni, infatti, le password non sono - o non dovrebbero essere - memorizzate in chiaro. È buona norma che il sistema esegua l’hashing della password scelta e memorizzi direttamente il digest prodotto dalla funzione. Quando un utente inserisce successivamente la propria password per autenticarsi, il sistema esegue nuovamente l’hashing di questa e confronta il digest con quello memorizzato. In questo modo, le password degli utenti vengono preservate in caso di data leakage.

Fondamentalmente, una rainbow table è una tabella precompilata di associazioni tra possibili, spesso probabili, password e i rispettivi hash. Una volta che un attaccante è entrato in possesso dell’hash della password della vittima designata, passo preliminare all’interno della kill chain, gli basterà confrontarla con le voci della tabella per cercare una corrispondenza.

Queste tabelle contengono solitamente un numero considerevole di record, mirando a massimizzare la probabilità di un match. A tal fine, vengono raccolte e inserite le password più comunemente utilizzate, come avviene in un normale attacco a dizionario, e vengono generate in modo massiccio nuove password in modo casuale e imprevedibile. Per questo motivo, le rainbow table generalmente non sono implementate come semplici file di testo o database, ma in modo da ottimizzare la ricerca e l’estrazione successiva di un record.

Rainbow Chain

Le tabelle arcobaleno vengono compilate partendo da un insieme molto vasto di password comuni, che viene poi esteso con una lista di password generate casualmente in maniera automatica. Ad ognuna di queste password non viene immediatamente associato il rispettivo hash, come si potrebbe pensare, ma viene utilizzata una tecnica per ottimizzare la ricerca di una corrispondenza, basata sul concetto di rainbow chain.

Le catene arcobaleno, a loro volta, si basano sul concetto di

• funzioni di hashing, che trasformano un testo di lunghezza variabile in una stringa di lunghezza fissata, in modo che non si possa risalire alla stringa originale, né trovare facilmente due stringhe che producano lo stesso hash;
• funzioni di riduzione, studiate, al contrario, per mappare un hash in una password. Per essere più precisi, le funzioni di riduzione trasformano un dato hash in una sequenza di testo potenzialmente utilizzabile come password all’interno di un sistema, ossia una stringa di testo che rispetti determinate proprietà come la lunghezza tipica delle password o l’utilizzo dei caratteri previsti all’interno di una password. Una funzione di riduzione molto semplice potrebbe essere, ad esempio, la funzione di troncamento dell’hash ai primi sei o otto caratteri.

A questo punto possiamo pensare a una catena arcobaleno come a una sequenza alternata di testo in chiaro e cifrato: ogni catena ha inizio con una password, cui segue il relativo hash, a sua volta seguito da una nuova password ottenuta riducendo l’hash e così via.

Data una password iniziale p, una funzione di riduzione r ed una funzione di hashing h, possiamo rappresentare una rainbow table in modo più formale come la seguente catena di trasformazioni: p → h1 = h(p) → p2 = r(h1) → h2 = h(p2) → p3 = r(h2) → h3 = h(p3) → … → pn = r(hn-1) → hn = h(pn).

In realtà, per aumentare le possibilità di successo dell’attacco e ridurre al minimo le probabilità di collisione, ad ogni passaggio di riduzione viene utilizzata una funzione di riduzione diversa. Questo dà il nome alle rainbow chain e, di conseguenza, alle rainbow table: possiamo rappresentare ogni colonna di testo in chiaro con un colore diverso, uno per ogni funzione di riduzione utilizzata, creando così una sequenza di colori differenti che ricordano quella degli arcobaleni.

Ricerca di un match

Come detto prima, la ricerca di un hash all’interno di una rainbow table può essere un problema computazionalmente molto costoso, sopratutto nel caso di tabelle molto grandi come quelle che vengono effettivamente utilizzate negli attacchi. In questo contesto, la memorizzazione dell’intera rainbow table non migliorerebbe la situazione, la renderebbe più complessa senza fornire alcun vantaggio. All’interno della tabella, non viene tuttavia memorizzata l’intera catena, ma solo i due estremi. Dato l’esempio sopra, il corrispondente record nella rainbow table sarà formato dalla coppia <p, hn>.

Nel momento in cui si tenta di decifrare l’hash di una password utilizzando la rainbow table, questo verrà confrontato con gli hash già presenti all’interno della tabella, vale a dire i membri destri delle varie coppie.

Se l’hash in possesso dell’attaccante coincide con uno degli hash presenti all’interno della tabella, viene presa la password associata a questo – vale a dire la password che ha dato inizio alla catena corrispondente – e si segue la catena fino ad ottenere la stringa che ha dato vita all’hash obiettivo. Una delle proprietà chiave che devono avere sia le funzioni di hash che le funzioni di riduzione, infatti, è la velocità di computazione. La catena deve poter essere percorsa velocemente e, non essendo memorizzata esplicitamente all’interno della tabella, dev’essere computazionalmente facile ricalcolare gli hash e le riduzioni quando serve. Questa tecnica sfrutta un concetto noto nell’informatica come il compromesso tempo-memoria.

Naturalmente, l’hash potrebbe non essere presente all’interno di un record come passo finale della computazione, ma potrebbe comparire come passo intermedio di una catena. In questo caso il semplice algoritmo di ricerca descritto non riuscirebbe a trovare la coincidenza, terminando con un mismatch. Per evitare questo comportamento, ed includere anche le computazioni nascoste e intermedie di ogni catena, nel caso di mismatch l’hash target viene ridotto ad una stringa tramite una delle funzioni di riduzione utilizzate nella creazione della rainbow table e il risultato viene nuovamente hashato. L’hash appena ottenuto viene così nuovamente confrontato con tutti i record della tabella, in un processo iterativo facilmente automatizzabile.

Naturalmente, il numero di iterazioni e trasformazioni cui sottoporre l’hash nel caso di mismatch, così come la lunghezza delle catene, è un fattore importante nella riuscita della decrittazione: più è alto questo valore, più hash vengono coperti dalla tabella. Catene troppo lunghe possono tuttavia influenzare negativamente le prestazioni del sistema.

Sale q.b.

Le rainbow table costituiscono uno strumento pericoloso nelle mani degli attaccanti, permettendogli di portare a compimento computazioni intrattabili con il tradizionale metodo forza bruta.

Per fortuna, però, vi sono semplici accorgimenti che possono rendere le rainbow table del tutto inutilizzabili, mettendo ancora una volta al sicuro i nostri dati. La tecnica più comune è chiamata salting e consiste nell’introduzione di una sequenza di caratteri generata casualmente nel momento in cui viene definita una password e inserita all’inizio o alla fine della stessa. La funzione di hashing andrà a calcolare quindi non più l’hash della password, bensì l’hash della password salata.

Nel caso in cui un attaccante riuscisse ad avere accesso al file contenente gli hash delle password, infatti, non gli basterà più una rainbow table contenente una lista di password, ma gli servirà aver memorizzato all’interno della rainbow table le password con salt. La probabilità di riuscita dell’attacco diventa molto bassa se si utilizza un salt lungo e fortemente casuale.

Inoltre, questa tecnica permette di rafforzare anche le password più deboli – spesso scelte perché facilmente memorizzabili – consentendo agli utenti di memorizzare password più semplici senza esporsi a rischi maggiori.

Naturalmente, per aumentare la robustezza del sistema e l’efficacia del salting, è necessario

• utilizzare salt differenti per ogni password, soprattutto nel caso di password uguali; altrimenti, password uguali verrebbero associate allo stesso hash, diminuendo l’efficacia del salting
• che i valori di salt vengano salvati in un file o in un database separato da quello in cui vengono memorizzate le password, in modo da mantenerli segreti nel caso in cui un attaccante riesca ad entrare in possesso degli hash delle password.

Conclusioni

Le rainbow table rappresentano una minaccia per la protezione di password protette da codifica hash. Questi strumenti forniscono un ausilio importante per gli attaccanti che, in possesso di un file di hash, vogliono decrittarne il contenuto per scopi malevoli.

Anche per questo caso, per fortuna, sono state studiate contromisure e accorgimenti per prevenire l’attacco. Il salting è la più comune ed efficace ed è facilmente attuabile, negli scenari più comuni, per gli amministratori di sistema.

Per diminuire le probabilità di riuscita dell’attacco, si dovrebbero anche utilizzare algoritmi di hashing avanzati – come bcrypt o scrypt – appositamente studiati per la protezione delle password, oltre che scegliere password complesse e differenti per ogni sistema.