Crypto-Class – vyhodnocení

Před časem jsem tu upozorňoval na free kurz kryptologie na Stanfordu, Crypto-Class, který vede profesor Dan Boneh. Od té doby uplynuly tři měsíce a kurz je za mnou. Normálně bych se spokojil s prostým komentářem u původního příspěvku, že kurz byl prima, ale protože v pondělí 11.6.2012 začíná další běh tohoto kurzu, je asi vhodné popsat, co se v něm můžete dozvědět a proč stojí za to investovat těch několik hodin týdně do studia. Pokud se o kryptologii zajímáte, doporučuji se na kurz zapsat – opravdu to stojí za to.

Registrace

Registrace do kurzu je, stejně jako celý jeho průběh, zdarma. Příznivé jsou i nároky na soukromí, systém po uživateli chce pouze jméno, příjmení, platný e-mail a souhlas s podmínkami používání. Součástí těchto podmínek je také „kód cti“ (Honor Code), slib, že budete pracovat poctivě a nebudete zveřejňovat řešení.

Struktura kurzu

Kurz je veden jako série přednášek, cvičení a nepovinných programovacích úloh. Každý týden (v prvním běhu kurzu typicky v neděli) jsou zveřejněny materiály pro dvě témata, a to:

1. Slajdy (PDF, PPTX) přednášek. Samy o sobě mi přišly poměrně málo použitelné v tom smyslu, že jenom ze slajdů se nic naučit nedá. Nezbytně nutný je výklad k nim.

2. Video s výkladem. V podstatě jde o promítané slajdy výše s trochou animací (Boneh s oblibou do slajdů čmárá, aby zvýraznil, o čem zrovna mluví nebo napsal vzorec a podobně) doprovázené výkladem. Tento výklad je samozřejmě v angličtině a pro pochopení látky je absolutně nezbytný, takže bez znalosti angličtiny se neobejdete. Dobrá zpráva pro ty, kdo angličtinou nevládnou úplně dokonale: Přišlo mi, že Boneh mluví velmi sorzumitelně a jednoduchou angličtinou, navíc jsou k dispozici titulky (anglické, u některých částí i další). Video lze streamovat (na výběr je mezi Flashem a HTML5) nebo stáhnout (ve formátu MP4). Rozsah je cca 3 hodiny týdně non-stop přehrávání.

3. Test z probírané látky. Test má obvykle 10 až 15 otázek, z nichž většina je ve formě „multiple-choice“ (zaškrtávání a, b, c, d), kde správná může být jedna nebo i více odpovědí; příjemné je, že skoro všechny otázky jsou na přemýšlení a aplikaci naučeného, jen výjimečně jde o definice a věty. Některé otázky mohou být otevřené, typicky jde o úlohy, kde se má něco spočítat. Na vyhotovení testu jsou standardně dva týdny od zadání, pokud se smíříte s 50% penalizací, lze úkol řešit až do konce kurzu. Jinak ale není doba testu omezena, můžete ho zpracovávat stejně dobře hodinu jako den. Počet pokusů je omezen na 4, počítá se nejlepší dosažené bodové ohodnocení.

4. Programovací úlohy jsou zadány k většině témat a jsou sice nepovinné, ale velmi doporučené – vesměs jsou formulovány tak, že na vstupu je šifrový text vytvořený algoritmem, ve kterém byla porušena některá ze zásad správného používání, a vy máte na základě této chyby vyluštit otevřený text. Řešit můžete v libovolném programovacím jazyku, nebo klidně i ručně, a vesměs jde o věci, které jde naprogramovat dost snadno – většina práce je s analýzou problému, ne s implementací ve zvoleném jazyku. Na vyřešení jsou opět dva týdny.

Po celou dobu kurzu je k dispozici diskusní fórum, kde lze probírat nejen látku kurzu („Nerozumím tomu a tomu“ nebo „Myslím si, že by to mohlo být i jinak“), ale v omezené míře dané kódem cti i samotnými testy a úkoly; zejména pokud se zaseknete na nějakém implementačním detailu, je dobré do diskuse nakouknout, pravděpodobně tam najdete něco, co vás nakopne správným směrem – třeba že při hledání kolizí je dobré vykašlat se na všechny ty úžasné pokročilé datové struktury, jako jsou hash tabulky nebo B-stromy, a spolehnout se radši na obyčejný quicksort…

Na konci kurzu je pak zadán závěrečný test, který má téměř stejnou strukturu i rozsah jako průběžné testy, akorát se týká celé probrané látky a jsou na něj jen dva pokusy.

Probíraná látka

Kurz se zabývá základy kryptologie, v šesti týdnech probírá následující témata:

1. Úvod do kryptologie (co to je, historický vývoj, používaná terminologie a značení), one-time pad, proudové šifry a útoky na ně, koncept perfektní a sémantické bezpečnosti.
2. Blokové šifry (DES, AES) a útoky na ně (hlavně útoky hrubou silou, ostatní jsou jen stručně zmíněny), koncept chosen plaintext security, šifrovací režimy (ECB, CBC, CTR).
3. Integrita zpráv (MAC funkce, padding), hashovací funkce, narozeninový paradox, časovací útoky.
4. Autentizované šifrování (spojení šifer a MAC, koncept chosen ciphertext security), útoky typu padding Oracle, odvozování klíčů, deterministické šifrování (umožňuje např. vyhledávat v šifrovaných datech, aniž by je server uměl dešifrovat), šifrovací režim XTS.
5. Výměna klíčů po otevřeném kanálu (Merkleho hádanky, Diffie-Hellman), šifrování s veřejným klíčem, základy teorie čísel (grupy, Fermatova a Eulerova věta, aritmetické operace v modulo N).
6. Šifrování s veřejným klíčem, RSA, ElGamal.

Struktura je vesměs taková, že na začátku Boneh nadhodí nějaký problém, který chceme vyřešit, ukáže naivní implementaci a důvody, proč není bezpečná, z toho se odrazí k definici bezpečnosti a návrhu, jak tedy problém řešit bezpečně. Případně opačným směrem, že ukáže bezpečnou implementaci a pak demonstruje, jak porušení jednotlivých předpokladů zlikviduje bezpečnost.

Testové otázky jsou pak často formulovány tak, že „máme algoritmus A, který splňuje vlastnost takové a takové bezpečnosti. Které z následujících algoritmů jsou také bezpečné?“ a následuje seznam algoritmů odvozených od A. Řada otázek je takových, že ze známých vstupních parametrů má student odvodit nějakou praktickou implementaci; hned v první sérii cvičení se například řešila obdoba klíčů na BluRay discích (každý přehrávač má svůj vlastní dešifrovací klíč; jakým způsobem zajistit, aby se při kompromitaci nějakého klíče mohl na nových discích tento klíč zakázat, ale přesto aby zůstala možnost přehrávání disku na ostatních nekompromitovaných zařízeních), v poslední sérii zase byla otázka, kterou jde krásně aplikovat na některé úlohy typu zero-knowledge (Alice a Bob chtějí vědět, jestli se nachází ve stejném státu, ale nechtějí, aby se ten druhý dozvěděl cokoliv jiného než „ano“ nebo „ne“). Už jenom proto je dobré se kurzu zúčastnit a testy dělat, i když vás třeba tolik nezajímá teorie nebo nemáte ambici získat „letter of accomplishment“ (doklad o úspěšném absolvování kurzu).

Programovací úlohy

Jak už jsem psal výše, programovací úlohy jsou nepovinné, ale doporučené. Když totiž vidíte, jak jednoduše jde vyřešit zdánlivě neřešitelný problém, začnete se hned jinak dívat na Bonehovu neustále opakovanou poučku, že nejen že by si člověk neměl navrhovat vlastní šifry, ale neměl by ani vytvářet svoje vlastní způsoby použití – naopak by se měl držet toho, že pokud to jen trochu jde, je třeba využívat známé a dobře ověřené knihovny jako OpenSSL.

Témata úloh byla:

1. Many time pad: Co udělá s bezpečností, pokud one-time-pad použijeme pro šifrování několika nezávislých otevřených textů. Na vstupu je jedenáct šifrových textů, o kterých víme jenom to, že byly zašifrovány pomocí XORu přes one-time-pad, a to všech jedenáct přes stejný one-time-pad. Výstupem má být text jednoho (pevně zadaného) z textů.

2. Slabý náhodný generátor: Máme posloupnost 9 náhodných čísel, která je výstupem slabého náhodného generátoru – údajně 56bitového. K dispozici je zdrojový kód generátoru (dva 28bitové lineární kongruenční generátory, jejichž výstupy se XORují), neznáme ovšem vnitřní stavy těchto generátorů. Úkolem je spočítat 10. vygenerované číslo. (Složitost je jen asi 2²⁸, ne 2⁵⁶, jak by člověk při použití 56bitového vnitřního stavu očekával.)

3. Hledání kolizí v hashi: Programátor použil pro vytváření hashe SHA256, ale řekl si, že přece nebude ukládat 256 bitů, ale pro dostatečnou bezpečnost mu stačí 50 bitů. S využitím narozeninového paradoxu mu máme ukázat, že se mýlí, tím, že vygenerujeme dva různé otevřené texty, které se hashují na stejnou hodnotu. (Složitost 2²⁵.)

4. Padding oracle: Máme webový server, který přijímá data šifrovaná pomocí AES v CBC režimu. Bohužel hacker zjistil, že se server chová jako padding oracle (různými chybovými kódy reaguje na různé chybové stavy při dešifrování), což mu umožnilo celý šifrovaný text dešifrovat. Máme k dispozici log požadavků, které na server posílal, a úkolem je dešifrovat stejný šifrový text, který dešifroval i hacker. (Na celý útok by bylo potřeba asi 256*délka požadavků, na dešifrování textu z logu stačí dokonce jen délka požadavků, což je samozřejmě mnohem méně než 2²⁵⁶ pokusů, které by vyžadoval správně použitý AES.)

5. Výpočet diskrétního logaritmu: Demonstruje využití meet-in-the-middle technik pro snížení výpočetní náročnosti – máme najít diskrétní logaritmus (najít exponent, na který když umocníme známý základ, dostaneme známý výsledek) v grupě řádu 2⁴⁰. Normálně by na to bylo třeba až 2⁴⁰ pokusů, ale s využitím techniky meet-in-the-middle si vystačíme jen s 2²⁰ pokusy. To je jeden z důvodů, proč pro Diffie-Hellmana potřebujeme delší klíče než pro symetrické šifry.

6. Faktorizace nevhodných RSA modulů: Pokud N=p*q, kde p a q jsou dostatečně velká prvočísla, tak faktorizace (ze známého N určit p a q) je výpočetně nezvládnutelným problémem (aspoň zatím). Pokud jsou však čísla p a q zvolena nešikovně, může být faktorizace mnohem jednodušší. Úloha to demonstruje na faktorizaci 1024bitového čísla, jehož faktory leží blízko u sebe a jsou tudíž snadno odhalitelné Fermatovou faktorizací.

Všechny úlohy jsou zadány tak, aby bylo vidět, že problém, který je neřešitelný*) hrubou silou, může být velmi snadno řešitelný s využitím slabin, které se „obyčejnému programátorovi“ jeví jako úplně neškodné, ale ve skutečnosti z obtížného problému dělají triviální. Třeba ta poslední úloha je v případě dobře zvoleného N dnešními prostředky neřešitelná, dokonce i při zapojení všech počítačů na světě; pro nevhodná N se ale ukáže, že výpočet nemusí trvat ani sekundu.

 

*) Myšleno neřešitelné v daných časových a výkonnostních mezích. Jistě není problém prolomit 56bitový kléč hrubou silou, soutěž DES Cracker to ukázala už před více než deseti lety, ale v domácích podmínkách s jedním počítačem to stále ještě není něco, co byste za odpoledne zvládli.

Budoucnost

V nejbližší budoucnosti, to jest zítra, začíná další běh tohoto kurzu. Těm, kdo se nezúčastnili, nebo i zúčastnili, ale časová náročnost jim neumožnila dokončit, vřele doporučuji. Registrace zde.

V průběhu příštího týdne by mělo proběhnout vyhodnocení výsledků a ti, kdo dosáhli aspoň 70 procent, by měli dostat potvrzení o tomto faktu. Doufám, že i já ho dostanu – 70 procent je docela snadných, dostal jsem je na první pokus ve všech týdnech kromě jednoho (autentizované šifrování jsem na první pokus nedokázal), ale pak jsem využil další volné pokusy a nakonec ve všech případech dosáhl sta procent, což může vypadat podezřele…

(Doplněno 16.6.: Vyhodnocení výsledků zde. Bohužel zatím jen nepodepsané, provozovatelům serveru Coursera se nepodařilo včas implementovat software pro digitální podpis, což u kurzu zaměřeného na kryptologii docela zamrzí…)

Pravděpodobně někdy na podzim by mělo být pokračování, Crypto II. Rozhodně si ho plánuji také zapsat, jestli to bude jen trochu podobné Crypto I, tak to bude stát za to. A to i v oblastech, které už znám (eliptické křivky, kvantová kryptografie).

Podobné příspěvky:

• Crypto-Class
• Securing Digital Democracy
• Vážná bezpečnostní chyba v BestCrypt Volume Encryption
• Sony Reader PRS-505 za 200 USD
• H2LRF v0.09

9 Responses to “Crypto-Class – vyhodnocení”

1. pepak napsal:

   25. 8. 2012 (21:02)

   Crypto II už má stránku online. Přednášky začnou 3. ledna, zaregistrovat se jde už teď.

2. pepak napsal:

   16. 6. 2012 (12:48)

   Vyhodnocení výsledků zde. Bohužel zatím jen nepodepsané, provozovatelům serveru Coursera se nepodařilo včas implementovat software pro digitální podpis, což u kurzu zaměřeného na kryptologii docela zamrzí…

3. pepak napsal:

   14. 6. 2012 (05:55)

   Kaco: Na PhD se mi to nezdá, kurz bych řadil spíš někam mezi bakaláře a magistra. Ale jako podpůrný materiál by to asi šlo.

4. Kaco napsal:

   14. 6. 2012 (01:21)

   Po prvych dnoch to vyzera, ze „dolezite je zucastnit sa“ 🙂

   Vyborne je, sa vsetky ucebne podklady daju stiahnut.

   Pri hladani dalsich podkladov (http://www.fi.muni.cz/usr/gruska/#resources) som zistil, ze prof. Gruska tento kurz odporuca studentom PhD http://www.fi.muni.cz/usr/gruska/#resources. U pana profesora som robil skusku pred 35+ rokmi :), uz vtedy to bol medzinarodne uznavany odbornik.

5. pepak napsal:

   12. 6. 2012 (18:38)

   Kaco: To je obtížné říct, záleží na tom, jak dobře jsi na tom s angličtinou, jak moc už toho z crypta, programování (pro programovací úlohy) a matematiky (5. a 6. týden) znáš atd. Já jsem tomu věnoval:

   * Prohlédnutí přednášek … cca 3 hodiny týdně.
   * Test po každém týdnu … cca hodinu.
   * Naprogramování úlohy … hodně různé, programování samotné bylo celkem rychlé, ale vymyslet, kudy do toho, občas dalo zabrat. Nebo naopak, vymyslet to bylo snadné, ale pak jsem se potýkal se záludnosti implementace GMP v Delphi. Ale za odpoledne se to vesměs dalo zvládnout.

   Ale podotýkám, že já už poměrně slušný crypto i matematický základ mám a angličtinu čtu jako češtinu a poslouchám skoro tak, takže jsem nepotřeboval žádné části přednášek projíždět víckrát.

6. Kaco napsal:

   12. 6. 2012 (18:21)

   Vdaka za inspiraciu!
   Vcera TO zacalo.
   Mam otazku: Zaujimalo by ma, kolko casu denne si celemu kurzu venoval v priemere denne. Uz som prihlaseny, ale zacinam mat uz na zaciatku pocit, ze to casovo nestiham

7. David napsal:

   11. 6. 2012 (12:13)

   Zapomněl jsem ještě link http://www.udacity.com/overview/Course/cs387/CourseRev/apr2012

8. David napsal:

   11. 6. 2012 (12:13)

   Přidávám se k doporučení, i když osobně jsem přes coursera.org dělal pouze machine learning. Zároveň, co se týče šifrování, je tu také ještě alternativa u „konkurenční“ udacity.com, kde je trochu jiný formát, založený na tom, že jsou jednotlivé lekce rozdělené na malá videa, která jsou prokládána častými otázkami a kurz samotný je projektově orientovaný.

9. abc napsal:

   11. 6. 2012 (09:49)

   +1