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

Peter Surda surda na shurdix.com
Pondělí Srpen 15 20:26:55 CEST 2005


On Mon, 15 Aug 2005 19:59:52 +0200 Michal Vymazal <blabla na secunet.cz> wrote:

>Peter Surda napsal(a):
>> 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.
A co si Kefalin predstavujete pod pojmom jednoznacny?

>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
No vidis, tak si na to nakoniec prisiel sam, ked sa ti to niekolkokrat vysvetli
:-)

Koliziu sa vsak v oboch pripadoch (MD5 aj SHA-1) uz podarit naslo, v pripade
SHA-1 metoda zatial nebola zverejnena. Okrem toho, nie je kolizia ako kolizia
(zase vid wikipedia).

>To mne ovsem moc neuklidnilo, protoze nahodu takto vyloucit nelze.
2^128 je zhruba 3 a za tym 38 nul. To dost mala nahoda. Pri pouziti "birthday
paradoxu" ti vyjde trocha mensie cislo, tak vela suborov vsak iste na celom
svete nie je. Keby mal kazdy clovek miliardu pocitacov a kazdy pocitac miliardu
suborov, a mame asi 6 miliard ludi, furt to dava "len" 6*10^27 suborov. Pre
porovnanie, google tvrdi, ze maju indexovanych nieco cez 8 miliard webstranok.

Spomenul som si, ze niekto sa raz stazoval na rsync. Autor v dokumentacii pisal,
ze pri pouziti kontrolnych suctov nie je na 100% garantovany korektny prenos
suboru, ale zaroven je to zanedbatelna pravdepodobnost. No a tomu dotycnemu sa
to nepacilo, ze ako ze zanedbatelna, ze to jednoducho musi byt 100% a inac je to
smejd :-).

>Nevite nekdo v cem je to hlavni kouzlo SHA-1?
Tak ako to zvycajne byva, v pouziti hlavy ;-)

>--
>Michal Vymazal
>vymazal at secunet dot cz

-- 
http://www.shurdix.org - Linux distribution for routers and firewalls


Další informace o konferenci Linux