/**************************************************************************************** * How Rainbow Tables work * * * * Written by: kestas.j.k (kestas.j.k@gmail.com) * * Translated by: RedLion (r3dlion[at]hotmail[dot]com) * * * ****************************************************************************************/ Le funzioni di hashing mappano il testo in chiaro in hash così che tu possa riconoscere un hash univoco per ogni testo in chiaro (da ora in poi: 'plaintext') Se vuoi trovare il plaintext di origine da un certo hash, ci sono due semplici metodi: - hashare 'ogni' plaintext uno per uno, finchè non trovi l'hash. - hashare 'ogni' plaintext uno per uno, ma immagazzinare ogni hash generato in una tabella ordinata così da cercare facilmente l'hash, senza dover generare tutti gli hash una seconda volta. Andare uno alla volta richiede molto tempo, ed immagazzinare ogni hash prende una quantità di memoria che semplicemente non esiste (parlando di tutti i plaintext, ad eccezione per i set più piccoli). Le RainbowTable (da ora 'RT') sono un compromesso tra la pre-computazione e il basso uso di memoria. La chiave per capire le RT è comprendere la funzione di riduzione (il nome non aiuta). Una funzione di hashing mappa del plaintext in hash, la funzione di riduzione mappa hash in plaintext. È importante notare che questa esegue un reverse della funzione di hash (mappando hash in plaintext), ma NON è la funzione inversa all'hash. L'intento delle funzioni di hashing è il rendere impossibile creare funzioni inverse a quella di hashing. Se prendi l'hash di un plaintext, ed esegui la riduzione dell'hash, questa non ti ridarà l'originale plaintext; ma qualche altro plaintext. Se il set del plaintext è [0123456789]{6} (noi vogliamo una RT di tutte le password numeriche di lunghezza 6), e la funzione di hashing è MD5(), un hash di un plaintext potrebbe essere MD5("493823") -> "222f00dc4b7f9131c89cff641d1a8c50". In questo caso la funzione di riduzione R() potrebbe essere tanto facile quanto prendere i primi 6 numeri dell'hash; R("222f00dc4b7f9131c89cff641d1a8c50") -> "222004". Noi abbiamo ora generato un altro plaintext dall'hash del plaintext precedente, questo è lo scopo della funzione di riduzione. Gli hash sono funzioni univoche, ad un solo senso, ed ugualmente lo sono le funzioni di riduzione. Le chains che creano le RT sono chains di hash univochi e le funzioni di riduzione iniziano con un certo plaintext, e finiscono con un certo hash. Una chain (lett: catena) in una RT inizia con plaintext arbitrario, lo hasha, riduce l'hash ad un altro plaintext, hasha il nuovo plaintext e così via. La table semplicemente immagazzina il plaintext iniziale, e l'hash finale con il quale tu decidi si finisca, e così una chain contenente milioni di hash può essere rappresentata con un singolo plaintext di origine, e con un singolo hash. Dopo aver generato molte chains la table potrebbe essere qualcosa di simile: iaisudhiu -> 4259cc34599c530b1e4a8f225d665802 oxcvioix -> c744b1716cbf8d4dd0ff4ce31a177151 9da8dasf -> 3cd696a8571a843cda453a229d741843 [...] sodifo8sf -> 7ad7d6fa6bb4fd28ab98b3dd33261e8f Le chains sono ora pronte per essere usate. Abbiamo un certo hash con un plaintext sconosciuto, e vogliamo vedere se esso è contenuto in una delle chains generate. L'algoritmo è: Cerca l'hash nella lista degli hash finali, se c'è lì esci dal loop. Se non c'è lì, riduci l'hash in un altro plaintext, e hasha il nuovo plaintext. Vai all'inizio Se l'hash corrisponde ad uno degli hash finali, la chain sulla quale l'hash corrisponde al finale contiene l'hash originario. Puoi ora capire che il plaintext iniziale della chain, e iniziare l'hashing e la sua riduzione, finchè non raggiungi l'hash noto con il suo segreto plaintext. In questo modo puoi controllare gli hash della chain, che non sono evidentemente immagazzinati da nessuna parte del disco, attraverso l'iterazione colonna per colonna per mezzo della table di chains, muovendosi indietro dall'ultima colonna della catena, fino al plaintext originario. Volendo controllare se l'hash esista nella quarta colonna dall'ultima in tutte le chains bisogna ridurre e hashare il dato hash per 4 volte, e controllare l'hash generato rispetto agli hash finali. Le collisioni sono l'unico problema delle RT. Ironicamente le collisioni sono viste come una brutta cosa per gli algoritmi di hashing, ma nel caso delle RT un algoritmo di hashing che genera collisioni con una certa regolarità sarà molto più sicuro. Un hash può essere generato da plaintext diversi (questa è ciò che si chiama collisione), ed è un grosso problema per le chains perchè ciò obbliga le chains che partono diversamente a convergersi in una. Inoltre si ottengono dei loop, che sono causati quando un hash è ridotto a plaintext che era già stato hashato in un punto precedente della catena. A causa di questi problemi di collisioni non c'è garanzia che ci sarà sempre un hash di un plaintext che verrà ridotto sino ad un altro plaintext dato. Se hai una semplice lista di hash ed i corrispondenti plaintext, qualora non trovassi un dato hash, sarai sicuro che l'hash non è presente nel set di quei plaintext. Se hai una tavola di chains, dove la funzione di riduzione riduce gli hash in un set di plaintext, tu potresti avere trilioni di chain generate ma potresti non aver generato ogni singolo plaintext del set che si intende verificare. Puoi solamente dire quanto sia probabile che una table di chains contenga un certo plaintext; una percentuale molto prossima al 100%, ma che probabilmente non raggiungerà mai il 100%. Se tu hai una rainbow table con 10 chains di lunghezza 100, tu hai hashato 1000 plaintext, ma anche se ci sono solo 100 plaintext nel set dei plaintext desiderati, i 1000 hash che hai nelle chain potrebbero non contenere tutti gli hash desiderati. Il modo in cui le collisioni vengono gestite è ciò che rende le Rainbow Table differenti dal loro predecessore, sviluppato nel 1980. Il predecessore risolveva i problemi di alcuni plaintext che non erano mai stati ridotti usando piccole tavole. Ogni piccola tavola usava una diversa funzione di riduzione. Questo non risolveva il problema completamente, ma sicuramente aiutava. Per risolvere la fusione di chain e i loop ogni chain finiva con un "distinct point" (punto di distinzione); un hash che era in qualche modo unico, es. hash dove i primi 4 caratteri fossero 0. Le chain continuavano ad andare fino a raggiungere il distinct point. Se due chain finivano allo stesso distinct point allora c'era stata una collisione da qualche parte nella catena, e una delle catene veniva scartata. Se una catena viene generata per un lungo periodo senza arrivare ad un distinct point, si sospetta un loop (dove una chain di hash termina riducendo e hashando un hash precedente della stessa catena). Il problema con questo è che se c'è una collisione ci sarà potenzialmente un intero ramo che deve essere tagliato senza essere inserito nelle chain, e un loop causerebbe la perdita di tutti gli hash che sono stati generati prima del loop. Inoltre, tutto il tempo speso nel generare quella chain sarebbe stato inutile, e fermandosi solo al distinct point si avrebbero chain di lunghezza variabile. Questo significa che tu potresti dover continuare a cercare un hash, specialmente all'interno di chain molto lunghe, dopo che le altre chain sono terminate. Le RainbowTable differiscono da questo, nella misura in cui non usano tabelle multiple per le funzioni di riduzione, usando solo una table. Comunque, nelle RT una diversa funzione di riduzione è usata per ogni colonna. In questo modo non c'è bisogno di tavole differenti con differenti metodi di riduzione, perchè le diverse riduzioni sono usate dentro la stessa tavola. In questo modo le collisioni e le fusioni di chain sono molto, molto più rare dato che dovrebbero avvenire sulla stessa colonna. Per una chain di lunghezza L la possibilità di collisione causante una fusione è ridotta a 1/L. I loop anche sono risolti, dato che se un hash in una chain è lo stesso di un hash precedente, questo non si ridurrà allo stesso plaintext. La ragione per cui sono chiamate Rainbow Tables è perchè ogni colonna usa una differente funzione di riduzione. Se ogni funzione di riduzione avesse un diverso colore, e si iniziasse con i plaintext in cima e si finisse con gli hash finali alla base, il tutto assomiglierebbe ad un arcobaleno (un arcobaleno molto lungo verticalmente e stretto). Usando le RT, l'unico problema che rimane è che non si può mai essere sicuri che le chain contengano tutti gli hash desiderati; per assicurare un maggiore grado di successo da parte di una RT, si dovrebbe generare molte più catene, ed ottenere dei ritorni in diminuzione. Spero che spiegando le Rainbow Table io non le abbia rese meno meravigliose. Enjoy your RT'ing RedLion.