Viteza forței brute caută cpu și gpu

Calculele de pe GPU au devenit recent foarte populare în toate domeniile în care este posibil să le folosiți. Una dintre aceste domenii este criptografia, mai restrânsă - selecția / căutarea parolelor. Din păcate, rezultatele reale ale muncii (așa cum se întâmplă de obicei) sunt împodobite în scopuri de marketing, astfel încât nu devine foarte clar care este, de fapt, câștigul de la utilizarea GPU-ului în acest domeniu.

Explicațiile lungi se încheie cu concluzii scurte (care probabil ar trebui citite la prima lectură a acestui articol).

Ce este pierderea parolei consumatoare de timp.

Dacă în urmă cu zece ani, fiecare dezvoltator a încercat să vină cu un fel de, algoritmul de criptare originală (dar, din moment ce aproape nimeni nu este un expert în domeniul criptografiei, marea majoritate a acestor algoritmi „originale“ au fost sparte la momentul respectiv), dar acum acest lucru a devenit mult mai ușor . Aproape peste tot se utilizează scheme dovedite și standard.

Pentru criptare, trebuie mai întâi să convertiți parola într-o cheie de tipul și mărimea specificată (etapa hash), iar apoi cu această cheie puteți să criptați datele (utilizând orice algoritm de încredere, cum ar fi AES).

Pentru hash, MD5 a fost folosit masiv recent, dar (după detectarea vulnerabilităților din algoritm), a înlocuit rapid SHA1. Cu SHA1 în prezent au nu este destul merge lin (complexitatea de a găsi coliziune este de aproximativ 2 ^ 63, iar recent mai mult și a anunțat reducerea numărului de până la 2 ^ 52), dar atunci când este utilizat într-o „încadrată“ ca PBKDF2 complexitate (sau, mai degrabă, ușurința) de a găsi o coliziune nu este atât de importantă.

În PDF9 Adobe a ratat foarte mult cu un nou algoritm, luând-o iterație SHA256 în loc de 50 MD5 + 20x RC4, care a accelerat viteza de forta bruta, comparativ cu versiunea anterioară este aproape două ordine de mărime. Validarea parolei după hash nu necesită nici o criptare, deci doar viteza SHA256 este importantă aici.

Algoritmul corect de criptare face imposibilă reducerea spațiului de căutare pentru chei. Adică, pentru a găsi, de exemplu, o cheie pe 128 de biți, trebuie să sortați opțiunile 2 ^ 128 == 3,4 * 10 ^ 38. Presupunând că un calculator trece printr-un miliard de opțiuni în al doilea, avem un miliard de calculatoare, și avem un miliard de ani, timp in care vom putea verifica doar 10 * 9 * 10 * 9 * 10 * 9 * 60 * 60 m * 24 h * 365,25 d

= 3,16 * 10 ^ 34 opțiuni, mai puțin de 1/10000 din intervalul necesar.

Un exemplu de algoritm de criptare nereușit: zipul clasic utilizează chei de 96 biți. În ciuda ultimilor 20 de ani de la crearea algoritmului, aceste chei sunt încă imposibil de ajuns pe frunte. Cu toate acestea, având o porțiune dintr-un fișier necriptat, puteți efectua așa-numitul atac plaintext, în timp ce complexitatea forță brută va scădea la 2 ^ 96 doar 2 ^ 38, care este doar câteva ore pentru calculator modern.

Toți algoritmii de criptare "puternici" (AES, Blowfish, etc) nu permit efectuarea unui atac de tip plaintext și nu permit reducerea spațiului de căutare. Deci, singura modalitate de a accesa fișierele criptate este să cunoști parola corectă.

Concluzie: algoritmul de criptare folosit nu are niciun efect asupra vitezei de scanare a parolei. Un algoritm bun oferă pur și simplu imposibilitatea de a selecta cheia "pe frunte". Și acum principalul lucru este de a itera prin conversia parolelor este o parolă într-o cheie, și este responsabil pentru algoritmi de hash (MD5, SHA1), mai degrabă decât algoritmi de criptare (AES, Blowfish).

Valoarea "numărul de iterații" spune puțin.

MD5, SHA1 (și descendenții săi ca SHA256, 384, 512) sunt foarte asemănătoare. Intrarea are o stare hash (128 biți pentru MD5, 160 biți pentru SHA1) și un bloc de date de 512 biți (64 byte). La ieșire, după operația de hash, obținem o stare de hash nou. Aceasta este inima algoritmului, funcția este denumită de obicei MD5_Transform, SHA1_Transform, etc.

Este important să rețineți că dimensiunea blocului este o constantă, este întotdeauna hashed 64 bytes. Dacă alimentat la intrare de 1 octet, acesta va fi suplimentat la 64 prin adăugarea simbolului zerouri terminator și o valoare de 8 octeți a lungimii blocului. Asta este, fișier separat de intrare hash funcție 64 × 1 octet sau o dată la fiecare 64 de biți - absolut identice cu planul viteza de procesare (nu de numărare faptul că atunci când se aplică 64 de biți va simbol terminator și un proces de valoare lungime deja în următorul bloc) .

Pentru unii algoritmi, numărul de iterații este scris ca numărul de apeluri către funcția de actualizare a hash-ului. Dar nu fiecare actualizare duce la un apel la funcția Transformare. Datele sunt acumulate în tampon și transferate în blocuri de transformare de 64 octeți. De exemplu, pentru RAR număr 3.x de iterații egal cu 262.144, dar numărul de blocuri prelucrate este egal cu ((dlina_parolya * 2 + 8 + 3) * 262144) / 64. De exemplu, parole în 4 lungime caracter va fi 77824 (+ 17 mai suplimentare blocuri pentru crearea IV pentru AES).

Ce dă reducerea numărului de iterații la numărul de blocuri pentru Transformare? Deoarece timpul pentru calculul hash-ului este independent de datele din bloc și este o constantă, cunoscând timpul de hash al unui bloc și numărul de blocuri, puteți calcula cu ușurință timpul de hashing total. Este, de asemenea, ușor de estimat cât de mult mai rapid sau mai lent diferiții algoritmi generează parole unul față de celălalt.

De exemplu, pe baza calculelor de mai sus, se pare că viteza de scanare a parolei WinZip / AES este

Concluzie: Numărul iterațiilor "virtuale" din algoritm înseamnă puțin. Pentru a estima viteza, trebuie să știți numărul de blocuri de 64 de octeți folosite pentru hashing. Cunoscând această valoare, viteza generală de procesare este ușor de obținut prin simpla multiplicare a acestei valori de către timpul de procesare al unui bloc de date.

Cât de repede pot să fac?

Acum suntem interesați de întrebarea cât de rapid poate fi procesat un bloc de date cu 64 de octeți. Operațiile folosite în funcția Transformare sunt cele mai simple - logică OR, XOR, NOT, AND, adăugarea aritmetică, schimburi. Toate acțiunile sunt efectuate pe numere întregi pe 32 de biți. Un bloc de date se potrivește cu ușurință în cache-ul L1 al oricăruia dintre procesoarele moderne, deci viteza de lucru cu memoria, mărimea acesteia, dimensiunea L2 sau RPM a unității de disc nu contează. Cu alte cuvinte, viteza căutării depinde în mod direct de viteza întregului ALU și practic nu depinde de orice altceva. Care dintre procesoarele moderne cu acest lucru este cel mai bun?

Procesoare.

Deoarece împărțirea diferitelor parole nu depinde una de cealaltă, este foarte avantajos să se folosească un set de instrucțiuni SIMD pentru prelucrarea lor paralelă. Cel mai bun SSE2 (deși „vechi» MMX are încă utilizare) vă permite să efectuați o operație imediat cu patru operanzi pe 32 de biți. Într-o primă variantă de realizare, un Pentium 4 cu viteza de SSE2 instrucțiuni nu merge lin (de exemplu, transportul registr-> 6 cicluri de cost registru, și executarea tuturor sau 2), dar chiar și atunci câștigul de aplicare a acestora a fost destul de notabile. În același timp punerea în aplicare SSE2 în arhitectura Intel Core este pur și simplu superb: este posibil să se efectueze 3 operațiuni pe ceas, cu rezultatul va fi gata în ciclul următor (latență == 1 bar). Adică, performanța de vârf a Core este de 12 operații cu un număr întreg pe 32 de biți pe ceas. Deși nu toate operațiile pot fi efectuate la această viteză maximă.

În ciuda apariției unor noi revizuiri de bază, trecerea de la 65nm la 45nm și, în final de presă Core i7, fără modificări semnificative în întreg ALU sa întâmplat. Prin urmare, Core i7 funcționează aproape la fel de bine ca sa strămoș 65nm Core 2. Capacitatea depinde numai de frecvența, deci, de exemplu, Q6600 tactat la 3 GHz (care este destul de o practică comună) este exact 3 / 2,66 = 12,7% mai rapid decât Core i7 920 pe frecvența nominală (fără a ține cont de explozia turbo). Costul Core i7, inclusiv placa de bază și memoria DDR3, este mult mai mare decât cel al sistemelor "vechi" pe Core 2 65 / 45nm.

Situația cu AMD este ceva mai gravă. Chiar și acum, există încă câteva sisteme cu procesorul Athlon XP. La un moment dat, a concurat foarte bine cu P4, dar nu există SSE2 în ea. În arhitectura K8, AMD a suportat SSE2, dar în cea mai primitivă formă: instrucțiunile pe 128 de biți au fost împărțite în două jumătăți și lansate pe un ALU pe 64 de biți. Aceasta a dus la faptul că diferența dintre codul MMX și SSE2 a fost practic inexistentă.

Odată cu apariția lui K10 (sau Phenom), AMD a oferit în cele din urmă sprijin pentru SSE2 într-un mod mai decent, dar Core 2 este mult inferior. K10 poate efectua până la 2 operații cu 4 întregi pe 32 de biți pe oră și rezultatul operației va fi gata doar după ceasul (latența == 2 ceas). Asta este, performanța de vârf este de 8 operații cu întregi pe 32 de biți pe ceas. Ce inseamna asta in comparatie cu K10 vs Core 2: procesorul de la AMD va fi de 1,5 ori mai lent in medie daca putem construi instructiuni astfel incat latenta nu este un factor limitator. În unele algoritmi, având în vedere numărul limitat de registre XMM, acest lucru este foarte dificil, dacă nu imposibil.

Pe de altă parte, nu toate operațiile Core 2 pot funcționa la nivelul "trei per ceas". Adăugările pot fi făcute doar două, și în general există o schimbare. K10 este capabil să transfere două registre XMM pe ceas, dar cu o latență de 3 cicluri. Prin urmare, raportul real de performanță al Core 2 vs K10 plutește undeva în jurul valorii de 1,25-2x. K10 este întotdeauna mai lent pentru sarcinile care depind doar de viteza SSE2 ALU, dar poate fi mai rapid pe algoritmi cu multe citiri din memorie și lipsă de operații logice.

Phenom II, care a apărut nu cu mult timp în urmă, diferă de pur și simplu Phenom # "și mult mai puțin decât Core i7 de la Core 2 45nm. Dar este, desigur, mai scump.

Este important de menționat că, în momentul de față, utilizarea SSE2 este obligatorie pentru prelucrarea paralelă a datelor. Funcționarea logică pe un registru pe 32 biți sau pe un registru de 128 de biți xmm care conține patru valori pe 32 de biți se efectuează exact în același timp. Numărarea pe Core 2 fără SSE2 este ca și cum ați lua un GPU și deconectați ¾ din toate procesoarele stream pe el.

De asemenea, problema parolelor parsing este perfect paralelizată, deoarece nu există o corelație între date. Prin urmare, performanța crește liniar în funcție de frecvența și numărul de nuclee. Nu are sens să folosiți un dual core "rapid", dacă puteți utiliza un quad core "lent". Cu alte cuvinte, Q6600 la frecvența de 2.4GHz va funcționa ca 4 * 2.4 = 9.6Ggts și E8600 3.33 GHz numai 3.33 * 2 = 6.66Ggts. Diferența de viteză este de 1,5 ori, iar diferența de preț este aproximativ aceeași, dar în direcția opusă.

Concluzie: Cel mai bun procesor pentru parola în acest moment este Intel Core Quad. Raportul preț / performanță este mai bun decât modelul Core 2 65 / 45nm. Sistemele de cost pe Core i7 de mai sus, iar frecvența nu este mai bună decât „vechi» 2. procesoare Core de la AMD rămâne mult în urma unor calcule întregi SSE2 și, astfel, diferența de preț dintre Core 2 și Phenom nu a compensa acest decalaj. SSE2 este necesar să se folosească, altfel posibilitățile procesoarelor moderne pur și simplu nu pot fi rezolvate.

Deci, cât de repede poate fi spulberat?

Viteza foarte brută a numărului de operațiuni utilizate poate fi estimată după cum urmează:

Desigur, o astfel de evaluare nu ia în considerare mai mulți factori diferiți, dar este potrivit să înțelegem cât de repede este posibil din punct de vedere teoretic efectuarea MD5_Transform. Rezultatele experimentate, ca de obicei, arată mai rău. Dar nu atât de mult:

MD5_Transform 72 de măsuri în modul pe 64 de biți.

MD5_Transformați 90 de cicluri în modul pe 32 de biți.

MD5_Transformați în cea mai simplă implementare pe SSE2 când procesați doar 4 blocuri la un moment dat 128 de cicluri.

SHA1_Transformă 175 cicluri în modul pe 32 de biți, 162 cicluri de ceas în modul pe 64 de biți.

Cu SHA256 valoare exactă nu este (deoarece foloseste SHA256 mult mai puțin), dar SHA256_Transform va dura cel puțin 425 de cicluri. Prezența unui număr semnificativ de schimburi și adăugiri poate crește această valoare.

Utilizarea modului pe 64 de biți vă permite să utilizați de două ori mai mulți registri XMM, care, la rândul lor, ajută la rezolvarea problemelor cu latență. Acest lucru este valabil mai ales pentru MD5, în cazul în care există foarte puține operațiuni, deci trebuie întotdeauna să așteptați rezultatele calculelor anterioare dacă procesați doar 4 blocuri de date la un moment dat.

Rezultatele teoretice și practice.

În cele din urmă, tabela rezumativă, pentru care totul a început. Compararea vitezelor pentru diferite tipuri de parole. Au fost utilizate următoarele:

Viteza a fost măsurată la un singur nucleu Intel Core 2 Q6600 @ 2.4GHz, ATI HD4850 la frecvența nominală 625Mgts, nVidia GTX 260 / w 192SP, de asemenea, la 1.242Ggts frecvență nominală.

Rezultatul este o listă cu o performanță de referință pe 4 nuclee Q6600 la o frecvență de 2,4 GHz:

Frecvență, număr de nuclee

Pretul CPU-ului sau GPU-ului

Prețul total al sistemului

2x ATI HD4870x2

0,75 x 800 x 2 x 2

4x nVidia GTX295

1,242 x 240 x 2 x 4

Pentru sistemele cu GPU lente (cum ar fi 8600 GT), este logic să se considere performanța ca CPU + GPU (ceea ce nu a fost făcut aici). Pentru procesor rapid același GPU va fi încărcat cu o cantitate suplimentară de calcule și sarcini de sincronizare, astfel încât să ia în continuare pe ea pur și simplu nu are nici un sens. În unele cazuri, un procesor quad-core poate să nu fie suficient pentru sistemele cu un GPU opt.

După cum puteți vedea, cea mai interesantă soluție în ceea ce privește prețul / performanța este un pachet de 4 HD4770. Încă o dată, cu toate acestea, este nevoie de o placa de baza, care poate găzdui patru astfel de carduri - în ciuda faptului că un singur cip sistem de răcire carte HD4770 ocupă un spațiu suplimentar.

Există o problemă "mică" - lipsa practică de software pentru cardurile ATI. Cardurile de la nVidia sunt suportate în recuperarea parolei distribuite de ElcomSoft #, dar cu ATI până acum, totul este complet rău.

Concluzie: creșterea performanțelor de la utilizarea unui GPU este de aproximativ 4x-5x comparativ cu sistemul modern de patru nuclee. Cardurile de la ATI sunt considerabil mai rapide la același preț, dar pentru ele nu există aproape niciun software. Odată cu creșterea numărului de GPU-uri în sistem, problemele cresc neliniar - este nevoie de o sursă de alimentare puternică, o carcasă specială, un sistem eficient de răcire etc.

Și de ce o astfel de creștere mică?

Concluzie: este întotdeauna util să gândiți singur.

Ce parole pot fi considerate persistente?

Articole similare

Pagina anterioară

Pagina următoare