Názory k článku
Vlastimil Klíma: Zcela nový koncept hašovacích funkcí

nevim, jestli je to tou druhou hodinou rani, ale toto podani me pripadne az moc pochopitelne az desive... ;-]

kazdopadne blahopreji panu klimovi, k _objevum_ a schopnostem sve vysledky "prodat", mj. i moznosti sve zavery publikovat ;-]

jedna vec me az moc strasi -- v nekolika pripadech jsem pouzil sha1 (pred md5 jsem se mel uz na pozoru) jako unikatni identifikator souboru (neco podobneho ma treba linusuv git), ale ted otazka jestli se s tim ma cenu trapit :-/ a ted otazka kolik lidi si takovou otazku vubec polozi?

Rozhodně se tím netrapte, teď je řada na kryptolozích.

Než bude navržen nový standard (5-7 let), doporučuji používat SHA-256 nebo Whirlpool. Ze všech hašovacích funkcí mají nejmenší riziko prolomení a vsadil bych si, že do těch 5-7 let nebudou prakticky prolomeny.

Platnost SHA-1 jako standardu bude ukončena za tři roky a dva měsíce.

Díky za blahopřání. Požádal jsem NBÚ o možnost publikovat výsledky proto, aby ten koncept mohl být podroben mezinárodní kritice. Mám z toho ohromnou radost, pochopitelně.

no pokial mate urobenich viac hashou naraz pre kazdy subor je podstatne mensia sanca vyrobit subor ktory bude mat vsetky hashe rovnake (gentoo ma v niektorich balickoch md5 + sha1 + sha256 + este nejake ine)

to je docela rozumne reseni... me trapi spis jina vec... pokud mam nejaky sklad souboru a jako identifikator pouzivam sha-1... za normalnich okolnosti je nemozne, aby dva soubory meli stejne hashe. ale co kdyz prijde nejaky chytrolin a da tam dva ruzne soubory se stejnym hashem... system se muze zacat chovat nepredvidatelne, protoze s tim nikdo nepocital a netestoval to.

Myslím, že to je moc dobrý nápad na příklad pro výuku zadních vrátek, díky. Místo toho, aby se systém začal chovat nepředvídatelně, stačí, aby začal vykonávat něco jiného než měl. Zadní vrátka jsou takto dobře zakamuflovaná a dost nebezpečná. Někdo je může instalovat teď a spustit je "zasláním dat do systému" kdykoliv později, až bude nějaká kolize uveřejněna. Při kontrole zdrojových kódů bude pravděpodobně přehlédnuta možnost, že by dva soubory mohly mít stejné hashe. Chce to ovšem šikovného programátora. Nenaprogramoval by někdo takovou věc na ukázku ? Teď se to může naprogramovat a předvést s MD5, za nějakou dobu i s SHA-1.

Myslite neco podobneho jako pred ca pul rokem udelal Ondra Mikle na PDFku, tj napr
vzor
main(){
printf("Hello world!");
}

backdoor:
main(){
printf("Hello world!");
backdoor_run();
//textovy "bordel" tak aby hash vzoru a backdooru odpovidala
}

? pochopil jsem zadani spravne?

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é.

Překlep: "speciální blokovou ifru"

Opraveno, díky.

Děkujeme za upozornění, omlouvám se za nedostatek a opravím.

Zase jsem o něco chytřejší. Bylo to pochopitelné i pro středoškoláka informatika.
děkuji

Nekece, si z teho blbe jak ja

Šak ja nepotřebuji rozumět té matematice. Ale je z toho jasné, že použití šifrovací funkce pro hashování může být problematické a popisovaný projekt se ho snaží řešit.

Po dlouhé době jsem si přečetl takto dlouhý článek až dokonce. Většinou čtu jen zprávičky.

Mám z toho radost. Pokud jste to takhle uchopil, je to přesně to, co jsem chtěl. Je to jednoduché, že ? Obávám se, že je to tak jednoduché, až to může urazit velké kryptology. V posledních deseti letech se objevilo několik objevů, které byly stejně jednoduché (cca na úrovni středoškolské matematiky), a které přesto byly velmi významné. Připomeňmne Bleichenbacherův útok na RSA, Vaudenayův útok na CBC, Jouxův útok na hašovací funkce. To všechno lze pochopit z pár jednoduchých matematických vztahů a slovního popisu. Možná si budete myslet, že si dělám legraci, ale právě vás, který nejste zahrnut desítkami stereotypů v kryptologii, může napadnout zcela nová konstrukce. Stejně tak jste se mohl při prvním setkání s hašovací funkcí zamyslet a říci "co je to za blbost tady používat šifrovací funkci, když to nemá umět dešifrovat". A bylo by to. Jistě, abyste si uvědomil, co jste vyslovil, bylo by nutné zase znát ony stereotypy a jejich problémy nebo by to musel slyšet někdo, kdo by tu myšlenku uměl ocenit a nezahodit.

Jak pise ten nade mno, mam vysku ale su z teho taky blbe. Tak ty blbe stredoskolaku nekece ze si z teho chytre.

kdyz uz tvrdite, ze mate vysku, mohl byste byt aspon konkretnejsi!? ja mam treba vysku 174 cm a rozumim tomu jakztakz ;-]

Bud jsem to nepochopil, nebo veta "Okrajová poznámka. Na obrázcích vidíme, že SNMAC je jakýmsi kompromisem mezi HMAC a SNMAC." neni tak uplne OK. druhe SNMAC bych nahradil NMAC.

Ano, máte pravdu. Jsem rád, že to čtete poctivě.

A tohle je taky opraveno, díky.

Rozvinula se tu diskuse k P, NP apod. problémům. To je ok, jen na okraj poznamenávám, že důkazy, které jsem předložil, nejsou na těchto problémech založeny (kdyby byly, nezlobil bych se, takhle je to ale lepší). Na základě počtu operací, které má útočník k dispozici, vypočítávám jeho šanci na nalezení kolize a na nalezení vzoru. V rozšířeném článku jsou to hodnoty začínající Adv_..., které znamenají pravděpodobnost úspěchu. Věty 1 až 4 říkají, že tyhle pravděpodobnosti jsou mizivé, pokud se počty nutných operací nepohybují v řádu 2^n u vzoru a 2^(n/2) u kolize. To je OK, protože tyhle počty operací jsou platné pro náhodná orákula také.

Nechapu. Co by jako mel "dukaz P/NP" dokazat? Pride mi, ze tu nikdo moc nerozumi tomu, co je to P a co je to NP. Problem nalezeni kolize k hasovaci funkci je resitelny v linearnim case protoze obor funkcnich hodnot je konecny. Tak nevim co by mel byt jako ten NP-uplny problem.

NP-uplnost je definovana nad !NEKONECNOU! mnozinout a problemu, ktery urcuje prislusnost do teto mnoziny. Tak napriklad, mnozina vsech grafu ktere lze obarvit 3mi barvami, je NP-uplna. (vsimnete si ze je nekonecna)

A i kdyby, to ze je nejaky problem NP-uplny nemusi znamenat ze je "neresitelny". NP-uplny problem ktery resi algoritmus se slozitosti O(1.000000001^n) je "resitelny" mnohem lepe nez kdejaky problem v P.

Co teda vlastne mame "P/NP dokazat"?

Problém P/NP jsem v diskusi ani v článku nezmínil, nevyužívám je. Když už se ale do toho pustili jiní diskutující, proč se jich nezeptáte?

Já bych nebyl proti, kdyby se ukázalo, že pro konkrétní instanci hašovací funkce je problém nalezení její kolize NP-úplný problém. Nedokazuje to nic, dává to jen lepší reference, :-)
A to z důvodu, který sám uvádíte pomocí symbolu O(1.000000001^n).

Teorie složitosti rozděluje problémy do tříd. V každé třídě jsou problémy přibližně (řádově) stejně složité. Jejich složitost se uvádí jako funkce jejich rozměru, parametru. Třeba u hašovací funkce je parametrem n počet bitů hašovacího kódu. Zatím známe algoritmy, které umí nalézt vzor (resp.kolizi) k zadané haši se složitostí 2^n (resp.2^(n/2)). To je exponenciální složitost (nikoli lineární...). Proto tento problém nemůže patřit do třídy P, kde mají algoritmy složitost nejvýše polynomiální vzhledem k n, tj. třeba n^3 apod.

Jedna z nesložitějších tříd problémů je třída NP-úplných problémů. Nikdo se nebude zlobit, když jeho kryptografické konstrukce budou odpovídat problémům z této třídy. Na druhé straně se tomu nepřikládá takový praktický význam, právě z důvodu, který uvádíte. Přikládá se tomu ale význam teoretický.

Pokud vás zajímají definice, například v on-line příručce na str. 57 - 63, http://www.cacr.math.uwaterloo.ca/hac/about/chap2.pdf

aha, takze kdyz mluvime o prislusnosti hashovaci funkce do tridy NP, musime ji mit parametrizovanou pres delku vystupniho hashe. Takze H(x, n) da na vystup n bytovy hash. Chapu to dobre? U takove funkce by se uz o NP uplnosti dalo diskutovat. Nicmene, i zde bych vysledku neprikladal prilisnou vahu, protoze napriklad fakt, ze "H(x, 1000) = konstanta" nic nemeni na tom, ze H muze byt nekde treba v PSPACE.

Sohlasím od začátku až do .....přílišnou váhu.
Nicméně mohli bychom v tom ustat, protože, jak jsem uvedl výše, ten nový koncept nemá s tímhle nic společného.

Vazeny pane, zkuste treba wikipedii. Patrne byste se dozvedel, ze prislusnost problemu do trid neni podminovana nejakou nekonecnosti. Zlozitost algoritmu je definovana jako pocet kroku klasickeho turingova stroje v zavislosti na delce vstupu (pouze 0 a 1). Samozrejme v realu nikdo netvori pravidla pro zakladni turinguv stroj, protoze bylo ukazano, ze libovolny pocitac (ne zrovna kvantovy - mluvime o deterministickych algoritmech :) urychluje vypocet "jen malo". Taky vstup nemusi byt pocitany binarne.

V praxi tedy vezmeme problem (zadani transformace vstupu na vystup) a merime, kolik kroku algoritmus potrebuje na vypocteni teto transformace. Pokud existuje (deterministicky) algoritmus, kde vstup neni v mocniteli, je problem v P, jinak je v NP. Specialni tridou je NPC, kam patri algoritmy, kde staci najit P algoritmus pro jeden z nich a cela trida NP bude patrit do P.

chtelo by to vic opatrnosti a premysleni, kolego... aaa mluvil o nekonecne tride problemu (spis instanci konkretniho problemu, ne?). Kdby byla konecna, tak se da i s resenim v klidu zakodovat do prechodove funkce turingova stroje, cili razem tu je ten deterministiciky algoritmus.

Skvely clanek, dik

Připojuji se k pochvale. A líbí se mi i diskuse pod článkem, zatím se vyvíjí hezky. :-)

> Na to nebyly klasické blokové šifry připraveny a nikdy proti této možnosti chráněny. je u > klasických blokových šifer zcela základním výchozím bodem.
Chybi cast vety?

Díky. Upadlo:
Předpoklad neznalosti klíče je u klasických .....

Mohl by mi někdo dát link popř vysvětlit co přesně hashovací funkce jsou? Děkuji

Přednáška pro MFFUK je na http://www.karlin.mff.cuni.cz/~tuma/nciphers/
je to moje přednáška I (úvodní myšlenky) a III (definice, vlastnosti).

Populárně: http://crypto-world.info/klima/1999/chip-1999-03-40-43.pdf
a http://crypto-world.info/klima/1999/chip-1999-04-44-46.pdf

Určitě existují lepší stránky, kde je to popsáno stručněji a výstižněji, tohle jsou spíš výkladové a učební texty, nikoli pro rychlé seznámení.

Na rootu jsem našel třeba:
http://www.root.cz/clanky/sifrovani-uvod-do-problematiky/

http://www.karlin.mff.cuni.cz/~tuma/nciphers/

Forbidden

You don't have permission to access /~tuma/nciphers/ on this server.

díky,
celý kurs
http://www.karlin.mff.cuni.cz/~tuma/nciphers.html

moje první přednáška (zajímavé kryptografické myšlenky)
http://www.karlin.mff.cuni.cz/~tuma/nciphers/Symetricka_kryptografie_I.pdf

moje třetí přednáška (obsahuje hašovací funkce, definice, vlastnosti)
http://www.karlin.mff.cuni.cz/~tuma/nciphers/Symetricka_kryptografie_III.pdf

Chtel bych se zeptat, zda by neslo udelat nejake "executive summary" - nejak jsem ze clanku (na "rychle precteni") nepochopil.

Co chapu: hashovaci funkce je neco, cemu na vstup zadam libovolna data a ona mi na vystupu vyhodi "signaturu" tech dat (typicky o pevne delce). Vzhledem k tomu, ze delka signatury je casto vyrazne mensi nez delka vstupnich dat (jinak by v podstate hash "nemel smysl" a slo by spise o kryptovani), tak pochopitelne musi dochazet ke kolizim. Vtip hashovaci funkce je v tom, ze by nemel existovat algoritmus (jiny nez "brute force"), ktery ze zadaneho hashe vykonstruuje vstup s timto hashem. To, jake operace hash se vstupem provadi, tak je v podstate cerna skrinka a musi se chovat vzdy deterministicky podle vstupu (jinak by nesla provadet kontrola hashe a dodanych dat).

V cem se od toho lisi popisovany pristup? (jestli vubec).

Diky.

Pochopil jste všechno správně. Jenom bych doplnil, že kromě odolnosti proti nalezení vzoru z hašovacícho kódu (jak píšete) by hašovací funkce by měla být také odolná proti nalezení kolize (dvou vstupů se stejným výstupem). To jsou dvě základní vlastnosti. Pak je ještě halda dalších, nespecifikovaných jednotlivě, ale globálně jako že hašovací funkce se musí chovat jakoby zcela náhodně (náhodné orákulum). Protože je to dost protichůdný požadavek proti přísně determiničnosti jejího předpisu (algoritmus, dokonce známý všem, i útočníkům) musí se obezřetně konstruovat. V práci říkám, že to nejde konstruovat z klasických blokových šifer, ale měly by se použit speciální, které jsou apriori lépe vybavené a konstruované proti útokům na hašovací funkce.

Executive summary by šlo doplnit, ale už jsem neměl sílu. A navíc, vy to nepotřebujete, pochopil jste všechno správně.

Mým cílem bylo ale ještě trochu více. Ze svojí práce jsem vybral jednu myšlenku a tu jsem takto populárně popsal. Myslím, že na seznámení s tím, oč jde, to stačí. Koho to chytlo, může se seznámit s celou prací. Rád bych s těmito lidmi diskutoval. Proto prosím neváhejte mi zde a na mail svoje dojmy a kritiky psát.

Jsem rád, že jste splnil to, čím jste vyhrožoval na aktualne a to, ze date do kopy hezky clanek! :-) Na druhe strane, jsem jen hloupý kolač, co se dešifrovánim nezabývá, ale přesto se nemohou zbavit dojmu, že řešením problemu bude stejně v praxi jen prodlužování hashovacího výstupu v závislosti na délce veritifikovaného dokumentu. Vede mne k tomu jednoduchá úvaha, že pro minimální dokument je nalezení stejného hashe vyloučeno, tak pro nekonečně dlouhý dokument je rpo limitovanou délku výstupu, nalezeni možné. Tedy různými konstrukcemi jen zvýšíme složitost nalezní stejného hash, ale nikdy to nemůžeme vyloučit. Při prodlužování délky výstupu se složitost nalezení výsledku zvyšuje velmi povzbudivě.

Ty poslední dvě věty:

Tedy různými konstrukcemi jen zvýšíme složitost nalezní stejného hash, ale nikdy to nemůžeme vyloučit. Při prodlužování délky výstupu se složitost nalezení výsledku zvyšuje velmi povzbudivě.

jsou perfektní.

Komentář k první větě:
Finta spočívá v tom, že pokud zvýšíme složitost dostatečně, třeba na 2^128, můžeme spát stejně klidně, jako kdyby tam bylo náhodné orákulum. U té nové konstrukce se podařilo (poprvé) dokázat, že ta složitost je taková jako u náhodného orákula.

Komentář k druhé větě:
Zvyšování délky kódu je "metoda kanadských dřevorubců" pro zvyšování bezpečnosti, zdvojnásobíte délku kódu a kvadraticky zvýšíte bezpečnost. Vede to k cíli, ale ne všude se hodí. A nesmí to být berlička proti slabé funkci uvnitř. Čím delší kód, tím složitější vnitřek příslušné funkce, a to ze zkušenosti roste také cca s kvadrátem, čili cca kvadraticky se snižuje rychlost. Vida, a jsem tam kde jsme byli - za kvadraticky zvýšenou bezpečnost zaplatíme kvadraticky sníženou rychlostí. Osobně to nazývám zákon zachování nepříjemností ([Klíma: "Tajná válka šifer", 1994]).

Asi jsem se špatně vyjádřil. Co se týká prodlužování délky hash výstupu, tak jsem nemyslel konstantní délku, ale protože se vstup zpracovává po blocích, tak výstupem na každý blok může být 1 bit (doplněný případně na celý bajt u posledního zpracovaného bloku standardním výstupem hash kompresní funkce. To by rychlost prakticky nemělo ovlivnit a složitost nalezení (pokud se ten výstup jednoho bitu udělá dobře aby negeneroval kolize) stejného hash bude uspokojivá i pro Vás :-).
Co se týče první komentované věty (možná si všímáte že rád beru věci od konce :-) ) tak bych k ní měl též poznámku. Souhlasím s Vámi že po sestrojení vhodné funkce na generaci hash se všichni radují, ze to má složitost 2^n, ale to jen do té doby než nějaký zatracený asiat to nějakou podivnou konstrukcí prolomí. Proto se i v běžném životě přikláním k tomu, že než jeden složitý zámek na dveře, tak raději dva o něco jednodušší - což snižuje pravděpodobnost náhodné překonatelnosti složitého zámku. Z toho vyplyne to co jste komentoval v druhé větě.

Čili jestli tomu rozumím, tak za každý hašovaný blok zprávy jeden bit. Když bude zpráva dlouhá tisíc bloků, tak hašovací kód bude mít 1000 bitů? Co když to bude milion bloků (64MByte soubor není nic výjimečného), bude hašovací kód milion bitů?

Tudy cesta nevede ze dvou hledisek.

První: hašovací funkce mají předepsánu pevnou délku hašovacího kódu, která je pevná. Zejména proto, že ten se podepisuje algoritmy jako RSA, DSA, ECDSA apod. A ty jsou stavěny na kód omezené délky (ideální max. 512 bitů).

Druhá: bezpenostní. Hašovací funkce musí být kvalitní i při hašování jednoho bloku. Jak dlouhý bude hašovací kód pro jeden blok? Až odpovíte, dejme tomu 256 bitů, řekneme stop. Jako útočníci se budeme zabývat pouze jedním blokem. Dostáváme klasickou hašovací funkci, kde není vaše konstrukce přidávání bitu za každý blok funční. Takže bychom museli dokazovat kvalitu původní funkce i přídavné konstrukce.

S těmi zámky na dveře je to zajímavé. Když si zloděj přinese štípačky na nějakou tlouštku "drátu" visacího zámku, tak těmi štípačkami dva stejné jednodušší zámky přeštípne. Když tam bude jeden tlustší, tak má smůlu, musí vzít štípačky větší. Zkrátka záleží na síle ochranného mechanismu. Pokud nevíme jakou mají sílu ty zámky, tak logicky větší důvěra bude v to, když tam budou dva různé.

Pokud se vrátíme k matematice, je možné tam dát dva zámky ve formě dvou různých metod. Protože kompresní funkci musíme opakovat mnohokrát, ty dvě různé metody musí být včleněny dovnitř funkce f. Čili teď se bavíme o vnitřní struktuře jednoho zámku (f), který má v sobě použity dva různé mechanismy ochrany. Ve skutečnosti kompresní funkce má použito více mechanismů. To, že nějaký génis přijde s nápadem jak je všechny dohromady obelstít, je možné. Stejně tak je možné vyhrát každý den první ve sportce. Vyloučit to nejde. Jde tady jen o pravděpodobnost. Byl bych rád, kdyby ty pravděpodobnosti byly srovnatelné, ale pokrok v kryptoanalýze v posledních letech svědčí spíš o opaku. Proto jsem navrhl funkce DN a HDN hodně robustní.

Alespoň podle včerejšího článečku Windows Forms Password Encryption Visual Basic 2005.

Citát:
A cryptographic hash function has the property that it is computationally infeasible to find two distinct inputs that hash to the same value; that is, hashes of two sets of data should match if the corresponding data also matches.

No nic - jen rada, buďte v takovýchto situacích obezřelí :-)

V jakých situacích? Při čtení MS dokumentace? Ale ovšem, díky za radu. ;-)

Zdravím a děkuji za článek. Mám dotaz. Píšete "Připomeňme, že pokud dáme zhašovat nějakou zprávu náhodnému (hašovacímu) orákulu, vygeneruje si právě v tom okamžiku náhodný řetězec, o kterém nemělo předtím ani potuchy, a vrátí vám ho. Orákulum si ještě vede tabulku už vygenerovaných hodnot, a pokud mu náhodou dáte zhašovat starou zprávu, vrátí vám výsledek stejný jako při prvním dotazu, tentokrát ze své tabulky."

Jak je možné, že orákulum pozná, že už jednou tu "starou zprávu" zhašovalo, když si ze vstupu "vygeneruje náhodný řetězec, o kterém nemělo předtím ani potuchy"?
Tabulku už vygenerovaných hodnot si může vést, jenže jak se tam píše ty jsou "náhodné", a tedy není možné aby pro ten samý vstup generoval ten samý výstup. Proto se tam taky musí vést ta tabulka, jak chápu.
Ale to by, podle toho jak se mi to jeví, znamenalo, že si orákulum musí uložit celou "starou zprávu" a k ní ten náhodný hash aby to bylo jisté. To je dost neefektivní a asi i nepřenositelné na jiný počítač takže to asi tak nebude :)
Jenže pokud by si místo celé staré zprávy orákulum uložilo nějaký menší "kousek" tak by to nejspíš zase byl "nějaký" haš. Jenže kde ho vzít a nevystavit se zase nutnosti něco hašovat?
hezký večer

Jak pisete, nahodne orakulum si musi ukladat jak povodnu spravu, tak vystup, ktory k nej priradilo (aby mohlo pri rovnakom dotaze odpovedat rovnako).

Nahodne orakulum je teoreticky model (podobne ako lubovolne ine orakulum alebo trebars nedeterministicky Turingov stroj), tj. neriesi sa, kde si bude ukladat tu tabulku, podstatne su len jeho "zvonka viditelne" vlastnosti.

Random oracle model ma hlavne v kryptografii velky vyznam, viz napr. http://en.wikipedia.org/wiki/Random_oracle_model. Napr. v mnohych dokazoch sily kryptosystemu sa predpoklada, ze hasovacie funkcie su nahodne orakula (co je v praxi splnit pomerne tazsie) a na zaklade vlastnosti nahodnych orakul sa odvodzuje sila kryptosystemu oproti urcitym utokom.

Preto vlastnost, ze nova konstrukcia hasovacich funkcii ich robi vypocetne nerozlisitelnymi od nahodnych orakul je dost vyznamna pre bezpecnost schem pouzivajucich nove hasovacie funkcie zalozene na SNMAC konstrukcii.

Dalsi teoreticky vyznam nahodnych orakul su relativizovane systemy v teorii zlozitosti, viz napr. Baker-Gill-Solovay (http://theory.csail.mit.edu/~madhu/ST05/scribe/lect02.pdf).

takze je to vlastne pseudonahodne orakulum, rozumim tomu dobre?

tak me napadlo, ze fraktaly maji podobne chovani.... na vcelku jednoznacnou otazku vraci naprosto nepredvidatelnou odpoved, ale pro stejny vstup je to porad to same...

Chtěl jsem napsat, že ano, ale je to složitější. Pseudonáhodné orákulum není definováno. Jestli tím chcete říci, že je to něco, co sice není náhodné orákulum, ale nevíme, jak to prokázat, pak jsou to všechny hašovací funkce.
U konstrukce SNMAC je prokázáno, že v limitě se blíží náhodnému orákulu a pro konečné rozměry máme odhady počtu operací, které jsou potřeba na dva specifické útoky - nalezení vzoru nebo kolize. Oba dva útoky vyžadují pro konečné rozměry stejný počet operací, jako kdyby tam bylo náhodné orákulum.
Nechce se mi tuhle skvělou konstrukci nazývat pseudonáhodné orákulum, už jen proto, že bychom mohli urazit Bellare, který před deseti lety vymyslel NMAC a Corona, který u NMAC udělal tu nerozlišitelnost.

Fraktály nejsou mojí oblíbenou parketou, už jsem jednou rozluštil systém šifrování, na nich založený. Podobně dopadl systém, využívající funkci popisující činnost oka a další. U hašování nejde zaměstnat jakýkoliv chaos.

Uvedu příklad. Mějme opravdové náhodné orákulum f (posadíme blázna Pepka Vyskočila ze Švejka před bednu míčků, v nichž jsou ukryty jedničky nebo nuly a chceme, aby je vytahoval, tj. emitoval nezávislou náhodnou stejnoměrně rozdělenou binární posloupnost. Nad ním bude dráb, který si bude zapisovat, všechny odpovědi Pepka Vyskoče do tabulky.). Uděláme Merkle-Damgardovu konstrukci hašovací funkce a použijeme v ní f jako je na obrázku 1 (tj. zpráva se vezme, rozdělí na bloky a ty se postupně komprimují pomocí funkce f). Myslíte že výsledná hašovací funkce bude náhodné orákulum nebo ne?

Jenom připomínám, že tuto konstrukci mají všechny současné hašovací funkce, protože to prakticky ani jinak nejde (viz plná verze příspěvku), ale místo náhodného orákula f tam mají nějakou konkrétní funkci, složenou z klasické blokové šifry a nějakých úprav. Jinými slovy vám dávám otázku, jestli současné hašovací funkce se stanou náhodnými orákuly, když místo jejich funkcí f dáme orákulum Pepka Vyskočila.

Pokud náhodou odpovíte ne, je to odpověď na to, že i dokonalý chaos (náhodné orákulum f) nelze jen tak nějak použít v hašovací funkci. Já vím, že je to rána, ale co myslíte, je to pravda nebo ne?

Nedal by sa ako SBS pouzit 128-bitovy Rijndael s 256-bitovym klucom? Kluc by bol tvoreny 128 bitmy spravy m_i a 128 bitmi kontextu h_{i-1} a zasifrovala by sa nim konstanta Const_0 resp. na konci Const_1. V takomto pripade by by boli n=128 a K=256. Rychlost by bola asi uboha, ale snad by sa dal znizit interny pocet rund, aby sa pre tento ucel neznizila bezpecnost.

V tejto suvislosti ma napada: je nejakym sposobom dolezity pomer cisel n a k? Je nejaky interval, v ktorom by sa mal tento pomer hybat?

errata:
Nove kryptograficke primitivum - koniec paragrafu: "konstruovat na pomoci"
Konstrukce SBS - koniec paragrafu: "mnoo ruznych navrhu"

Martine,
nejdřív ti chci veřejně poděkovat za korekturu angličtiny první části příspěvku pro Eurocrypt (Martin udělal korekturu první den na svojí vědecké stáži ve Francii a během pár hodin jsem měl výsledek, stačil jsem to ještě v noci poslat na server Eurocryptu). Teď ovšem musím také poděkovat Dr.Tomáši Rosovi za první korekturu a za pečlivé pročtení a důkladnou odbornou kontrolu textu. To byla ohromná práce a pomoc.

Tak a teď ke kryptologii. Díky za názor, moc rád podiskutuji. Tvůj návrh je přímočarý a naprosto logický. Nalézá se v posloupnosti námětů takto: Obr.1 -> Obr.2 -> ... -> Martin. Podobně se snažil zaměstnat dvě klasické blokové šifry Hirose, viz
[Hir04]. Tvůj návrh je lepší v tom, že už využívá té myšlenky konstanty v otevřeném textu. To zabraňuje lecčemus. Zbývá poslední problém, a tím je místo klasické blokové šifry (Rijndaelu) tam dát tu speciální. U tvé konstrukce by útočník mohl hledat jen jeden blok zprávy, přičemž proměnná hi je konstanta - inicializační vektor. Obdrží kompresní funkci, která má pouze 128bitový vstup, vedený do klíče (druhá polovina klíče je konstanta, otevřený text je konstanta).

A jsme tam, kde jsme byli. Máme klasickou blokovou šifru Rijndael, přičemž útočník na ni doráží prostřednictvím klíče. Na to nebyl Rijndael stavěn (ani žádná jiná klasická bloková šifra). Stačí malinká úprava - dát tam šifru, která je stavěna na útok zpoza klíče, a je to v pořádku. No, ale to je SBŠ. A jsme tam, kde jsme byli, jen o patro výše, chráněni proti tomuto útoku. A jiný nám nehrozí, protože zbytek jsou konstanty.

Pokud se týká závěrečné úpravy g, může leccos zachránit, ale neměla by to být berlička na nějaké (nové) vady předchozí konstrukce, kterým můžeme zabránit už v té konstrukci samé.

[Hir04] S. Hirose: Provably secure double-block-length hash functions in a black-box model, Information Security and Cryptology - ICISC 2004, 7th International Conference, Seoul, Korea, December 2-3, 2004, Lecture Notes in Computer Science, Vol. 3506, pp. 330-342

Místo Obr.1 -> Obr.2 ->...
má být
Obr.3 -> Obr.4 -> ...

Dakujem za odpoved. Zatial nemam este uplne ujasnene, preco je moznost manipulovat s klucom nebezpecna, takze to budem povazovat chvilku za axiom :).

Asi mate pravdu, ze zo sucasnych blokovych sifier nejde jednoducho a efektivne urobit SBS. Keby to ale islo, bola by to iste velka pomoc pri konstrukcii SNMAC, pretoze napr. Rijndael je celkom slusne prevetrany zo vsetkych stran a sucasne prace o jeho bezpecnosti by sa dali pouzit pri studiu SNMAC.

Dalsi (velmi dolezity) aspekt je rozsirenie Rijndaelu v mnohych produktoch (HW/SW), ktore by potrebovali velmi malu zmenu v navrhu, aby sa dali pouzit aj v SNMAC. Na podobnych zakladoch staval Alex Biryukov pri navrhu prudovej sifry Lex [Bir06].

Podla mna by bolo teda z praktickych ucelov velmi v(y)hodne, zamysliet sa nad uplatnenim sucasnych sifier v roli SBS.

Moj predosly navrh ste (opravnene, vid axiom :) ) zmietol, tak hned predkladam druhy :). Priznam sa ale, ze nemam nastudovanej mnoho literatury o kryptoanalyze blokovych sifier, takze mozno bude Vasa vytka opat jednoducha.

Tu je navrh: pouzit tentokrat 256-bitoveho Rijndaela s 256 bitovym _konstantnym_ klucom, pricom vstup by sme vytvorili z m_i a h_{i-1} rovnako ako kluc v minulom navrhu. Na vystupe by sme dostali 256 bitov, ktore by sme "skratili" tak, ze by sme XORli hornu a dolnu polku. Vysledok specialnej "blokovej sifry" by bolo tychto 128 bitov. Uvodzovky preto, lebo si neviem narychlo predstavit, ako by sa taketo nieco desifrovalo - najskor nijak, o co nam vlastne ide.

V takomto navrhu by uz sa vsetky vstupne bity spracovavali homogenne a manipulacia s klucom by bola nemozna. Opat by to bolo samozrejme pomale. Neviem, kolko rund SNMAC by bolo potrebnych.

[Bir06] A.Biryukov "The Design of a Stream Cipher LEX", Lecture Notes in Computer Science, proceedings of SAC'2006. ( http://homes.esat.kuleuven.be/~abiryuko/sac06-lex.pdf )

Tak to se mi moc líbí. Názory neber jako výtku, diskutujeme, jsou to názory. Pojďme trochu dále k podstatě tvého návrhu. Zkusme NExorovat obě poloviny výstupu, jak navrhuješ, ale vzít jenom první polovinu jako výstup, tj. 128 bitu z E_const_klic(mi, hi-1).

Který z obou návrhů je lepší?

Z praktického hlediska je lepší ten druhý návrh, protože je o jednu operaci rychlejší. (přesněji dokonce o více, protože z konce algoritmu by se mohly odstranit další operace, které vytváří nepoužitou druhou polovinu výstupu).

Podstatná otázka: který z obou návrhů je lepší teoreticky ?

Mate (opat) pravdu. Vystup z blokovej sifry by sa "nemal lisit od nahodneho textu", takze by malo byt jedno, ci zoberieme len prvych 128 bitov vystupu alebo XOR oboch polovic. Myslim si teda, ze Vas navrh je lepsi z hladiska praktickeho (aj ked jeden XOR pri Rijndaeli je zanedbatelny), ale z hladiska teoretickeho su obe konstrukcie ekvivalentne (za predpokladu, ze sa Rijndael sprava "rozumne").

Vsetky doterajsie studie sa zaoberali komplentnym Rijndaelom (nie "okresanou" verziou, ktora by na konci vypustila par vypoctov kvoli tej jednej nepouzitej polovici vystupu). Ak by sme chceli nejakym sposobom existujuce vysledky vyuzit, predsa len sa mi javi lepsi ten XOR, pretoze je postaveny na komplentej verzii.

Co ma viac trapi na tejto konstrukcii je fakt, ze cely cas sa pracuje s blokom 256 bitov a vystup je "iba" 128 bitovy. Nie je to skoda? Je to dan za to, ze sme do kluca dosadili konstantu. Stalo by asi za uvahu, ako to napravit tak, aby sme o tych 128 bitov neprisli a zaroven by bola splnena podmienka spracovavania vsetkych vstupnych bitov homogenne. Vy ste si s tym ale uz mozno pracu dal a vysledky uvidime po publikacii SBS DN.

Myslim, ze teraz ste hovoril o mojom prvom navrhu, ktory daval hasovanu spravu do kluca. V druhom navrhu som tento nedostatok opravil, do kluca dal konstantu a hashovanu spravu spolu s kontextom dal do vstupnych 256 bitov sifry. V tomto pripade by sa nedali vyuzit diferencie v hasovanom texte (opat za predpokladu, ze je Rijndael slusna sifra). Jedine, co by mohol utocnik skusat menit, je vstup, cim sa ale dostavame ku generickemu utoku.

Je ale pravda, ze na taketo pouzitie nebol Rijndael pravdepodobne stavany a je nevhodny. Moja snaha pouzit Rijndael bola odovodnena tou kopou usilia, ktora za nim stoji a jeho ohromne rozsirenie v HW/SW.

Som zvedavy na Vas komentar ohladom tej efektivity 256bit blok vs. 128bit vystup.

PS. Mozno sa do pondelka neozvem, pretoze v ubytovni akosi neposlucha internet a zajtra mame volno, takze sa vopred ospravelnujem.

Jo Martine, máš pravdu, byl jsem v internetové kavárně a čekal na ženu. (Šli jsme na Bondovku - Casino Royal. Doporučuju. )Tak jsem předtím zabrousil na root a v půlce odpovědi přišla žena, takže jsem přepnul procesor na jiný kontext a rychle jsem odpověděl. Takhle to dopadlo. Zkrátka dosaď si v těch předchozích argumentech svůj druhý návrh. Ono je to v podstatě jedno, kam se co nacpe v klasické blokové šifře. V každém případě vzniká neefektivní konstrukce. Opět si vypomůžu analogiií. Jednou strkáme to auto na koleje naštorc, podruhé podélně, potřetí podélně a ještě mu místo gum dáme železná kola. Když ho takhle vymódíme, nebylo by lepší ho postavit znovu, čili postavit "železniční auto"? Čili tohle je moje argumentace. Ta myšlenka s hotovým Rijndaelem vypadá na první pohled dobře, ale když to homomorfismem převedeme na příklad se železnicí, tak to vypadá asi takhle: "Když už máme to Lamborgini hotové, a dáme mu železná kola, nemohlo by to také jezdit na železnici ?"

Takže jde pouze o efektivnost. Klasické blokové šifry byly vystavěny tak, aby efektivně zužitkovaly fakt, že máme k dispozici něcoutajeného, a tohle zaměstnáme v té konstrukci maximálně. Proto se klíč fedruje do každé rundy blokové šifry, i když by nemusel.... Proto se tam cpe jednoduchou operací xor, což opět těžce využívá fakt, že se tam xoruje něco neznámého. Proto dřívější šifry nezpracovávaly rundovní klíče vůbec nijak (DES, TripleDES) a současné jen velmi vlažně (Rijndael). Když ale do klíče nacpeme u klasické blokové šifry konstantu, co to vlastně děláme? Původní záměr, aby se nějaká meziproměnná obarvila neznámým klíčem a stala se pro útočníka neznámou v každé rundě, se najednou stává docela jiným principem - konstanta v roli klíče pouze činí jednotlivé rundovní transformace jinými, ale nikoli neznámými. Prostě se tady přeměňuje smysl transformací. A to není dobré, protože to nemusí vyjít. Ta šifra to může ustát, ale nemusí. Proto to musíme škrtnout z principiálního hlediska.

Já bych byl docela rád, kdybys řekl, že se ti na tom nezdá to nebo ono, protože bych chtěl, aby se ten návrh ostřeloval.

Reaguji na vlákno o tom, že MD5 ještě žije. Bohužel nejen v dokumentaci. Na nedávné kryptografické konferenci se odhadovalo, že náhrada MD5 v klíčových produktech, normách apod. bude trvat minimálně pět let.

Klasický příklad, na něž mě upozornil Pavel Vondruška je ke kontrole neporušenosti software pomocí MD5:
http://www.lavasoft.de/download_and_buy/detection_database/

Tenhle soft používají miliony lidí.

Pro distribuci SW je útok na MD5 přímno ukázkový. Naprogramoval mi ho Ondrej Mikle. Příslušnou informaci najdete například v diskusi na aktuálně.cz

Tam jsem také napsal pro nevěřící následující příklad (donutili mne k tomu). V diskusi jsem dostal různé texty a měl jsem docílit aby se k nim našly druhé texty, které by byly smysluplné, se stejnou haší. Kdysi jsem Ondru použádal, aby ten příklad udělal na tři texty (je možno libovolné množství, libovolných typů souborů, libovolného obsahu).


Příklad. Dostal jsem v diskusi texty

"Cena produktu je 1000 korun českých"
"Já mám koně vrané koně"
"Objednáváme u Vás 200 cihel"

a jejich protistrany

"Cena produktu je 1 000 000 korun českých"
"Pec nám spadla"
"Zavazuji se zaplatit panu X částku jeden milion korun českých"

Vyrobil jsem kolizi.

Takže si stáhněte soubor http://cryptography.hyperlink.cz/2004/package1.exe, vypočtete si jeho haš, dostanete 01b467556bd0e353fc2134620144c415. Je to samorozbalovací soubor, jeho spuštěním vzniknou první tři soubory.

Pak si stáhněte soubor http://cryptography.hyperlink.cz/2004/package2.exe, vypočtete si jeho haš, dostanete 01b467556bd0e353fc2134620144c415. Je to samorozbalovací soubor, jeho spuštěním vzniknou druhé tři soubory.

Jestliže haš souborů package1.exe a package2.exe je stejná, můžeme elektronický podpis jednoho vydávat za elektronický podpis druhého a naopak. Takže když někdo podepíše první tři soubory, podepsal i druhé tři a naopak.

Kolizi může vyrobit kdokoli programem, který je už od března na
http://cryptography.hyperlink.cz/2004/kolize_hash.htm.
Je tam krátký návod. Také tam najdete program http://cryptography.hyperlink.cz/2004/fsum.exe, který vypočte md5 hash od souboru, který zadáte jako parametr.

Myslím, že Rijndaela v roli SBŠ sa asi vzdáme. Prečítal som si zhova Váš článok, zatiaľ bohužiaľ bez dokazov. Snáď sa k nim cez víkend konečne dostanem. Mám na Vás pár otázok:

Veta 1 hovorí o _náhodnom_ výbere blokovej šifry E z BC(K,n). No ale odkiaľ takúto šifru zoberieme? Všetky, ktoré máme (a budeme mať), majú nejaký konkrétny predpis. Vadí nám to? (tá istá otázka sa vzťahuje k náhodnému orákulu vo Vete 3). Nemože nastať rovnaký problém ako u spojitých funkcií z R do R?: náhodne zvolená funkcia z takejto množiny nemá nikde deriváciu, ale musíme sa veľmi snažiť, aby sme nejakú explicitne našli. Nebude rovnaký problém s náhodným výberom blokovej šifry/orákula? (Tu máme ale výhodu, že BC(K,n) je konečná množina, aj keď obrovská.)

Vo Vete 2 má symbol <---^$ (dolár nad šípkou) dva rozne významy. Náhodná voľba blokovej šifry je jasná, ale zápis "(M,M') <---^$ A" mi až taký jasný nie je. Znamená, že si útočník A náhodne volí správy M a M' a skúša, či majú rovnaký haš? To asi nie. Takto útočník nepostupuje. Nemalo by byť zápis "(M,M') <---^$ A" nahradený zápisom "(M,M') <--- A_E_E^-1" (bez dolára). Ak je moja interpretácia zápisu "(M,M') <---^$ A", tak nám v súčasnom znení veta hovorí, akú výhodu má najsilnejší útočník, ktorý si zvolí _náhodne_ dve správy a pozrie sa, či nemajú rovnaký haš. Sporné je to v tom, že najsilnejší útočník takto postupovať nebude a bude správy voliť rozumnejšie. (Opať je podobná otázka relevatná k Vete 4.)

Každopádne si myslím, že značenie obsahujúce podtržítka zvádza k interpretácii dolného indexu, čo napr. pri A_E_E^-1 vedie k zmatenie čitateľa. Vy ste už s týmto značením zrastený :), ale aj tak by som navrhol preznačiť (ak nie je zaužívané z inej literatúry).

V závere článku uvádzate parametre špeciálnej blokovej šifry DN, K=8192 a n=512. Na prvý pohľad sú to pekné okrúhle čísla, ale keď si uvedomíme, že jej uplatnenie by malo byť hlavne v SNMAC a do 8192 bitov kľúča sa bude sypať 512 bitov kontextu, ostáva nám nie až tak okrúhlych 7680 bitov. Myslím, že programátorom by sa omnoho ľahšie delilo hašovanú správu na bloky po 8 Kb. Mimochodom ma takého čísla (K, n) vedú k domnienke, že v DN nie sú rundové kľúče generované jeden po druhom, ale samotný kľúč je rozdelený na rundové kľúče (z čoho by vyplývalo, že rúnd je 16*L).

Na záver mi predsa len stále nedá pokoj ten Rijndael :). A propos homogenita spracovávania bitov správy a kľúča ma napadla takáto myšlienka (opať Rijndael): namiesto multiplikatívnej inverzie v telese GF(2^8) v kroku SubBytes by sa v GF(2^8) navzájom vynásobili príslušné bajty "pretekajúceho" kontextu a kľuča. XOR kľúča na konci rundy by sa vynechal. Opať by to ale bolo na úkor efektivity, pretože by sme museli mať predpočítanú tabuľku o veľkosti 256^2 bajtov (vs. 256 bajtov u Rijndaela).

Veta 1 hovorí o _náhodnom_ výbere blokovej šifry E z BC(K,n). No ale odkiaľ takúto šifru zoberieme? Všetky, ktoré máme (a budeme mať), majú nejaký konkrétny predpis. Vadí nám to? (tá istá otázka sa vzťahuje k náhodnému orákulu vo Vete 3).

"Trocha" to vadi. Trik je v tom, ze ziadna konkretna funkcia (blokova sifra) nie je nahodnym orakulom, tym padom nie je mozne nic podobne dokazat, ak sa dosadi konkretna blokova sifra. Tie vety platia pre nahodne vybranu funkciu z mnoziny vsetkych hasovacich funkcii s HMAC/NMAC konstrukciou, teda vypovedaju o sile konstrukcie, ale nehovoria moc o konkretnej instancii. Fakt je, ze sa s tym moc neda robit, akurat mozno zabezpecit blokovu sifru proti niektorym utokom (v zmysle ako tu o tom debatujete). Na druhej strane stare konstrukcie (ako iteracne hasovacie funkcie) nemali ani tieto vlastnosti.

Lepší bych nedokázal odpovědět. Tak jenom připojím kratičký důkaz.

Skutečně, jakákoliv konkrétní (nejen hašovací) funkce f nemůže být náhodným orákulem. Stačí dát dvěma lidem ten funkční předpis f a obou dvou se nezávisle ptát na výsledek hašovací hodnoty na konkrétní vstup. Jestliže první z nich vlastní náhodné orákulum, nemůže ten druhý se stoprocentní jistotou předvídat všechny hodnoty, které ten první odpoví. První by je měl totiž vybírat náhodně. Je tu zanedbatelná pravděpodobnost, že ten druhý se vždycky náhodně trefí do odpovědi prvního. Ta pravděpodobnost je menší než jakékoliv malé číslo, pokud orákulum nemá limitovánu délku zprávy.

Martine, díky za diskusi. Je to zajímavé. Těším se na tvoje postřehy k důkazům. Teď probereme tyhle.

Myslím, že Rijndaela v roli SBŠ sa asi vzdáme. Prečítal som si zhova Váš článok, zatiaľ bohužiaľ bez dokazov. Snáď sa k nim cez víkend konečne dostanem.

Rád bych přesvědčil kryptology zvučných jmen, aby se Rijndaela vzdali. A aby se vzdali všech klasických blokových šifer. Proto jsem rád za každou připomínku. Musím s vyzbrojit na "horší" časy, které ještě přijdou.

Věta 1.....

Na to odpověděl "abyssal" výše nebo níže (teď tam nevidím).

Vo Vete 2 má symbol šipka---^$ (dolár nad šípkou) dva rozne významy. náhodná voľba blokovej šifry je jasná, ale zápis "(M,M') šipka---^$ A" mi až taký jasný nie je. znamená, že si útočník A náhodne volí správy m m' skúša, či majú rovnaký haš? to asi nie.

Když útočník něčím odpoví, už si to prověřil, že je to kolize. Pokud kolizi nenalezne, vrací odpověď "nenalezeno". Útočník může ale nalézt mnoho kolidujících zpráv, takže zápis "(M,M') šipka---^$ A" znamená, že si vyberteme libovolnou z těchto jeho odpovědí. klidně by to mohlo být i bez dolaru. tahle interpretace by měla vyplynout popisu v odstavečku "konvence" §3.1 a §3.4. Určitě by to mohlo být popsáno ještě podrobněji, ale musel jsem krátit, abych se vešel do stanoveného rozsahu příspěvku na Eurocrypt.

V závere článku uvádzate parametre špeciálnej blokovej šifry DN, K=8192 a n=512. Na prvý pohľad sú to pekné okrúhle čísla, ale keď si uvedomíme, že jej uplatnenie by malo byť hlavne v SNMAC a do 8192 bitov kľúča sa bude sypať 512 bitov kontextu, ostáva nám nie až tak okrúhlych 7680 bitov. Myslím, že programátorom by sa omnoho ľahšie delilo hašovanú správu na bloky po 8 Kb. Mimochodom ma takého čísla (K, n) vedú k domnienke, že v DN nie sú rundové kľúče generované jeden po druhom, ale samotný kľúč je rozdelený na rundové kľúče (z čoho by vyplývalo, že rúnd je 16*L).

Ajajajajaj. Ajajajajaj. Ajajajajaj. Na to ještě nemůžu reagovat, až tak za měsíc nebo spíš dva, až to bude povolené. Jen na ten začátek. Za kulaté považuji násobky osmi, tedy zarovnání na bajty. Ostatní zarovnání nemají při hašování velký smysl. Zkuste se zeptat programátorů. Dostanete pokaždé jinou odpověď podle toho, v jaké aplikaci nebo aplikacích hašování používají. Pokud to bude programátor, který pokrývá nejrůznější aplikace hašovacích funkcí, jeho odpověď by mě zajímala. Obávám se ale, že by odpověděl stejně jako já. Rigorózně by se to dalo zjistit jenom statistickým průzkumem.

Na záver mi predsa len stále nedá pokoj ten Rijndael :). A propos homogenita spracovávania bitov správy a kľúča ma napadla takáto myšlienka (opať Rijndael): namiesto multiplikatívnej inverzie v telese GF(2^8) v kroku SubBytes by sa v GF(2^8) navzájom vynásobili príslušné bajty "pretekajúceho" kontextu a kľuča. XOR kľúča na konci rundy by sa vynechal. Opať by to ale bolo na úkor efektivity, pretože by sme museli mať predpočítanú tabuľku o veľkosti 256^2 bajtov (vs. 256 bajtov u Rijndaela).

Ta úvaha z hlediska homogenity je dobrá, ale není dobrá z hlediska kolizí. Hned v první rundě by došlo k velké komprimaci dvou bajtů vstupu (a,b) na jeden bajt výstupu (c) z té operace SubBytes: c = SubByte(a,b). Kolize byste mohl konstruovat ihned od první operace, a to nalezením nejen dvou, ale velkého množství různých dvojic (a,b), vedoucích na stejný výstup c. Ke kolizi by stačila jedna taková dvojice. Princip té komprese se může uplatnit až později. Nicméně, i když je tu chybička, myšlenku bych nezahazoval, jen ji posunul na pozdější využití. To vede k obecnějšímu závěru. Začal jste už přemýšlet, jak konstruovat komprimační funkci, a nikoli šifrovací funkci. Šifrovací schopnost jste ani náhodou při té úvaze o zobrazení dvou bajtů na jeden nechtěl využít. Podle mého to chce se oprostit od myšlení svázaného s klasickými šiframi a začít na tu úlohu hledět nezaujatě, nesvázaně se stereotypy posledních dvaceti let. Jděte do toho, držím vám palce.