Rainbow Tables: Che cosa sono le tabelle ar­co­ba­le­no?

Se ini­zial­men­te si pensa che con questo nome si indichi un gio­cat­to­lo di­ver­ten­te, si scoprirà ben presto che ci si riferisce, invece, a un potente strumento che serve per decifrare le password. Un gruppo re­la­ti­va­men­te grande di persone investe molte energie nel cracking delle password, perché da un lato ci sono i cy­ber­cri­mi­na­li, che pensano di be­ne­fi­cia­re da azioni criminali, e dall’altro si ritrovano esperti, che devono ve­ri­fi­ca­re re­go­lar­men­te l'ef­fi­ca­cia delle misure di sicurezza impostate. In precise cir­co­stan­ze le tabelle ar­co­ba­le­no 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, è in­te­res­san­te com­pren­der­ne il principio. Grazie a una migliore co­no­scen­za del sistema, se siete utenti capirete meglio perché sono ne­ces­sa­rie password complesse, mentre se siete dei webmaster sco­pri­re­te a cosa dovreste prestare at­ten­zio­ne per mettere al sicuro le vostre password.

Og­gi­gior­no le password non vengono più salvate su Internet senza cifratura (o almeno si spera). Quando gli utenti di una piat­ta­for­ma 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 pro­ce­di­men­to simile sarebbe troppo poco sicuro: a un hacker ba­ste­reb­be ri­chie­de­re l'accesso al database e potrebbe subito in­tru­fo­lar­si negli account di ogni singolo utente.

Per l'e-commerce, l'online banking o i servizi di e-go­vern­ment casi di questo tipo sarebbero molto gravi. Perciò i servizi online uti­liz­za­no diversi mec­ca­ni­smi crit­to­gra­fi­ci per co­di­fi­ca­re le password degli utenti: nei database è presente solo un hash della password.

Dall'hash non si può in­di­vi­dua­re di­ret­ta­men­te la password, anche se si conosce la funzione crit­to­gra­fi­ca. Non c'è pos­si­bi­li­tà 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 in­do­vi­na­re la password fino a quando non trova la giusta sequenza.

Questo metodo può anche essere combinato con password che si trovano in un di­zio­na­rio, nella co­sid­det­ta wordlist. In questi file ot­te­ni­bi­li su Internet si trovano in­nu­me­re­vo­li password, che sono molto co­no­sciu­te o sono state scoperte in un attacco pre­ce­den­te su un altro sistema. Così la de­co­di­fi­ca per gli hacker avviene più ve­lo­ce­men­te: prima di tutto provano tutte le password presenti nel di­zio­na­rio, processo che tuttavia, a seconda della com­ples­si­tà delle password (lunghezza e tipi di caratteri uti­liz­za­ti), può ri­chie­de­re un po' di tempo e degli specifici requisiti.

Le tabelle ar­co­ba­le­no fanno un altro passo in avanti rispetto alle password presenti nelle wordlist: anche queste tabelle si trovano su Internet e si possono uti­liz­za­re per carpire le password. In questi file, che a volte hanno una di­men­sio­ne di centinaia di gigabyte, si trovano delle password per­ti­nen­ti al­l'al­go­rit­mo di crit­to­gra­fia uti­liz­za­to insieme ai loro hash. Tuttavia non sono complete: al loro posto si generano delle precise catene che possono essere calcolate fa­cil­men­te a partire dai valori veri e propri, riducendo così la necessità di spazio richiesto da tabelle sempre più grandi. Con le tabelle ar­co­ba­le­no si possono assegnare quindi gli hash, che sono stati trovati in un database, alle password cor­ri­spon­den­ti in un testo in chiaro.

Per capire come fun­zio­na­no le tabelle ar­co­ba­le­no, si deve conoscere almeno il fun­zio­na­men­to basilare degli algoritmi crit­to­gra­fi­ci. Così è anche più facile com­pren­de­re il vantaggio delle tabelle già pronte e il correlato compresso tempo-memoria.

Da quando nella cifratura si usano le funzioni crit­to­gra­fi­che di hash, i relativi algoritmi hanno sempre subito modifiche. Gli standard che 10 anni fa erano con­si­de­ra­ti in­vio­la­bi­li sono visti og­gi­gior­no come delle gravi in­fra­zio­ni della sicurezza. Comune a tutti è però il fatto che il contenuto da crit­to­gra­fa­re funzioni tramite algoritmi e venga generato alla fine un hash, che è di solito un numero esa­de­ci­ma­le di una lunghezza definita. Infatti in­di­pen­den­te­men­te dalla lunghezza del contenuto ori­gi­na­rio, alla fine risulta sempre un hash di 128 bit. Nella crit­to­gra­fia sono decisive quattro proprietà:

1. Lo stesso input genera sempre lo stesso hash: solo così il valore può fun­zio­na­re 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 col­li­sio­ni simili. Le funzioni di hash moderne e gli hash di lunghezza suf­fi­cien­te mi­ni­miz­za­no 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 im­pro­pria­men­te, ma si possono solo com­pren­de­re.
4. Le funzioni di hash devono essere davvero complesse, ma non troppo: per garantire la sicurezza, un algoritmo non deve lavorare troppo ve­lo­ce­men­te, perché si fa­ci­li­te­reb­be anche il lavoro degli hacker. Neanche la con­ver­sio­ne dovrebbe essere troppo com­pli­ca­ta, perché deve anche essere messa in pratica.

Gli hash compresi nelle tabelle ar­co­ba­le­no vengono creati pre­li­mi­nar­men­te, ancora prima di un attacco: gli hacker possono entrare in possesso delle tabelle ar­co­ba­le­no e uti­liz­zar­le per scoprire le password. Questi file sono però molto grandi e quindi, per evitare di superare lo spazio richiesto, le tabelle ar­co­ba­le­no si servono di una funzione di riduzione, che converte l’hash in un semplice testo. È im­por­tan­te notare che la funzione di riduzione non permette di sfruttare un pro­ce­di­men­to inverso partendo dall’hash, quindi non re­sti­tui­sce il testo semplice ori­gi­na­rio (ad esempio la password), ma uno com­ple­ta­men­te nuovo (perché il contrario non è possibile).

Da questo testo si genera di nuovo un hash. In una tabella ar­co­ba­le­no 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 in­for­ma­zio­ni e con­si­de­ran­do le funzioni di riduzione uti­liz­za­te si possono in­di­vi­dua­re 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 in­ter­me­dio con i valori presenti nella tabella.

La sfida nella creazione delle tabelle consiste nel fatto che i contenuti di partenza, che rap­pre­sen­ta­no l’inizio di una nuova catena, non devono essere già comparsi in un testo semplice di una catena pre­ce­den­te. Grazie a questa tecnica si possono diminuire no­te­vol­men­te le di­men­sio­ni di tabelle simili, anche se man­ten­go­no una mole di diverse centinaia di gigabyte.

Si parla di un com­pro­mes­so tempo-memoria se viene impiegato un tempo di ese­cu­zio­ne maggiore per uti­liz­za­re meno memoria o viceversa. Un attacco forza bruta occupa molto poco spazio, visto che i calcoli crit­to­gra­fi­ci vengono eseguiti nuo­va­men­te 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 de­ci­fra­zio­ne molto ve­lo­ce­men­te. Le tabelle ar­co­ba­le­no rap­pre­sen­ta­no un com­pro­mes­so tra i due sistemi: infatti eseguono calcoli in tempo reale, ma in misura inferiore e occupano meno spazio rispetto alle tabelle complete.

Ge­ne­ral­men­te si ha a di­spo­si­zio­ne 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 re­la­ti­va­men­te veloce, infatti ora serve solo com­pren­de­re le ri­pe­ti­zio­ni della catena e si ottiene così il risultato de­si­de­ra­to. 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 cor­ri­spon­den­te 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 ar­co­ba­le­ni. In pratica non si utilizza solo una funzione di riduzione, ma in ogni passaggio se ne usa un’altra. Questo ga­ran­ti­sce un migliore risultato nel caso della riduzione e impedisce che si ripetano gli hash nella tabella, ma ha lo svan­tag­gio che trovare delle com­bi­na­zio­ni di hash e password è un po’ più complesso nelle catene.

Così le riduzioni della serie devono essere at­tra­ver­sa­te: partendo dal pre­sup­po­sto 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 evi­den­zia­re con colori le diverse funzioni di riduzione, cosa che nel caso di molte ite­ra­zio­ni può portare a un ar­co­ba­le­no, da cui le tabelle prendono il nome.

Quanto riportato si spiega nel modo seguente: la password inserita è k; m è un mol­ti­pli­ca­to­re in­de­fi­ni­to (in questo esempio 2000). Per A si imposta so­li­ta­men­te la sezione aurea (). Modulo (mod) estrae il resto di una divisione che viene eseguita in questa funzione con 1. Le parti intere ar­ro­ton­da­no infine il risultato a un numero intero, qualora sia ne­ces­sa­rio. Il risultato finale h(k) è l’hash h per l’input k.

Visto che il nostro hash è composto da quattro cifre, lo com­ple­tia­mo all’inizio con uno 0: 0408.

In una tabella ar­co­ba­le­no per questa funzione di hash devono ora agire le funzioni di riduzione. Una pos­si­bi­li­tà molto facile di ridurre l’hash è ad esempio quella di uti­liz­za­re solo le ultime due cifre, com’è il caso della password 78 e dell’hash correlato 0408 con la riduzione 08. Qui si co­strui­sce di nuovo un hash ser­ven­do­si della funzione pre­im­po­sta­ta e così via.

La frequenza delle ri­pe­ti­zio­ni può essere scelta li­be­ra­men­te. Più una ri­pe­ti­zio­ne è frequente, meno memoria serve per la tabella ar­co­ba­le­no, anche se aumenta il tempo di ela­bo­ra­zio­ne. In questo esempio ese­gui­re­mo 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 ar­co­ba­le­no è però quello di di­mi­nuir­ne le di­men­sio­ni. Perciò in una tabella ar­co­ba­le­no 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 ar­co­ba­le­no create, sta­bi­len­do così che il valore non compare nella tabella, ma si nasconde in una catena. Di con­se­guen­za 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 ap­par­tie­ne di­ret­ta­men­te 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. Ap­par­tie­ne quindi a questo valore la password 08.

Dopo aver capito come gli hacker riescano a in­tru­fo­lar­si negli account degli utenti ri­cor­ren­do a una tabella ar­co­ba­le­no, dovrebbe essere chiaro che si devono impostare dei mec­ca­ni­smi di difesa adeguati. Sia gli utenti sia i re­spon­sa­bi­li 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 ar­co­ba­le­no, visto che il processo di de­co­di­fi­ca ri­chie­de­rà più tempo. Con la lunghezza della password aumentano anche espo­nen­zial­men­te le di­men­sio­ni delle tabelle ne­ces­sa­rie. Inoltre è utile non usare delle parole reali, ma piuttosto delle catene di caratteri casuali per impedire attacchi a di­zio­na­rio. Nella scelta di una giusta password vi possono aiutare i password manager. È però molto im­por­tan­te, in­di­pen­den­te­men­te da quale forma di attacco sfruttino gli hacker, non uti­liz­za­re la stessa password più di una volta: se qualcuno è stato capace di cor­rom­pe­re un database, di decifrare le password e di scovare i dati personali, riuscirà fa­cil­men­te ad accedere a tutti gli altri account su Internet ser­ven­do­si della stessa password.

Anche gli am­mi­ni­stra­to­ri di un server possono prendere alcune pre­cau­zio­ni per pro­teg­ge­re i loro utenti. Il primo passo sarebbe ov­via­men­te quello di non con­sen­ti­re agli hacker di arrivare ai database con gli hash. Che sia più facile a dirsi che a farsi lo di­mo­stra­no le molte vio­la­zio­ni avvenute sui server delle grandi aziende. Perciò si deve per forza pro­teg­ge­re l’hash, in­co­min­cian­do a non uti­liz­za­re degli algoritmi obsoleti.

Sia MD5 sia SHA-1 risultano da molto tempo non sicuri e le relative tabelle ar­co­ba­le­no si trovano fa­cil­men­te su Internet. Con questi algoritmi si possono scoprire le password che vengono rese come hash nel giro di pochi secondi. Perciò è in­di­spen­sa­bi­le in­for­mar­si re­go­lar­men­te sullo sviluppo di nuovi algoritmi e su quanto sia sicura la funzione di hash uti­liz­za­ta. SHA-2 e così anche la sua variante più co­no­sciu­ta SHA-256 sono con­si­de­ra­ti ancora sicuri, nel frattempo è però anche di­spo­ni­bi­le SHA-3, che promette una maggiore sicurezza.

Per strut­tu­ra­re la de­co­di­fi­ca delle tabelle ar­co­ba­le­no in modo un po’ più difficile, og­gi­gior­no si usa il co­sid­det­to salt: quando un utente sta­bi­li­sce una password, il sistema crea un valore casuale ag­giun­ti­vo, il salt. Questo valore con­flui­sce 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 con­fu­sio­ne: 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 di­zio­na­rio non vengono evitati con questo pro­ce­di­men­to, ma questa misura ag­giun­ti­va risulta efficace proprio contro le rainbow tables. Una simile tabella è creata pre­li­mi­nar­men­te sulla base di un algoritmo di hash e in­di­pen­den­te­men­te dal database che si usa. I salt non possono quindi essere contenuti nelle tabelle ar­co­ba­le­no, visto che i creatori della tabella non erano ancora a co­no­scen­za del salt.

Un altro vantaggio del salt è che gli utenti non devono se­gnar­se­lo, quindi possono essere caotici e so­prat­tut­to 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 in­se­ri­sca­no la stessa password e scrivano così anche lo stesso hash nel database. Infine il salting aiuta anche nel caso in cui gli utenti uti­liz­zi­no sempre la stessa password per diversi servizi: l’hash me­mo­riz­za­to è 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 di­zio­na­rio. Anche pepper è una sequenza di caratteri casuale che con­flui­sce 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 se­pa­ra­ta­men­te e in un luogo più sicuro.

Spesso viene uti­liz­za­ta una catena di caratteri fissa per tutte le password della piat­ta­for­ma, perciò pepper non aiuta contro il fatto che più utenti di­spon­go­no della stessa password perché uti­liz­za­no anche lo stesso pepper, cosa che porta di nuovo ad avere un hash identico. In parole povere gli am­mi­ni­stra­to­ri do­vreb­be­ro affidarsi a una com­bi­na­zio­ne composta da salt e pepper.