Vlákno názorů k článku Python Cryptography Toolkit (1) od Fletcher - První odstavec pod zmiňovaným nadpisem obsahuje několik ne...
-
Fletcher (neregistrovaný)První odstavec pod zmiňovaným nadpisem obsahuje několik ne zcela přesných a jednoznačným výroků.
1) "...a vrátí posloupnost dat o určité velikosti na výstupu..."
Výstupní data mají KONSTANTNÍ délku, nezávisle na velikosti vstupu. Možná, že autor slovo "určité" myslel vzhledem ke zvolené hash funkci, ale to není z tetxtu zřejmé.
2) "...Je možné, že dvě odlišné posloupnosti dat budou mít po výpočtu stejný výstup. To znamená, že hašovací funkce jsou jednostranné, není tudíž možné z výsledku vypočítat původní data...."
Tady je autor zcela mimo. Z existence kolize implikuje jednosměrnost hash funkce!
To, že hash funkce může mít kolizi nesouvisí (resp. souvislost by se tu našla, ale ne tak jak uvádí autor) s tím, že hash funkce jsou jednosměrné. Dobrá hash funkce nemá kolize a přesto je zcela jistě jednosměrná.
3) "...Funkce označené hvězdičkou jsou 160bitové, ostatní pak 128bitové."
Autor zde měl patrně na mysli skutečnostm, že délka výstupu u MD2,4,5 je 128b a u RIPMD-160 a SHA-1 160b.
4) fonetický přepis hash -> haš (případně heš) je hrozný , i když možná jazykově správný. -
Petr Svoboda (neregistrovaný)Mel bych k bodu 2) dve pripominky (vzhledem k tomu, ze kritizujete autora za nepresne formulace, myslim ze opravnene).
a) Myslim si, ze jednosmernost hash funkci souvisi predevsim s kolizemi. Nevim, na cem byste u nich jinak zalozil jednosmernost.
b) Podle mne vsechny hash funkce maji z principu jejich funkce kolize. Je to zobrazeni z jedne mnoziny do druhe, pricemz ta druha je mensi, takze kolize byt musi. Myslim si, ze zde pletete dve veci dohromady. V kryptografii se o bezkoliznosti mluvi v souvislosti s "hledanim" kolizi. To musi byt tezke, aby se dala ta funkce v kryptografii pouzit (mimo jinych vlastnosti). Napsat ze dobra hash funkce nema kolize je zcela jiste dost nepresne. -
puco (neregistrovaný)V bode a) nemate pravdu. Ak si zoberete identitu, tato funkcia nie je jednosmerna ale zato odolna voci koliziam (ziadne nema). A opacny extrem, nech f = x^2 mod n (n = p*q). Tato funkcia je jednosmerna, lebo je tazke hladat druhe odmocniny (na tomto je zalozeny Rabinov system ) zato koliziu je velmi lahke najst x a -x.
-
Nevim, jestli bych identitu oznacil za hash funkci a nemyslim si, ze ma smysl se o tom dale bavit - samozrejme kolize nema. ;-)
Druhy pripad podle mne nepopira to, co jsem napsal. Kdyby ta funkce nemela kolize, problem je radove jednodussi - spocist jednu odmocninu lze. Ze bych psal o tom, ze kdyz snadno najdu kolizi funkce neni jednosmerna, si nejsem vedom. Psal jsem, ze hlavni pricinou jednosmernosti jsou kolize.
Ale abych zbytecne nezobecnoval. Urcite existuji funkce, u kterych je tezke spocist inverzni hodnotu, a ktere jsou bezkolizni. U hash funkci je ale podle me hlavni prekazkou zpetneho vypoctu existence kolizi. Tezkost zpetneho vypoctu podle mne spis souvisi s hledanim kolizi 1. radu. -
puco (neregistrovaný)Ta identita nema byt dobra hashovacia funkcia, skor ukazuje ako su pozadovane vlastnosti od seba nezavisle, teda vieme najst funkcie, ktore maju jednu vlastnost a druhu zase nemaju.
Neviem ako myslite, ze kebyze ta funkcia nema kolizie, tak je problem radovo jednoduchsi a ide spocitat druhu odmocninu . Aby to bolo presne, je zrejme ze ide spocitat odmocninu ale zatial nepozname efektivny algoritmus == polynomialny pravdepodobnostny algoritmus. Nerozumiem ako existencia kolizii moze branit spatnemu vypoctu a to myslim dokazuje ten priklad s tym umocnovanim nadruhu. -
Nerozumiem ako existencia kolizii moze branit spatnemu vypoctu a to myslim dokazuje ten priklad s tym umocnovanim nadruhu.
Nerozumim tomu, jak by existence kolizi mohla nebranit inverznimu vypoctu. Jak z vysledku urcim, co bylo vzorem? Mohu si pouze vygenerovat vsechny mozne vzory. Takze mam sice mozny vzor, ale nevim, ktery to je. Kdyz pouziji vas priklad s q^2, tak navic dosahnu toho, ze bude tezke ty mozne vzory generovat.
Ve svem puvodnim prispevku jsem v bodu a) byl opravdu nepresny. Stale mam ale pocit, ze pro kryptograficke hash funkce obtiznost vypoctu inverzni funkce souvisi spis s kryptografickou bezkoliznosti, nez s jednosmernosti. Ale bohuzel si nejsem jist, jak je jednosmernost definovana, takze sve tvrzeni nemohu podlozit definici. :-/ -
puco (neregistrovaný)Mam dojem, ze si trochu mylite vyznam h. funkcie. To ze najdem obe odmocniny a neviem, ktora bola hashovana je jedno, tu funkciu som prelomil. Priklad pri digitalnych podpisoch h. funkcia nema utajit podpisany dokument, ten je verejne znamy (no mozno nie verejne ale ten kto ma overit podpis tak ho musi mat). V dig. podpisoch sluzi hashovacia funkcia aj na to, aby sa nedala vytvorit dobre podpisana sprava (random message forgery). Ja s Vami suhlasim, ze kebyze viem ratat tie odmocniny tak aj tak nezistim ktoru odmocninu zahashoval niekto druhy, ale h. funkcia na to nema sluzit.
definicia jednosmernosti: h. funkcia h:X->Y je jednosmerna, ak pre dane y\inY nie je efektivne mozne najst x\inX takze, ze h(x)=y. -
wake (neregistrovaný)dobra hashovaci funkce mozna kolize ma, ale perfektni hashovaci funkce ne. ;);)
-
puco (neregistrovaný)k bodu 3)
Dobrá hash funkce nemá kolize a přesto je zcela jistě jednosměrná.
- SHA-1 je momentalne povazovana za "dobru" h. funkciu a predsa ma kolizie (to vyplyva z toho, ze mohutnost mnoziny sprav je vacsia ako mohutnost mnoziny retazcov dlzky 160 bitov). Teda skor by sa hodilo napisat: Dobra h. funk. je odolna voci koliziam (odolnost sa deli na silnu a slabu).
