Kolíziu u hashovacej funkcie SHA-1 je možné nájsť už na 2 ^ 52 krokov

DSL.sk, 11.6.2009

Tím z austrálskej Macquarie univerzity v Sydney prezentoval skôr tento rok na konferencii Eurocrypt 2009 postup, ktorý umožňuje nájsť kolíziu hashovacej funkcie SHA-1 po rádovo 2 ^ 52 operáciách.

Útok tak môže viesť k nájdeniu vôbec prvej kolízie u SHA-1, teda nájdeniu dvoch rozdielnych správ s rovnakou SHA-1 hash hodnotou.

Doteraz najlepší zverejnený útok mal zložitosť 2 ^ 63 operácií, kolízia pomocou neho ale doteraz nebola nájdená respektíve nebola zverejnená a nie je známe, či niekto kolíziu pomocou tohto útoku vôbec hľadá.

Nový útok má samozrejme ešte relatívne ďaleko k použiteľnému útoku s prijateľnou zložitosťou na praktické aplikácie, bezpečnosť hashovacej funkcie SHA-1 je ale potrebné považovať za ešte menšiu ako doteraz.

V súčasnosti americký National Institute of Standards and Technology, NIST, vyberá novú hashovaciu funkciu, ktorá má nahradiť doteraz používané MD5 a SHA-1. NIST v súčasnosti odporúča používať už iba hash funkcie z rodiny SHA-2, konkrétne SHA-224, SHA-256, SHA-384 a SHA-512, ktoré sú ale len obdobou SHA-1.

MD5 bola definitívne kompromitovaná ako použiteľná hash funkcia na konci roka 2008, keď tím bezpečnostných expertov pomocou kolízií v MD5 uskutočnil reálny demonštračný útok na infraštruktúru X.509 digitálnych certifikátov a vytvoril falošné certifikáty prehliadačmi ale overované ako dôveryhodné.




Najnovšie články:



Diskusia:

prepracovaný? :) Od: enx | Pridané: 11.6.2009 15:31 tím bezpečnostných exportov -dakto tu veľa píše o kompoch :D Odpovedať Známka: 4.7 Hodnotiť:

Re: prepracovaný? :) Od: claudius | Pridané: 11.6.2009 16:57 co sa stalo s md6? uz bol vyradeny z dalsieho postupu? Odpovedať Známka: -3.3 Hodnotiť:

Re: prepracovaný? :) Od: kryptolog | Pridané: 11.6.2009 19:07 MD6 je stále jeden z kandidátov na SHA-3. Za chvíľu budú vyhlásení kandidáti, ktorí postupujú do druhého kola. Bude ich cca 15-20 -- najrýchlejší bez slabín a potom ostatní, ktorí sa budú NISTu pozdávať. Hlavný problém MD6 je jeho celková náročnosť na CPU. Je síce veľmi ľahko paralelizovateľná, čo takmer lineárne zrýchľuje aj na desiatkach jadier, cieľom súťaže je ale nájsť taký štandard, ktorý by bol použiteľný aj na 8bitových procesoroch. Tam tej výpočetnej sily moc nie je a taká MD6 by bola aj niekoľkonásobne pomalšia ako najrýchlejšie kandidátske funkcie -- Edon-R a BMW, v ktorých má mimochodom prsty český kryptológ Vlasta Klíma. ... ak je nejaká funkcia extrémne rýchla, je u nej preukázaná "dostatočná bezpečnosť" (čítaj nebola nájdená závažná slabina) tak je to doležitejšie ako pomalý akademický návrh. Odpovedať Známka: 10.0 Hodnotiť:

Re: prepracovaný? :) Od: kryptolog | Pridané: 11.6.2009 19:10 ... niekoľkodesiatoknásobne pomalšia ... Odpovedať Známka: 3.3 Hodnotiť:

Re: prepracovaný? :) Od reg.: Snake :) | Pridané: 11.6.2009 21:11 prispevok z kategorie inteligentnejsich ;) dakujem :) Odpovedať Známka: 10.0 Hodnotiť:

Re: prepracovaný? :) Od: Ja. | Pridané: 11.6.2009 21:14 Klíma je ten, čo sundal md5? Odpovedať Hodnotiť:

Re: prepracovaný? :) Od: kryptolog | Pridané: 11.6.2009 21:42 Áno aj nie. 1. zlomenie: Úž hodne dávno sa vedelo, že MD5 nie je ideálna hašovacia funkcia (už z princípu, že má krátky výstup) a Moorov zákon nepustí. 2. zlomenie: V roku 2005 prišla skupina Číňanov vedená prof. Wangovou a ako prví predviedli prakticky na počkanie kolíziu pre túto funkciu. 3. zlomenie: Vlastík Klíma rapídne urýchlil ich postup, takže bolo možné spočítať kolíziu za 15 minút na notebooku oproti "čínskym" 16 hodinám na výkonnom clustri. Odpovedať Známka: 10.0 Hodnotiť:

Re: prepracovaný? :) Od: kryptolog | Pridané: 11.6.2009 21:42 4. zlomenie: Následne prišli minulý rok ľudia okolo Marka Stevensa, ktorí boli schopní zneužiť MD5 takým sposobom, že začala byť nebezpečná aj v reálnom živote. Prišli do reálnej certifikačnej autority, ktorá ešte stále po všetkých tých varovaniach používala MD5. Nechali si podpísať žiadosť o osobný certifikát a vo vačku si potajme schovávali veľmi podobnú žiadosť, na ktorú podpis od autority tiež sedel vďaka vhodne zvolenej a krvopotne vypočítanej kolízii v MD5. Druhá žiadosť mala "malinkú odlišnosť" -- bol z nej zrazu validný certifikát podradenej certifikačnej autority, ktorý nebolo jednoduché revokovať. ... takže nie je sundať ako sundať :). Odpovedať Známka: 10.0 Hodnotiť:

Re: prepracovaný? :) Od: Mumsito | Pridané: 12.6.2009 0:30 Kryptografiou sa zivis alebo je to len konicek? Lebo toto co tu pises je fakt ze sila. Odpovedať Známka: 10.0 Hodnotiť:

Re: prepracovaný? :) Od: ~~~ | Pridané: 12.6.2009 9:43 zaujimave, dik za info Odpovedať Hodnotiť:

Re: prepracovaný? :) Od: joe07 | Pridané: 11.6.2009 21:30 Prispevok z kategorie ohurujucich :) Dakujem naozaj zaujimavy prispevok. Co citavam tieto diskusie tak musim povedat ze sem takmer nepatri :D kvalitou je rozhodne niekde uplne inde Odpovedať Známka: 10.0 Hodnotiť:

Fijuuuuuuuuuuuuuu Od: Xavier de la Slovak | Pridané: 11.6.2009 16:03 super clanok nechcelo sa mi ho citat, ale moze byt dobry. Odpovedať Známka: -6.1 Hodnotiť:

Re: Fijuuuuuuuuuuuuuu Od: _xxx | Pridané: 11.6.2009 16:33 super prispevok, zasluzi si -10 bodov. btw preco negativne prispevky nie su odlisene farbou? Odpovedať Známka: 2.6 Hodnotiť:

Re: Fijuuuuuuuuuuuuuu Od: sineddd | Pridané: 11.6.2009 18:36 lebo si slepy Odpovedať Známka: -6.4 Hodnotiť:

Re: Fijuuuuuuuuuuuuuu Od: Gbq | Pridané: 11.6.2009 17:20 + :D si zabil Odpovedať Známka: -0.3 Hodnotiť:

Re: Fijuuuuuuuuuuuuuu Od: whut | Pridané: 12.6.2009 12:58 aj ja som rovno presiel na diskusiu :D Odpovedať Hodnotiť:

Vypocet? :P Od: hanbim sa | Pridané: 11.6.2009 16:12 Ako dlho teda trva vykonanie 2^52 krokov? Ak ratam ze spominany krok, operacia = 1 cpu instrukcia tak pri 3GHz by to bolo 417 hodin... viem ze je to poriadna sprostost :( kedze su rozne typy procesorov atd Odpovedať Známka: 5.4 Hodnotiť:

Re: Vypocet? :P Od: Mettiu | Pridané: 11.6.2009 16:17 No ty vychadzas z toho ze jeden krok = jedna instrukcia co je urcite nespravne. Jeden krok bude hned niekolko instrukcii a niektore procaky spracaju dve instrukcie za takt myslim ze core procaky to dokazu takze je to dost tazke takto odhadnut ako dlho byt o trvalo. Odpovedať Známka: 6.9 Hodnotiť:

Re: Vypocet? :P Od reg.: Pjetro de | Pridané: 11.6.2009 20:28 Myslim ze mas pravdu :-) BTW moderne CPU Core 2 ci Core i7 alebo aj Ph II su uz tak optimalizovane, ze spravia v jednom cykle bud 3 alebo 4 instrukcie, spolu tak mame na 4 jadra 12 ci 16 instrukcii za takt. Inak to s tymi operaciami a krokmi je fakt sranda ... Niektori ludia myslia JEDINOU operaciou ci krokom zrejme aj vynasobenie dvoch 100-cifernych cisel ... samozrejme to je blbost, CPU uvazuje v dvojkovej sustave a 100-ciferne cislo v 10tkovej sustave je 301-ciferne v dvojkovej ... na nieco taketo je treba az desattisice ci mozno dokonca statisice operacii, pricom pod pojmom operacia sa rozumie napr. len rozoznanie 0 ci 1 na 173. mieste v slede 301 nul a jednotiek, pripadne ich vymena ... alebo ulozenie hodnoty do registra cpu ci do cache ... ale to uz zabieha asi do mikro-instrukcii cpu ... Nie som cpu inzinier, ale aj na primitivitu typu 5x3=15 treba velmi vela desiatok operacii a stovky mikroinstrukcii ... Odpovedať Známka: 3.3 Hodnotiť:

Re: Vypocet? :P Od: kryptolog | Pridané: 11.6.2009 20:58 Pjetro, Pjetro, nepreháňaj. Desatisíce? Stotisíce? Na vynásobenie dvoch dlhých čísel, napr. 512 bitových, je potrebných na moderných 64-bitových CPU rádovo desiatky operácií. Doporučujem pozrieť Karatsubov algoritmus. Odpovedať Známka: 10.0 Hodnotiť:

Re: Vypocet? :P Od: rms | Pridané: 11.6.2009 22:12 Hura, konecne niekto fundovany! Takze ten cas vypoctu zistime ako? Odpovedať Známka: 6.7 Hodnotiť:

Re: Vypocet? :P Od: kryptolog | Pridané: 11.6.2009 22:22 Presný počet cyklov procesoru závisí na konkrétnom CPU, prekladači, kóde, frekvencii, atď. Nechce sa mi to tu počítať, ale tie 512 bitové čísla stačí rozdeliť na osem 64 bitových kusov, navzájom ich v správnom poradí poprenásobovať a posčitovať. Dokopy by som to videl na max. 50 násobení (MUL) a 50 sčítaní (ADD). Žiadne desaťtisíce. Odpovedať Známka: 6.7 Hodnotiť:

Re: Vypocet? :P Od: kryptolog | Pridané: 11.6.2009 22:31 ... počet cyklov závisí ... na frekvencii. Peknú blbosť som napísal :). Odpovedať Známka: 10.0 Hodnotiť:

Re: Vypocet? :P Od reg.: Pjetro de | Pridané: 12.6.2009 10:14 hej, to je pravda, nasobenie sa da zjednodusit zgrupovanim (vytvaranim skupin cislic) a ich nasobenim a kombinovanim parcialnych vysledkov (nemusime mat len "skupiny" jednotlivych cislic) ... vynasobenie dvoch 64bitovych cisel tak moze vdaka specializovanym instrukciam trvat kratko :-) ale nechcem vidiet kolko manipulacii s 0 a 1 treba spravit napr. pri nasobeni 10111010 11110011 Odpovedať Známka: 10.0 Hodnotiť:

Re: Vypocet? :P Od reg.: Pjetro de | Pridané: 12.6.2009 10:27 a to boli len dve 8-bitove cisla :-) inak samozrejme ze cim je nieco specialnejsie (napr. nasobenie dvoch rovnakych cisel = druha mocnina), tym efektivnejsie a rychlejsie algoritmy je mozne nasadit (ponivac mame specialne pripady) Odpovedať Hodnotiť:

Re: Vypocet? :P Od: rms | Pridané: 11.6.2009 22:12 Hura, konecne niekto fundovany! Takze ten cas vypoctu zistime ako? Odpovedať Známka: -3.3 Hodnotiť:

Re: Vypocet? :P Od reg.: Pjetro de | Pridané: 12.6.2009 10:06 algoritmus som priznavam nepozeral, ale narazeme na problem co myslime pod pojmom operacia ... ked iba rozlisenie 0 ci 1 na x-tej pozicii retazca 512tich nul a jednotiek, resp. nahradenie 0 ci 1 za nieco ine (ale samozrejme tiez 0 ci 1) na zaklade istych logickych pravidiel (or and xor ...), tak tych "operacii" bude treba asi viac Odpovedať Hodnotiť:

Re: Vypocet? :P Od: kryptolog | Pridané: 12.6.2009 19:52 Pojmom operácia som mal na mysli MUL, ADD a podobne. Na moderných procesoroch možu mať na vstupe dva 64 bitové operandy. Odpovedať Hodnotiť:

Re: Vypocet? :P Od reg.: 34224 | Pridané: 12.6.2009 2:23 mas takmer pravdu, az na fakt ze CPU realne neda 3 az 4 instrukcie na takt. na vec typu 5x3 staci jedna instrukcia -> MUL, co ale vobec neznamena ze sa vykona za jeden takt (aj ked ALU obsahuje nasobicku). instrukcie trvaju od 1 do cca 12 taktov. vdaka pipeline sa ale nemusi cakat tych 1 az 12 taktov na to aby sa mohla vykonavat dalsia. a dalej CPU (tusim ze je to superscalarita) moze vyuzivat casti ktore momentalne instrukcia nepotrebuje. a este tu mame out-of-order vykonavanie. takze spocitat kolko trva 2^52 krov (co sa nerovna 2^52 instrukcii), je silne netrivialne. a teraz ma zakopte. ;-) Odpovedať Známka: 10.0 Hodnotiť:

Re: Vypocet? :P Od reg.: Pjetro de | Pridané: 12.6.2009 10:03 Ale kdeze zakopat, pises velmi fundovane ... na "velke", moderne, nove instrukcie je sice treba malo CPU cyklov, avsak tieto instrukcie su tak zlozite, ze su rozlozene do velkeho poctu mikro-instrukcii. Vec typu 5x3 sa moze dat vypocitat specialnou instrukciou, avsak v dvojkovej sustave to je zapisene pod sebou nasledovne: 101 * 011 ------ 101 101 000 ------ ------ 01111 a na nieco taketo treba tucty mikroinstrukcii (jedina mikroinstrukcia niekde v retazci odlizi 0 od 1, prip. nahradi podla istych logickych pravidiel, ale zrejme o nic viac) Odpovedať Hodnotiť:

Re: Vypocet? :P Od reg.: x x l l | Pridané: 13.6.2009 1:02 Tak toto platilo mozno tak pred 30+ rokmi. Dnes sa to skutocne vynasobi na niekolko par cyklov CPU v hardwarovej nasobicke. Vsak co si myslis, na co sa vyuzivaju tie stovky milionov tranzistorov (po odratani cache su to stale stovky milionov tr:) Rozhodne to nie su mikroinstrukcie, ale rozne algoritmy, implementovane priamo v HW. Mikroinstrukcie sa pouzivaju maximalne tak na osetrovanie bugov v CPU a na implementaciu dnes uz prakticky nepouzivanych instrukcii (koli spetnej kompatibilite) a modov CPU. Dalsia pravda je taka, ze dnes uz vyrobcovia CPU vcelku kaslu na celociselne naosbenie/delenie. Je mozno 2-3x pomalsie ako operacie vo FPU, no roznodne sa aj tak nevykonava mikroinstrukciami:) Odpovedať Hodnotiť:

Re: Vypocet? :P Od reg.: x x l l | Pridané: 13.6.2009 1:13 ...ale ak by si chcel ist naozaj do hlbky a brat za jednotku najmensej operacie NAND (alebo NOR), alebo len obycajne zopnutie tranzistoru, tak skutocne, na trivialne vynasobenie dvoch cisel procesor vykona urcite aj niekolko miliard operacii:) Odpovedať Hodnotiť:

Re: Vypocet? :P Od: rms | Pridané: 12.6.2009 12:37 ano ano, toto vsetko som si uvedomoval uz s prvym postom a prave kvoli tej netrivialnosti ma to drazdi :) ide o to spravit odhad pre jednotlive typy procesorov na zakladne dostupnych poznatkov Odpovedať Hodnotiť:

Re: Vypocet? :P Od reg.: x x l l | Pridané: 13.6.2009 0:40 Nasobenie je praveze trivialna operacia a da sa lahko rozlozit do pipeline a tak isto sa da na urovni hardware dobre paralelizovat (existuju pochopitelne hardwarove nasobicky, takze ziadne orgie s mikroinstrukciami sa nekonaju). Maximalne sa to vykona v menejbitovych nasobickach na niekolko krokov. Ovela vacsi problem je delenie, ktore je uzke hrdlo vsetkych dnesnych CPU a aj najrychlejsie delicky maju priepustnost tak jedno delenie za 7..8 cyklov (pri dnesnych GHz uz hadam nedosiahnutelny vykon) Odpovedať Hodnotiť:

Re: Vypocet? :P Od reg.: 34224 | Pridané: 13.6.2009 21:37 sorry, ale fakt nevies co su mikroinstrukcie Odpovedať Hodnotiť:

Re: Vypocet? :P Od reg.: x x l l | Pridané: 14.6.2009 9:42 No pouc ma majstre... Odpovedať Hodnotiť:

Re: Vypocet? :P Od: blizz.boz | Pridané: 11.6.2009 16:44 hovori ti nieco grid computing? Odpovedať Známka: -5.0 Hodnotiť:

Matika Od: Matik | Pridané: 11.6.2009 17:01 to si sa teda riadne preratal Odpovedať Známka: 2.0 Hodnotiť:

Riesenie Od: Nadeo | Pridané: 11.6.2009 17:10 sha1(md5()) Odpovedať Známka: -6.7 Hodnotiť:

Re: Riesenie Od reg.: Chuck Garabedian | Pridané: 11.6.2009 17:17 myslis? Odpovedať Známka: -4.5 Hodnotiť:

zla stavba viet Od reg.: Kveri | Pridané: 11.6.2009 20:03 Neviem, ci vsetky clanky pise jeden autor alebo vsetci autori nevedia pisat. Niektore vety nemaju spisovne a korektne poradie slov, napriklad posledna. Nezda sa vam? Ja to vidim uz prakticky v kazdom clanku/novinke tu na dsl.sk Odpovedať Známka: 0.0 Hodnotiť:

Re: zla stavba viet Od reg.: Kveri | Pridané: 11.6.2009 20:05 a to niesom nijaky slovencYnar a nechcem na nikoho nakladat, ale zle sa to cita... Odpovedať Známka: 0.0 Hodnotiť:

Re: zla stavba viet Od reg.: Snake :) | Pridané: 11.6.2009 21:13 nerob :) lebo dostanes ban :) Odpovedať Známka: 10.0 Hodnotiť:

Pridať komentár