Rainbow Tables: Che cosa sono le tabelle arcobaleno?

Se inizialmente si pensa che con questo nome si indichi un giocattolo divertente, si scoprirà ben presto che ci si riferisce, invece, a un potente strumento che serve per decifrare le password. Un gruppo relativamente grande di persone investe molte energie nel cracking delle password, perché da un lato ci sono i cybercriminali, che pensano di beneficiare da azioni criminali, e dall’altro si ritrovano esperti, che devono verificare regolarmente l'efficacia delle misure di sicurezza impostate. In precise circostanze le tabelle arcobaleno rendono possibile scoprire le password nel giro di pochi secondi.

Anche se non siete stati vittima di hacker e non prevedete di usare queste tabelle per altri scopi, è interessante comprenderne il principio. Grazie a una migliore conoscenza del sistema, se siete utenti capirete meglio perché sono necessarie password complesse, mentre se siete dei webmaster scoprirete a cosa dovreste prestare attenzione per mettere al sicuro le vostre password.

Oggigiorno le password non vengono più salvate su Internet senza cifratura (o almeno si spera). Quando gli utenti di una piattaforma scelgono una password per il loro account, la sequenza di caratteri non viene mostrata come testo in chiaro in un qualsiasi database su un server. Infatti un procedimento simile sarebbe troppo poco sicuro: a un hacker basterebbe richiedere l'accesso al database e potrebbe subito intrufolarsi negli account di ogni singolo utente.

Per l'e-commerce, l'online banking o i servizi di e-government casi di questo tipo sarebbero molto gravi. Perciò i servizi online utilizzano diversi meccanismi crittografici per codificare le password degli utenti: nei database è presente solo un hash della password.

Dall'hash non si può individuare direttamente la password, anche se si conosce la funzione crittografica. Non c'è possibilità di risalire al processo in maniera inversa, così gli hacker ricorrono ad esempio agli attacchi di forza bruta: in questo caso un programma per il computer tenta di indovinare la password fino a quando non trova la giusta sequenza.

Questo metodo può anche essere combinato con password che si trovano in un dizionario, nella cosiddetta wordlist. In questi file ottenibili su Internet si trovano innumerevoli password, che sono molto conosciute o sono state scoperte in un attacco precedente su un altro sistema. Così la decodifica per gli hacker avviene più velocemente: prima di tutto provano tutte le password presenti nel dizionario, processo che tuttavia, a seconda della complessità delle password (lunghezza e tipi di caratteri utilizzati), può richiedere un po' di tempo e degli specifici requisiti.

Le tabelle arcobaleno fanno un altro passo in avanti rispetto alle password presenti nelle wordlist: anche queste tabelle si trovano su Internet e si possono utilizzare per carpire le password. In questi file, che a volte hanno una dimensione di centinaia di gigabyte, si trovano delle password pertinenti all'algoritmo di crittografia utilizzato insieme ai loro hash. Tuttavia non sono complete: al loro posto si generano delle precise catene che possono essere calcolate facilmente a partire dai valori veri e propri, riducendo così la necessità di spazio richiesto da tabelle sempre più grandi. Con le tabelle arcobaleno si possono assegnare quindi gli hash, che sono stati trovati in un database, alle password corrispondenti in un testo in chiaro.

Per capire come funzionano le tabelle arcobaleno, si deve conoscere almeno il funzionamento basilare degli algoritmi crittografici. Così è anche più facile comprendere il vantaggio delle tabelle già pronte e il correlato compresso tempo-memoria.

Da quando nella cifratura si usano le funzioni crittografiche di hash, i relativi algoritmi hanno sempre subito modifiche. Gli standard che 10 anni fa erano considerati inviolabili sono visti oggigiorno come delle gravi infrazioni della sicurezza. Comune a tutti è però il fatto che il contenuto da crittografare funzioni tramite algoritmi e venga generato alla fine un hash, che è di solito un numero esadecimale di una lunghezza definita. Infatti indipendentemente dalla lunghezza del contenuto originario, alla fine risulta sempre un hash di 128 bit. Nella crittografia sono decisive quattro proprietà:

1. Lo stesso input genera sempre lo stesso hash: solo così il valore può funzionare come checksum. La password inserita è uguale a quella salvata nel database? Solo quando due hash sono identici, il sistema consente l'accesso.
2. Un hash dovrebbe sempre essere univoco: diversi input non possono essere generati con lo stesso hash. Solo così la funzione può garantire che venga immessa la giusta password. Visto che il numero dei possibili hash è limitato, ma non lo è il numero dei possibili input, non possono essere escluse collisioni simili. Le funzioni di hash moderne e gli hash di lunghezza sufficiente minimizzano il rischio fin dove possibile.
3. Gli hash non si possono desumere con il processo inverso, quindi non si può mai derivare il contenuto originale. Perciò non si possono neanche decifrare gli hash, come viene affermato a volte impropriamente, ma si possono solo comprendere.
4. Le funzioni di hash devono essere davvero complesse, ma non troppo: per garantire la sicurezza, un algoritmo non deve lavorare troppo velocemente, perché si faciliterebbe anche il lavoro degli hacker. Neanche la conversione dovrebbe essere troppo complicata, perché deve anche essere messa in pratica.

Gli hash compresi nelle tabelle arcobaleno vengono creati preliminarmente, ancora prima di un attacco: gli hacker possono entrare in possesso delle tabelle arcobaleno e utilizzarle per scoprire le password. Questi file sono però molto grandi e quindi, per evitare di superare lo spazio richiesto, le tabelle arcobaleno si servono di una funzione di riduzione, che converte l’hash in un semplice testo. È importante notare che la funzione di riduzione non permette di sfruttare un procedimento inverso partendo dall’hash, quindi non restituisce il testo semplice originario (ad esempio la password), ma uno completamente nuovo (perché il contrario non è possibile).

Da questo testo si genera di nuovo un hash. In una tabella arcobaleno non compare solo una volta, ma più volte, di modo che si formi una catena. Nella tabella finale sono presenti solo la prima password e l’ultimo hash di una catena. Sulla base di queste informazioni e considerando le funzioni di riduzione utilizzate si possono individuare anche tutti gli altri valori. L’hash da scoprire viene di nuovo ridotto e reso come hash seguendo le stesse regole, dove si compara ogni risultato intermedio con i valori presenti nella tabella.

La sfida nella creazione delle tabelle consiste nel fatto che i contenuti di partenza, che rappresentano l’inizio di una nuova catena, non devono essere già comparsi in un testo semplice di una catena precedente. Grazie a questa tecnica si possono diminuire notevolmente le dimensioni di tabelle simili, anche se mantengono una mole di diverse centinaia di gigabyte.

Si parla di un compromesso tempo-memoria se viene impiegato un tempo di esecuzione maggiore per utilizzare meno memoria o viceversa. Un attacco forza bruta occupa molto poco spazio, visto che i calcoli crittografici vengono eseguiti nuovamente a ogni attacco. Invece una tabella, in cui sono presenti miliardi di password con i loro hash, occupa molto spazio, ma in compenso può eseguire la decifrazione molto velocemente. Le tabelle arcobaleno rappresentano un compromesso tra i due sistemi: infatti eseguono calcoli in tempo reale, ma in misura inferiore e occupano meno spazio rispetto alle tabelle complete.

Generalmente si ha a disposizione un hash preciso di cui si vorrebbe scoprire la password vera e propria, che si nasconde dietro questo valore. Prima di tutto si cerca nella lista un hash. Se lo si trova all’inizio o alla fine di una catena, si risale alla password in modo relativamente veloce, infatti ora serve solo comprendere le ripetizioni della catena e si ottiene così il risultato desiderato. Ma che cosa succede se non si trova l’hash nella tabella?

In questo caso si comincia con una riduzione dell’hash, con la stessa funzione con la quale sono state create le catene. Il risultato è che si verifica di nuovo la funzione di hash, che si ripete fino a quando non si ritrova un hash in una delle parti finali, ma non sarà svelata la password ricercata. Si è però trovata la catena corrispondente che si nasconde nell’hash. Perciò si comincia ora con il punto di partenza della catena e si eseguono di nuovo le riduzioni a turno e l’hashing, fino a che si arriva all’hash ricercato e così anche al testo in chiaro della password.

Alla fine ci si chiederà che legame abbiano le tabelle con gli arcobaleni. In pratica non si utilizza solo una funzione di riduzione, ma in ogni passaggio se ne usa un’altra. Questo garantisce un migliore risultato nel caso della riduzione e impedisce che si ripetano gli hash nella tabella, ma ha lo svantaggio che trovare delle combinazioni di hash e password è un po’ più complesso nelle catene.

Così le riduzioni della serie devono essere attraversate: partendo dal presupposto che si è costruita la catena con le riduzioni R₁, R₂, R_3, si comincia prima di tutto la ricerca con la funzione R_1. Se non ci sono risultati, si ricorre prima all’R₂, poi all’R_3, e così via. All’interno delle tabelle si possono evidenziare con colori le diverse funzioni di riduzione, cosa che nel caso di molte iterazioni può portare a un arcobaleno, da cui le tabelle prendono il nome.

Quanto riportato si spiega nel modo seguente: la password inserita è k; m è un moltiplicatore indefinito (in questo esempio 2000). Per A si imposta solitamente la sezione aurea (). Modulo (mod) estrae il resto di una divisione che viene eseguita in questa funzione con 1. Le parti intere arrotondano infine il risultato a un numero intero, qualora sia necessario. Il risultato finale h(k) è l’hash h per l’input k.

Visto che il nostro hash è composto da quattro cifre, lo completiamo all’inizio con uno 0: 0408.

In una tabella arcobaleno per questa funzione di hash devono ora agire le funzioni di riduzione. Una possibilità molto facile di ridurre l’hash è ad esempio quella di utilizzare solo le ultime due cifre, com’è il caso della password 78 e dell’hash correlato 0408 con la riduzione 08. Qui si costruisce di nuovo un hash servendosi della funzione preimpostata e così via.

La frequenza delle ripetizioni può essere scelta liberamente. Più una ripetizione è frequente, meno memoria serve per la tabella arcobaleno, anche se aumenta il tempo di elaborazione. In questo esempio eseguiremo la riduzione per ben tre volte.

La tabella sopra mostra le catene complete con i risultati delle funzioni di hash e di riduzione. L’obiettivo di una tabella arcobaleno è però quello di diminuirne le dimensioni. Perciò in una tabella arcobaleno già pronta sono compresi solo il margine sinistro e destro della tabella. Tutti gli altri valori vengono desunti.

Ora non sono più presenti tutti gli hash nella tabella. Se ad esempio si sa che si nasconde una password dietro all’hash 1888 si inizia una ricerca nelle tabelle arcobaleno create, stabilendo così che il valore non compare nella tabella, ma si nasconde in una catena. Di conseguenza si deve eseguire ora una riduzione che dà come risultato 88. Anche questo valore non fa parte delle tabelle, quindi si calcola di nuovo l’hash (0768) e la riduzione (68). Il relativo hash 0048 si trova nella terza riga, mentre la password nella stessa riga (03) non appartiene direttamente all’hash, perché è solo l’inizio della catena.

In questo modo si fornisce però il punto di partenza per il prossimo calcolo: da 03 si calcola l’hash 1708, che si riduce a 08 e crea di nuovo l’hash 1888, quello che si cercava. Appartiene quindi a questo valore la password 08.

Dopo aver capito come gli hacker riescano a intrufolarsi negli account degli utenti ricorrendo a una tabella arcobaleno, dovrebbe essere chiaro che si devono impostare dei meccanismi di difesa adeguati. Sia gli utenti sia i responsabili delle offerte web possono prendere delle misure per impedire attacchi di questo tipo o almeno renderli più difficili.

Per gli utenti è bene in generale seguire il consiglio di scegliere delle password il più possibile lunghe, formate sia da lettere maiuscole, minuscole, da cifre e da altri caratteri: ciò complica la riuscita di attacchi forza bruta e del ricorso alle tabelle arcobaleno, visto che il processo di decodifica richiederà più tempo. Con la lunghezza della password aumentano anche esponenzialmente le dimensioni delle tabelle necessarie. Inoltre è utile non usare delle parole reali, ma piuttosto delle catene di caratteri casuali per impedire attacchi a dizionario. Nella scelta di una giusta password vi possono aiutare i password manager. È però molto importante, indipendentemente da quale forma di attacco sfruttino gli hacker, non utilizzare la stessa password più di una volta: se qualcuno è stato capace di corrompere un database, di decifrare le password e di scovare i dati personali, riuscirà facilmente ad accedere a tutti gli altri account su Internet servendosi della stessa password.

Anche gli amministratori di un server possono prendere alcune precauzioni per proteggere i loro utenti. Il primo passo sarebbe ovviamente quello di non consentire agli hacker di arrivare ai database con gli hash. Che sia più facile a dirsi che a farsi lo dimostrano le molte violazioni avvenute sui server delle grandi aziende. Perciò si deve per forza proteggere l’hash, incominciando a non utilizzare degli algoritmi obsoleti.

Sia MD5 sia SHA-1 risultano da molto tempo non sicuri e le relative tabelle arcobaleno si trovano facilmente su Internet. Con questi algoritmi si possono scoprire le password che vengono rese come hash nel giro di pochi secondi. Perciò è indispensabile informarsi regolarmente sullo sviluppo di nuovi algoritmi e su quanto sia sicura la funzione di hash utilizzata. SHA-2 e così anche la sua variante più conosciuta SHA-256 sono considerati ancora sicuri, nel frattempo è però anche disponibile SHA-3, che promette una maggiore sicurezza.

Per strutturare la decodifica delle tabelle arcobaleno in modo un po’ più difficile, oggigiorno si usa il cosiddetto salt: quando un utente stabilisce una password, il sistema crea un valore casuale aggiuntivo, il salt. Questo valore confluisce insieme alla password nella funzione di hash e genera così un altro valore, al di là della semplice password.

Il salt e l’hash si trovano entrambi in un database, cosa che potrebbe generare un po’ di confusione: gli hacker che accedono al contenuto del database, riescono a ottenere così il nome utente, l’hash e il relativo salt. Infatti gli attacchi forza bruta e a dizionario non vengono evitati con questo procedimento, ma questa misura aggiuntiva risulta efficace proprio contro le rainbow tables. Una simile tabella è creata preliminarmente sulla base di un algoritmo di hash e indipendentemente dal database che si usa. I salt non possono quindi essere contenuti nelle tabelle arcobaleno, visto che i creatori della tabella non erano ancora a conoscenza del salt.

Un altro vantaggio del salt è che gli utenti non devono segnarselo, quindi possono essere caotici e soprattutto molto lunghi. In questo modo gli hash sono di nuovo complessi e risultano difficili da gestire. Inoltre un salt impedisce che due o più persone inseriscano la stessa password e scrivano così anche lo stesso hash nel database. Infine il salting aiuta anche nel caso in cui gli utenti utilizzino sempre la stessa password per diversi servizi: l’hash memorizzato è diverso su tutti i servizi per via del salt.

Accanto a salt c’è anche pepper, che complica a sua volta gli attacchi forza bruta o a dizionario. Anche pepper è una sequenza di caratteri casuale che confluisce nell’hash insieme alla password, ancora meglio se combinato con salt. Al contrario di salt, il pepper non si salva in un database insieme agli altri dati di login, ma separatamente e in un luogo più sicuro.

Spesso viene utilizzata una catena di caratteri fissa per tutte le password della piattaforma, perciò pepper non aiuta contro il fatto che più utenti dispongono della stessa password perché utilizzano anche lo stesso pepper, cosa che porta di nuovo ad avere un hash identico. In parole povere gli amministratori dovrebbero affidarsi a una combinazione composta da salt e pepper.