Una tabella arcobaleno è "solo" una rappresentazione compatta di una tabella di valori hash precalcolati. Durante la costruzione della tabella arcobaleno, molti possibili input vengono provati e sottoposti a hash. Ogni input incontrato durante la costruzione della tabella verrà attaccato con successo con quella tabella e nessun altro. La valutazione dell'hash concentra la maggior parte del costo di costruzione della tabella.
Quindi, in sostanza, il costo di costruire una tabella arcobaleno che può invertire le password N equivale approssimativamente al costo di provare quelle password N attraverso la funzione hash - il punto della tabella arcobaleno è che lo costruisci una volta e quindi puoi usarlo per spezzare diverse password. (Per essere precisi, a causa di collisioni a catena durante la costruzione della tabella, il costo è in effetti più vicino a 1,7 * N , ma ignoriamolo per il momento.)
Una volta ho fatto alcune esperienze con SHA-1. Un semplice hash della password con SHA-1 ha il costo di elaborare un singolo "blocco" (SHA-1, come MD5, elabora i dati per blocchi da 64 byte), che richiede circa 900 operazioni logiche o aritmetiche a 32 bit. Un'implementazione ottimizzata su un processore Intel Core2 x86 può farlo in circa 500 cicli di clock. Tuttavia, gli attacchi con password (sia direttamente che per la costruzione di tabelle arcobaleno, non importa) sono un lavoro altamente parallelo, quindi è possibile utilizzare le istruzioni SSE2 che offrono registri a 128 bit e dove un singolo codice operativo può eseguire quattro Operazioni a 32 bit contemporaneamente. SSE2 ha meno tipi di operazioni disponibili (in particolare, non offre rotazioni, solo turni), quindi il conteggio delle operazioni sale a circa 1200; ma, in alcune condizioni, l'unità SSE2 eseguirà più codici opzionali contemporaneamente. Quindi finiamo con 800 cicli di clock, per quattro istanze SHA-1 in parallelo. Bottom-line: il mio PC è un Intel Core2 Q6600, con quattro core a 2,4 GHz. Ogni core può eseguire la mia implementazione SSE2, generando approssimativamente 48 milioni password hash al secondo.
Ho anche una scheda grafica Nvidia non troppo piccola e la GPU può eseguire codice arbitrario tramite CUDA . Questa è una 9800 GTX +, con 128 core a 1,84 GHz. Ogni core può eseguire un'operazione a 32 bit per ciclo (c'è una latenza elevata, ma, grazie all'elevata parallelizzazione, questo throughput one-instruction-per-cycle può essere mantenuto). I core non conoscono le rotazioni, quindi ogni codice utilizzerà 1200 cicli di clock per password hash. La performance totale è 160 milioni hashed password al secondo.
Il mio PC e la mia scheda grafica risalgono all'inizio del 2009 e non sono al top della gamma. Al giorno d'oggi si possono trovare, per poche centinaia di dollari, una GPU che avrà password hash circa tre volte più veloci della mia 9800 GTX +. Quindi supponiamo che un utente malintenzionato con un PC comune (che costa meno di 1000 $) possa disporre di mezzo miliardo di password al secondo.
A quella velocità, tutte le password con 8 caratteri alfanumerici (lettere maiuscole e minuscole e cifre) sono passate in circa 5 giorni . Con un PC da 1000 $. Se si utilizza MD5, le cose sono circa il 30% più veloci (MD5 usa un po 'meno operazioni di SHA-1). I buoni schemi di hashing delle password non usano una semplice invocazione hash: usano hashing iterato con, diciamo, 2000 invocazioni hash annidate: questo moltiplica il costo per l'attaccante dello stesso fattore 2000 (quindi trasforma i "5 giorni" in circa 28 anni, letteralmente "invecchia" come lo metti).