Názor k článku Nalézání kolizí MD5 - hračka pro notebook od anonym - Díky za konstruktivní dotaz. Dávám ho mimo, a...

Díky za konstruktivní dotaz. Dávám ho mimo, a proto musím opakovat i text.

Datum: Dnes 23:23
Autor: jk
Titulek: Re: objevitel nebo zlepšovatel ?

Vykašlete se na to, to snad nemá smysl odpovídat. Já se těšil, že se tu v diskusi dozvím nějaké zajímavosti, a místo toho tu početně převažují nesmysly od ignorantů, kteří pravděpodobně netuší co to ta md5 vlastně je, a reakce na ně.

Odpověď: To je daň za demokracii. Diskuse odráží její stav. Misto věcného řešení problemů diskuse o nicem. Kdyby politici venovali cas na vytvareni a urovnavani tzv. vladni krize na věcné řešení problemů (jak říká Švejnar), mozna bychom meli do skolstvi o par miliard vic. Kdyby se TADY diskutovalo k veci, mohli bychom se neco dozvedet nebo vyresit. Treba ten protokol s ip. Nebo ty vase otazky. Jsou dobre, musel jsem se znovu na neco podivat. To obohati mne i vas.

Radsi bych se zeptal
- myslite, ze ted Cinani svuj postup zverejni? Prijde mi, ze jakekoli dalsi cekani jaksi ztraci vyznam.

Odpověď: Skutecne další čekání bylo napínání veřejnosti. Bylo to dost neobvykle. Číňané svůj postup ale už zveřejnili! Je to velmi čerstvá novinka. Proběhlo to v tichosti a nenápadně. Bylo to zřejmě tak, že jakmile se prof. Wangová dozvěděla, že její příspěvek byl přijat na konferenci Eurocrypt 2005, dala ho k ostatním pracem na své internetové stránky a nechala to osudu. První to našel nějaký člověk, který si přečetl můj článek, pak dal vyhledávat "Wang" a to ho dovedlo až k jejímu článku. Byl schován v čínských znacích ale anglický název prominoval. Tak jsem se to dozvěděl i já. Pak jsme se tomu s Pavlem Vondruškou chvíli věnovali, kdy to tam asi dala a výsledek je výše. Informace o tom je například na http://www.root.cz/zpravicky/cinsti-vedci-promluvili/ s mým komentářem k obsahu a zdroj je na
http://www.crypto-world.info/news/index.php?prispevek=1245 .

- co si myslite o tom puvodnim "zverejneni-nezverejneni" formou ukazky, naslednem "prokecnuti" ze se umi najit kolizi pro libovolny inic. vektor,...? Kdyby takhle nekdo publikoval objev v nejakem jinem oboru, setkalo by se to se znacnou nelibosti.

Odpověď: No vypadá to dramaticky, ale vsadil bych na jiný scénář. U inicializačních vektorů se spletli. Když na to byli upozorněni, vyrobili kolizi se správným IV. Pak už bylo každému jasné, že to umí pro jakýkoliv IV, tak to i napsali. Nezveřejnili to proto, že by jejich příspěvek pak nemohl být přijat na Eurocrypt 2005. Crypto 2004 už nestíhali, uzávěrky příspěvků jsou půl roku před konferencí! Je to opravdu velice divné, že by si nezkontrolovali MD5 podle kontrolních příkladů. Mám ale své zkušenosti. Když jsem publikoval ten svůj článek, nechal jsem tam také chybu - v příkladu pro volený inicializační vektor jsem kolizi (data) našel správně, ale část programu, která dělala výpis hodnot pěkně do složených závorek, použila MD5 se správným IV. No a tuhle hodnotu jsem pochopitelně dal do příspěvku. Právě proto, že to vypadá naprosto nerealisticky, bych si tipnul, že ta čínská chyba je ze života.

- teď se tedy rychle bude nahrazovat za SHA-256 a spol. Z takoveho letmeho nadhledu to u me budi trochu neduveru. Jsou to zase iterativni funkce zhruba stejneho typu. Nepredstavuju si, ze je mozne nejake "definitivni reseni", jde o cas, ale tady mi pripada, ze kryptoanalyza postupuje dost rychle, az vy a cinani sve vysledky zverejnite, pujde mozna jeste rychleji... Existuji nejake podle vas zajimave hasovaci fce postavena na uplne jinych zakladech?

Odpověď: Je to pravda, ten rychlý postup bourání hašovacích funkcí v minulém a letošním roce všechny trochu zaskočil a vyděsil. I NIST. Ukázalo se, že princip iterování v hašovacích funkcích je genericky špatný. To (pouze) teoreticky a pro budoucnost odrovnává i hašovací funkce SHS-256/384/512/224, i když jen teoreticky a jen koncepčně. V praxi mají a pravděpodobně ještě asi pár let budou mít dost vysokou složitost, aby mohly sloužit. Ono stačí 10-20 bitů složitosti navíc a rok se promění v tisíc nebo milion let, čili velikost hašového kódu hraje ohromnou roli. Teoretické výhrady k iterování se mohou v praxi, pokud není nic lepšího, vzít jako zanedbatelné riziko. Horší je to s rizikem, že někdo na něco zase přijde. Ale to je z jiného soudku, to existuje vždycky. Hašovací funkce nejsou podloženy žádnými důkazy o nerozbitelnosti. Nicméně se to riziko zdá být vždycky větší, když někdo na něco nového přijde. Pak to zase utichne a jede se dál. Na tohle nové paradigma v chování ke kryptografickým technikám jsem se snažil upozornit v článku "Nedůvěřujte kryptologům". Potěšilo mě, když Lenstra vlastně ve svém současném článku o hašovacích funkcích z 26.2. říká velmi podobně věci.

Nejsem žádný odborník na hašovací funkce, ale maslím, že všechny současné mají iterativní strukturu. Takže se bude muset hledat jiný koncept. K tomu byl snad už vypsán nějaký projekt. Adi Shamir je téhož názoru, že potřebujeme nový koncept. Je to logické, protože Joux a Kelsey-Schneier ukázali, že současný koncept je teoreticky špatný. Je potřeba si pospíšit, protože proces výběru nového standardu trvá několik let a to nehovořím o tom, že kryptologové nejsou připraveni a nemají v šuplíku žádný nový kocept, pokud vím.
Osvěžil jsem si Tiger (http://www.cs.technion.ac.il/~biham/Reports/Tiger/tiger/tiger.html), ale je také iterativní, navíc 192bitový výstup není perspektivní. Vnitřek je ovšem zajímavý. Má jen nevýhodu, že ty vnitřní funkce nejsou tak dobře prozkoumány. Tipuji, že nová hašovací funkce bude mít vnitřek vystavěn na stejných základech jako SHA-1,2, protože to jsou prozkoumané věci. Podobně jako AES má základy z DES, i když se tváří, že ne. Když se dobře podíváte na vnitřek mikroskopem, všude je nálepka "stará dobrá DES".

- nejsou ty hase trochu presprilis popularni? Ma treba HMAC oproti MAC se symetrickou sifrou nejake bezpecnostni vyhody, nebo jde o rychlost?

Jsou použity všude možně. Vývojáři si na ně zvykli a dají je všude, kde to jde. Mezi HMAC a MAC je čistě z praktického hlediska rozdíl jen v rychlosti - HMAC je pomalejší. Je to asi tak, že pokud někdo má už v aplikaci hašovací funkci, a nevadí mu rychlost, pak nemusí už implementovat symetrickou šifru a MAC k tomu, aby zajistil (nepadělatelnou) integritu dat. Použije prostě HMAC místo MAC a kód se nezvětší. Jinak HMAC i MAC zajišťují totéž.