Hlavní navigace

Vlákno názorů k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od Martin Hlaváč - Myslím, že Rijndaela v roli SBŠ sa asi...

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

  • 17. 11. 2006 19:16

    Martin Hlaváč (neregistrovaný)
    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).
  • 17. 11. 2006 21:06

    abyssal (neregistrovaný)
    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.

  • 18. 11. 2006 11:34

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

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