RAINBOW TABLES: Cosa sono?

[Nirvana1289]

Premesse

Il post

Crack di una wpa di un Router Alice

ha ispirato l'apertura di questo thread. All'inizio ho provato a spiegare lì cosa sono le rainbow tables, ma su richieste esterne ho deciso di approfondire la spiegazione dell'algoritmo e soprattutto dare a questo importante argomento una sezione sufficientemente ampia.

questo non è un tutorial, ma un solo un thread esplicativo teorico, per l'utilizzo vi rimando alle tante guide per coWPAtty presenti nel forum

un ringraziamento particolare a cancrena che mi ha permesso di capire come spiegare questo abbastanza complicato sistema di decifrazione forzata.


Premesse matematiche

Per capire qualcosa dobbiamo avere bene in mente alcuni concetti matematici di base.

Funzione
Una funzione trasforma una/delle variabili in ingresso in un risultato in uscita. come notazione utilizzerò:

Funzione (input) = output

Applicazione lineare
Una applicazione lineare è una funzione che partendo da un solo input, genera un output formato due o più funzioni normali, in questa maniera:

ApplLineare (input) = [ Funz1 (Input, Funz2 (Input, - - - , FunzN (Input ] = output

(a tutti quelli che si offenderanno per questa definizione: scusate ma mi serviva il concetto, non posso essere troppo rigoroso... so che in realtà quelle che uso non sono apllicazioni lineari ma così posso farmi capire...)

Funzioni reversibili e irreversibili

Una funzione si dice reversibile quando esiste una funzione inversa tale che:
Se

Funzione (input) = output

allora

FunzInversa (output) = input

Se questo non accade allora la funzione si dice irreversibile, cioè non esiste un modo per recuperare l'input che ha determinato l'output.

Gli Hash

Quando inseriamo una password (xxxxx) in un sito per il login, essa deve esser inviata ad un server per poter essere comparata con un database dove sono salvate tutte le password. A questo punto ci troviamo di fronte a due enormi buchi di sicurezza:
- la password inviata in chiaro potrebbe essere facilmente sniffata;
- il database delle password potrebbe essere facilmente rubato mediante un attacco (DoS per esempio, tipo dopo un buffer overflow)
Per risolvere questi due problemi ci vengono incontro le funzioni crittografiche (come MD5 o SHA-1 ecc.) e il Web2.0 con le pagine php. Se noi includiamo nella pagina sul client un piccolo script php che sia in grado di trasformare in maniera irreversibile la nostra stringa xxxxxx (la password) in una stringa a lunghezza fissa [HASH o Digest dell'Hash], dalla quale non si sia più in grado di risalire alla password iniziale e creare sul server un database di tutti questi hash abbiamo risolto i due problemi di sicurezza. Anche se si sniffasse l'hash, esso non potrebbe essere ritrasformato nella password iniziale.

Esempio pratico:
Password: backtrack
Hash MD5: 5E28850DE5A33B62119108CCAF35A157

Cioè scritto sotto forma di funzione:

MD5(backtrack) = 5E28850DE5A33B62119108CCAF35A157

Cosa sono le RAINBOW TABLES?

Sono delle tabelle di associazione per ottenere delle chiavi crittografiche (nel nostro caso le pass wep o wpa o wpa2) riducendo in maniera significativa la necessità di risorse di sistema e di tempo.

La caratteristica principale di queste tabelle è che possono essere utilizzate unicamente per degli attacchi contro le hash delle password.

Le rainbow tables sono formate da righe (dette catene) e colonne. Nel nostro esempio, supponiamo di avere una tabella di M righe e N colonne

Come si generano le RAINBOW TABLES?

Le catene sono legate tra loro da una relazione simile ad una applicazione vettoriale, dominata da due tipi principali di funzioni irreversibili:

• Funzione Hash:
  Simbolicamente la indichiamo come:
  
  
  Hash(password)
  
  La funzione di hash è sempre uguale in tutta la rainbow tables
• Funzione Riduzione:
  La funzione di riduzione è ciò che contraddistingue le rainbow table, infatti sono delle funzioni che da un Hash genrano una stringa. Tale stringa non ha nulla a che fare con la password che ha generato l'hash. Simbolicamente lo indichiamo:
  
  
  R[x]( Hash(password) ) = stringa
  
  dove [x] è un indice numerico (1, 2, ecc.) che ci permetterà di contraddistinguere due funzioni di riduzione diverse, infatti ci sono diverse funzioni di riduzione nelle rainbow tables, tante quante sono le colonne, quindi N-1.

Cerchiamo ora di capire come sono collegate tra loro i vari termini di una catena.

1. Da una prima password A1, che è il primo elemento della catena, si genera un hash:
   
   
   Hash(A1) = H1
2. Dal H1, mediante una una funzione di riduzione, si ottiene una nuova password A2, che diventerà il secondo elemento della catena:
   
   
   R1 ( Hash(A1) ) = R1 ( H1 ) = A2
3. Il processo riprende ciclicamente: la password A2 viene sottoposta ad Hash:
   
   
   Hash( R1 ( Hash(A1) ) ) = Hash(A2) = H2
4. Mediante una nuova funzione di riduzione si genera una nuova password
   
   A3 che sarà al terzo posto della catena:
   
   R2 ( Hash( R1 ( Hash(A1) ) ) ) = R2 ( Hash(A2) ) = R2 ( H2 ) = A3
5. - - -
6. Il processo continua fino alla generazione di AN password differenti.
   
   
   AN = R(N-1) ( A(N-1) )

In definitiva abbaimo ottenuto una catena così composta:

A1 A2 A3 - - - AN

Questa catena altro non è che una applicazione lineare irreversibile del tipo:

Catena(A1) = [ A1 , R1 ( Hash(A1) ) , R2 ( Hash ( R1 ( Hash(A1) ) ) , - - - , AN ]

Questo tipo di applicazione è eseguita su una password B1, in questo modo otterremo una nuova catena da inserire sotto la precedente

Come sono legate tra di loro le colonne? La risposta è semplice: ad ogni colonna è stata applicata un solo tipo di funzione di riduzione:

1. Alla prima colonna non è associata alcuna funzione di riduzione
2. Alla seconda colonna è associata la funzione di riduzione R1
3. alla terza colonna è associata la funzione di riduzione R2
4. - - -
5. Alla N-esima colonna è associata la funzione di riduzione R(N-1)

Quindi possiamo visualizzare la tabella come una cosa del tipo:

§R R1 R2 R3 - - - R(N-1)
§1 A1 A2 A3 - - - AN
§2 B1 B2 B3 - - - BN
- - - - - - - - - - - - -
§M Z1 Z2 Z3 - - - ZN

(scusate per la tabulazione...)

Questa è la rainbow table.

[Nirvana1289]

- 2 parte -


Come si scovano le password da un hash di una password con le RAINBOW TABLES?

1. Ottenuto l'hash di una password (che chiameremo Digest), su di esso si esegue la Funzione di Riduzione R(N-1) dell'ultima colonna N per ottenere una stringa StringN.
   
   
   R(N-1) ( Digest ) = StringN
2. StringN viene confrontata con tutte le password della colonna N, da AN a ZN.
3. Se StringN è diversa da tutte le password della colonna N, si ritorna alla hash iniziale Digest, sulla quale si esegue la funzione di riduzione R(N-2), la nuova stringa String(N-1)
4. Si esegue la funzione
   
   
   String(N-1) = R(N-2) ( Hash ( (String(N) ) )
   
   e in seguito si riprende il confronto con le voci della tabella:

• Se il test fallisce nuovamente si eseguono 3 riduzioni, 4 riduzioni, ecc. e così via fino a quando non si ottiene un confronto valido. Se compiute tutte le N-1 riduzioni non si è ottenuto nessun confronto valido, allora la procedura fallisce completamente: la rainbow table non è in grado di reperire la password.

1. Se il test ottiene un confronto valido, la password viene recuperata all'inizio della catena che ha prodotto la collisione di una password della rainbow table e della StringX

Un esempio pratico

Bisogna osservare questa immagine per capire, in quanto farò riferimento ad essa:


Immagine esempio

1. Partendo dall'hash rex3s si computa l'ultima funzione riduttiva usata nella tabella R3 e si controlla se la password appare nell'ultima colonna della tabella.
2. Se il test fallisce ("rambo" non appare nella tabella), si computa una catena cn le due ultime riduzioni.
   • Se il test fallisce ancora, si continua con 3, 4 riduzioni, fino a quando non si trova la password. Se nessuna catena contiene la password allora l'attacco fallisce
3. Se il test è positivo ("linux32" appare alla fine della catena di riduzioni E in una colonna della tabella), la password si trova all'inizio della catena che ha prodotto "linux32". Qui all'inizio catena salvata nella tabella corrispondente troviamo "passwd".
4. A questo punto, si genera una catena e si comparano ad ogni iterazione, gli hash con l'hash iniziale rex3s. Il test diviene valido se troviamo rex3s nella catena. La password corrente "culture" è quella che produce l'intera catena: il suo hash è rex3s: l'attacco è riuscito.

Vantaggi e svantaggi
Questo algoritmo riduce di molto il tempo di individuazione di una password e migliora automaticamente la complessita del dizionario. Inoltre nel caso delle wpa è facile costruirle basandosi sugli algoritmi di calcolo delle aziende distributrici. Anche se non si individua con precisione un solo algoritmo si possono creare rainbow tables con più algoritmi possibili e aumentare le probabilità di scovare una wpa.

il problema è che per creare una rainbow table bisogna possedere un sistema particolarmente potente. Tutto quello che si perde nel ritrovare la password lo si riguadagna nel calcolo di questo particolare tipo di "dizionario". è praticamente impossibile per un sistema standard creare una rainbow tables utilizzabile.
Inoltre le rainbow tables sono particolarmente deboli a tecniche di Salting, ossia alla aggiunta, in fondo alla password, di simboli lettere o numeri a caso.

Spero di essere stato abbastanza chiaro, sono disponibile per chiarimenti.

Ciao a Tutti

Nirvana1289@Ana7h3ma#

[brigante]

ma questa è la sezione giusta infatti....

intendevo dire che alla fine una volta terminato il tutorial lo sposterò nella sezione tutorial, ma questa è comunque la sezione giusta, nessun problema.

[edit]

### MOVED ###

[edit]

[tex63willer]

Volevo solo fare i complimenti a Nirvana per l'ottima iniziativa. Grazie

[B@Rz-]

Originally Posted by dpmika

beh quindi anche con queste rainbow se volessi trovare la mia wpa del router alice che è quella di default non la troverei mai?

"mai" e' una parola abbastanza grossa...
certo che puoi trovare la tua password dalle rainbow tables, basta che tu ti generi delle rainbow tables appropriate...

prova a dare un'occhiata alle funzioni di airolib-ng.

dato che le chiavi wpa/wpa2 vengono criptate fondendo password e essid, le rainbow tables che andrai a creare dovranno contenere sia la tua essid sia un dizionario che contenga la tua password.

tieni presente che per un dizionario "abbastanza" grande e' necessario un tempo per generare le rainbow tables "abbastanza" lungo, quindi non ha molto senso crearsi una RT per un singolo essid. a quel punto conviene usare semplicemente il dizionario puro, magari velocizzando la ricerca con CUDA (un saluto a keeley ha fatto una bella guida). in pratica il tempo che perdi per generare la rt non riesci a riguadagnarlo con gli incrementi di velocita' nella ricerca di password.

l'utilizzo delle rainbow tables e' invece mooooolto utile quando cerchi password di router che hanno ancora l'essid di default lasciati della casa produttrice, ad esempio SITECOM, NETGEAR, CISCO ecc, magari perche' stai facendo wardriving in qualche paese del mondo in cui sia ancora legale. questo perche' ti puoi generare tranquillamente le rainbow tables dal cluster di casa tua (o magari scaricarti quel bel pacco da 32GB gia' renderizzate da renderman con 1000 essid). A quel punto se l'essid sta tra quei 1000, in pochi minuti puoi analizzare una wordlist di (mi pare) una 20-ina di milioni di password con cui renderman ha fatto il rendering.

ps:
complimenti e grazie a nirvana, nel forum internazionale qualche tempo fa (forse anche adesso) c'era un continuo spam di persone che chiedevano chiarimenti sull'argomento!

[darkstar89]

Ciao, mi scuso ma non ho capito come usare le RAINBOW TABLES ..
Io ho gli handshake, ho provato a fare l' md5sum dell' handshake, e guardare se mi dava la passwd tra i vari siti, tutti mi hanno rimandato ??????
Mi dite come fare? e se posso evitare di scaricare i vari file?....
GraZieeeEeE

[B@Rz-]

Originally Posted by darkstar89

Ciao, mi scuso ma non ho capito come usare le RAINBOW TABLES ..
Io ho gli handshake, ho provato a fare l' md5sum dell' handshake, e guardare se mi dava la passwd tra i vari siti, tutti mi hanno rimandato ??????
Mi dite come fare? e se posso evitare di scaricare i vari file?....
GraZieeeEeE

No, credo profondamente alle teorie evolutive di Darwin.

Poiche' google di solito da' risultati troppo complessi visto che devono essere addirittura LETTI e talvolta COMPRESI, ti suggerisco di fare un salto su youtube, li' ti fanno vedere esattamente i passaggi da fare per usare queste "magiche" rainbow tables.

In questo modo sarai in grado di utilizzarle meccanicamente.

PS: sai cos'e' un handshake?

[darkstar89]

Mi scuso....
Dopo aver letto e capito come posso usarle,
non ci riesco , mi viene dato un'errore con le raimbow di alice, l'errore dice di verificare se il dabase è criptato, io l'ho scaricato e provato senza modificarlo...
Sapete darmi qualche risposta?..Avete altri consigli?
Graziiiiiiiieeeee

[Biante]

Grazie per la guida