Vlákno názorů k článku Ukradená hesla LinkedIn: Proč tolik povyku? od Andy - Díky, chápu naprosto přesně. :)

Díky, chápu naprosto přesně. :)

dovolil bych si nesouhlasit. Bezkoliznost je požadavek kvůli heslům ale hashovací funkce se rozhodně nepoužívají jen pro hesla ale pro miliony dalších účelů a tam jsou požadavky zcela jiné.

Například my běžně používáme/tvoříme hashe tak aby naopak kolize byla bylo jich velmi hodně ale byli rovnoměrně rozprostřeny do hashu. tj aby jeden obraz nemel jeden hash a druhých 100 obrazů taky jeden hash.

Jj, já vím, v této diskusi nicméně primárně vníma pojem "bezkoliznost" tak, jak je vysvětlil autor článku ve svém díle ("Hash kódy na serverech LinkedIn a dalších dále těží z bezkoliznosti (odlišit lze různé úrovně), která připřípadné autentizaci porovnáním výsledných hash kódů dokáže zajistit, že heslo bude akceptováno právě tehdy, když je zadáno správně. Správný hash kód totiž díky bezkoliznosti mohl vzniknout pouze ze správného hesla."). T.j. s úplným vyloučením možnosti kolize.

K bezkoliznosti bych řekl jenom následující:

- Definice podle Prof. Dana Boneha (Stanford, jinak viz kurz http://www.crypto-class.org): Nechť H:M->T je hashovací funkce. Kolizí pro funkci H rozumíme pár m0, m1 z M takový, že H(m0)=H(m1) a m0<>m1. Řekneme, že H je bezkolizní*), pokud pro všechny explicitní účinné algoritmy A platí, že pravděpodobnost, že A vrátí kolizi pro H, je zanedbatelná**).

*) Boneh používá výraz "collision resistant", tj. "odolávající kolizím", ale česká literatura to vesměs překládá jako bezkoliznost.

**) Zanedbatelnost je definována jinde, pro tuto diskusi ji stačí chápat intuitivně.

- Definice podle Doc. Róberta Lórencze (ČVUT FIT):
-- Bezkoliznost 1. řádu := je odolnost proti kolizi a požaduje, aby bylo výpočetně nezvládnutelné nalezení libovolných dvou různých (byť nesmyslných) zpráv M a M' tak, že h(M) = h(M').
-- Bezkoliznost 2. řádu := Hašovací funkce h je odolná proti nalezení 2. vzoru, jestliže pro daný náhodný vzor x je výpočetně nezvládnutelné nalézt 2. vzor y <> x tak, že h(x ) = h(y ).

V další literatuře je to obdobně.

Závěr: "Bezkoliznost" v kryptografii není chápána jako absolutní nemožnost kolize (pro kterou by skutečně bylo potřeba, aby výstup hashovací funkce byl nejméně tak velký, aby se jím dala vyjádřit celá množina vstupů).

Doplňuju, že s tou bezkolizností je to ještě trošku jinak, (obecně na to, aby mohl být hash bezkolizní, musí být velikost hashe větší, než velikost vstupních dat, ze které je vypočítáván - pokud tedy linkedin podporuje hesla obsahující více než 160 bitů entropie, nemůže být SHA1 použit "bezkolizně").

Požadavky na kryptografickou hashovací funkci pak pro úplnost jsou:

1) Odolnost vůči získání předlohy. Pro daný hash c je obtížné spočítat x takové, že h(x)=c (hashovací funkce je jednosměrná.)
2) Odolnost vůči získání jiné předlohy. Pro daný vstup x je obtížné spočítat y takové, že h(x)=h(y).
3) Odolnost vůči nalezení kolize. Je obtížné systematicky najít dvojici vstupů (x,y), pro které h(x)=h(y).

Požadavek 3) má ovšem k bezkoliznosti hoodně daleko.

Aha, takže za předpokladu, že zpětné rozšifrování je možné, akorát to není časově zvládnutelné, to už chápu. Díky.

"Možnost rozšifrování" existuje vždy. Jednosměrnost zajišťuje "pouze" to, aby to nebylo výpočetně zvládnutelné (jinými slovy, "Víme přesně, jak by se to mělo dělat, ale nezvládneme to v požadovaném čase, například po dobu existence vesmíru").

"Bezkoliznost" je vlastnost, kterou musí mít dobrý hash. Pokud ji nemá, není to dobrý hash. O sečtení čísel na SPZ nikdo netvrdí, že to je dobrý hash, tudíž nemusí mít bezkoliznost - bylo to opět nabídnuto jako demonstrace principu jednosměrnosti, ne principu bezkoliznosti.

Mockrát děkuji _pepak & tdvorak.

Ale u obou vysvětlení narážíme na ty dva problémy, na kterých jsem se při přemýšlení sám zasekl.

_pepak uvádí, že "vynásobit dvě prvočísla je jednoduché, najít je je složité" => tím popírá to, že by neexistovala možnost rozšifrování

tdvorak naopak připouští "koliznost" dvou odlišných šifrovaných hesel => opět to nesouhlasí s teorií, kdy pro jeden vstup existuje jen jeden možný (unikátní) výstup

Takže jsem stále zaseklý na začátku.

Velmi jednoduchý příklad z reálného světa: představte si, že sčítáte čísla uvedená na poznávací značce auta. pro 2U3-4567 vám vyjde 27 (2+3+4+5+6+7). Z této hodnoty už ale nedovedete zpětně rekonstruovat původní značku. Jedním směrem je výpočet znám, naopak to nelze odvodit. Druhou věcí je to, že značka 1U34568 bude mít podle této 'hashovací funkce' také výsledek 27, pro dva různé vstupní řetězce máte shodný výstupní - kolizi.

Velmi zjednodušeně: Jednosměrnost je zajištěna tím, že spočítat určitou funkci je snadné, ale spočítat její inverzi je obtížné. Triviální příklad je vynásobit dvě prvočísla (jednoduché) a ze součinu dvou prvočísel najít ta prvočísla (velmi obtížné, pokud jsou ta prvočísla dost velká). Nematematický příklad: smíchat cukr, mouku a sůl je jednoduché, získat ze směsi cukru, mouky a soli samostatné suroviny je obtížné.

U hashovaných hesel to znamená, že porovnat shodu dvou hesel je jednoduché (jedno už mám zahašované, z druhého spočítám hash velmi jednoduše, porovnám hashe - to si mohu dovolit díky vlastnosti "bezkoliznost"), ale z hashe získat původní heslo je složité (více méně - musím vyzkoušet zahashovat všechna možná hesla, dokud nenajdu shodu).

Zajímalo by mě, jak funguje jednosměrné šifrování. Zaujalo mě, že již nelze proces obrátit a heslo rozšifrovat, přitom při ověřování lze zadané heslo zašifrovat tak, aby se získal stejný výstup. Takže šifrovací klíč musí být neustále stejný a nedochází mi, proč by to nešlo i obráceně - rozkódovat. Nemáte nějaký odkaz na článek toto vysvětlující?