Prima di tutto un’introduzione: a parte il titolo colorito, questa rubrica vuole spiegare in poche semplici parole alcuni argomenti su cui i giovani (talvolta neanche troppo) che si avvicinano al mondo dell’informatica hanno le idee un po’ confuse.
L’informatica è un mondo affascinante, ma bisogna coglierne il fascino, come in qualunque disciplina. Spesso ci si innamora di aspetti che non esistono, e si rimane delusi prima di scoprire quelli belli davvero. Spero che queste righe servano a qualcuno per scoprirli prima possibile.
Ma veniamo all’argomento di oggi, le rainbow table.
L’hashing
Uno dei problemi con cui ci si scontra quando si scrive un software che richiede una forma di autenticazione è quello di dover memorizzare password nel modo più sicuro e affidabile possibile. Una soluzione estremamente diffusa è l’utilizzare funzioni di hash.
Una funzione di hash è una funzione che, data una stringa di qualunque lunghezza (anche nulla) restituisce in output una stringa di lunghezza sempre uguale. Data una certa stringa, una funzione di hash ritornerà sempre la medesima stringa di lunghezza fissa.
Una funzione di hash, quindi, permette un meccanismo piuttosto semplice: invece di salvare una password, si può salvare l’hash della password. Quando l’utente proverà a fare di nuovo login, invece di controllare se la password corrisponde, basterà vedere se l’hash della password corrisponde.
Ad esempio, l’utente sceglie “pluto” come password. Invece di salvare “pluto” sul mio database, applico la funzione md5, una diffusa funzione di hash, alla stringa “pluto”, e salvo il risultato. La funzione md5 genera stringhe lunghe 32 caratteri nella loro rappresentazione esadecimale. In particolare, l’hash di “pluto” è “c6009f08fc5fc6385f1ea1f5840e179f”.
Quando l’utente proverà a rifare login, inserirà la sua password, e il programma gli applicherà di nuovo la funzione md5, che darà come risultato di nuovo “c6009f08fc5fc6385f1ea1f5840e179f”, e sarà possibile dire che la password è corretta.
I pregi dell’hashing
Il più grande pregio delle funzioni di hashing è il loro essere suriettive ma non biiettive. Come abbiamo visto, data una stringa si ottiene sempre lo stesso hash, ma non è possibile in alcun modo fare l’operazione inversa, perché si tratterebbe di un problema con infinite soluzioni.
Se qualunque stringa viene trasformata in una stringa sempre lunga uguale (con l’md5, per esempio, l’hash della stringa vuota e quello di “pedissequamente”, così come quello di qualunque parola, frase o romanzo in versi, sarà sempre 32 caratteri), esistono più stringhe che hanno il medesimo hash. Ne esistono, ai fatti, infinite (questa cosa andrebbe dimostrata ma potete abbastanza fidarvi).
La motivazione è abbastanza evidente. Le stringhe che si possono creare sono infinite, anche solo per il fatto che possono essere lunghe quanto si vuole. Le stringhe lunghe 32 caratteri in esadecimale, invece, sono “poche” (, non pochissime ma assai meno che infinite). A ognuna delle “poche” stringhe hash dovranno corrispondere parecchie delle stringhe lunghe quanto voglio.
Questo impedisce tecnicamente di risalire a una password venendo in qualche modo a sapere il suo hash. Una gran comodità. E il tutto avviene senza dare il più ovvio dei problemi di sicurezza: è un numero non infinito ma comunque molto grande, ed è “praticamente impossibile” che due password “sensate” abbiano lo stesso hash. Insomma, tirando a indovinare la data di nascita della persona non becchi casualmente una password che funziona anche se non è la sua. Ci sono algoritmi di hash che generano stringhe assai più lunghe, che abbassano ulteriormente questa possibilità.
I difetti dell’hashing – le rainbow table, finalmente
Chi di voi ha un minimo di mentalità logica, avrà già capito che il pregio è anche un gran difetto. è un numero finito, e qualunque altra funzione di hashing avrà un numero finito di risultati.
Molti di voi conosceranno il concetto di attacco “brute force”: provare tantissime password finché non si indovina quella giusta. La memorizzazione di password come hash permette di semplificare molto questo tipo di attacchi.
L’idea è semplice: se devo rompere delle password memorizzata come hash md5, posso farmi una tabella con tutti i possibili hash associando ad ognuno una stringa che lo genera. Non è un’operazione comodissima, ma si può fare una volta per tutte. Una volta che ho uno strumento del genere, posso provare una dopo l’altra tutte le stringhe, e almeno una dovrà funzionare per forza.
Questo tipo di tabella, opportunamente ottimizzata per non fargli occupare una quantità di spazio enorme (ricordiamo che già è un numero grande e ci sono funzioni di hash migliori), si chiama rainbow table.
Una rainbow table, insomma, è un elenco di “tutte le password possibili” per un dato algoritmo di hashing.
Specifici algoritmi di hashing possono avere ulteriori grandi e piccoli difetti, che qui non tratto.
Le contromisure
La più ovvia contromisura alle rainbow table è l’utilizzo di algoritmi di hashing che generano stringhe più lunghe, ma è una contromisura temporanea. Prima o poi lo spazio su disco necessario a contenere rainbow table di algoritmi migliori diventa alla portata di chiunque, specialmente considerato che grazie ai sistemi di ottimizzazione non è mai necessario moltissimo spazio.
Una misura molto più efficace è il cosiddetto salt, o sale. L’idea è semplicissima: prima di calcolare l’hash di una password, posso aggiungere alla password stessa una stringa casuale, da salvare assieme alla password, che viene appunto detta salt. In questo modo non memorizzo l’hash della password, ma quello di una sua versione modificata.
Quando l’utente vorrà fare login, posso andare a vedere quale fosse il salt applicato alla password originalmente, accodarlo alla password che sta usando e vedere se l’hash corrisponde.
Quando qualcuno tenterà un attacco rainbow table, invece, fallirà, perché come abbiamo detto le rainbow table non contengono (e non possono contenere) le vere password, ma contengono delle stringhe che hanno lo stesso hash e che è molto improbabile coincidano con la vera password.
Facciamo un esempio semplice. La mia password è “ciao”. il sistema ci aggiunge in coda una stringa casuale, per esempio “dfkjf”, calcola l’hash di “ciaodfkjf” e lo salva assieme a “dfkjf” nella lista delle password. Un attaccante trova una password che ha lo stesso hash di “ciaodfkjf”, e tenta di usarla. La password, però, non sarà “ciao”, perché “ciao” ha un hash diverso, e accodata al salt “dfkjf” non funzionerà.
Ovviamente si possono fare rainbow table che contengano tutti i possibili salt, dato che ogni sistema utilizzerà necessariamente una stringa casuale di lunghezza finita, ma ogni bit di lunghezza del salt raddoppia la dimensione della rainbow table. Basta un salt relativamente breve per rendere la tecnica virtualmente insostenibile.
Le rainbow table hanno senso nel 2020?
Questa è una domanda difficile. La risposta che darei è “poco”. Nella mia carriera di programmatore, prima hobbista e poi professionista, ho visto cose davvero orride in posti dove decisamente era bene non fossero, ma avviene sempre meno. La diffusione di framework di sviluppo robusti e di un minimo di cultura della sicurezza, sta facendo sì che gli algoritmi di hash più deboli (il citato md5, di infima robustezza, era utilizzatissimo per le password un tempo) non vengano più usati, o vengano usati quantomeno con il salt.
Oggi la maggior parte degli sviluppatori e dei framework utilizzano bcrypt, un algoritmo di hashing piuttosto complesso, che utilizza molte diverse misure di sicurezza, tra le quali l’aggiungere già di per sé un salt alla password.
Insomma, per quanto di schifezze se ne trovino, è abbastanza difficile che un attacco rainbow, oggi, serva a qualcosa.
Conoscerle, però, è utile. Si tratta infatti di un classico e istruttivo esempio di hacking, ovvero dell’arte di trovare soluzioni intelligenti ai problemi. Utilizzare grandi quantità di memoria, relativamente economica e disponibile, al posto della potenza di calcolo è un esempio di soluzione intelligente.
