Kryptografické protokoly

Kryptografická primitiva (jako hashovací funkce, symetrická šifra, asymetrická šifra) jsou nástroje ke stavbě složitějších programů. Dávají nějaké záruky o svém fungování (například, šifru nejde prolomit) a na základě toho pak můžeme dokázat, že celý program dává nějaké záruky bezpečnosti.

Kryptografický protokol je konkrétní řešení nějakého problému týkajícího se bezpečné komunikace (utajené, odolné vůči podvodu). Záleží na situaci a na našem rozhodnutí, proti jakým útokům má být protokol odolný.

Demotivační cvičení: problém milionářů

Dva milionáři chtějí zjistit, kdo je bohatší. Měsíční výdělek každého z nich je celé číslo v rozsahu 0 a 109 dolarů.

Máme zaručit:

  1. nedovědí se nic víc o tom, kolik peněz vydělává ten druhý. Nestačí tedy napsat dvě částky na papír a porovnat.
  2. jeden i druhý milionář může podvádět. Protokol v takovém případě smí dát špatný výsledek (samozřejmě), ale nesmí odhalit nic navíc.
Protokol zatím navrhneme jen rámcově. Jakým způsobem ho někdo může narušit, a vůči jakým útokům má být odolný? Jak by se celá záležitost zjednodušila, kdyby oba milionáři měli společný důvěryhodný počítač, do kterého můžou tajně napsat každý svůj vstup?

1. Kontrolní součet

Program dostane na vstupu libovolně dlouhou zprávu a na výstup dá číslo omezené délky (kontrolní součet).

  1. Obvyklé drobné změny ve zprávě (vzniklé chybou při přenosu dat) se projeví změnou kontrolního součtu.
  2. Kontrolní součet jde spočítat velmi rychle, a v lineárním čase vzhledem k délce zprávy.

Cvičení 1a: kontrola vůči zpřeházení

Nemáme síťovou kartu a všechna data diktujeme telegrafistovi. Jeho nejčastějším překlepem je prohození dvou sousedních písmen. Jaký kontrolní součet tuhle chybu odhalí?

2. Hashovací funkce

Program dostane na vstupu libovolně dlouhou zprávu a na výstup dá číslo omezené délky (hash).

  1. Drobná změna ve zprávě se projeví zásadně na celém hashi. Podobné zprávy mají ve většině případů zásadně rozdílné hashe.
  2. Hash neříká nic o zprávě, ze které byl spočítán.
  3. Výpočet hashe trvá přiměřeně dlouho, a lineárně dlouho vzhledem k délce zprávy.

Cvičení 2a: lámání hesel

Operační systém ověřuje, jestli uživatel zadal správně heslo. Útočník má offline přístup k disku: může ho z počítače vytáhnout a přečíst všechna data. Útočník nemá být schopný odhalit hesla. Postupně přibývají další komplikace:

  1. Útočník si může doma připravit libovolně náročný výpočet a přinést si výsledek s sebou. Přístup k disku má pak jen jednou a krátce. Chceme, aby v takovém případě hesla neodhalil.
  2. Každý rok a půl se počítače zrychlí na dvojnásobek. Chceme, aby systém mohl jen s drobnými změnami být bezpečný i za deset let.

Cvičení 2b: vzdálené přihlášení

Server ověřuje, jestli uživatel zadal správně heslo. Útočník vidí všechny zprávy, ale nemůže je měnit. Protokol nesmí útočníkovi dovolit se přihlásit na server.

  1. Útočník si může zaznamenat všechno, co posílal uživatel, a totéž poslat serveru znovu (replay útok). Chceme, aby takové přihlášení nefungovalo.

Cvičení 2c: kámen, nůžky, papír

Uživatelé si chtějí po sítí náhodně vylosovat, kdo vyhrál. Síť je bezpečná, ale oba uživatelé můžou podvádět.

  1. Protokol může selhat, pokud uživatelé nespolupracují.
  2. Pokud protokol neselže, tak oba uživatelé musejí mít záruku, že výsledek je spravedlivý.

Cvičení 2d: anonymní dotazník

Studenti vyplňují dotazník ohledně výuky. Chceme zajistit, že každý ho vyplní jednou.

  1. Z našich záznamů nesmí jít zjistit, kdo odpovídal jak.
  2. Když program spouštíme, měl by obsahovat co nejmíň dat. Nechceme si ukládat přihlašovací údaje.

3. Symetrická šifra

Program A na vstupu dostane šifrovací klíč a libovolně dlouhou zprávu (plaintext) a dává libovolně dlouhý výstup (ciphertext). Program B na vstupu dostane šifrovací klíč a ciphertext, a na výstup dává původní zprávu (plaintext).

Obvyklé situace útoku:

  1. Programy A i B jsou útočníkovi dopodrobna známé. Bezpečnost nemůže být skrytá v programu, musí spočívat na volbě klíče.
  2. Útočník zachytí ciphertext, ale nezná klíč. Nesmí se dovědět nic o plaintextu.
  3. V programu je dočasně uložený klíč a útočník může požádat o zašifrování libovolných dat. Nesmí se dovědět nic o klíči.
Běžně používané šifry bývají vůči těmto útokům odolné.

Cvičení 3a: hashovací funkce pomocí šifry

Máme k dispozici program na symetrické šifrování a chceme vyrobit program na hashovací funkci. Dává naše řešení patřičné záruky? Jaké má nevýhody oproti skutečné hashovací funkci?

Cvičení 3b: šifra na jedno použití

Potřebujeme si zajistit šifrovanou komunikaci s ponorkou po celou dobu jejího provozu. Ponorce můžeme jednou bezpečně předat data, a to když vyplouvá z přístavu.

  1. Útočník má k dispozici neomezený výpočetní výkon.

Cvičení 3c: šifrování wi-fi

WEP je zastaralý a na několik způsobů prolomený protokol zabezpečení bezdrátových sítí. Zabezpečení se sdíleným klíčem spoléhá na to, že uživatelé znají klíč a útočník nikoli.

  1. Pokud uživatelé pošlou dvakrát úplně stejnou zprávu, útočník to nesmí poznat.

4. Asymetrická šifra

Program K vyrobí dvojici náhodných klíčů P (public), S (secret). Program A na vstupu dostane klíč P a libovolně dlouhý plaintext, a na výstup dává ciphertext. Program B na vstupu dostane klíč S a ciphertext, a na výstup dává plaintext.

Cvičení 4a: end-to-end šifrování

Uživatelé chtějí komunikovat v prostředí, kde útočník může kteroukoliv zprávu přečíst nebo změnit. Pokud útočník zprávu změní, protokol musí selhat a zprávu nedoručit. Pokud protokol neselže, útočník se nesmí dovědět skoro nic o obsahu zprávy.

  1. Jak takový protokol implementovat pomocí asymetrické šifry?
  2. Co se útočník o zprávě dozví nevyhnutelně?

Cvičení 4b: útok CRIME

Představme si následující protokol:

  1. Uživatel pošle serveru požadavek obsahující libovolný kód M.
  2. Server na konec kódu M připíše tajnou zprávu S, obojí zkomprimuje (jako obyčejný zip), pak zašifruje tajným klíčem a výsledek pošle zpět.
  3. Uživatel zná tajný klíč, takže přijatá data dešifruje, rozbalí zip a přečte si tajnou zprávu S.
Útočník může serveru poslat požadavek kolikrát chce a zpráva S je pořád stejná. Útočník nezná tajný klíč. Jak může odhalit zprávu S?

Cvičení 4c: symetrická šifra pomocí asymetrické

Máme k dispozici všechny tři programy na asymetrické šifrování a chceme vyrobit program na symetrické šifrování. Naše zadání to neumožňuje vyřešit. Kde je potíž?

Cvičení 4d: rychlejší asymetrické šifrování

Asymetrické šifry obvykle spočívají na vznešené matematice a jsou moc pomalé na zpracování velkých objemů dat. Jak navrhnout protokol, který zaručuje bezpečí asymetrické šifry a rychlost té symetrické?

5. Digitální podpis

Program K vyrobí dvojici náhodných klíčů P (public), S (secret). Program A na vstupu dostane klíč S a libovolně dlouhý plaintext, a na výstup dává ciphertext. Program B na vstupu dostane klíč P a ciphertext, a na výstup dává plaintext.

Cvičení 5a: podpis zprávy

Uživatelé se můžou jednou potkat a bezpečně si předat libovolná data. Později si chtějí poslat e-mail. Útočník může zprávu přečíst a změnit.

  1. Pokud útočník zprávu změní, protokol musí selhat.
  2. Digitální podpis vyžaduje vznešenou matematiku a je moc pomalý na zpracování celé zprávy.

Cvičení 5b: řetěz certifikátů

Chceme ověřit, že se připojujeme na správný webový server. Na celém světě jsou tisíce důvěryhodných advokátů, kteří se osobně setkají s majitelem serveru a vystaví mu certifikát.

  1. Advokáti přibývají jako houby po dešti. Jak v takovém prostředí průběžně označovat ty důvěryhodné?
  2. Advokátů a webů k ověření je přehršel. Pracovní zátěž se nesmí v systému soustředit na jedné osobě.
  3. Občas vystavíme omylem certifikát nedůvěryhodnému nebo neschopnému advokátovi a po nějaké době mu přestaneme důvěřovat.

Cvičení 5c: síť důvěry

Uživatel, kterého jsme doteď neznali, nám pošle e-mail. Chceme ověřit, že zprávu poslal opravdu on.

  1. Máme společné kamarády, se kterými se na takovou situaci můžeme předem připravit.
  2. Nemáme společné kamarády, ale někteří z mých a jeho kamarádů se mezi sebou znají.

Cvičení 5d: podpis fotografie

Fotoaparát v sobě může mít bezpečně uložené tajemství, a navenek dávat svoje (libovolné) ověřovací údaje. Chceme mít možnost ověřit, že fotografie byla vyrobená na daném fotoaparátu. Útočník má přístup k ověřovacím údajům, ale nezná tajemství.

Cvičení 5e: vodoznak

Fotoaparát v sobě má uložené tajemství, které je známé jen jeho výrobci. Vodoznak je strojově čitelný údaj nenápadně zabudovaný do každé fotografie, který obsahuje číslo fotoaparátu. Útočník musí mít jen malou šanci vodoznak smazat a nepoškodit přitom celý obraz.

Řešení: problém milionářů

Protokol může fungovat nějak takhle:

  1. Jeden milionář si vymyslí sadu milionu klíčů. Zná jen jediný klíč z téhle sady, ostatní jsou nahodilé nebo nesmyslné. Sadu klíčů předá druhému milionáři.
  2. Druhý milionář sepíše ke každému číslu od nuly do milionu odpověď mám víc nebo mám míň. Každou takovou odpověď zašifruje odpovídajícím klíčem ze sady. Šifrované odpovědi pošle zpátky.
  3. První milionář dešifruje jednu odpověď a ostatní zahodí. Potom tentýž protokol provedeme ještě jednou, opačným směrem.

Zbývá několik zásadních otázek:

  1. Jak by mohl první milionář podvádět a přečíst víc než jednu odpověď?
  2. Jak tenhle protokol implementovat pomocí asymetrické šifry?
  3. Jak může podvádět druhý milionář?