Perché le GPU sono così brave a infrangere le password?

Per completare la risposta di @ Terry: una GPU ha molti core (centinaia). Ogni core è fondamentalmente in grado di calcolare un'operazione aritmetica a 32 bit per ciclo di clock - come una pipeline . In effetti, la GPU funziona bene con il parallelismo estremo : quando ci sono molte unità di lavoro identiche da eseguire, in realtà molti più di nuclei effettivi ("identici" che significa "stesse istruzioni", ma non "stessi dati").

Alcuni dettagli , per una scheda NVidia un po 'vecchia (una GTX 9800+, dall'inizio del 2009): ci sono 128 core, suddivisi in 16 "unità multicore". Ogni multicore può avviare 8 operazioni per ciclo (da qui l'idea di 128 core: ovvero 16 volte 8). Il multicore gestisce le unità di lavoro ("thread") per gruppi di 32, in modo che quando un multicore ha un'istruzione da eseguire, in realtà trasmette quell'istruzione ai suoi 8 core su 4 cicli di clock. Questa è l'operazione avvio : ogni singola operazione impiega fino a 22 cicli di clock per essere eseguita. Puoi immaginare l'istruzione e i suoi operandi che camminano nel circuito come una linea frontale che avanza, come un'onda in una piscina: una determinata onda impiegherà del tempo per raggiungere l'altra estremità della piscina, ma puoi inviare diverse onde in sequenza.

Quindi puoi mantenere il ritmo di "128 operazioni a 32 bit per ciclo" solo se hai almeno 22 volte più "thread" da eseguire (cioè un minimo di 22 · 128 = 2816), tale che i thread possono essere raggruppati per pacchetti di 32 thread "identici" che eseguono le stesse istruzioni nello stesso momento, come i ballerini hip-hop. In pratica, esistono alcune soglie e vincoli interni che richiedono più thread per raggiungere l'ampiezza di banda ottimale, fino a circa 4096.

Potrei raggiungere quasi il 99% della larghezza di banda ottimale con un'implementazione SHA-1. SHA-1 usa un po 'più di 1100 operazioni a 32 bit (che sarebbe circa 900 su una CPU, ma una GTX 9800+ non ha opcode rotazione , quindi le rotazioni devono essere divise in due turni e logico o), e la GPU funzionava a 1450 MHz, per un totale complessivo di circa 160 milioni di calcoli SHA-1 al secondo. Questo può essere ottenuto solo finché hai milioni di istanze SHA-1 da calcolare in parallelo, come nel caso del crack delle password (in qualsiasi momento hai bisogno di 4096 SHA-1 paralleli per alimentare il Core GPU, ma devi anche affrontare i costi I / O per l'immissione di potenziali password, e questi costi saranno dominanti se non hai molte istanze SHA-1 da elaborare).

Il PC host, sulla sua CPU (un Intel Core2 quad-core a 2,4 GHz), poteva raggiungere circa 48 milioni SHA-1 al secondo e che era con codice SSE2 completamente ottimizzato. Un singolo SHA-1 utilizzerà circa 500 cicli di clock su tale CPU (la CPU può calcolare diverse istruzioni in un singolo ciclo, a condizione che non siano in competizione per le risorse e non dipendano l'una dall'altra), ma, per il crack delle password , vale la pena utilizzare SSE2 con i suoi registri a 128 bit e in grado di calcolare 4 istruzioni in parallelo. Con i vincoli SSE2, occorrono circa 800 cicli di clock per eseguire quattro SHA-1 paralleli, quindi 200 cicli di clock per istanza SHA-1. Ci sono quattro core in quella CPU e il tutto funziona a 2400 MHz, quindi 48 milioni al secondo.

L'hardware più recente sarà più veloce, ma GPU in più. Una GTX 680 sfoggia un whois 1536 core e ci sono due tale GPU in una GTX 690. Stiamo parlando di miliardi di istanze SHA-1 al secondo qui.

(Per il confronto, ho anche realizzato un'implementazione di SHA-1 sul processore di celle , cioè la CPU in una console PS3, con i suoi coprocessori da 8 "SPU" .Una SPU non era disponibile. Con gli altri 7, ho raggiunto circa 100 milioni di SHA-1 al secondo, cioè meglio di una grande CPU contemporanea, ma non così buona come una buona GPU della stessa epoca.)

Riepilogo: le GPU raggiungono grandi prestazioni utilizzando il pesante parallelismo, con centinaia (se non migliaia) di core. Ciò è reso possibile da pipelining (ogni singola operazione richiede molti cicli per essere eseguita, ma le operazioni successive possono essere avviate come i camion su un'autostrada) e la decodifica delle istruzioni condivise (poiché molti core eseguiranno le stesse istruzioni al stessa ora).

Una GPU è eccellente per elaborare calcoli matematici. Il rendering grafico è semplicemente una serie di complessi calcoli matematici. Quindi sono gli algoritmi di hashing.

Una GPU ha centinaia di core che possono essere utilizzati per calcolare funzioni matematiche in parallelo. In genere una CPU ha 4-8 core. Sebbene il core della CPU sia molto più veloce di un core della GPU, l'hashing della password è una delle funzioni che è possibile eseguire in parallelo molto facilmente. Questo è ciò che dà alle GPU un vantaggio enorme nelle password di cracking.

Dovresti notare che dei tre algoritmi che hai citato, PBKDF2 può ancora essere crackato relativamente facilmente su una GPU. L'algoritmo PBKDF2 in termini molto semplici hash una password con una funzione hash come MD5 o SHA1 migliaia di volte. Anche se molto più potente di un semplice hash MD5 o SHA1, può ancora essere crackato relativamente veloce con una GPU.

bcrypt e scrypt sono progettati per evitare l'enorme aumento dei tempi di cracking che una GPU offre a un utente malintenzionato. Vedi questa incredibile risposta di Thomas Pornin per maggiori informazioni: link