C3 seminár

We discuss a reduction notion relating the random oracles in two cryptographic schemes A and B. Basically, the random oracle of scheme B reduces to the one of scheme A if any hash function instantiation of the random oracle (possibly still oracle based) which makes A secure also makes B secure. In a sense, instantiating the random oracle in scheme B is thus not more demanding than the one for scheme A. If, in addition, the standard cryptographic assumptions for scheme B are implied by the ones for scheme A, we can conclude that scheme B actually relies on weaker assumptions. Technically, such a conclusion cannot be made given only individual proofs in the random oracle model for each scheme.

Jedným z hlavných cieľov výskumu v oblasti kryptografie je poskytnutie dobrého a efektívneho riešenia pre problém bezpečnej komunikácie. V dnešnej dobe vidíme rastúcu potrebu riešenia bezpečnosti na Internete. Na bezpečnú komunikáciu dvoch a viacerých účastníkov komunikácie je potrebná ich vzájomná autentifikácia a výmena kľúčov. Problém autentifikácie sa zaoberá útočníkom, ktorý kontroluje komunikačné linky používané legitímnymi účastníkmi. Útočník môže odpočúvať posielané správy, môže ich modifikovať, vymazávať, omeškávať ich a vkladať falošné správy. Na základe aktivít útočníka môžeme útočníkov rozdeliť na aktívnych a pasívnych.

Zo smerov, ktorými sa uberá výskum zaoberajúci sa týmito protokolmi sú protokoly na autentifikáciu a výmenu kľúča založené na heslách (password based authenticated key exchange = PAKE). Tieto protokoly sú viac reálne zrealizovateľné, pretože ich tajný kľúč je vybraný z malej množiny možných hodnôt (napr. štvormiestny pin). Vďaka tejto vlastnosti sa ľahšie používajú, nepotrebujú prídavné kryptografické zariadenia na uchovávanie tajného kľúča s veľkou entropiou. Avšak ich slabosťou sú slovníkové útoky. Cieľom pri návrhu protoko- lov bude obmedzenie útočníka na online slovníkové útoky. V tomto prípade musí byť útočník prítomný a interagovať so systémom, aby bol schopný overiť, či bolo jeho hádanie správne. Bezpečnosť v týchto systémoch zvyčajne záleží na politike znevalidovania alebo blokovania použitia hesla, ak sa objaví určitý počet neúspešných pokusov.

Budem prezentovať niekoľko prístupov k problému rozširovania priestoru kľúčov pre blokové šifry, ktorým možno dosiahnuť zvýšenie bezpečnosti. Je známe, že dvojité šifrovanie bezpečnosť nezvyšuje (kvôli meet-in-the-middle útoku) a v praxi používaným spôsobom je trojité šifrovanie (3DES). My sa zameriame na efektívnejšie konštrukcie, ktoré potrebujú menej ako tri volania použitej blokovej šifry. Ukážeme, že konštrukcie využívajúce jedno volanie nemôžu v našom modeli zvýšiť bezpečnosť a navrhneme konštrukciu s dvoma volaniami, ktorá dosahuje optimálnu bezpečnosť (porovnateľnú s trojitým šifrovaním). Prezentované výsledky sú spoločnou prácou so Stefanom Tessarom.

Budem prezentovať niekoľko všeobecných konštrukcií na time-memory-data tradeoff. Cieľom týchto konštrukcií je invertovať danú jednosmernú funkciu a nájsť kompromis medzi pamäťovou a časovou zložitosťou. V niektorých prípadoch vie táto konštrukcia využiť aj väčšie množstvo získaných dát (napríklad dlhší keystream pri prúdovej šifre). Následne ukážem ako sa tieto konštrukcie dajú pri niektorých prúdových šifrách ešte zlepšiť, keď využijeme niektoré slabiny týchto šifier.