Ondra podstatu vysvětlil právě v předchozí odpovědi, jenom to sepišme:
Uvažujme novou hašovací funkci H(x), která je složena ze tří hašovacích funkcí takto: H(x) = H1(x) || H2(x) || H3(x).
Nejprve si vysvětlíme první Jouxovu fintu. Pracuje za předpokladu, že u dané hašovací funkce umíme najít kolizi pro libovolnou inicializační hodnotu. První dvojici kolidujících zpráv nalezneme pro IV z definice dané hašovací funkce H. Další IV definujeme jako výsledek právě proběhlého hašování (tj. hodnotu první kolize) a pro tuto hodnotu nalezneme druhý pár kolidujících zpráv. Takto pokračujeme až do k-té dvojice. Nyní můžeme vytvořit celkem 2^k zpráv, majících stejnou haš tak, že z každé z k dvojic zpráv vybereme jednu nebo druhou zprávu a ty zřetězíme (viz snímek 18 prezentace na http://cryptography.hyperlink.cz/2004/Hasovaci_funkce_a_cinsky_utok_MFFUK_2004.ppt).
Obecně jsme tak se složitostí pouze k* 2^(n/2) získali 2^k kolizí n-bitové hašovací funkce.
Vezmeme konstrukci H(x) = H1(x) || H2(x) || H3(x) pro tři různé hašovací funkce. Pro jednoduchost nechť mají stejnou délku haše n bitů. Pak se složitostí (n/2)* 2^(n/2) nalezneme Jouxovou metodou 2^(n/2) dvojic H1-kolidujících zpráv, v nichž bude s pstí 1/2 jedna kolize současně i pro H2. Máme tedy dvě zprávy x, pro něž je H1(x) || H2(x) stejná. Složitost je (n/2)* 2^(n/2). Takových dvojic zpráv si nyní vyrobíme n/2 za sebou opět Jouxovým postupem. Složitost je (n/2)* (n/2)* 2^(n/2). Získáme ovšem 2^(n/2) zpráv, v nichž nalezneme s pstí 1/2 jednu dvojici, která má stejnou haš H3(x). Celková složitost pro kolizi H(x) = H1(x) || H2(x) || H3(x) je tak (n/2)* (n/2)* 2^(n/2), pro n = 128 je to 4096 * 2^64. A to je právě druhá Jouxova finta.
Pokud ovšem umíme nalézt kolizi rychleji než za za složitost 2^64, můžeme uvedený postup i výpočet upravit. Číňani umí nalézt kolizi MD5 za hodinu, MD4 za vteřiny. Takže si to můžete napočítat.
Uvedený postup platí i pro silné hašovací funkce, třeba pro nalezení kolize MD5(x) || SHA1(x) bychom potřebovali 80 hodin pro 80 kolizí MD5 čínským postupem a poté 2^80 výpočtů SHA-1. Jinými slovy prolomená hašovací funkce do této konstrukce přispívá velmi malou složitostí (zde 80 hodin).
Odpověď na názor
Odpovídáte na názor k článku Praktické útoky na digitální podpisy používající hašovací funkci MD5.
Re: tri ruzne funkce
celé vláknoPravidla pro diskutující
Přidáním čtenářského příspěvku do diskusí či fóra souhlasíte s tím, že budete dodržovat následující pravidla. Při jejich hrubém porušení se vystavujete riziku smazání příspěvku, jeho modifikaci, v krajním případě i zablokování přístupu do diskusí.
Redakce ze zásady nezasahuje do čtenářských diskusí a zavazuje se, že nebude mazat ani modifikovat příspěvky, kromě případů, kdy tyto porušují některé z následujících pravidel. V takové situaci je na zvážení redakce, zda příspěvek modifikuje s viditelným upozorněním, či přímo smaže. Redakce nikdy nemaže „nesouhlasné komentáře“ jen proto, že jsou nesouhlasné. Vítáme střet názorů, ale vždy v rámci slušné a kultivované debaty.
Příspěvky nesmí obsahovat:
- Vulgární či hrubé výrazy.
- Urážlivé výroky na adresu druhé osoby či skupiny osob.
- Texty, které mají za cíl jen vyprovokovat emotivní reakci (trolling).
- Rasové útoky či útoky na jakoukoliv jinou menšinu či skupinu obyvatel.
- Komerční nabídky a affiliate odkazy.
- Odkazy na warez, sériová čísla, licenční kódy, pornografii a další nevhodný materiál stejně jako žádosti o poskytnutí tohoto obsahu.
- Prokazatelně protiprávní obsah.
Informace o soukromí: U všech přidaných komentářů provozovatel ukládá IP adresu a hostname odesílatele. U neregistrovaných uživatelů se na webu zobrazuje část hostname, případně IP adresy, neumožňující identifikovat konkrétní počítač.
Povolené značky XHTML: a, br, code, em, li, ol, p, pre, strong, sub, sup, ul
