Mamma ho perso la password

persosottotitolo: che belle che sono le Rainbow Table

Nella mia esperienza mi son fatto convinto che la cartina al tornasole per stabilire se qualcuno passa troppo tempo davanti ad un computer è chiedere se ha mai dimenticato una password. Se la risposta è affermativa, si ha a che fare con un geek (nel mio caso ho dimenticato più volte una password!).

Mentre cazzeggiavo mi informavo sul web, mi sono imbattuto in ophcrack, un programma per crackare le password di Windows; tale programma fa uso delle cosidette Rainbow Table (d'ora in poi semplicemente RT). Il programma così com'è funziona anche per Vista, ma ha in generale alcune limitazioni: le RT incluse permettono di crackare solo password contenenti caratteri alfanumerici. Una password considerata "forte" non può essere perció crackata con la dotazione di RT del programma.

Una cosa carina è una versione LiveCD basata su Linux che una volta lanciata fa tutto da sola: carica le tabelle in memoria, individua il SAM, e in pochi minuti esegue la ricerca (10 minuti in tutto sulla mia macchina virtuale). Anche tale versione ovviamente è limitata alle password alfanumeriche. RT più complete sono in vendita un po' in giro (quella completa per coprire le password di Windows richiede 60GB di spazio su disco) ed i link sono disponibili nella pagina di ophcrack. Faccio notare che per poter crackare le password di Windows bisogna essere amministratori oppure avere accesso fisico al PC per fare il boot da CD (nel caso qualcuno voglia farsi tentare da aprire un baco).

Ma come funzionano le RT? Il meccanismo è un po' complicato e parafrasando Einstein ora che l'ho capito potrei anche spiegarlo agli altri. Nella spiegazione faccio riferimento ad un algoritmo "semplificato".

Le password vengono di solito memorizzate usando una funzione hash che data una password restituisce una stringa "complicata" (d'ora in poi semplicemente hashcode). La funzione hash non è invertibile nel senso che è impossibile trovare una semplice funzione matematica che dato un hashcode restituisca la password. Per generare le RT, viene definita una funzione reduce che dato un hashcode restuisca una nuova password (diversa da quella che ha generato l'hashcode: in parole povere la funzione reduce non è l'inversa della funzione hash in quanto l'inversa come già detto non esiste). Di tale nuova password viene generato un nuovo hashcode il quale verrà poi dato in pasto alla funzione reduce che genererà una nuova password, ecc. ecc. Il tutto per un discreto numero di volte (nell'esempio qui sotto riportato da WikiPedia l'operazione viene effettuata tre volte). In realtà in ci sono diverse funzioni reduce, una per ogni passaggio (nella figura indicate come R1, R2, R3)

 

RAINBOW TABLE1

Nell'esempio sopra si parte da password a caso (wikipedia, abcdefgh, passwd) si calcola l'hashcode corrispondente (ao4kd, 1vn6s, dicm4); poi si applica la prima funzione reduce (R1) e si ottiene una nuova password (secret, bernie, culture) e si ripete con le successive funzioni fino ad ottenere l'ultima password (rootroot, myname, linux23). Alla fine di questi semplici passaggi si memorizza nella RT solamente la password di partenza e quella di arrivo.

Nel caso di cui sopra si avrà una RT fatta in questa maniera:

wikipedia rootroot
abcdefgh myname
passwd linux23

E ora arriviamo al dunque: come si calcola la password dato un hashcode e una RT? In questo modo:

  1. prendere l'hashcode in ingresso e applicare l'ultima funzione reduce ottenendo una nuova password
  2. confronta tale password con una delle password contenute nella colonna di destra della RT
  3. se la password non esiste nella colonna di destra, applicare all'hashcode di partenza la penultima funzione reduce ottenendo una nuova password, calcolarne l'hashcode e usarlo come nuovo hashcode tornando al punto 1.
  4. se la password invece esiste, restituire al chiamante il valore corrispondente sulla colonna sinistra.

Ora se la RT è completa e l'hashcode iniziale è valido, alla fine del loop si avrà una password di partenza da dare in pasto ad un'altra funzione che prende in ingresso l'hashcode di partenza e la password trovata dalla procedura precedente, seguendo iterativamente i seguenti passi:

  1. calcolare l'hashcode della password
  2. se coincide con l'hashcode di partenza la password cercata è quella
  3. se non coincide con l'hashcode di partenza genera una password usando la funzione reduce e ricomincia da 1.

Un esempio: sia secret la password da cercare. Secondo la figura, il suo hashcode è 9kpmw; quindi l'obiettivo sarà trovare la password associata a 9kpmw.

Applicando la prima procedura con la funzione R3 otteniamo come prima nuova password pippo. pippo non è nella tabella (colonna a destra)  e quindi si itera ancora. Si applica la R2 all'hashcode di partenza ottenendo jimbo, quindi si calcola l'hashcode di jimbo che stando alla figura è v0d$x e da questo generiamo una nuova password usando stavolta R3(rootroot). In questo caso la procedura si ferma perché rootroot è presente nella RT ed è associata a wikipedia come password di partenza.

Ora tocca avviare la seconda procedura usando wikipedia e 9kpmw.

Si calcola l'hashcode di wikipedia ottenendo ao4kd. Siccome non è l'hashcode che si sta cercando, si fa un'altra iterazione. ao4kd usando la funzione reduce genera secret. Si calcola l'hashcode di secret che è 9kpmw: ovvero l'hashcode di partenza. La password cercata quindi è secret.

Con l'algoritmo vero ogni entry della tabella è generato attraverso svariate iterazioni (nell'ordine di diverse migliaia). E a complicare le cose nella realtà può accadere che la prima procedura procuri un falso positivo nel qual caso bisogna continuare ad iterare: dato un buon insieme di funzioni reduce, per generare le RT che coprono tutte le possibili password di Windows sono richiesti diversi anni calcolo. Le RT oggi disponibili sono state infatti ottenute attraverso sistemi di network computing.

La bellezza di questa tecnica è la totale indipendenza dalla funzione di hash. Quindi si può applicare per generare RT anche per altri algoritmi (MD5 ad esempio). Resta infine da dire che per invalidare l'uso delle RT basta un semplice algoritmo di salting. Tanto di cappello all'inventore di tale tecnica, Philippe Oechslin.

-enjoy

Potrebbero interessarti anche:
Commenti (18):
1. Luca
mercoledì 25 luglio 2007 alle 7:09 PM - unknown unknown unknown
   

Se non avessi letto:

"Faccio notare che per poter crackare le password di Windows bisogna essere amministratori oppure avere accesso fisico al PC per fare il boot da CD (nel caso qualcuno voglia farsi tentare da aprire un baco)."

avrei scritto:

"Esperto microsoft ammette le vulnerabilità di Windows Vista.

L'ammissione da parte di un esperto di casa Micro$oft dell'ennesima vulnerabilità di Windows sVista non è che l'ultima conferma di quanto sia sempre più indispensabile passare ad un sistema libero e aperto come Linux. Oppure a sistemi migliori come MacOS. O ancora non valga la pena di lasciare XP, se proprio ci teniamo a rimanere ostaggi di Micro$oft.

Dopo averci illustrato un bug di sicurezza da cui è evidentemente affetto anche sVista, l'esperto spiega anche quanto sia semplice rubare le password di sVista, l'unico sistema operativo moderno che non usa tecniche di salt)" Stick out tongue

Invece ho letto l'avviso per cui la domanda vera è  perché windows non utilizza un algoritmo di salt?

   
2. Paperino
mercoledì 25 luglio 2007 alle 7:24 PM - unknown unknown unknown
   

Risposta di un esperto di sicurezza (non io): legacy. Smile

   
3. amok
mercoledì 25 luglio 2007 alle 9:15 PM - unknown unknown unknown
   

l'attacco locale cessa di esistere quando il bitLocker e' attivo. Quindi avviso o non avviso, Vista resta il meglio che c'e' :-)

   
4. Luca
mercoledì 25 luglio 2007 alle 9:24 PM - unknown unknown unknown
   

Grazie per il post, è la prima volta che mi sembra di aver capito bene come funzionano le RT

   
5. Blackstorm
mercoledì 25 luglio 2007 alle 11:03 PM - unknown unknown unknown
   

Anche a me... Fondamentalmente il funzionamento è semplice... però bisogna essere malati per tirare fuori un algoritmo del genere... :)

Una domanda: ma in realtà, non basta avere accesso all'hashcode, per crackare la pwd?

   
6. Paperino
giovedì 26 luglio 2007 alle 1:39 AM - unknown unknown unknown
   

Si basta, ma con un hashcode - senza le RT - hai bisogno di anni calcolo per crackare la pwd con algoritmi di forza bruta.

Un'alternativa è quella di creare un dizionario che associ tutte le password ai rispettivi hashcode, ma richiederebbe uno spazio enorme (svariate migliaia di TB).

Le RT possono diventare il giusto compromesso tra spazio (60GB ma se si raddoppiano le reduce functions lo spazio dovrebbe diminuire _quasi_ proporzionalmente) e il tempo richiesto (nell'ordine dei minuti).

   
7. Shance
giovedì 26 luglio 2007 alle 12:14 PM - unknown unknown unknown
   

Io ho sempre resettato (non craccato) password con questo sistema:

home.eunet.no/.../ntpasswd

Accedendo al db sam locale, come da queste news del buon Daniel Petri www.petri.co.il/forgot_administrator_password.htm.

In 5 minuti con un cd di boot o floppy.

Per password di un dominio la cosa si complica, queste RT funzionano per le password di dominio? Come ci si comporta in un DC?

Ciau ciau

   
8. Stefano
giovedì 26 luglio 2007 alle 12:21 PM - unknown unknown unknown
   

E' già un pò che utilizzo il LiveCD come coltellino svizzero per risolvere il problema password che talvolta affligge i clienti.....e spesso la password che recupero è, in ordine: 1) Nome di eventuali figli\mogli\mariti, 2) Data di nascita (propria o di figli); 3)Nome della propria squadra di calcio del cuore (per i maschietti)....

Quando essa password non sia la classica blanck (che però di solito provo per prima)

   
9. Paperino
giovedì 26 luglio 2007 alle 5:21 PM - unknown unknown unknown
   

@Shance:

resettare la password porta a perdere alcuni dati criptati tramite l'hash di partenza (encrypted folders, password di outlook memorizzate, ecc.). Funziona anche con le password di domino anche se non ho capito la meccanica per ottenerne l'hash. Per le password di dominio il reset è più innocuo.

   
10. Shance
giovedì 26 luglio 2007 alle 6:30 PM - unknown unknown unknown
   

Ottimo, provo subito in bel dominio!

Grazie^^

   
11. Pr3d
domenica 29 luglio 2007 alle 5:41 PM - unknown unknown unknown
   

Beh ma ci sono molte utility che permettono il reset della password amministrativa di Windows.

Uno per esempio è l'utilizzo di BartPe (una specie di Live), si fa bootare il dvd e si avvia il sistema operativo dal supporto ottico, una volta dentro c'è disponibile un tool che permette il reset della password.

Oppure tempo fa avevo trovato anche un programmino per floppy da avviare che permetteva di selezionare qualsiasi utente e forzarne il cambio password.

   
12. Blackstorm
lunedì 30 luglio 2007 alle 9:35 AM - unknown unknown unknown
   

Uhm... non so se in vista questi tool funzionano ancora...

   
13. ViK
giovedì 23 agosto 2007 alle 10:57 AM - unknown unknown unknown
   

Esiste qualcosa del genere anche per MacOs?

P.S.= l'idea dell'algoritmo è semplicemente geniale a mio avviso...

   
14. Paperino
lunedì 27 agosto 2007 alle 3:20 PM - unknown unknown unknown
   

Non esiste. MacOs -> *nix -> Password Salting. A spanne nessuna possibilità di usare le rainbow tables.

   
15. ViK
martedì 28 agosto 2007 alle 11:24 AM - unknown unknown unknown
   

Peccato... E qualcosa altro k non siano le rainbow table?

   
16. Paperino
mercoledì 29 agosto 2007 alle 1:54 PM - unknown unknown unknown
   

@ViK: jack the ripper, di cui però non conosco dettagli implementativi. Con questo su un 486 recuperai una decina di password nel giro di poche ore.

   
17. Blackstorm
mercoledì 29 agosto 2007 alle 2:49 PM - unknown unknown unknown
   

Uhm... Jack the ripper era molto carino, ma attualmente non credo sia in grado di reggere il passo con i moderni algoritmi... almeno, non la versione che ho io...

   
18. .:Mik:.
martedì 16 ottobre 2007 alle 10:46 PM - unknown unknown unknown
   

Mi sapete dire dove trovare jack the ripper? è freeware?

   
Lascia un commento:
Commento: (clicca su questo link per gli smiley supportati; regole di ingaggio per i commenti)
(opzionale, per il Gravatar)