Staňte se programátorem: Prolomení MD5

Diskuze čtenářů k článku

05. 09. 2009 00:37

Opet mi chybi vice rozvedena pointa, co to vlastne hashovani je (jak se lisi od sifrovani) a proc se pouziva. Laik by si podle me mohl po precteni myslet, ze hash je totez co sifra. Vysvetleni hashove tabulky by zde bylo take namiste.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 11:07

Krok 1: Projdete si tento serial jako odstrasujici priklad.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 10:07

Myslím, že užití funkce Hashe MD5 a pokus o jeho "prolomeni" byl v tomhle pripade slapnutim vedle, asi by bylo lepsi kdyby ukazka demonstrovala moznosti na prikladu pocitani kontrolnich souctu souboru a jejich overeni.

Ukazka by to byla asi praktictejsi (a beznejsi) nez lamani MD5 hashu.

Souhlasím  |  Nesouhlasím  |  Odpovědět
avatar
31. 08. 2009 09:16

"Jako uživatel tedy mohu mít jistotu, že po transformaci sekvence X dostanu výsledek Y a ***neexistuje žádná jiná sekvence bajtů, se kterou bych dostal stejný výsledek Y***. Tento jev se nazývá kolizí a každá hašovací funkce se s tímto problémem potýká. "

Samozřejmě, že ke stejnému hashi Y EXISTUJE dokonce NEKONEČNĚ mnoho rozdílných vstupů X. U MD5 má digest délku 128 bitů (16 bytů) a tak je snad zřejmé, že kódování mnohem větší množiny vstupů vždy povede ke kolizím. Příklad v článku v teoretické rovině proto vůbec nemusí vracet původní řetězec X, ale nějaký jiný X', který jen shodou okolností dává také výsledek Y (pro tenhle konkrétní případ o délce 4 znaků ale zřejmě kolize existovat nebude).

Co se týče příkladu s metodou Rand, je tam uvedena náhodná inicializace časem generátoru pseudonáhodných čísel, a proto bude sekvence při každém spuštění programu vracet vždy různá čísla a tedy tentýž digest Y nám to "dekóduje" po každém spuštění programu jindy. To, že je to metoda i jinak nevhodná a v průměrném případě bude pomalejší než brute-force procházení množiny vstupů od začátku do konce je další věc (protože v případě toho náhodného generátoru se zcela jistě některá čísla zopakují než bude vyčerpána celá vstupní množina)

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 09:35

přesněji spočetně mnoho

Souhlasím  |  Nesouhlasím  |  Odpovědět
avatar
31. 08. 2009 09:49

Díky, už je to tu jako na starém Živě.cz, kdy člověk chodil hledat informace do diskusí místo do článků.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 10:47

Muzes byt rad ze tady ty informace najdes alespon v diskuzi.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 08:48

Pokud někdo opravdu chce seriózně prolamovat MD5ky, použije nejspíše (pokud nemá k dispozici botnet) toto: http://3.14.by/en/md5... .

Příjemnou zábavu.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 01:18

Použití funkce md5() mi moc jako prolomení nepřijde. Čekal jsem (no, vlastně ani nečekal) hledání kolizí. Viz http://www.mscs.dal.ca/~selinger/md5collision/... odkaz na to původní pdfko bohužel nefunguje a na disku se mi to hledat nechce.

Souhlasím  |  Nesouhlasím  |  Odpovědět
avatar
31. 08. 2009 00:32

Sa mi to len zdá, alebo tá "crackovacia" metóda naozaj skúša nájsť heslo pomocou (zakaždým) náhodne generovaných znakov? To si z nás snad děláte legraci, pane kolego

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 00:40

Jo taky bych rekl ze tato metoda neni zrovna ta prava.

Nahodne vygenerovat retezec a udelat jeho md5 hash. Mno to ze ten algoritmus "dojde" na konec za tech 40s je spise nahoda. Protoze tento algoritmus muze bezet klidne milion let a nemusi najit vysledek.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 00:53

Souhlas - takhle je to jako kdyby měl zloděj správný svazek klíčů a místo jednoho po druhém se do zámku snažil náhodně rvát co mu přijde pod ruku - když je blb (a jako autor nevyřazuje nesprávné pokusy) a nebo prostě jenom smolař, dovnitř se nedostane nikdy...

Jinak na brute force lámání bych ve 3. tisíciletí pochopil třeba kompilaci do poctivé binárky (matematika 10-100× rychlejší), když už ne rovnou paralelizaci pomocí GPU - předváděný .NET je v tomhle případě opravdu onanie...

Souhlasím  |  Nesouhlasím  |  Odpovědět
avatar
31. 08. 2009 06:47

samotny MD5 hash nepocita .NETti kod, ty poctiva binarko

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 07:38

No tady se autor opravdu trochu seknul, to je pravda. Nalezení stejného hashe je v tomto případě spíš věcí náhody, než výpočetního výkonu.

Jinak o té vaší "poctivé binárce" tak asi rozumíte .NETu jako kráva houslím. .NET je kompilovaný, takže vaších avizovaných 10-100x se přemění na 1.2x a to maximálně a taky je dost základních assembly psaných ve standartním neřízeném kódu. A ohledně paralelizace pomocí GPU, tak nevím jestli je tohle patří do podobné knížky pro začátečníky, když to nezvládne ani řada profesionálních programátorů.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 12:22

Pri vypoctoch tohoto typu, teda pri takych, kde je treba len hrubu vypoctovu silu je .NET brzodou nezavsle od toho, ci spomali 1.2x alebo 1000x. Pretoze to 1.2x ti k roku prida dva mesiace

Dalsi sialeny napad je vytvarat nieco take ako GUI aplikaciu. Taka aplikacia totiz musi popri dekodovani "poziciavat" CPU proceduram pre GUI, pripadne dokonca neustale nieco prekreslovat (aspon progress bar) a tym spotrebuje pre grafiku okolo viac vykonu, nez pre samotny vypocet.

Samozrejme je tu aj druha moznost, GUI proceduru vobec nevolat, to ale skonci docasnym zamrznutim programu bez moznosti jeho prerusenia/pozastavenia/restartovania a pri dostatocne dlhom vypocte pravdepodobne skonci tym, ze uzivatel zamrznuty program "zakilluje."

Souhlasím  |  Nesouhlasím  |  Odpovědět
a-c
31. 08. 2009 14:14

nesmysly. zpomaleni diky .NET existuje, ale pokud to nekdo nechce mlatit v assembleru, tak je minimalni. GUI na to uz vubec nema vliv - samotna rezie OS je mnohem vyssi, a prekreslovani se deje pouze tehdy, pokud je potreba, pricemz rezie na progress bar je zanedbatelna. a "zamrznuti" se da velmi snadno vyresit spustenim vypoctu v jinem threadu, ale o to v tehle ukazce neslo. aspon predpokladam. zadna optimalni multi-threadova paralelni aplikace, ale proste ukazka "rychle a jednoduse".

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 14:32

> nesmysly. zpomaleni diky .NET existuje, ale pokud to nekdo nechce mlatit v assembleru, tak je minimalni.

Ako som uz spomenul, to "minimalni" treba znasobit tou miliardou pokusov, ktore bude treba prebehnut.

> GUI na to uz vubec nema vliv - samotna rezie OS je mnohem vyssi

Navrhnut vyuzitie menej narocneho OS som jaksi nemal odvahu

> a prekreslovani se deje pouze tehdy, pokud je potreba,

... respektive aspon dva krat za sekundu, ak chceme implementovat dake tie "stop" a "pause" tlacitka (ci aspon regulerne ukoncenie programu) alebo aspon raz za (tusim) 5 sekund, ak nam nevadi ich oneskorena reakcia ale chceme zabranit hlaske "program neodpoveda."

> a "zamrznuti" se da velmi snadno vyresit spustenim vypoctu v jinem threadu, ale o to v tehle ukazce neslo. aspon predpokladam.

Ako pripadne vyuzitie viacerych jadier/CPU by som si skor predstavoval rozdelenie vypoctu na viac casti (u bruteforce attacku by to nemal byt problem.) Inak by rozdelenie programu na vlakna znamenalo len dalsie mrhanie strojoveho casu, obzvlast na jednojadrovom procesore.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 16:59

Ono zpomalení .NETu je dost diskutabilní, zrovna v tomhle případě bude naprosto minimální, protože se jedná o jednu maličkou metodu. Tím pádem ji JIT zkompiluje a navíc bude mít dost času, takže udělá i hodně optimalizací (odhad). Režie .NETu se projeví daleko více na jiných místech, které tady nemáme.

To, že je to okénková aplikace, zase taky tolik nezpomaluje, čas strávený systémem prací s okny je naprostý zlomek času, který aplikace stráví počítáním. To jsou naprosto zanedbatelné faktory.

Co je ovšem daleko větší diletantnství autora, že při každém počítání MD5ky vytváří nový StringBuilder, a to naprosto zbytečně. Může krásně použít ten starý, navíc v případě, že jsou všechny stringy stejně dlouhé. V běžných situacích tyhle věci nemá smysl řešit, protože jestli vytvořím jeden nebo sto objektů, je celkem jedno. v tomhle případě, kdy se metoda spouští milionkrát, to ale smysl řešit opravdu má. Není radno zapomínat, že vytvoření StringBuilderu alokuje nějaký buffer, kam pak stringy cpe. Když použijeme ten starý, nic nového již nealokujeme.

Další neschopností autora je i v tak krátké ukázce kódu ohlídat si překlepy. Pojmenovat proměnnou lenght místo length se sice jeví jako prkotina, ale zrovna tento překlep je dost nešťastný a svědčí o tom, že autor nemá jasno, kde se píše TH a kde HT - je Length, ale Height.

Mimochodem vysvětlení, jak je to s těmi kolizemi, by také mohlo být trochu méně odfláklé. Věta "Jako uživatel tedy mohu mít jistotu, že po transformaci sekvence X dostanu výsledek Y a neexistuje žádná jiná sekvence bajtů, se kterou bych dostal stejný výsledek Y." je naprostý nesmysl. I když je tam napsáno "jako uživatel", jistotu nikdy nemám, mám pouze skoro jistotu.

Souhlasím  |  Nesouhlasím  |  Odpovědět
31. 08. 2009 00:22

Vždy si rád prečítam nové diely tohto humoristického seriálu

Souhlasím  |  Nesouhlasím  |  Odpovědět
avatar
31. 08. 2009 02:14

Precits nadpis, prolitnout kod a pak tim smichem nevzbudit spici cleny rodiny... a ten smich od place bude stezi rozeznatelny...

Souhlasím  |  Nesouhlasím  |  Odpovědět
avatar
31. 08. 2009 06:23

Mě nejvíc pobavila informace o tom, že do databáze se ukládá čistý hash. Dál už jsem to raději nečetl.

Souhlasím  |  Nesouhlasím  |  Odpovědět
Zasílat názory e-mailem: Zasílat názory Můj názor