Expert zrýchlil hľadanie hesiel k SHA-1 sumám o 21%

DSL.sk, 6.12.2012

Jens Steube, autor populárneho softvéru hashcat pre hľadanie hesiel hrubou silou z ich kontrolných súm vytvorených hashovacími funkciami, nezanedbateľne zlepšil algoritmus hľadania hesiel z ich kontrolných SHA-1 súm.

Steube svoje výsledky prezentoval v utorok na konferencii Passwords^12 v nórskom Oslo.

Pri hľadaní hesiel hrubou silou z ich kontrolných súm, ktoré sa používajú pri ukladaní hesiel v informačných systémoch, sa postupne počítajú kontrolné sumy pre všetky možné hodnoty hesiel, v prípade SHA-1 majú vstupné dáta funkcie, heslo prípadne rozšírené o ďalšie bity, 512 bitov.

Štandardná implementácia SHA-1 bez optimalizácií pozostáva z 1148 operácií. Po viacerých v minulosti nájdených optimalizáciách bol doteraz dosiahnutý podľa Steubeho na GPU najnižší počet 828 operácií.

Steube prišiel ale na novú pomerne zaujímavú ale pritom jednoduchú optimalizáciu, ktorú je možné použiť iba v prípade počítania SHA-1 pre množstvo podobných hodnôt.

Na začiatku výpočtu SHA-1 sa 512 bitov vstupu rozširuje na 2048 bitov postupným XOR-ovaním 32-bitových slov podľa predpísanej jednoduchej schémy. Medzi dopočítanými bitmi je ale pomerne malá závislosť. Vzhľadom na použitie XOR je tak pri fixovaní 480 bitov testovaného hesla možné predpočítať dopočítavané bity a pri výpočtoch SHA-1 súm postupne pre vstupy s rozličnými hodnotami zvyšných 32 bitov získať dopočítané bity pri rozširovaní vstupu na 2048 bitov výrazne menším počtom operácií ako pri plnom výpočte pri všetkých testovaných heslách.

Tak je možné efektívne počet krokov pre jednu testovanú hodnotu znížiť o 21.1% na 694 krokov.

Ako vyplýva z povahy optimalizácie túto samozrejme nie je možné použiť na zrýchlenie výpočtu SHA-1 kontrolnej sumy pre jednu hodnotu a zrejme ani pri počítaní rainbow tabuliek s vyššou dĺžkou reťazí.

Podľa prezentácie (PDF) Steube optimalizáciu našiel už v prvom štvrťroku 2011, prečo ju zverejnil až teraz a či respektíve odkedy ju využíva jeho nástroj hashcat nie je jasné.


Najnovšie články:



Diskusia:

dnes má meniny Mikuláš Od: Kapor z Vane | Pridané: 6.12.2012 9:50 ...tak dúfam že sa ten kapor z chodby uráči a donesie niečo tekuté pod zub... Odpovedať Známka: 4.7 Hodnotiť:

Re: dnes má meniny Mikuláš Od: trigger.* | Pridané: 6.12.2012 10:05 ako to suvisi so sionistami a ich planmi na ovladnutie sveta? Odpovedať Známka: 3.6 Hodnotiť:

Re: dnes má meniny Mikuláš Od: stuka | Pridané: 6.12.2012 10:45 pocuje kapor, veris v zivot po vianociach ? Odpovedať Známka: 7.1 Hodnotiť:

komu to prospeje? Od: hud | Pridané: 6.12.2012 10:27 naco a kedy sa taketo dopocitavanie vyuziva? Odpovedať Známka: -5.8 Hodnotiť:

Re: komu to prospeje? Od: TnT | Pridané: 6.12.2012 10:34 na brute force zoo gay porna Odpovedať Známka: 7.1 Hodnotiť:

Re: komu to prospeje? Od reg.: Pjetro de | Pridané: 6.12.2012 10:56 To mas tazke odpovede - velmi vsak zalezi nato, kto sa pyta. Asi ako odpovede na otazky naco su komu goniometricke funckie, komplexne cisla, boolova algebra, fourierova transformacia vyuzivajuca prvy spomenuty "nezmysel" a ine matematicke "zbytocnosti". To ze bez nich by pocitace ci iste "veci vb pocitacoch" v podstate neexitovali, sa niektorym ludom neda vysvetlit. Odpovedať Známka: 6.2 Hodnotiť:

Re: komu to prospeje? Od: smeghead | Pridané: 6.12.2012 12:18 Problémom asi je že nikomu sa to vysvetľovať ani nechce. Využitie niektorých matematických postupov mi vysvetlili až na vysokej škole, na strednej mali v paži, jednoducho nadhodili "máte to vedieť". A na to aby som si to sam odvodil zo samotných poučiek a prekomplikovaných definícií, na to som jednoducho príliš blbý. Odpovedať Známka: 8.0 Hodnotiť:

Re: komu to prospeje? Od reg.: Pjetro de | Pridané: 6.12.2012 12:52 Blby, to je zle slovo. Bezny clovek si len neuvedomuje rozsiahlost dusevneho vlastnictva ludstva a co s cim suvisi a co vsetko sa vsade vyuziva. Nie je to kvoli blbosti, ale len kvoli rozsahu toho dusevneho vlastnictva ludstva. Darmo je, polyhistori defacto vyhynuli pred pol-tisicrocim (aj ked niekto nam tvrdil ze to bolo pred 250 rokmi :). Odpovedať Známka: 7.1 Hodnotiť:

Re: komu to prospeje? Od: Izmail | Pridané: 6.12.2012 14:46 A ty neprestanes s tym vlastnenim dusi, unterwasserman. Dusa je iluzia vytvorena predstavou nesmrtelnosti. Vlastnictvo je iluzia vytvorena egom. Ego je osobny vztah k sebe, zrkadlo v mysli. Odpovedať Známka: -2.5 Hodnotiť:

Re: komu to prospeje? Od reg.: leader | Pridané: 6.12.2012 20:44 ujasni si pojmy dusa vs dusevny dusevny = opak telesneho, dusevna praca, dusevna choroba dusa = ozivujuci princip, podla niektorych filozofov mala aj materialny charakter alebo bola aj smrtelna Odpovedať Známka: 7.8 Hodnotiť:

Re: komu to prospeje? Od reg.: Pjetro de | Pridané: 7.12.2012 6:56 Mojenko ty si mimo alebo ano? Idiom "dusevne vlastnictvo" vidis prvy krat alebo ano? Ja ti to prelozim: vedomosti, zrucnosti, navyky ... cul je aj moderne take one, ze "know how", ale to nie celkom dobre vystihuje podstatu, hlavne eventualny doslovny preklad. Odpovedať Známka: 7.8 Hodnotiť:

Pošli papier Od: prdlajs | Pridané: 7.12.2012 22:22 A ja som dneska rano cestou na zachod zrychlil svoj krok o 200%, ked to na mna prislo o trochu skor. Odpovedať Hodnotiť:

Pridať komentár