Password cracking tramite Rainbow Tables

Abbiamo appena installato una nuova copia del nostro Windows, spendendo ore di lavoro per aggiornarlo con quel cumulo di patch comunemente detto Windows Update; scelta una robusta password alfanumerica cediamo a Morfeo, sicuri che il nostro sistema sia inviolabile.
Sicuramente molti si riconosceranno in questo esempio in cui si susseguono ore e ore spese per installare, configurare e aggiornare un sistema. A protezione del nostro lavoro poniamo diligentemente una password di dieci o più caratteri che ricordiamo a fatica perchè, consci di quanto sia rapido violare una password comune, abbiamo scelto una stringa difficile quale
%%3N1rvAn@!-- Un buon lavoro, meritorio di un giusto riposo; eppure questo sistema soffre di una debolezza che ne rende le password prone a un rapido cracking. In questo articolo discuteremo il password cracking tramite rainbow tables, una tecnica che permette di velocizzare il cracking di credenziali di certi sistemi di diversi ordini di grandezza, presentandone le peculiarità e i limiti.
Password e Hash

Prima di tutto, riflettiamo un attimo su come vengono generalmente memorizzate le nostre password: ovviamente non è desiderabile che queste informazioni sensibili siano conservate in chiaro pertanto tipicamente si preferisce utilizzare algoritmi di hashinghash). che codificano le nostre password mediante funzioni matematiche non invertibili. Per coloro digiuni di analisi matematica, si ricorda che una funzione non invertibile è un'associazione tra due oggetti per cui non è possibile ottenere il dato di partenza tramite il solo risultato; riportato al nostro caso significa che non è possibile ottenere la password possedendo solo il valore generato dall'algoritmo di hashing (detto
Sebbene molti pensino il contrario, un hash è tutt'altro che univoco e, al contrario, esistono infiniti valori che producono lo stesso hash; tuttavia in un buon algoritmo di hashing la probabilità che si trovino due stringe che producano lo stesso hash è minima, un valore infinitesimale, giustamente (in senso statistico) approssimabile a zero. Questo comporta che individuare una stringa che è codificata nello stesso hash in cui è codificata la nostra password è assolutamente improbabile.
Quando digitiamo la nostra password viene ricalcolato l'hash, mediante lo stesso algoritmo, ed è questo valore e non la password ad essere confrontata. In tal modo possiamo tranquillamente mantenere su file i nostri hash, sicuri che tra le centinaia di migliaia di miliardi di combinazioni possibili la nostra password sia inviolabile. Ovviamente un attacco che miri ad esaurire tutte le possibilità (detto "spazio delle chiavi") arriverà indubbiamente a trovare una stringa capace di produrre il nostro stesso hash ma, da quanto appena detto, la nostra assicurazione è che le combinazioni sono in numero tale da non permettere questa operazione in tempi ragionevoli.
Rainbow Tables

Introduciamo le rainbow tables; l'idea fu concepita negli anni ottanta dal matematico americano Martin Hellman, ma ha avuto la sua vera diffusione attraverso i successivi studi di Philippe Oechslin.
Alla base vi è una considerazione piuttosto semplice e intuitiva: "perchè calcorare ogni volta tutte i possibili hash sino a ricavarne uno che corrisponda alla password cercata?" Se avessi anzitempo calcolato e memorizzato ogni possibile combinazione in una sorta di elenco telefonico dell'algoritmo, potremmo in maniera più agile eseguire una ricerca nell'archivio e trovare l'hash giusto. Difatti il costo di un password cracking è principalmente funzione del calcolo degli hash, che ricordiamo essere prodotto di complessi algoritmi matematici; rispetto a quest'ultimo, il confronto tra stringhe per determinare se l'hash (la fase di ricerca) è corretto costituisce un costo temporale irrisorio.
Accettata questa idea, sussiste un solo problema: un archivio tale da esaurire lo spazio delle chiavi di un algoritmo degno di questo nome sarebbe nell'ordine delle centinaia di terabyte (1 terabyte = 1024 gigabyte); un comune elaboratore non possiede nè sufficiente memoria nè sufficiente potenza per analizzarla.
L'idea di Oechslin

Philippe Oechsin, un esperto in sicurezza informatica, ha ideato un procedimento per ridurre un archivio di hash in una tabella molto decisamente più piccola e manegevole. Non è scopo di questo articolo illustrare in modo dettagliato le funzioni matematiche alla base di questa tecnica: per tali approfondimenti si rimanda al documento originale dell'autore. In questo contesto forniremo solo una semplificata idea di come funzioni il procedimento. Coloro che non avessero particolare dimestichezza con i concetti matematematici proposti a seguire possono, senza indugiare e senza pena, saltare al paragrafo successivo.
Iniziamo calcolando l'hash corrispondente alla nostra password; ora, definiamo una formula di riduzione R tale che converta un hash in una stringa appartenente ad un certo insieme prestabilito (stringhe alfanumeriche di otto caratteri, stringhe con punteggiatura di sei caratteri, ecc...). Ovviamente il valore generato non sarà la password di partenza in quanto abbiamo già ribadito l'impossibilità di invertire una funzione di hashing. Iterando k volte il procedimento genereremo una catena "password -> hash -> password -> hash" di migliaia di elementi. Tra tutti questi, memorizziamo su disco solo il primo e l'ultimo: in tal modo abbiamo ottenuto un risparmio di memoria pari a k volte. Per coloro con qualche appetito matematico, la formula a seguire determina la nostra serie:

ovvero, come descritto, la password al passo i+1 è il risultato della formula di riduzione i-esima applicata all'i-esimo hash. Avendo eseguito questo procedimento t volte con t funzioni di riduzione R diverse, abbiamo a disposizione t coppie di valori, attraversabili tramite una catena, generata dalla funzione f; quando desideriamo trovare la password corrispondente ad un hash, possiamo semplicemente applicare al nostro dato la funzione f e controllare che il risultato non sia presente nella lista di coppie memorizzate. Se così non fosse, continuiamo ad iterare la funzione f sintanto che il risultato non corrisponda con uno dei nostri valori.
Per chi avesse perso il punto della situazione, stiamo semplicemente attraversando le catene di valori partendo da un punto a noi ignoto. Applicando iterativamente la funzione, ricostruiamo la catena partendo dal nostro hash sino ad arrivarne al capo; ottenuto questo risultato, la catena a cui appartiene quest'ultimo elemento (che noi abbiamo memorizzato) è una candidata ideale a contenere la nostra password. Visto che possediamo anche il primo elemento della catena, possiamo applicare la nostra funzione sino a giungere al valore precedente il nostro hash. Per come è generata la catena stessa, questo è probabilmente la password cercata (o una stringa che genera il medesimo hash); possiamo verificarlo calcolandone l'hash. Questo metodo genera raramente falsi positivi, dovuti essenzialmente a come la formula di riduzione R genera il prossimo elemento della catena.
Tralasciando altri difficili dettagli matematici, per i quali i volenterosi troveranno ampie risposte nell'articolo originale di Oechsin, questo procedimento permette di ridurre esponenzialmente il tempo di ricerca e lo spazio in memoria delle tabelle (in particolare, il tempo di computazione si riduce col quadrato della grandezza della tabella).
Servizi online

Chi ancora non ha ceduto, giungendo sino a questo punto, si sarà forse domandato come generare queste tabelle in quanto il tempo necessario a codificarle corrisponde, essenzialmente, a quello richiesto ad esaurire uno spazio delle chiavi con caratteristiche prestabilite (alfanumerici, con simboli, ecc...). Effettivamente realizzare buone tabelle con computer domestici è un'impresa non semplice e nemmeno particolarmente sensata: spendere qualche anno per realizzare una tabella che copra le sole password di otto caratteri alfanumerici non è un'idea così brillante. Fortunatamente la rete è pervasa di cluster di macchine utilizzabili per il calcolo parallelo, tali da ridurre il tempo per generare ottime tabelle in pochi mesi; sono disponibili servizi online di generazione e di ricerca per i più noti algoritmi (ad es. LM, NTLM, MD5, SHA1) sia in forma gratuita che a pagamento. Ad esempio, uno studio ha evidenziato la potenza del password cracking tramite calcolo parallelo sfruttando il servizio cloud di Amazon; un punto di riferimento per tutti coloro che volessero iniziare a provare queste tecniche rimane indubbiamente Free Rainbow Tables.
Una semplice difesa

Svelato il problema ci rimane da discutere una soluzione. Per iniziare vale sempre la pena ricordare le regole di base per una password sicura: almeno otto-dieci caratteri che utilizzino combinazioni di caratteri alfanumerici maiuscoli, minuscoli e simboli. Contro le rainbow tables serve però ancora qualcosa in più, in particolare è possibile utilizzare una tecnica in uso sui sistemi Unix e derivati da oltre 25 anni: le salt password, letteralmente "password salate".
Alla base delle salt password, un'idea che combina semplicità e perspicacia: prima di computare l'hash di una password, le si aggiunge un insieme di bits casuali (bits di salt). Questi bits possono essere ricavati da qualsiasi sorgente quali username, data o dal clock. Calcolatone l'hash, si riaggiungono in chiaro tali bit, divisi da dei marcatori che permettano di identificarli. Ad esempio:
Password: NuVoLoSo Salt prescelto: cX Stringa da codificare: cXNuVoLoSo Hash: ZT�Z�NbTL�)�E? Stringa memorizzata: cXZT�Z�NbTL�)�E? Il vantaggio di tale tecnica è evidente, a salt differenti corrispondono hash differenti per password uguali. Questo vanifica la la tecnica delle rainbow tables o di altri dizionari di hash precompilati. Un evenutale aggressore dovrebbe calcolare tante tabelle per tutte le combinazioni dei bits di salt, mentre ogni bit duplica la grandezza dell'archivio e il tempo necessario a realizzarlo.
A titolo di esempio, i primi sistemi Unix utilizzavano un salt a dodici bit unito all'algoritmo DES (Data Encryption Standard): questo significa che ogni password aveva 2^12 = 4096 combinazioni; nei sistemi moderni si utilizzano tipicamente dai sedici ai sessantaquattro bits. Tale stratagemma espande evidentemente in modo inaccettabile la grandezza delle tabelle.
Seppure la contromisura sia semplice e poco costosa, molti sistemi ancora non la implementano. Tra questi sicuramente troviamo la famiglia si sistemi operativi Microsoft Windows ma anche molti software applicativi quali PHP e MySQL; in questi casi un attacco tramite rainbow tables risulta terribilmente efficace.
Conclusioni

Considerare il proprio sistema protetto solo perchè si dispone di un performante sistema operativo, aggiornato e dotato di firewall e antivirus, è semplicemete una chimera. Ovviamente questi aspetti sono prioritari e non devono essere tralasciati ma la sicurezza informatica è un processo che va ben oltre questi aspetti.
Oggigiorno, con l'enorme incremento di potenza di calcolo esprimibile da CPU e (soprattutto) GPU, il concetto di password cracking ha ripreso deciso vigore, sia esso effettuato in brute force che tramite rainbow tables. Una basilare conoscenza dell'argomento aiuterà quantomeno a riflettere sull'intrinseca insicurezza delle password a cui abitualmente ci affidiamo
Approfondimenti e riferimenti