Hlavní navigace

Vlákno názorů k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od Petr Simandl - Zdravím a děkuji za článek. Mám dotaz. Píšete...

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

  • 14. 11. 2006 19:01

    Petr Simandl
    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
  • 14. 11. 2006 19:41

    abyssal (neregistrovaný)
    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).
  • 15. 11. 2006 1:24

    deda.jabko (neregistrovaný)
    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...
  • 15. 11. 2006 7:31

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