Vlákno názorů k článku
Vlastimil Klíma: Zcela nový koncept hašovacích funkcí

Zajímalo by mě --- jak se dokazuje, že něco nejde efektivně spočítat?

Může se to převést na NP-úplný problém a pak tomu věřit, že NP-úplné problémy nejdou řešit polynomiálně --- ale pokud např. problém nejde vyřešit polynomiálně v 90% případů a jde vyřešit v 10%, tak sice může být NP-úplný, ale šifrovací algoritmus, který jde v 10% případů rozlousknout, je na nic.

Nebo je to důkaz pouze částečný --- nejde to spočítat algoritmy skládajícími se z určitých operací?

to je zajimava otazka... tipl bych na prevod na nejaky NP-uplny problem...

ale cekam, ze za par let se objevi clovek podobneho kalibru, ktery bude louskat NP uplne problemy v polynomickem case bez mrknuti oka...

Jenomže potřebuješ mnohem silnější vlastnost, než je NP-úplnost (i za předpokladu, že NP-úplné problémy řešit v polynomiálním čase nejdou)

Příklad: problém, zda se program zastaví, nelze vyřešit (to je dokonce dokázáno) --- jenomže: když si nageneruješ z náhodných instrukcí program, tak z třeba z 99% případů ti spadne hned, čímž si dokázal, že se zastaví, a z 0.9% se zacyklí tak, že tok instrukcí nezávisí na obsahu paměti, čímž jsi dokázal, že se nezastaví --- a teprve u toho zbylého 0.1% začne být dokazování obtížnější.

Takže máme sice matematicky dokázáno, že existuje program, u kterého nelze určit, zda se zastaví nebo ne, ale u 99,9% náhodně nagenerovaných programů to určit lze bez jakékoli duševní námahy.

Matematika umí dokázat, že nějaká instance problému nejde řešit --- pro potřeby šifrování by bylo třeba dokázat, že žádná instance problému nejde efektivně řešit --- a není mi jasné, jak tohle dělat a zda to vůbec jde.

omlouvam se za anglictinu, ale nejsem si jisty, jake jsou ceske terminy :))

posledni odstavec se zabyva vztahem mezi tzv. worst-case hardness a average-case hardness. pro vetsinu problemu (napr. NP-uplne problemy batohu, obchodniho cestujiciho apod...) pouze plati, ze jsou tezke v nejhorsim pripade, a dokonce vime, ze nahodna instance (pri uniformnim pravdepodobnostnim rozlozeni) je jednoducha (s velkou pravdepodobnosti). pouze u nekolika malo uloh (lattice problems; ?mrizky?) se umi dokazat, ze jsou tezke i pro nahodnou instanci.

bohuzel kryptografie zalozena na mrizkach neni pro praxi prilis efektivni, takze se neprosadila oproti RSA, coz ale neznamena, ze takovy kryptosystem neexistuje.

Velmi výstižné!

Prevodom na NP-uplne to nie je, trik je v relativizacii s nahodnymi orakulami. Ide o vypocetnu nerozlisitelnost hasovacej funkcie od nahodneho orakula, tj. pravdepodobnost lubovolneho programu rozlisit hashovaciu funkciu od nahodneho orakula je zanedbatelna (nieco ako e^-n)

Zlozitost (a pravdepodobnost najdenia kolizie/preimage) sa pocita oproti poctu dotazov na orakula, v pripade orakul (ciernych skriniek) nic ine neostava.

Myslim, ze paper hovori o konstrukcii mnoziny (rodiny) hasovacich funkcii, ktore sa tak spravaju a nie o jednej konkretnej instancii hasovacej funkcie, co je celkom rozdiel - kod konkretnej instancie uz moze clovek analyzovat (nie je obmedzeny len na dotazovanie orakul).

V paperi Coron et al., kde je dokaz ze tie hash fn. su limitne nerozlisitelne od nahodnych orakul, sa predpoklada, ze kompresna funkcia f je nahodne orakulum. Podobne navrh SNMAC/NMAC/... predpoklada, ze kompresna funkcia je nahodne zvolena blokova sifra (tj. opat nahodne orakulum).

V praxi je ale nutne mat nejaku konkretnu instanciu hasovacej funkcie, tam predpoklad nahodnej blokovej sifry splneny asi nie je - je tam jedna konkretna (AFAIK o ziadnej konkretnej blokovej sifre nebolo dokazane, ze by bola nahodnym orakulom, ale nie som si 100% isty). Predpokladane SBC (special block cipher) ale maju niektore silne vlastnosti (homogenita, odolnost proti diferencialnym a linearnym utokom).

Zaver: nova schema konstrukcie - nova rodina hashovacich funkcii - je preukazatelne odolna proti "starym neduhom" ako Jouxov extension attack apod. a je vypocetne nerozlisitelna od nahodneho orakula. Co je po "nedavnej deziluzii" z nalomenia mnohych hashovacich funkcii slusny uspech.

(nestudoval som to zatial podrobne, spominane papery - Klima, Coron et. al - len som zbezne presiel, radsej uz idem spat jak pozeram na cas)

Co mi nie je uplne jasne je ta uloha Const0/Const1 - chapem, ze utocnik nema mat moznost ovplyvnovat kluc "blokovej sifry" (volbou hashovanych dat), ale neviem, kde sa tie konstanty beru a nie je mi moc jasny vyznam zapisu "f: {0, 1}^K → {0, 1}^n : k → E_k(Const0)".

Ty konstanty mohou být jakékoliv různé. První konstanta vytváří kompresní funkci f, druhá konstanta závěrečnou úpravu g. O té závěrečné úpravě je víc pojednáno v plné zprávě.

Útočník má dnes možnost ovlivňovat klíč u KLASICKÝCH blokových šifer, které jsou použité v hašovacích funkcích. Navíc má možnost ovlivňovat i otevřený text. Navíc tyhle proměnné se téměř ve všech konstrukcích spojují lineárně. Navíc klíč je použit mnohokrát "tak jak je" bez modifikace, takže účinky jeho změn lze sledovat hluboko ve vnitřku hašování.

Pokud použijeme speciální blokovou šifru, nemusíme se obávat veškerou proměnnou prohnat přes klíč a jedině přes klíč. SBŠ má na to vystavěna obranná opatření (na rozdíl od klasické). Konstantní otevřený text je pak volen proto, aby tu funkci nešlo invertovat. Inverzí klasické blokové šifry dostáváte různé otevřené texty, u speciální blokové šifry byste dostal jeden jediný otevřený text. To asi nebude inverze. Jistě, pokud proženete proměnnou klíčem, výsledek je náhodné zobrazení. Smyslem je tedy jednak dostat náhodné zobrazení (na rozdíl od permutace u klasické) a neinvertovatelnou funkci (na rozdíl od invertovatelné u klasické).

Problém HASH funkcí je v tom, že zkracují původní informaci na určitou délku, kompresní funkce sice také, ale zachovává zobrazení 1:1, což HASH nedělá. Otázka je, zda je potřeba jedna velikost HASHe.
Druhá rovina je např. smysluplnost informace. Všech kombinací znaků na stránce je mnoho, ale relativně málo takových stránek má nějaký smysl, ještě méně jich bude mít smysl např. v českém jazyce. Zase je otázka, jakou mohutnost má množina všech "smysluplných" stránek. Rozdíl obecně dvou NP-problémů nemusí být NP plný problém, může mít i polynomiální složitost.

to ze je problem NP-uplny jeste neznamena ze je tezke ho vyresit. Co je horsi, slozitost O(1.00001^n) nebo O(n^100000)? Nedavno byl nalezen algoritmus, ktery overuje prvociselnost a je v P. Jenze slozitost toho algoritmu je neco kolem O(n^12), takze jeho prakticek vyuziti je v podstate nulove.

Zajimavy je napriklad dusledek: predpokladame-li ze P!=NP!=co-NP - coz je velmi pravdepodobne, problem overeni prvociselnosti je v P, problem overeni "neprvociselnosti" je taky v P a z toho by se dalo usuzovat, ze algoritmus na faktorizaci je taky v P.

Pro vysvetleni, je-li problem v NP, a mame-li instanci problemu I, muzeme k ni najit certifikat C. Platnost tohoto certifikatu muzeme overit v poly. case. Napriklad, Obchodni cestujici. Instance je nejaky konkretni graf a certifikat bude ona cesta. Overeni ze je cesta opravdu obchodni cesta (dale jen OC), je snadne. Jenze, jestlize grafem zadna OC nevede, jaky dame certifikat? Neexistence OC je totiz v co-NP. U prvociselnosti to ale neplati, tam je prvociselnost i neprvociselnost v P.

Takze, kdybych mel hadat, faktorizace je v P. Myslite si ze kdyz nekdo najde poly. alg. pro faktorizaci, ze rozbyje sifrovani verejnym klicem? Ja myslim ze ne, protoze ten algoritmus bude mit slozitost sice v P ale s tak velkym exponentem, ze v realu bude stejne nepouzitelny.

muzete dat link na ten algoritmus na prvociselnost v P ?

Manindra Agrawal, Neeraj Kayal, Nitin Saxena: Primes is in P

Ze neco efektivne spocitat nejde se dokazat neda.

Predstav si, ze Klima navrhne nejakou svou novou funkci a vedci v CERNU pri ostrelovani castic objevi nejakou skrytou featuru kvantove mechaniky - ze se do kvantove castice da naprogramovat algoritmus a pak na ni poslat zadani zakodovane ve svazku fotonu a ona je zprocesuje tak, ze okamzite vypadne vysledek, pro libovolne slozite funkce.

Ze se neco takoveho stane se vyloucit neda. Ani by se to nedalo vyloucit za predpokladu, ze bychom kompletne znali zaklady vesmiru.

Protipriklad: nejake primitivni brebery zkoumaji vesmir, jenz se sklada z rady cisel: 1,2,3,4,5,6,.... Brebery zjisti, ze vesmir ma jen 1 fyzikalni zakon, a zadne dalsi - ze hodnota ve vesmiru bude vzdy o 1 vetsi nez predchozi hodnota

Tak si brebery spokojene ziji a veri, jak vyresili problem popisu vesmiru. a vesmir jde 999999,1000000, 1000001, 1000002, a najednou bum! - 455567 a ozve se zachechtani z nebe :)

Proste ke kazdemu vesmiru v kterem veri obyvatele ze jeho zakony poznali se da sestrojit takovy, v kterem to neni pravda pridanim nejakeho specialniho okamziku a jednoho if-else navic do kodu vesmiru.

Z toho plyne mravni ponauceni - neverte nicemu. Nic neni dokonale, at by o tom matematici udelali dukazu sebevic.

Máte naprostou pravdu. Matematici o tom vědí, kryptologové tuplem. Ovšem kryptografové jsou nepoučitelní blázni, kteří se snaží postavit se zákonům. Nicméně jinak to nejde, pokud chceme "zaměstnat" fantastickou myšlenku jednocestné funkce pro blaho lidstva, nepříklad ve výpočetní technice. Bez hašovací funkce by dneska nefungoval ani mobil. Takže se vždycky musí najít nějaký obětní beránek a něco navrhnout a pak čekat, až mu to ostatní omlátí o hlavu. To jsou kryptografové.