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.

A che cosa servono le tabelle arcobaleno?

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.

Consiglio

Non utilizzate dei termini semplici per le vostre password perché rendete la vita più facile agli hacker. Nel nostro articolo sulle password sicure scoprite come si dovrebbe creare una password.

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.

Come funzionano le tabelle arcobaleno?

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.

Tecnica di crittografia

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

Gli hash non si usano solo per crittografare le password. Le funzioni servono ad esempio anche come checksum per programmi completi: gli algoritmi generano dall'intero codice sorgente un hash. In questo modo può essere ad esempio garantito che la versione del programma scaricata da Internet sia identica all'originale e non sia stata sostituita da un malware.

Funzioni di riduzione

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.

Compromesso tempo-memoria

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.

Processo nelle tabelle arcobaleno

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.

Che nesso c’è tra le tabelle e gli arcobaleni?

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 R1, R2, R3, si comincia prima di tutto la ricerca con la funzione R1. Se non ci sono risultati, si ricorre prima all’R2, poi all’R3, 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.

Le tabelle arcobaleno spiegate con un esempio

Le tabelle arcobaleno si comprendono meglio se si affronta il procedimento con un esempio. Tuttavia non utilizziamo nessuna delle funzioni di hash conosciute per la sicurezza delle password, perché sono troppo complesse per essere applicate a esempi semplici. Ci serviamo così di una funzione molto più facile, chiamata metodo moltiplicativo:

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.

N.B.

Se volete provare questa funzione su Excel, potete utilizzare la funzione ARROTONDA.DIFETTO per arrotondare e la funzione RESTO per Modulo. Quindi: =ARROTONDA.DIFETTO (RESTO(A1*0,618;1)*2000;1)

Usiamo come possibili password una serie di caratteri composta solo da due cifre, quindi da 00 a 99. Così la tabella ha dei limiti ben definiti e le lettere dovrebbero essere trasmesse ugualmente con valori numerici. Per la password 78 risulta quindi valido:

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

Password Hash
zero zero
01 1236
02 0472
03 1708
78 0408
99 0364

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.

p1 h1 p2 h2 p3 h3 p4 h4
zero zero zero zero zero zero zero zero
01 1236 36 0496 96 0656 56 1215
02 0472 72 0992 92 1712 12 0832
03 1708 08 1888 88 0768 68 0048
04 0944 44 0384 84 1824 24 1664
05 0180 80 0879 79 1644 44 0384

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 ilmargine sinistro e destro della tabella. Tutti gli altri valori vengono desunti.

p1 h4
zero zero
01 1215
02 0832
03 0048
04 1664
05 0384
06 1260
07 0656
09 0944
10 0607
11 0539
13 0607
14 1824
17 0272
18 0651
19 1104
20 1664
21 0204
22 1552
25 0944
26 1215
27 0832
29 1664
30 0384
31 1260
33 0272
34 0944
37 0992
38 0656
39 1824
40 1440
41 0159
42 0272
43 0651
45 1824
46 0204
47 zero
49 0384
50 zero
53 0048
54 1664
55 0384
57 0656
58 1328
59 0651
61 0539
62 0992
63 0656
65 1440
66 zero
69 1104
70 1664
71 0204
73 1712
74 0384
77 0832
78 0048
81 1260
82 1712
83 0272
85 0428
86 1484
89 1824
90 0384
93 0700
94 1552
95 1824
97 1552
98 1036
99 0384
N.B.

In questo esempio le dimensioni delle tabelle arcobaleno rispetto a quelle originarie sono diminuite solo di poco, dato che sono presenti ora 140 record contro i 200 iniziali. Ciò dipende dalla mole inferiore in generale, dalle funzioni di riduzione e di hash meno complesse, oltre che dal numero basso delle riduzioni. Questa tabella arcobaleno rimane quindi un esempio adatto.

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.

Misure contro le tabelle arcobaleno

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.

Utenti

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.

Amministratori

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.


Un momento! Prima di lasciarci scopri
la nostra offerta per il rientro dalle ferie:
dominio .it a 1 € per il primo anno!

Primo anno a 1 € IVA escl.,
poi 10 €/anno IVA escl.

Inserisci il dominio desiderato nella barra di ricerca per verificarne la disponibilità.