V cem je hlavni kouzlo SHA-1? (Was: Re: MD5 a nejvetsi mozna velikost vychoziho souboru (minen soubor ze ktereho chci spocitat hash))

[Michal Vymazal]

Peter Surda napsal(a):
> On Sun, 14 Aug 2005 20:44:41 +0200 Michal Vymazal <blabla na secunet.cz> wrote:
> 
> 
>>Ale o tom tu prave celou tu dobu mluvime, ze. Jak velky muze byt vzor,
>>aby ten hash byl jednoznacny a tim padem jedinecny.
> 
> Vid predchadzajuce prispevky.
> 
> 
>>Takze pokud vzor ma (nejvyse) 2 na 64 bitu a vysledkem je 128 bitovy
>>hash, pak by tato podminka mela byt splnena.
> 
> Ocividne si mylis si pocet moznosti a dlzku dat. Akonahle mas data dlhsie ako
> 128 bitov, musi nevyhnutne existovat kolizia pri pocitani hashu, ktory ma presne
> 128 bitov.
> 
> 128bitovy hash moze nadobudnut 2^128 roznych hodnot. 2^64bitov dlha sprava moze
> nadobudnut 2^(2^64) = ca 2^18000000000000000000 (18 nul) roznych hodnot, a ked
> si uvedomime, ze 2^64 je limit a nie pevna hodnota, je ich este viac. Kolizii je
> tam tympadom ludovo povedane ako nasratych.

Jenze, pokud by tato uvaha platila, jak potom muze NSA uznat takovyto
hashovaci algoritmus? Oni skutecne tvrdi, ze otisk je jednoznacny.
Nejednoznacnost otisku zatim (mysleno u SHA-1) nikdo neprokazal. Vyse
uvedenou uvahu prece museli vyvracet jako jednu z prvnich :-) A SHA-1
ani RIPEMD-160 zatim nejsou oznaceny jako "insecure".

Jednim z moznych vysvetleni je skutecnost, ze 2 na 128 (potazmu 2 na
160) je ponekud "velke" cislo (velky pocet moznosti, velky prostor),
takze se nikomu zatim nepadarilo kolizi najit (MD5 opomijim, protoze tam
  uz kolize nalezeny byly). To mne ovsem moc neuklidnilo, protoze nahodu
takto vyloucit nelze. Nevite nekdo v cem je to hlavni kouzlo SHA-1?
Treba nejake prohlaseni typu "V pripade nalezeni kolizi jsme matematicky
prokazali, ze velikost koliznich zprav se bude lisit nejmene o x radu,
takze to urcite poznate"?

Takze jsem zatim dospel k dalsi oprave meho puvodniho dotazu:
V cem je hlavni kouzlo SHA-1?

> 
> Tych 2^64 je podla wikipedie obmedzenie algoritmu, ktory deli data na chunky pri
> SHA-1 (v algoritme samotnom tento limit nevidim, asi to ma kryptograficke
> zdovodnenie). To je ina vec ako jedinecnost hashu.
> 


-- 
Michal Vymazal
vymazal at secunet dot cz