brute force sebességét a CPU és a GPU

előző ◈ a következő

GPU számítási utóbbi időben nagyon népszerű minden régióban, ahol lehetőség van, hogy használja őket. Az egyik ilyen terület a kriptográfia, szűkebben - kiválasztás / válogatás a jelszavak. Sajnos, a tényleges munka eredményeire (mint ahogy általában ez a helyzet) díszít marketing célokra, úgy, hogy nem nagyon világos, amely ténylegesen részesülnek a GPU használat terén.

Hosszú rövid magyarázat végén csatlakozók (ami valószínűleg megéri, és olvassa el, amikor elolvasta az első a cikket).

Abban az időben töltött brute force.

Ha tíz évvel ezelőtt, minden fejlesztő megpróbálta felér egyfajta, az eredeti titkosító algoritmus (de mivel szinte senki sem szakértő a kriptográfia területén, a legtöbb ilyen „eredeti” algoritmusok törtek az idő), de most ez sokkal könnyebb lett . Szinte minden vizsgált standard áramkört.

Titkosításra, először meg kell alakítani a jelszót egy kulcs egy bizonyos típusú és méretű (lépés tördelés), majd használja ezt a gombot, hogy titkosítja a tényleges adatok (bármely megbízható algoritmus, mint AES).

Hash MD5 közelmúltig nagy mennyiségben, de (felfedezése után sebezhetőségét algoritmus) elég gyorsan cserélni SHA1. Az SHA1 jelenleg még nem teljesen simán megy (a megállapítása összetett ütközés mintegy 2 ^ 63, és az utóbbi időben egyre bejelentette számának csökkenése legfeljebb 2 ^ 52), de ha azt használják az egyes „keretes”, mint PBKDF2 komplexitás (vagy inkább könnyű) ütközés hely nem olyan fontos.

A PDF9 Adobe nagyon hiányzott egy új algoritmust, akik egy iterációs SHA256 50 helyett MD5 + 20x RC4, ami felgyorsította a sebesség brute force, mint az előző változat majdnem két nagyságrenddel. De miután tördeljük a jelszó érvényesítése nem igényel titkosítást, úgyhogy csak az a fontos SHA256 sebességet.

Megfelelő titkosítási algoritmus lehetetlenné teszi brute force csökkentését helyet kulcsokat. Ez az, hogy megtaláljuk, például 128 bites kulcs kell átmenni 2 ^ 128 == 3.4 * 10 ^ 38 lehetőségeket. Feltételezve, hogy egy számítógép megy keresztül milliárd lehetőség a második, van egy milliárd számítógépet, és van egy milliárd év, mely idő alatt leszünk képesek ellenőrizni, csak 10 * 9 * 10 * 9 * 10 * 9 * 60 * 60 m * 24 óra * 365,25 d

= 3,16 * 10 ^ 34 megvalósításokban, a kívánt tartományban kevesebb, mint 1/10000.

Példa sikertelen titkosítási algoritmusok: a 96 bites kulcs klasszikusan zip. Annak ellenére, hogy az elmúlt több mint 20 év óta a létesítmény az algoritmus, ezeket a kulcsokat egyelőre lehetetlen rendezni „a homlokán.” Azonban, miután egy részét egy nem titkosított fájlt, akkor végezze el az úgynevezett nyílt szövegű támadás, míg a bonyolultsága brute force fog esni, hogy 2 ^ 96 csak 2 ^ 38, ami csak egy pár órát a modern számítógép.

Minden az „erős” titkosítási algoritmusok (AES, Blowfish, stb) nem engedi a sima támadás, és nem teszik lehetővé, hogy csökkentsék a helyet kereső. Így az egyetlen módja annak, hogy hozzáférjen a titkosított fájlok - tudni, hogy a helyes jelszót.

Következtetés: A titkosítási algoritmus által használt gyakorlatilag nincs hatása a sebesség brute force. Jó algoritmus egyszerűen lehetetlenné teszi választógomb „a homlokán.” És most a lényeg az, hogy halad végig az átalakítás jelszavakat egy jelszót egy kulcs, és ez felelős a hash algoritmusok (MD5, SHA1), ahelyett, titkosítási algoritmusok (AES, Blowfish).

Az érték a „iterációk száma”, mondja kicsit.

MD5, SHA1 (és annak leszármazottai, mint SHA256, 384, 512) nagyon hasonló. A bemenetnél van egy állam hash (128 bit a MD5, 160 bitet SHA1) és az adatok blokk mérete 512 bit (64 bájt). A kilépés után tördeljük műveletek, megkapjuk az új állam a hash. Ez a szíve az algoritmus, a funkció általában az úgynevezett MD5_Transform, SHA1_Transform stb

Fontos megjegyezni, hogy a blokk mérete állandó, mindig hashelt pontosan 64 bájt. Ha bemenetére táplált 1 bájt, akkor ki kell egészíteni, hogy a 64 hozzáadásával nullák terminátor szimbólum és egy 8-bájtos érték blokkhosszúság. Azaz, a fájl külön input hash függvény, 64 × 1 byte vagy egyszer minden 64 byte - teljesen azonos a feldolgozási sebesség sík (nem számítva azt a tényt, hogy ha az 64 bájt szimbólum terminátor és a hossz értéke folyamat már a következő mondatban) .

Egyes algoritmusok írva az iterációk számaként függvényhívásokkal frissíteni a hash. De nem minden változtatás vezet hívja Transform funkciót. Az összegyűjtött adatok a pufferben, és átvisszük Transform blokkok 64 bájt. Például a RAR 3.x iterációk száma egyenlő 262.144, de ez a szám a feldolgozott blokkok egyenlő ((dlina_parolya * 2 + 8 + 3) * 262144) / 64. A, például jelszavak 4 karakteres lesz 77.824 (+ 17 több további blokkok létrehozásához IV AES).

Mit hoz az ismétlések számát, hogy a blokkok száma a Transform? Mivel a hash számítási idő független az adatokat a blokk is állandó, tudván az időt tördeljük egy blokk, és az egységek számát könnyen kiszámítható a teljes idő hasítás. Azt is könnyű megbecsülni, hogy sokkal gyorsabb vagy lassabb különböző jelszó generálása algoritmusok egymáshoz képest.

Például alapján számítások egyértelműen látszik, hogy a sebesség WinZip / AES brute force in

Következtetés: A szám a „virtuális” ismétlések az algoritmus nem jelent sokat. Ahhoz, hogy megbecsüljük a sebesség ismernie kell a száma 64 byte-os blokk használt hasítás. Ismerve ezt az értéket, az általános feldolgozási sebesség könnyen előállítható egyszerűen megszorozva ezt az értéket a feldolgozás egy adatblokk.

Milyen gyorsan tudok hash?

Most mi érdekli a kérdés, hogy milyen gyorsan tudja feldolgozni a 64 byte-os adatblokkot. Operations ispolzueschiesya Transform funkció a legegyszerűbb - logikai OR, XOR, NOT, AND, aritmetikai kívül műszakban. Minden művelet a 32 bites egész szám. Egy adatblokk könnyen elfér bármelyik L1 cache modern processzorok, hogy a sebesség a memória mérete, a méret a L2 vagy RPM merevlemez nem játszik szerepet. Más szóval, a sebesség közvetlen függvénye értéke ALU sebesség, és gyakorlatilag nem függ a többi. Egyes modern processzorok a legjobb?

Processzorok.

Mivel tördeljük különböző jelszavakat nem függnek egymástól, akkor nagyon előnyös, ha valamilyen SIMD utasításkészlet a párhuzamos feldolgozás. Legjobb SSE2 (bár a „régi» MMX még használat) lehetővé teszi, hogy valamely művelet azonnal négy 32 bites operandus. Egy első megvalósításban a Pentium 4-os sebességgel SSE2 utasítás nem fog simán (például szállítás registr-> honnan regiszter 6 cikluson és egészben vagy 2), de még akkor is a nyereség az alkalmazásuk meglehetősen figyelemre méltó. Ugyanakkor SSE2 végrehajtását a Intel Core architektúra egyszerűen gyönyörű: lehetséges, hogy végre 3 művelet per óra, az eredmény kész lesz a következő ciklusban (latency == 1 bar). Azaz, a csúcs teljesítménye a Core 12 műveletek 32-bites egész ciklusonként. Bár nem minden művelet végezhető ezen a csúcssebesség.

Annak ellenére, hogy az új mag felülvizsgálata, az átmenetet a 65 nm-es a 45 nm-es, és végül engedje Core i7, nincs jelentős változás az integer ALU történt. Ezért Core i7 működik majdnem valamint annak őse 65nm Core 2 kapacitása függ csak a frekvencia, így például Q6600 órajele 3 GHz (ami elég gyakori gyakorlat) pontosan 3 / 2,66 = 12,7% -kal gyorsabb mint a Core i7 920 a névleges frekvencia (kivéve turbó tört). Az ára a Core i7, beleértve az alaplap és DDR3 lényegesen magasabb, mint a „régi” Core 2 rendszer 65 / 45nm-es.

A helyzet valamivel rosszabb az AMD. Még most is, még mindig jó néhány rendszerek Athlon XP processzor. Abban az időben, ő nagyon jól versenyezni P4, de nincs SSE2. Az építészet, a K8 AMD tette támogatása SSE2, de a legprimitívebb formája: 128 bites utasítások vannak osztva két részre, és fut a 64 bites ALU. Mi vezetett arra a tényre, hogy a különbség az MMX és SSE2-kód szinte nem volt.

Az Advent a K10 (vagy Phenom) AMD végre SSE2 támogatása méltóságteljesen, de a Core 2 lényegesen rosszabb. K10 képes elvégezni akár 2 műveletek 4 x 32-bites egészek ciklusonként, és a művelet eredménye lesz kész csak ciklus után (látencia == 2 ciklus). Azaz, a csúcs teljesítménye 8 műveletek egy 32-bites egész ciklusonként. Mit jelent ez szempontjából összehasonlítást K10 vs Core 2: Az AMD processzor átlagosan 1,5-szer lassabb, ha meg tudjuk építeni utasítást, hogy a várakozási idő nem volt korlátozó tényező. Bizonyos algoritmusok, tekintettel a korlátozott számú XMM regiszterek, így nagyon nehéz, ha nem lehetetlen.

Másrészt, nem minden művelet Core 2 végezhet szinten „három órajelenként. Kiegészítéseket lehet csak kettő, és a változások általában egy. K10 képes mozogni két XMM regiszterek per óra, de a várakozási idő 3 cikluson keresztül. Ezért a tényleges aránya teljesítményű Core 2 vs K10 lebeg valahol 1.25-2x területen. K10 mindig lassabb feladatok csak attól függ a SSE2 ALU sebességet, de lehet gyorsabb algoritmusok különféle értékeket a memória, és a hiányzó logikai műveleteket.

Phenom II, ami nem tűnt olyan régen, csak eltérő Phenom # „és sokkal kisebb, mint a Core i7 egy 45nm-es Core 2. De szükség van, persze drágább.

Fontos megjegyezni, hogy ebben az időben a használata SSE2 kötelező párhuzamos feldolgozás. A logikai művelet egy 32 bites regiszter, vagy több mint 128-bites XMM regiszter, amely négy 32 bites érték, kerül végrehajtásra pontosan ugyanabban az időben. Számított a Core 2 nélkül SSE2 ez olyan, mint, hogy a GPU és a ki rajta ¾ valamennyi stream processzor.

Továbbá, a jelszó-helyreállítási feladatot tökéletesen párhuzamosított, mivel nincs összefüggés az adatokat. Ezért a termelékenység növekedésével lineárisan gyakoriságát és a magok számának. Semmi értelme, hogy a „gyors” dvuhyadernik, ha ez lehetséges, hogy „lassú” chetyrohyadernik. Más szóval, Q6600 2,4 GHz frekvencia fog működni, mint 4 * 2.4 = 9.6Ggts és E8600 3,33 GHz csak 3.33 * 2 = 6.66Ggts. A különbség a sebesség 1,5-szer, az árkülönbség közel azonos, de az ellenkező irányba.

Következtetés: A legjobb CPU brute force jelenleg az Intel Core Quad. Az az ár / teljesítmény jövedelmezőbb Core 2 65 / 45nm-es. Költség rendszerek Core i7 fenti és a frekvencia nem jobb, mint a „régi» 2 Core processzorok az AMD-től messze elmarad az SSE2 egész számításokat, és így az ár közötti különbség a Core 2 és Phenom nem kompenzálja ezt lag. SSE2 szükséges fogyasztást, valamint a képességeit a modern processzorok egyszerűen nem derül ki.

Tehát miután az összes, milyen gyorsan tud hash?

Nagyon durván, a sebességet, a felhasznált függvények az alábbiak szerint becsülhető:

Természetesen egy ilyen értékelés nem veszi figyelembe számos különböző tényező, de alkalmas arra, hogy gyorsan megérteni, milyen gyorsan ez elméletileg lehetséges, hogy végre MD5_Transform. Tapasztalt ugyanazt az eredményt, mint mindig, úgy néz ki, még rosszabb. De nem annyira:

MD5_Transform 72 cikluson át egy 64 bites módban.

MD5_Transform 90 ciklus 32 bites módban.

MD5_Transform a legegyszerűbb megvalósítása a feldolgozó SSE2 csak 4 blokk 128 alkalommal kullancsok.

SHA1_Transform 175 óra a 32-bites módban, óra 162 64-bit.

A SHA256 pontos értéke nem (mert ez használ SHA256 sokkal kevesebb), de SHA256_Transform lesz legalább 425 ciklus. A jelenléte sokkal nagyobb számú műszakok és kiegészítések valószínűleg növeli ezt az értéket.

A 64 bites módban lehetővé teszi, hogy kétszer a XMM regiszterek, ami viszont segíti megoldani a problémákat a késleltetést. Ez különösen hatással van MD5, ahol a tranzakciók nagyon kicsi, hogy mindig meg kell várni az eredményeket a korábbi számítások ha a folyamat csupán 4 adatblokk egy időben.

Az elméleti és a gyakorlati eredmények.

És végül egy összefoglaló táblázat a kedvéért, amely mindent indult. Összehasonlítása az árak a különböző jelszavakat. Ezeket használják:

Speed mértük egy egymagos Intel Core 2 Q6600 @ 2,4 GHz-es, ATI HD4850 a névleges frekvencia 625Mgts, nVidia GTX 260 / w 192SP is névleges frekvencián 1.242Ggts.

Az eredmény egy lista a kiindulópontot a termelékenység 4 atommagok Q6600 2,4 GHz frekvencia:

Frekvencia, magok számának

Az ár a CPU vagy GPU

Az ár a teljes rendszer

2x ATI HD4870x2

0,75 x 800 x 2 x 2

4x nVidia GTX295

1,242 x 240 x 2 x 4

Rendszerek esetében lassabb GPU (mint a GT 8600), érthetővé válik, hogy fontolja meg a teljesítmény, mint a CPU + GPU (ami nem történt meg itt). A gyors azonos GPU processzor kerül betöltésre további számítások és feladatok szinkronizálás, hogy vegye be tovább, hogy csak nincs értelme. Egyes esetekben, a quad-core processzorok nem lehet elég rendszerek 8 GPU.

Mint látható, a legérdekesebb megoldás az ár / teljesítmény kombinációja 4-HD4770. Ismét azonban megköveteli egy alaplap, amely képes befogadni a négy ilyen kártya - annak ellenére, hogy a HD4770 egyetlen chip-kártya hűtési rendszer vesz fel további nyílásba.

Volt egy „kis” probléma - a szinte teljes hiánya szoftver ATI kártyákat. Kártyák az nVidia által támogatott ElcomSoft # „s Elosztott Password Recovery, de az ATI, amíg a dolgok nagyon rossz.

Következtetés: A teljesítmény-erősítés segítségével egyetlen GPU mintegy 4-5-szeresére, mint a modern quad rendszer. ATI kártyák sokkal gyorsabb ugyanazon az áron, de alig vagy egyáltalán nem szoftver. A növekedés a száma GPU nemlineáris problémák nőnek rendszer - van szükség nagy teljesítményű tápegység, egy kamra, egy hatékony hűtőrendszer, stb