Comprendo che una tabella arcobaleno risolve il problema di archiviazione quando si attacca una password usando gli hash precalcolati. Tuttavia, poiché le tabelle arcobaleno sono essenzialmente una versione compressa degli hash, non è necessario decomprimerle prima di confrontarle con gli hash di destinazione? Il processo di decompressione non è costoso? In che modo il tempo impiegato per decomprimere una tabella arcobaleno è paragonabile a quello utilizzato negli hash di calcolo da zero?
No. La compressione non funziona come la compressione tradizionale in stile RLE o LZMA.
Le tabelle Rainbow sono essenzialmente una tabella di ricerca che ti permette di trovare una stringa data il suo hash. Sono progettati per essere incredibilmente efficaci nel trovare un hash nell'indice su miliardi di voci, riducendo al minimo lo spazio su disco.
Ora, immagina di costruire un tavolo per molte e molte stringhe. Gli hash di alcune stringhe iniziano con gli stessi byte, ad esempio "StackExchange", "ILikeWaffles9", "ILikeWaffles13507" e "Decompression242" quando l'hash con MD5 inizia tutti con 0xF2. Invece di memorizzare tutti e tre gli hash completamente, puoi costruire una struttura ad albero in modo tale che i dati appaiano così:
f2 ="ILikeWaffles13507" 173dcd3c1a83febadc8ed1759c3ffc ="Decompressione242" 17f4a64e4036025c07b24a96ec787a ="ILikeWaffles9" 50514201b94be52c1ea16cd688384e ="StackExchange" Nota che gli hash sono ordinati per ordine numerico.
Infatti, poiché le prime due stringhe condividono anche lo stesso secondo byte (0x17), queste possono anche essere concatenate:
5cb1c6953bb0c62c639f3d7a242ec4 ="ILikeWaffles13507" f2 ="Decompressione242" 17 ="ILikeWaffles9" 3dcd3c1a83febadc8ed1759c3ffc ="StackExchange" Ciò consente anche di eseguire una ricerca incredibilmente rapidamente: invece di dover cercare nella tabella completa, devi solo attraversare l'albero, quindi cercare in un elenco più piccolo di hash. Poiché gli hash sono ordinati, puoi eseguire una ricerca binaria , che ha anche ottime prestazioni.
Ad esempio, se ho l'hash f4a64e4036025c07b24a96ec787a , cerco il primo nodo dell'albero 50514201b94be52c1ea16cd688384e , quindi cerco di vedere se c'è un sub-nodo per il secondo byte, 5cb1c6953bb0c62c639f3d7a242ec4 . C'è, quindi continuo giù. Controllo se esiste un sotto-nodo per f217f4a64e4036025c07b24a96ec787a . Non c'è, quindi ora cerco l'elenco all'interno del nodo f2 . So che 17 sarà probabilmente vicino alla fine di tale elenco, quindi inizio da lì. Trovo che l'hash corrisponda a quello che sto cercando, quindi ora so che il testo in chiaro è "Decompression242".
È anche incredibilmente efficiente in termini di spazio quando hai milioni o miliardi di hash, perché non duplichi parti dell'hash che sono condivise con altri testi in chiaro.
EDIT: Spiacente, avrei dovuto sottolineare che non è letteralmente come funzionano le tabelle arcobaleno. Questo è solo un esempio di come la compressione possa funzionare in questo senso, senza la necessità di salvare effettivamente un hash completo per ogni testo in chiaro. Non intendevo implicare il contrario. La risposta di IMSoP descrive meglio il funzionamento effettivo.
La cosa fondamentale da ricordare è che le tabelle arcobaleno sono solo utili quando si desidera effettuare più ricerche di hash per quel tipo di hash. Si genera una tabella arcobaleno per una lista di stringhe o un elenco di caratteri particolare in anticipo, solo una volta, e quindi è possibile utilizzare quel set di dati generato tutte le volte che lo si desidera. È un compromesso fare molto lavoro prima del tempo, in modo che le tue ricerche successive siano molto veloci.
Un'altra cosa fondamentale è che qualsiasi sistema di hash che include un salt rende inutilizzabili le tabelle arcobaleno, poiché ogni combinazione di password e di sale dovrebbe (idealmente) essere unica e abbastanza lunga da rendere poco pratico costruire una tabella arcobaleno per ogni possibile password e combinazione di hash.
La tua premessa di base è sbagliata: una tabella arcobaleno non è solo un elenco compresso di ogni possibile ricerca di hash, e devi ancora fare un po 'di hashing al volo. Invece, è un modo di sfruttare la natura degli hash per evitare di archiviare le ricerche in primo luogo e minimizzare l'importo che è necessario ricalcolare.
Wikipedia ha una spiegazione abbastanza dettagliata e c'è una domanda esistente qui con buone risposte , ma l'idea di base è creare una tabella come questa:
Dai valori che hai memorizzato, puoi recuperare tutte le ipotesi generate al passaggio 3. In un certo senso, ogni coppia di {first guess, last hash} "comprime" l'intera catena di ipotesi generate.
Ma il trucco è che non hai bisogno di provare tutte le catene per invertire un hash, perché se prendi l'hash che stai attaccando e inizi al punto 2, finirai per finire in uno degli ultimi hash memorizzato (al punto 6). Una volta che lo hai trovato, puoi ricreare ("decomprimi", se vuoi) solo quella catena , passando dal passo 1 (l'ipotesi della password memorizzata) e generando tutte le ipotesi intermedie.
Una differenza importante tra questa e la compressione è che puoi rendere la tabella memorizzata piccola quanto vuoi , rendendo le catene più lunghe - dovrai solo spendere più tempo a rigenerare gli hash scegliere una catena e ricreare la catena scelta. Potresti avere un milione di catene di lunghezza dieci, o dieci di lunghezza un milione, spazio di archiviazione contro il tempo di CPU .
Ovviamente è possibile comprimere i dati risultanti utilizzando qualsiasi algoritmo che ti piace. Alcuni di questi richiedono la decompressione dell'intera tabella prima di cercarla, altri potrebbero disporre i dati in modo che siano ancora ricercabili ma occupino meno spazio. Ma sarebbe anche possibile memorizzare l'intera tabella arcobaleno come, diciamo, una lista ordinata su un SSD veloce, e avresti ancora spazio su una tabella hash completa perché stai solo memorizzando l'inizio e fine di ogni catena, non di tutti i possibili hash.
Leggi altre domande sui tag hash password-cracking rainbow-table