Hlavní navigace

Vlákno názorů k článku Vlastimil Klíma: Zcela nový koncept hašovacích funkcí od Abraxis - Chtel bych se zeptat, zda by neslo udelat...

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

  • 14. 11. 2006 8:55

    Abraxis (neregistrovaný)
    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.
  • 14. 11. 2006 9:36

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

    Mard (neregistrovaný)
    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ě.
  • 16. 11. 2006 9:37

    bez přezdívky
    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]).
  • 17. 11. 2006 0:59

    Mard (neregistrovaný)
    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ě.
  • 17. 11. 2006 9:57

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