Hlavní navigace

Názor k článku Praktické útoky na digitální podpisy používající hašovací funkci MD5 od Ondrej Mikle - No urcite narastie, ale velmi zavisi od typu...

  • Článek je starý, nové názory již nelze přidávat.
  • 9. 12. 2004 16:15

    Ondrej Mikle (neregistrovaný)

    No urcite narastie, ale velmi zavisi od typu utokov a analytickych znalosti suvislosti medzi tymi hashovacimi funkciami.

    Ako priklad spolocna kolizia u MD5 a CRC32, co sme robili: pre jeden MD5 kolidujuci par treba hodinu pocitania na ibm p690, kolizia u CRC32 sa da vypocitat na papieri, lebo je to jednoducha linearna funkcia (nie je kryptograficky bezpecna a nie je to ani jej ucel). Ale uz spolocna kolizia potrebuje 16 MD5 kolidujucich parov (16 hodin) + zanedbatelny cas na otestovanie 2^16 sprav na koliziu u CRC32.

    V pripade troch hashovych funkcii H1, H2, H3 s 256-bitovym vystupom, ktore by boli zlomene rovnakym sposobom ako MD5, by vypocet sucasnej kolizie trval dost dlho.

    Pre ilustraciu: Predpokladajme, ze najdenie paru kolidujucich sprav pre H1, H2, H3 (kazdu osobitne) trva hodinu a nie je znama ziadna pouzitelna analyticka suvislost medzi tymi hashovacimi funkciami (tj. ze zostava len brute-force narodeninovym paradoxom).

    Pre sucasnu koliziu H1 a H2 treba vypocitat 128 parov navazujucich sprav, ktore koliduju pre H1, Jouxovou fintou z toho mame 2^128 kolidujucich sprav pre H1, a tie musime otestovat pre koliziu v H2. Zlozitost 2^128 je uz dost, pridanie dalsej kolizie od H3 nam zlozitost este zvysi.

    Ak vsak bude znama nejaka suvislosti medzi jednotlivymi hashovacimi funkciami, celkova zlozitost sa moze rapidne znizit, ale o kolko, to je tazke povedat, pretoze zavisi konkretne na tom, co budeme vediet.