it-swarm-eu.dev

quanto tempo ci vuole per generare effettivamente le tabelle Rainbow?

Ho letto dei tavoli Rainbow perché penso che siano piuttosto interessanti perché in realtà sono un concetto piuttosto semplice.

Ad ogni modo, mi chiedevo, qualcuno è stato effettivamente coinvolto nel generarne uno? Com'è possibile? Semplicemente non vedo come sia effettivamente possibile generare ogni combinazione di ogni personaggio.

Se escludiamo caratteri speciali, ci sono questi numeri di caratteri.

ABCDEFGHIJKLMNOPQRSTUVWXYZ abcdefghijklmnopqrstuvwxyz 1234567890

Sembra che ci siano 26 + 26 + 10 = 62 caratteri

Ciò significa che una password di lunghezza 8 ha 62 ^ 8 combinazioni.

che è uguale a 218340105584896

Questo da solo sembra che ci vorranno anni per generare. Che dire quando aumentiamo il numero di caratteri a 12 e aggiungiamo i caratteri speciali (diciamo che ce ne sono altri 10 solo guardando i personaggi che si ottengono premendo il tasto maiusc - numero)?

Otterremmo 72 ^ 12 = 19408409961765342806016

questo è un numero abbastanza grande da richiedere anni per arrivare.

27
stickman

Una tabella Rainbow è "solo" una rappresentazione compatta di una tabella di valori di hash precalcolati. Durante la costruzione della tabella Rainbow, vengono provati e sottoposti a hash molti input possibili. Ogni input che è stato riscontrato durante la costruzione della tabella verrà attaccato con successo con quella tabella e nessun altro. La valutazione dell'hash concentra la maggior parte dei costi di costruzione della tabella.

Quindi, fondamentalmente, il costo di costruzione di una tabella Rainbow che può invertire [~ # ~] n [~ # ~] le password è approssimativamente equivalente al costo di provare quelle [~ # ~] n [~ # ~] password attraverso la funzione hash - il punto della tabella Rainbow è che la costruisci una volta e quindi può usarlo per rompere diverse password. (Per essere precisi, a causa delle collisioni a catena durante la costruzione del tavolo, il costo è in effetti più vicino a 1,7 * N , ma per il momento ignoriamolo. )

Una volta ho fatto alcune esperienze con SHA-1. Un semplice hash di password con SHA-1 ha il costo di elaborare un singolo "blocco" (SHA-1, come MD5, elabora i dati mediante blocchi a 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 (direttamente o per la costruzione della tabella Rainbow, non importa) sono un lavoro altamente parallelo, quindi si potrebbero usare le istruzioni SSE2 che offrono registri a 128 bit e dove può eseguire un singolo codice operativo quattro operazioni a 32 bit contemporaneamente. SSE2 ha meno tipi di operazioni disponibili (in particolare, non offre rotazioni, solo spostamenti), quindi il conteggio delle operazioni sale a circa 1200; ma, in alcune condizioni, l'unità SSE2 eseguirà diversi codici operativi contemporaneamente. Quindi finiamo con 800 cicli di clock, per quattro istanze SHA-1 in parallelo. In conclusione: il mio PC è un Intel Core2 Q6600, con quattro core a 2,4 GHz. Ogni core può eseguire la mia implementazione SSE2, ottenendo all'incirca 48 milioni password con hash al secondo.

Ho anche una scheda grafica Nvidia non troppo piccola e la GPU può eseguire codice arbitrario attraverso CUDA . Questa è una 9800 GTX +, con 128 core a 1,84 GHz. Ogni core può eseguire un'operazione a 32 bit per ciclo (esiste un'elevata latenza, ma, grazie all'elevata parallelizzazione, è possibile mantenere questo throughput di una istruzione per ciclo). I core non conoscono le rotazioni, quindi ogni codice utilizzerà 1200 cicli di clock per password con hash. Il rendimento totale è 160 milioni password con hash al secondo.

Il mio PC e la mia scheda grafica sono dei primi del 2009 e non sono di fascia alta. Al giorno d'oggi, per poche centinaia di dollari, è possibile trovare una GPU che eseguirà il hash delle password circa tre volte più velocemente della mia 9800 GTX +. Supponiamo quindi che un utente malintenzionato con un PC comune (che costa meno di 1000 $) possa avere mezzo miliardo di password al secondo.

A quella velocità, tutte le password con 8 caratteri alfanumerici (lettere maiuscole e minuscole e cifre) vengono superate in circa 5 giorni . Con un PC da $ 1000. Se usi MD5, le cose sono circa il 30% più veloci (MD5 usa un po 'meno operazioni di SHA-1). Tuttavia, i buoni schemi di hashing delle password non usano una semplice chiamata di hash: usano l'hash iterato con, per esempio, 2000 invocazioni di hash nidificate: questo moltiplica il costo per l'attaccante per lo stesso fattore 2000 (quindi trasforma i "5 giorni" in circa 28 anni, letteralmente "invecchia" come dici tu).

30
Thomas Pornin

Quanto tempo ci vuole per generare una tabella Rainbow per un hash molto semplice, usando una sola iterazione? Ci vuole un'ora! O meno, se lo desideri.

Mentre le risposte sopra sono del tutto corrette, c'è uno sviluppo importante che non menzionano. Amazon EC2 e altri provider di server 'cloud computing'.

Oggi chiunque abbia una carta di credito può andare su aws.Amazon.com e inviare un na manciata di istanze spot EC2 , per meno di cento dollari. Oppure, se disponi di un buon codice CUDA disponibile, noleggia 50 delle più costose istanze "Cluster GPU" di Amazon con due processori grafici NVIDIA Tesla M2050.

(Un po 'come le compagnie aeree, Amazon ha prezzi differenziati. Se hai bisogno di un server EC2 specifico con disponibilità garantita, i prezzi sono più alti. Ad esempio, puoi ottenere un'istanza "Hi-CPU Large" con 8 core di CPU virtuali per 0,68 USD all'ora Se sei disposto ad acquistare la stessa istanza dei permessi di fornitura in eccesso nelle ore di riposo, puoi ottenerlo con sconto del 40% -50% .)

La creazione di tabelle Rainbow può essere eseguita in parallelo con un aumento lineare delle prestazioni, ovvero con 100 computer funzionanti è 100 volte più veloce di un singolo computer.

Amazon non ti addebita per istanza, addebita per istanza-ora. Pertanto, eseguire 1.000 server per un'ora costa lo stesso di un server per 1.000 ore.

La natura parallela della creazione di tavoli Rainbow, presa insieme a servizi come Amazon EC2, significa che non c'è più la domanda "quanto tempo impiega". C'è un "quanto sei disposto a pagare per ottenerlo veloce, rispetto a pagare di meno e ottenerlo in pochi giorni?". La differenza di costo e tempo deriva principalmente dalla differenziazione dei prezzi di Amazon tra istanze EC2 "normali" rispetto alle "istanze spot" più economiche.

18
Jesper M

Utilizzando una semplice esecuzione di test 26 ^ 5, sono stato in grado di generare una tabella esadecimale ascii in Ruby che ha generato 228488 output MD5 al secondo. Tutte le voci 11881376 hanno richiesto 52 secondi sul mio Core i7 di 1,5 anni. Se non avessi apportato miglioramenti al mio programma, mi sarei aspettato che funzionasse per 26 settimane per generare il tuo elenco 62 ^ 8.

Probabilmente potrei apportare miglioramenti al mio programma eseguendo otto programmi separati, uno per hyperthread, per partizionare lo spazio del problema. Se ogni programma salvasse l'output sul proprio disco, non competerebbero per IO larghezza di banda. Mi aspetterei un fattore da quattro a sei speedup rispetto al mio stupido programma a thread singolo per 4-6 runtime di settimane. Se dovessi riscrivere in C, potrei aspettarmi un altro fattore di 1,5 speedup. (Forse di più? Da un lato è un semplice programma, dall'altro un array C lungo 13 byte, modificato in fase di runtime, probabilmente verrà eseguito con molta meno memoria e ovviamente nessuna garbage collection rispetto alla creazione e alla distruzione degli oggetti stringa Ruby.)

Mi aspetterei un pomeriggio di lavoro e qualche centinaio di dollari di nuovi attrezzi mi permetterebbero di finire i 62 ^ 8 tavoli due settimane su hardware di largo consumo.

E certo, nessuno usa MD5 a singola esecuzione su password; ridimensiona i miei risultati finali per quanto il tuo hash a senso unico sia molto più costoso di MD5. :)

6
sarnold

Vedi i calcoli della mia velocità di hash della mia rete di mining bitcoin su Come eseguire l'hashing sicuro delle password? - Sicurezza IT per ciò che le persone determinate con schede GPU più moderne possono ottenere in termini di hash grezzo. La community è in esecuzione a 11 Thash/s (11 * 10 ^ 12 hash/s) all'inizio di luglio 2011 ....

1
nealmcb