Hlavní navigace

Vlákno názorů k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od Martin Hlavac - Nedal by sa ako SBS pouzit 128-bitovy Rijndael...

Článek je starý, nové názory již nelze přidávat.

  • 15. 11. 2006 17:13

    Martin Hlavac (neregistrovaný)
    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"
  • 16. 11. 2006 9:23

    bez přezdívky
    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
  • 16. 11. 2006 10:13

    Martin Hlavac (neregistrovaný)
    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 )
  • 16. 11. 2006 11:47

    bez přezdívky
    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 ?
  • 16. 11. 2006 12:53

    Martin Hlavac (neregistrovaný)
    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.
  • 16. 11. 2006 16:14

    anonymní
    Z praktického hlediska by bylo lepší použít Rijndael tak, jak je. Teoreticky jak říkáš, by měly být oba návrhy stejně silné. Chtěl jsem jenom demonstrovat, že na tom xoru na konci tak moc nezáleží a zjednodušit si povídání.

    Tak se podívejme, co nám ta kompresní funkce dělá. Vezme otevřený text jako konstantu a do půlky klíče dá další konstantu (při kompresi prvního bloku je to IV) a do druhé půlky klíče dá zprávu. Zašifruje to. Vezme výstup a prohlásí ho za haš.

    Útočník má nyní možnost zkoumat, co dělají diference ve zprávě (tj. difrence v klíči) s diferencemi na výstupu (tj. s diferencemi v šifrovém textu). Byla bloková šifra Rijndael konstruována proti těmto typům útoků? Bohužel nebyla. Může tyto útoky ustát? Může. Ale bude to VEDLEJSI (a upřímně řečeno nepatrně náhodný) efekt její konstrukce. Já ve svém návrhu chci, aby obrana proti takovým útokům byl hlavní cíl konstrukce. Jestliže chceme, aby hlavním cílem blokové šifry byla odolnost proti útokům ze strany klíče, nebudeme je ale konstruovt tak, jako blokové šifry, jejichž hlavním cílem byla ochrana otevřeného textu za předpokladu, že útočník nezná klíč. Lidově řečeno na železnici je vhodnější jezdit vlaky , i když autem by to šlo taky. I tady jde o efektivitu, takže ta nová (speciální) bloková šifra by se mohla vytemperovat tak, aby obrazně řečeno dobře jezdila na železnici.

    K té druhé myšlence o efektivitě se ještě vrátím, teď už musím končit. Omlouvám se.
  • 16. 11. 2006 17:46

    Martin Hlavac (neregistrovaný)
    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.
  • 16. 11. 2006 22:38

    bez přezdívky
    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.