Vlákno názorů k článku Tunely v hašovacích funkcích: kolize MD5 do minuty od bedo - 1. Kolízie MD5 spomínané v článku znamenajú, že...

1. ne, ale pracuje se na tom
2. ano, je to jen o málo složitější (podrobnosti jsou zrovna v článku ve Sdělovací technice č. 4). Něco vyjímám:

Dvě hašovací funkce
K nalezení kolize funkce MD5 || SHA1 potřebujeme pouze 2^80 zpráv, které mají stejnou MD5 haš. Mezi nimi nalezeneme pak dvě, které mají i stejnou SHA1, čili kolizi celé MD5 || SHA1. Trikem Jouxové získáme těch 2^80 zpráv pouze se složitostí POUZE 80 krát složitost nalezení jedné kolize MD5 (teď jednu kolizi umím na notebooku, na kterém píšu, jsem připojen na internet a běží mi test kolizí, za 30 sekund - trochu jsem původní program vylepšil). Získání těch 80 na sebe navazujících zpráv je teda za 2400 sekund. Zbývá je zkombinovat do 2^80 zpráv a zhašovat pomocí SHA-1. Čili je to až na tu hodinu práce navíc úplně stejné jako kdybychom vzali 2^80 libovolných zpráv a hledali v nich kolizi SHA-1. Poznamenávám, že tento dotaz jsem dostal i od pracovníka jedné velké certifikační autority.

Jedna hašovací funkce s více inicializačními hodnotami
Podobný dotaz, tentokrát od Panda Software, jsem dostal na možnost posílení haše pomocí dvou inicializačních vektorů. Nápad byl jako haš volit h(IV1, x) || h(IV2, x). Avšak použijeme-li trik Jouxové, dostáváme složitost útoku řádově jen 64 krát vyšší než pro samotné h(IV1, x). Avšak složitost se dále zvýší, pokud použijeme h(IV1, x) || h(IV2, x) || h(IV3, x). To jsem jim také doporučil (jako řešení jdoucí jejich směrem nikoli jako obecné, vůbec ne jako obecné). Uvažujeme-li konkrétně MD5 a že jsme schopni nalézt kolizi MD5 za jednu sekundu (na velkém stroji můžeme uvažovat za sekundu), pak kolizi MD5(IV1, x) || MD5(IV2, x) umíme trikem Jouxové najít se složitostí 64* 2^64 * 1s a kolizi MD5(IV1, x) || MD5(IV2, x) || MD5(IV3, x) se složitostí 64* (64* 2^64 * 1s), což je více než 2^64 hodin nebo přesněji je to 4096*2^64 krát složitější než jednoduchá kolize MD5. Čili tudy určitá cesta také vede (pro uzabřené systémy, kde je implementovaná MD5 a už není místo na kód, ale je tam místo i čas na výpočet trojnásobné haše s různými IV).

Další opatření.
Opatření šité na míru proti současným útokům, ale určitě účinné i na mnohé jiné útoky. Konkrétně můžeme z jednoho (například u MD5 a SHA1) 512-bitového bloku m, který máme zpracovat, vytvořit a zpracovat bloky dva, a to například m || C(m), kde C bude nějaký kontrolní kód bloku m. Pokud nám rychlost zařízení toto umožní, volíme C co nejsložitější (nedoporučuje se C(m) = m), ale například C jako nelineární zobrazení, dále zařazení čítače bloků do C(m) apod. Velmi mnoho opatření tohoto typu bylo navrženo na třech speciálních kryptologických konferencích, které řešily problémy hašovacích funkcí [6] [7] [8]. Pokud hledátě řešení tímto směrem, dobré jsou z těchto konferencí náměty z prací autorů Halevi - Krawczyk, Biham, Szydlo - Yin, Jutla - Patthak, Lucks, Rivest a Coron.

[6] Cryptographic Hash Workshop, NIST, USA, Oct. 31 - Nov. 1, 2005, http://www.csrc.nist.gov/pki/HashWorkshop/program.htm
[7] Conference on Hash Functions (Ecrypt), June 23-24, 2005, Przegorzaly (Krakow), Poland, http://www.ecrypt.eu.org/stvl/hfw/
[8] WEWoRC 2005, Western European Workshop on Research in Cryptology, Leuven-Heverlee, Belgium, July 5-7, 2005, http://www.cosic.esat.kuleuven.be/WeWorc/allAbstracts.pdf