MD5 a nejvetsi mozna velikost vychoziho souboru (minen soubor ze ktereho chci spocitat hash)

[Dalibor Straka]

On Sat, Aug 13, 2005 at 04:25:52PM +0200, Michal Vymazal wrote:
> Prave ze ten otisk je (lepe receno mel by byt) jednoznacny, pokud
> vstupni soubor neni vetsi nez doporucena nejvyssi hodnota. U SHA-1 a
> RIPEMD-160 jsem tuto hodnotu v dokumentaci nasel. U MD5 nikoliv.
> 
> Jeden z utoku na MD5 spociva v tom, ze k "puvodnimu balicku vstupnich
> dat" pridate dalsi balicek vtupnich dat. MD5 si s tim jaksi neporadi
> (hodne zjednodusene receno) a pro obe vstupni zpravy (ktere v soucasne
> dobe asi nebudou davat smysl pro cloveka) vyrobi stejny hash. Mne
> zajima, zda je tento utok principialne mozny i na SHA-1 a RIPEMD-160.
> teorii u SHA-1 jsem cetl, zajimaji mne ale prakticke vysledky. U
> RIPEMD-160 jsem zatim nenasel nic.
> 
> MV
> 
> 
> Libor Chocholaty napsal(a):
> > Zadny 128 bitovy otisk nebude jednoznacny, pokud jej budete delat ze
> > souboru delsiho nez 128 bitu, ne?
> 
> Jisteze je jednoznacny - to je cely vtip hashovani.
> 
Je jasne, ze kdyz zobrazuji z prostoru o velikosti A do prostoru
velikosti B, kde A>B, musi mit nektere vzory stejny obraz.

Utoky na MD5 se vedou prave tak, ze se najdou dva vzory, ktere
vyprodukuji stejny hash(obraz) a pak se zkoumaji jiste podminky, ktere
jeden ze vzoru musim mit, aby se v kratkem case nasel dalsi vzor s
totoznym obrazem. Tech podminek (na bity) je zhruba 200.

Utoky na SHA-1 jsou zatim neuspesne. Navic Cinani maji dve zpravy, ktere
maji az do 8. pruchodu (ono se to zvejka nekolikrat) stejny hash. A
potvory tvrdej, ze maji i vic, ale nechteji je zverejnit, aby si udrzeli
prvenstvi v "prolomeni" SHA-1. (Tak tvrdil Klima a Tuma, ktery mi to
prednaseli pred mesicem.)

-- Dalibor Straka