C3 seminár

Analýza vlastností kompresných funkcií konštruovaných z náhodných premutácií (inštancovaných napr. z blokových šifier) - odolností voči kolíziám a hľadaniu vzoru. Základné horné odhady získané v ideálnom modeli s neobmedzene silným útočníkom. Prezentácia vychádza z článku Security/Efficiency Tradeoffs for Permutation-Based Hashing (Rogaway, Steinberger, EC 2008).

The cascade encryption is a simple and practical construction used to enlarge the key space of a blockcipher without the need to switch to a new algorithm. Instead of applying the blockcipher only once, it is applied l times with l independently chosen keys.
It is well-known that double encryption improves the security only marginally, due to the meet-in-the-middle attack. Hence the shortest reasonable length of a cascade is l=3, which is also widely used. At EC 2006, Bellare and Rogaway presented a proof that triple encryption significantly improves the security over single and double encryption. Their result is stated in the ideal cipher model and implies that the cascade construction is indistinguishable from a random permutation as long as the number of queries does not reach 2^{k+0.5min(k,n)}. We shall discuss the proof of this result along with some improvements and a generalization to longer cascades.

Jednou z dôležitých vlastností kryptografických hašovacích funkcií je ich "podobnosť" s náhodným orákulom. Napríklad klasická Merkleho-Damgardova konštrukcia nie je neodlíšiteľná od náhodného orákula (teda nemá vlastnosť Pro -- pseudorandom oracle). Ukážeme vzťah vlastnosti Pro a iných vlastností hašovacích funkcií, ako napríklad odolnosti voči kolíziám, odolnosti nájdenia vzoru, vlastnosti pseudonáhodnej funkcie a ďalších.

Ľubovoľná kryptografická konštrukcia (bloková šifra, prúdová šifra, MAC a pod.) môže byť popísaná ako sústava polynómov nad GF(2). Kryptoanalýza potom nie je nič iné, ako riešenie sústavy pre neznáme hodnoty bitov kľúča. Cube attack je spôsob ako efektívne riešiť sústavu tzv. "tweakable" polynómov, v ktorých môžeme ľubovoľne meniť hodnoty verejných premenných (napr. bity otvoreného textu). Spomenieme aplikácie útoku na blokové šifry a prúdové šifry (a špeciálne na prúdovú šifru Trivium). Prezentácia vychádza z článku Cube Attacks on Tweakable Black Box Polynomial (Dinur, Shamir, ePrint 2008/385).

Niektoré aplikácie požadujú vysokú rýchlosť šifrovania aj za cenu zníženia jeho bezpečnosti. Zvýšenie rýchlosti sa dá pri zachovaní pôvodného (kvalitného ale výpočtovo náročného) šifrovacieho algoritmu dosiahnuť napríklad zašifrovaním len časti dát. Práca analyzuje bezpečnosť algoritmov selektívneho šifrovania postavených na rôznych metódach výberu tejto časti.

Častou metódou autentifikácie je použitie hesla známeho obom komunikujúcim stranám. Takéto heslá sú zvyčajne vyberané z veľmi malej množiny, čím umožňujú útok typu brute-force. Bude demonštrovaný protokol založený na kombinácii symetrického a asymetrického šifrovania, ktorým si aj za týchto podmienok komunikujúce strany dokážu dohodnúť spoločný kľúč. Poukázané bude na úskalia spôsobené použitím konkrétnych kryptografických primitív namiesto ideálnych šifier.

V prezentácii uvediem "state of the art" na poli kryptografických homomorfizmov. Počiatočný záujem od Rivest, Adleman, Dertouzos 1978, potom zopár návrhov napr. Ferrer alebo Fellows a Koblitz, ktoré boli zlomené a spomeniem zopár existujúcich grupovych homomorfizmov (RSA, Goldwasser-Micali, Paillier). Druhá časť sa bude zaoberať algebraickými homomorfizmami (zachovávajú operácie + aj *), konkrétne budem prezentovať konštrukciu z PhD práce od D. Rappeho. Existencia algebraických homomorfizmov je stále otvorenou otazkou.

Odhalíme čo znamenajú a ako fungujú základné pojmy z teórie informácie ako Entrópia, Relatívna entrópia (alebo aj Kullback-Leiber divergence) a Vzájomná informácia. Ukážeme si základné vzťahy a nerovnosti, súvis s kódovaním a pravdepodobnostnými rozdeleniami. Pokúsime sa ukázať vzťah s Kolmogorovskou zložitosťou.

Od roku 2004 vieme, že zreťazovanie výstupov dvoch hašovacích funkcií (teda f(m)||g(m)) nie je vďaka multikolíznemu útoku, dostatočne bezpečný spôsob kombinácie dvoch h.f. Ukážeme, že aj pri slabých kompresných funkciách je multikolízny útok najlepší možný. Výsledok sa opiera o fakt, že kombinácia f(m)+g(m) je neodlíšiteľná od náhodného orákula. Prezentácia vychádza z článku On the Strength of the Concatenated Hash Combiner When All the Hash Functions Are Weak (Hoch, Shamir, ICALP 2008)

Je všeobecne známy fakt, že ak máme dve mince, ktoré nie sú úplne spravodlivé (tj. dve náhodné premenné s iným ako rovnomerným rozdelením na množine {0,1}), tak zoXORovaním ich výsledkov dostaneme novú náhodnú premennú, ktorá bude ťažšie odlíšiteľná od rovnomerného rozdelenia ako pôvodné. Zároveň ak je aspoň jedna z mincí spravodlivá, bude aj výsledná konštrukcia spravodlivá.
Článok Indistinguishability Amplification (Maurer, Pietrzak, Renner - Crypto 2007), ktorý budem na seminári prezentovať, rozširuje toto intuitívne pozorovanie na oveľa všeobecnejšie systémy než náhodné premenné. Výsledkom sú dve tvrdenia, popisujúce rôzne spôsoby zvýšenia neodlíšiteľnosti od ideálneho systému kombinovaním nezávislých systémov. Prvé tvrdenie popisuje, ako sa zlepší neodlíšiteľnosť kombinovaného systému od ideálneho v porovnaní s neodlíšiteľnosťou pôvodných systémov. Druhé popisuje podmienky, za ktorých je kombinovaný systém bezpečný voči silnému útočníkovi (napr. adaptívnemu), ak sú pôvodné systémy bezpečné voči slabšiemu útočníkovi (napr. neadaptívnemu).