Hashovací funkce

HackForum

Hashovací funkce#
Dobrý den. V současnosti je bezpčečnost na internetu na prvním místě. Pokud se posílají citlivé údaje z klienta na server (nebo opačně), je vhodné, aby tato komunikace byla šifrována.
V případě, že se např. přihlašuji do své e-mailové schrinky, je mé heslo (které píšu do formuláře) následně zašifrováno a převedeno na HASH, který doputuje po síti až ne server, kde je porovnán s hashem, který je na serveru uložený.
Nj. pokud je ale hashovací funkce normální matematická funkce a je známa (předpokládám, že zdrojové kody MD5 a pod. jsou dosutpné). jak je možné , že nelze (resp. je to obtížné) ze získaného (odchyceného) hashe zpětně heslo zjistit a to velmi rychle se 100 % jistotou úspěchu...?

Vím, že to nejde, ale není mi už tak jasné proč. Přeci pokud mám např. funkci y=2x + 5 a já vím, že y = 10 (y..reprezentuje hash), tak jsem snad vždy schopen vypočítat to "x" (tedy heslo).

Takže moje otázka je, jak vypadá taková hashovací funkce z pohledu matematika a proč není tak jednoduché k ní vypočítat "funkci inverzní", která by okamžitě převáděla hash na heslo?
Dik za odpoveďi....
(odpovědět)
Anonymous | 195.39.54.125/unknown18.2.2010 13:44
re: Hashovací funkce#
faktorizace
(odpovědět)
Emkei | E-mail | Website | PGP18.2.2010 15:37
re: Hashovací funkce#
Znáte třeba problém batohu?

Matematicky se jedná o problém výběru z množiny celých čísel její podmnožiny tak, aby součet prvků této podmnožiny byl roven nějaké předem zvolené konstantě. (analogicky: naskládat do batohu různě těžká zavazadla tak, aby vážil přesně třeba 50kg)

Pokud vám někdo sestaví onu chtěnou podmnožinu, snadno a hlavně rychle ověříte, jestli splňuje zadané kritérium (sečtete prvky a porovnáte s konstantou).

Sestavení této podmnožiny je ovšem horší, zatím se neví o lepším způsobu (až na pár víceméně bezvýznamných detailů), než vyzkoušet všechny podmnožiny.

Hashovací funkce jsou postavené na podobném principu - snadno pro nějaký řetězec X a hashovací funkci h() zjistíte hodnotu h(X), kterou porovnáte s uloženým hashem (analogie v sečtení prvků a porovnání s konstantou). Opačný proces je ovšem výpočetně náročnější (ale ne nemožný).

"...a proč není tak jednoduché k ní vypočítat "funkci inverzní", která by okamžitě převáděla hash na heslo?" - to jsou docela hluboké problémy teorie složitosti :-)
(odpovědět)
mr.Crow. | 213.211.34.*18.2.2010 16:33
re: Hashovací funkce#
Možná, že přemýšlíte, jak se dostat k peněžnám transakcím prováděných na internetu :) K tomu můžu přiložit snad jen odkaz na Riemannovu hypotézu [link] :) Zatím se uvažuje o tom, že spadá mezi problémy NP úplných úloh (tzv. neřešitelné problémy tisíciletí), na jejichž řešitele čeká hodně tučná odměna :)
(odpovědět)
Duck | 194.212.102.*18.2.2010 17:23
re: Hashovací funkce#
NP úplné problémy jsou takové, které jsou na nedeterministickém turingáči řešitelné v polynomiálním čase ("jsou ověřitelné" v pol. čase), ovšem těžko říct, jestli i na deterministickém (tedy jestli jsou i řešitelné v pol. čase). Jestli ano nebo ne, je jeden z tzv. problémů milénia, mezi které patří i Riemannova hypotéza.

Kladná odpověď na jednu z hypotéz (Riemannovu nebo P=NP) by možná znamenala nějaký podstatně rychlejší algoritmus pro faktorizaci.

Tohle píšu, protože si nejsem jistý, jestli v tom máš pořádek :-)
(odpovědět)
mr.Crow. | 213.211.34.*18.2.2010 18:17
re: Hashovací funkce#
Špatně jsem se vyjádřil a plně souhlasím s tím, co jsi napsal :) Díky za upřesnění :)
(odpovědět)
Duck | 194.212.102.*18.2.2010 22:25
re: Hashovací funkce#
Mozna ze to co napisu je kravina, ale neni jednoduchy priklad funkce ke ktere se obtizne hleda inverzni pouhe posunuti v posuvnem registru?

y = (x << (x - (x % 2))) / x ** 10

Z hlavy me nenapada jak k tomu najit inverzi.
(odpovědět)
Bystroushaak_ | 147.230.164.*18.2.2010 20:33
re: Hashovací funkce#
mas pravdu, k funkcii prakticky sa rovnajucej y=f(x)=0 pre vsetky x>1 je skutocne nemozne najst povodny vstup :)
(odpovědět)
stopa27 | 85.216.196.*18.2.2010 22:26
re: Hashovací funkce#
Nj, chybka, zkousel jsem to na "A" - "z" - tzn 65 - 122.
(odpovědět)
Bystroushaak_ | 147.230.164.*18.2.2010 23:13
re: Hashovací funkce#
Anonymous - michas hrusky s jabkama a pokladas spatne formulovane otazky


V současnosti je bezpčečnost na internetu na prvním místě.

Neni ...

Pokud se posílají citlivé údaje z klienta na server (nebo opačně), je vhodné, aby tato komunikace byla šifrována.

Ano, prinejmensim ...

V případě, že se např. přihlašuji do své e-mailové schrinky, je mé heslo (které píšu do formuláře) následně zašifrováno a převedeno na HASH, který doputuje po síti až ne server, kde je porovnán s hashem, který je na serveru uložený.

TAK TAKHLE NE! V takovem pripade nema smysl nejaky hash vubec pouzivat. Autentizacni token nemuzes jen tak poslat. Musis pouze prokazat, ze ho znas. K tomu jsou ruzne protokoly (asymetr., zero knowlige, chalenge response, ...)

Nj. pokud je ale hashovací funkce normální matematická funkce a je známa (předpokládám, že zdrojové kody MD5 a pod. jsou dosutpné). jak je možné , že nelze (resp. je to obtížné) ze získaného (odchyceného) hashe zpětně heslo zjistit a to velmi rychle se 100 % jistotou úspěchu...?

Otazkou je, cemu rikas matematicka funkce. Rozhodne nemusi byt spojita a prosta. Jsou ruzne druhy hashovacich funkci s ruzny pouzitim. MD5, stejne jako MD2 nebo MD4 je popsana ve svem RFC.

Vím, že to nejde, ale není mi už tak jasné proč. Přeci pokud mám např. funkci y=2x + 5 a já vím, že y = 10 (y..reprezentuje hash), tak jsem snad vždy schopen vypočítat to "x" (tedy heslo).

Takže moje otázka je, jak vypadá taková hashovací funkce z pohledu matematika a proč není tak jednoduché k ní vypočítat "funkci inverzní", která by okamžitě převáděla hash na heslo?


Nebudu rozebirat vlastnosti ruznych typu hashovacich funkci, to by vydalo na jeden nebo i vice clanku. Jen lehce napadnu tvrzeni, ze k hashovaci funkci neni mozne spocitat funkci inverzni. Pro vybranou vstupni mnozinu to neni zas tak slozite - hledej pojem rainbow tables, resp. puvodni clanek od Martina Hellmana.


Ty tezke problemy lze vysvetlit i jinak, velice zjednodusene. Predstav si rubikovu kostku nebo treba puzzle. U takoveho hlavolamu je jednoduche rozhodnout, ze je spravne poskladany, ale samotne slozeni jednoduche rozhodne neni. Skladani muzes urychlit tim, ze ten samy hlavolam v te same konfiguraci budete resit dva a kazdy z vas si vybere jen polovinu moznych cest. Muzete to resit ctyri, kazdy se cvrtinou cest ...
Timto zpusobem vymenis potrebny cas pro reseni za vice prostoru potrebneho k reseni.


Kdyby te to vice zajimalo, tak shanej materialy na tema vypocetni slozitost, vycislitenost a NP-uplnost
(odpovědět)
drd | 85.160.7.222/127.0.0.*19.2.2010 11:51
re: Hashovací funkce#
Anonymous: predstav si treba logicke operatory, jako je OR (XOR, NOR, ...).
Vem z retezce, ktery chces zahashovat postupne bity po dvou a aplikuj na ne OR. Dostanes nejaky vysledek, ze ktereho uz ale nikdy nedostanes puvodni retezec. Pokud to takhle aplikujes vickrat, pravdepodobnost ziskani toho puvodni se dal snizuje.
Napriklad:
1101 0010
(1 || 1) = 1
(0 || 1) = 1
(0 || 0) = 0
(1 || 0) = 1
Vysledek mas 1101. Jak z nej ale zjistis, ten puvodni retezec? Nijak. Dokazes jen vypocitat mnozinu vsech puvodnich retezcu, ktera tento vysledek dava (10010010, 01100001, ...).
Tehle funkci muzes samozrejme pouzit vic a jinych, ruzne je kombinovat, v pripade ze nemas dostatek znaku tak je doplnovat, ruzne otacet atd.

----------
public static void main(String args[]){
 throw new UnsupportedOperationException("Not implemented!");
}


(odpovědět)
pr0ph3t19.2.2010 12:34
re: Hashovací funkce#
[link]

Vlastimil Klíma : Hašovací funkce, principy, příklady, kolize, přednáška na ČVÚT, Cryptofest, 2005

když už tu máme takové pěkné vzdělávací vlákno.
(odpovědět)
mr.Crow. | 213.211.34.*19.2.2010 13:22

Zpět
Svou ideální brigádu na léto najdete na webu Ideální brigáda
 
 
 

 
BBCode