Úvod do protokolů

Celý smysl kryptografie je řešit problémy. (Vlastně je to celý smysl počítačů — na což mnoho lidí zapomíná). Kryptografie řeší problémy, které zahrnují utajenost, autentičnost, celistvost a nepoctivé lidi. Můžete se naučit všechno o kryptografických algoritmech a technikách, ale toto jsou jenom akademické problémy, dokud nebudou řešit problém. Kvůli tomu se nejdříve podíváme na protokoly.

Protokol je posloupnost kroků, který zahrnuje dva nebo více účastníků a slouží ke splnění úkolu. To je důležitá definice.

"Posloupnost kroků" znamená, že protokol je sled od začátku do konce. Každý krok musí být proveden postupně a před dokončením předchozího kroku nelze provést žádný další krok.

"Zahrnující dva nebo více účastníků" znamená, že jsou nutné minimálně dvě osoby (nebo více osob) k dokončení protokolu, jedna osoba nemůže udělat protokol. Jedna osoba sama o sobě může uskutečnit sérii kroků vedoucích ke splnění úkolu, jako například upéct koláč, ale to není protokol. Musí existovat někdo, kdo koláč sní, abychom měli protokol.

Konečně "slouží ke splnění úkolu" znamená, že protokol musí něčeho dosáhnout. Cokoliv, co vypadá jako protokol, ale neslouží ke splnění nějakého úkolu, není protokol, ale ztráta času.

Protokoly mají ještě další vlastnosti:

  • Kdokoliv účastný na protokolu musí znát protokol a všechny jeho kroky, jak za sebou následují.

  • Kdokoliv účastný na protokolu s ním musí souhlasit.

  • Protokol musí být jednoznačný, každý krok musí být dobře definován a nesmí existovat možnost špatného pochopení.

  • Protokol musí být kompletní, musí být popsána konkrétní činnost pro každou možnou situaci.

Protokoly jsou obvykle konstruovány jako série kroků. Vykonávání protokolu jede lineárně přes všechny kroky, pokud není pokyn k rozvětvení do jiného kroku. Každý krok zahrnuje minimálně dvě věci, buď výpočet u některého ze dvou anebo více účastníků anebo poslání zprávy mezi účastníky.

Kryptografický protokol je protokol, který používá kryptografii. Účastníci mohou být jak přátelé, kteří jeden druhému důvěřují implicitně, tak i protivníci, kteří jeden druhému nedůvěřují, že mají na počítači nastavený správný čas dne. Kryptografický protokol zahrnuje nějaký kryptografický algoritmus, ale obecně cíl protokolu je něco za prostým tajemstvím. Strany účastnící se protokolu mohou chtít sdílet části svých tajemství, aby vypočítali hodnotu, společně vygenerovali náhodnou sekvenci, přesvědčili se navzájem o své identitě, nebo současně podepsat smlouvu. Smyslem použití kryptografie v protokolu je zabránit nebo odhalit odposlouchávání a podvádění. Pokud jste je nikdy neviděli protokoly dříve, protokoly radikálně změní vaše představy o tom, co vzájemně nedůvěřivé strany mohou dosáhnout prostřednictvím počítačové sítě. Obecně platí, že toto lze uvést jako:

Nemělo by být možné udělat více nebo se naučit více, než co je specifikované v protokolu.

Tohle je mnohem těžší, než to vypadá. V několika následujících kapitolách probereme některé protokoly. V některých protokolech je možné, aby jeden z účastníků podváděl druhé. V jiných protokolech je možné odposlechem podvrhnout protokol respektivě se dozvědět tajné informace. Některé protokoly selžou, protože to nebyli návrháři dostatečně důkladní ve svých definicích požadavků. Ostatní selhávají, protože jejich designéři nebyli ve svých analýzách dostatečně důkladní. Stejně jako u algoritmů, je mnohem snazší prokázat nebezpečnost protokolu než jeho bezpečnost.

Účel protokolu

V každodenním životě existují neformální protokoly téměř pro všechno: objednávání zboží po telefonu, hraní pokeru, hlasování ve volbách. Nikdo moc nepřemýšlí o těchto protokolech; postupem času se vyvíjely, každý ví, jak je používat a fungují poměrně dobře.

V dnešní době se stále více lidských interakcí odehrává přes internet namísto tváří v tvář. Počítače k tomu potřebují formální protokoly, aby mohly dělat stejné věci, které lidé dělají bez přemýšlení. Pokud jste se přestěhovali z jednoho státu do dalšího a našli jste volební místnost, která vypadá úplně jinak než ta, na kterou jste byli zvyklí, se můžete snadno přizpůsobit. Počítače nejsou zdaleka tak flexibilní.

Mnoho protokolů tváří v tvář se spoléhá na přítomnost lidí, aby byla zajištěna spravedlnost a bezpečnost. Poslali byste cizímu člověku hromadu peněz, aby pro vás nakoupil potraviny? Hráli byste s někým poker, kdybyste ho neviděli míchat a rozdávat? Poslal byste vládě svůj tajný hlasovací lístek bez jistoty anonymity?

Je naivní předpokládat, že lidé na počítačových sítích jsou poctiví. Je naivní předpokládat, že manažeři počítačových sítí jsou poctiví. Je dokonce naivní předpokládat, že konstruktéři počítačových sítí jsou poctiví. Většina je, ale těch pár nepoctivých může napáchat hodně škody. Formalizací protokolů můžeme zkoumat způsoby, jak je mohou nepoctivé strany rozvrátit. Pak můžeme vyvinout protokoly, které jsou imunní vůči tomuto podvratu.

Kromě formalizace chování protokoly abstrahují proces splnění úkolu od mechanismu, kterým je úkol splněn. Komunikační protokol je stejný, ať už je implementován na PC nebo mobilním telefonu. Můžeme prozkoumat protokol, aniž bychom se zabředli do detailů implementace. Když jsme přesvědčeni, že máme dobrý protokol, můžeme jej implementovat do všeho, od počítačů přes telefony až po inteligentní toustovače.

Herci

Abych pomohl demonstrovat protokoly, požádal jsem o pomoc několik lidí (viz tabulka). Alice a Bob jsou první dva. Budou provádět všechny obecné protokoly pro dvě osoby. Alice zpravidla zahajuje všechny protokoly a Bob odpovídá. Pokud protokol vyžaduje třetí nebo čtvrtou osobu, Carol a Dave budou tyto role vykonávat. Další herci budou hrát specializované vedlejší role; budou představeny později.

herec jeho funkce

Alice

První účastník ve všech protokolech.

Bob

Druhý účastník ve všech protokolech.

Carol

Účastník třístranných a čtyřstranných protokolů.

Dave

Účastník čtyřstranných protokolů.

Eve

Kdo tajně poslouchá.

Mallory

Škodlivý aktivní útočník.

Trent

Důvěryhodný arbitr (rozhodce).

Walter

Správce; bude hlídat Alici a Boba v některých protokolech.

Peggy

Osvědčovatel

Victor

Ověřovatel

Arbitrované (rozhodované) protokoly

Rozhodce (arbitrator)je nezúčastněná třetí strana, které důvěřujete k dokončení protokolu (viz obrázek 2.1a). Nezaujatý znamená, že rozhodce nemá žádný osobní zájem na protokolu a žádnou zvláštní oddanost žádné ze zúčastněných stran. Důvěryhodný znamená, že všichni lidé zapojení do protokolu přijímají to, co říká, jako pravdivé, co dělá jako správné, a že svou část protokolu doplní. Rozhodci mohou pomoci dokončit protokoly mezi dvěma vzájemně nedůvěřivými stranami.

align-center
Figure 1. rozhodovaný protokol

V reálném světě jsou právníci často využíváni jako rozhodci. Například Alice prodává auto neznámému Bobovi. Bob chce zaplatit šekem, ale Alice nemá jak zjistit, zda je šek krytý. Alice chce, aby byl šek proplacen, než předá titul (auto) Bobovi. Bob, který Alici nevěří o nic víc než ona jemu, nechce předat šek, aniž by získal titul (auto).

Najděme právníka, kterému oba důvěřují. S jeho pomocí mohou Alice a Bob použít následující protokol, aby zajistili, že ani jeden druhého nepodvede:

  1. Alice uděluje titul (auto) advokátovi.

  2. Bob dá šek Alici.

  3. Alice uloží šek.

  4. Po uplynutí stanovené doby, než bude šek proplacen, právník předá titul Bobovi. Pokud šek ve stanovené lhůtě neproběhne, Alice to prokáže advokátovi a ten vrátí vlastnické právo Alici.

V tomto protokolu Alice věří právníkovi, že Bobovi titul neposkytne, dokud nebude šek proplacen, a že jí ho vrátí, pokud šek nebude zúčtován. Bob věří právníkovi, že bude mít titul, dokud nebude šek proplacen, a že mu ho dá, jakmile se tak stane. Advokátovi je jedno, jestli šek projde. Svou část protokolu udělá v obou případech, protože v obou případech dostane zaplaceno.

V tomto příkladu hraje právník roli escrow agenta. Právníci také působí jako rozhodci v případech závěti a někdy i pro jednání o smlouvě. Různé burzy fungují jako rozhodci mezi kupujícími a prodávajícími. Bankéři také rozhodují o protokolech. Bob může použít ověřený šek k nákupu auta od Alice:

  1. Bob vypíše šek a dá ho bance.

  2. Poté, co odložíte dostatek Bobových peněz na pokrytí šeku, banka potvrdí šek a vrátí ho Bobovi.

  3. Alice předá titul Bobovi a Bob předá ověřený šek Alici.

  4. Alice uloží šek.

Tento protokol funguje, protože Alice důvěřuje certifikaci bankéře. Alice důvěřuje bance, že pro ni bude držet Bobovy peníze, a ne že je použije k financování nejistých operací s nemovitostmi v zemích zamořených komáry.

Dalším rozhodcem je notář. Když Bob obdrží od Alice notářsky ověřený dokument, je přesvědčen, že Alice dokument podepsala dobrovolně a vlastní rukou. Notář může v případě potřeby vystoupit u soudu a tuto skutečnost potvrdit. Koncept arbitra je starý jako společnost. Vždy existovali lidé – vládci, kněží a tak dále – kteří měli pravomoc jednat spravedlivě. Rozhodci mají v naší společnosti určitou společenskou roli a postavení; zrada důvěry veřejnosti by to ohrozila. Právníci, kteří hrají hry s vázanými účty, například čelí téměř jistému vyloučení. Tento obrázek důvěry v reálném světě vždy neexistuje, ale je ideálem. Tento ideál lze přenést do počítačového světa, ale s počítačovými arbitry existuje několik problémů:

  • Je snazší najít neutrální třetí stranu a důvěřovat jí, pokud víte, kdo to je, a vidíte jeho tvář. Dvě strany, které jsou vůči sobě podezřívavé, budou pravděpodobně také podezřívavé vůči anonymnímu arbitrovi někde jinde v síti.

  • Počítačová síť musí nést náklady na údržbu arbitra. Všichni víme, co si právníci účtují; kdo chce nést takovou režii sítě?

  • Každému rozhodovacímu protokolu je vlastní zpoždění.

  • Rozhodce se musí zabývat každou transakcí; je úzkým hrdlem v rozsáhlých implementacích jakéhokoli protokolu. Zvýšení počtu rozhodců v implementaci může tento problém zmírnit, ale zvyšuje náklady.

  • Vzhledem k tomu, že každý v síti musí rozhodci důvěřovat, představuje zranitelný bod pro každého, kdo se snaží síť rozvrátit.

I přesto mají arbitři stále svou roli. V protokolech používajících důvěryhodného arbitra bude roli hrát Trent.

Posuzované protokoly

Vzhledem k vysokým nákladům na najímání rozhodců lze rozhodovací protokoly rozdělit na dva nižší podprotokoly úrovně. Jedním z nich je subprotokol bez arbitráže, který se provádí pokaždé, když strany chtějí dokončit protokol. Druhý je arbitrážní subprotokol, který se provádí pouze výjimečně při okolnosti, když dojde ke sporu. Tento speciální typ rozhodce se nazývá rozhodčí. Rozhodčí je také nezaujatá a důvěryhodná třetí strana. Na rozdíl od arbitra není přímo zapojený do každého protokolu. Rozhodčí je přivolán pouze k určení, zda byl protokol proveden spravedlivě.

Soudci jsou profesionálními rozhodčími. Na rozdíl od notáře je soudce přibrán pouze v případě, že existuje spor. Alice a Bob mohou uzavřít smlouvu bez soudce. Soudce smlouvu nikdy nevidí dokud jeden z nich nepotáhne druhého k soudu.

align-center
Figure 2. posuzovaný protokol

Tento protokol o podpisu smlouvy lze formalizovat takto:

Nearbitrovaný subprotokol (prováděný pokaždé):

  • Alice a Bob vyjednají podmínky smlouvy.

  • Alice podepíše smlouvu.

  • Bob podepíše smlouvu.

    Arbitrovaný subprotokol (provádí se pouze v případě sporu):

  • Alice a Bob předstoupí před soudce.

  • Alice předkládá své důkazy.

  • Bob předkládá své důkazy.

  • Soudce rozhoduje o důkazech.

Rozdíl mezi rozhodčím a rozhodcem (jak je použit v tomto výkladu) je v tom, že rozhodčí není vždy nezbytně nutný. Ve sporu je povolán rozhodčí, aby rozhodl. Pokud neexistuje žádný spor, rozhodčí je zbytečný.

Existují příslušné počítačové protokoly. Tyto protokoly spoléhají na to, že strany budou čestné; ale pokud někdo někoho podezřívá z podvádění, existuje soubor dat, takže důvěryhodná třetí strana (rozhodčí) může určit, zda někdo podváděl. V dobrém rozhodovacím protokolu by rozhodčí mohl také určit podvodníka. Namísto toho, aby se zabránilo podvádění, posuzované protokoly odhalují podvádění. Nevyhnutelnost detekce působí preventivně a odrazuje od podvádění.

Samovynucovací protokoly

Samovynucovací protokol je nejlepší typ protokolu. Samotný protokol zaručuje poctivost. K uskutečnění protokolu není nutný žádný rozhodce. K vyřešení sporů není potřeba žádný rozhodčí. Protokol je konstruován tak, aby nemohlo dojít k žádným sporům. Pokud se o to jedna ze stran pokusí podvádět, druhá strana okamžitě to okamžitě detekuje a protokol se zastaví. Kdykoliv by podvádějící strana doufala, že podvádí, tak se to nestane.

V nejlepším ze všech možných světů by byl každý protokol samovynucovací. Bohužel neexistuje samovynucovací protokol pro každou situaci.

align-center
Figure 3. samovynucovací protokol

Útoky proti protokolům

Kryptografické útoky mohou být namířeny proti kryptografickým algoritmům používaným v protokolech, proti kryptografickým technikám používaným k implementaci algoritmů a protokolů nebo proti samotným protokolům. Protože tato část pojednává o protokolech, budu předpokládat, že kryptografické algoritmy a techniky jsou bezpečné. Budu zkoumat pouze útoky proti protokolům.

Lidé mohou vyzkoušet různé způsoby útoku na protokol. Někdo, kdo není zapojen do protokolu, může odposlouchávat část nebo celý protokol. Tomu se říká pasivní útok, protože útočník neovlivňuje protokol. Jediné, co může udělat, je dodržovat protokol a pokusit se získat informace. Tento druh útoku odpovídá útoku založenému pouze na šifrovaném textu, jak je popsáno v části Kryptografie a kryptoanalýza - úvod. Vzhledem k tomu, že pasivní útoky je obtížné odhalit, protokoly se snaží pasivním útokům spíše předcházet, než je detekovat. V těchto protokolech bude roli odposlechu hrát Eva.

Případně by se útočník mohl pokusit změnit protokol ve svůj vlastní prospěch. Mohl předstírat, že je někdo jiný, zavádět nové zprávy do protokolu, mazat existující zprávy, nahrazovat jednu zprávu jinou, přehrávat staré zprávy, přerušovat komunikační kanál nebo měnit uložené informace v počítači. Tyto útoky se nazývají aktivní útoky, protože vyžadují aktivní zásah.

Forma těchto útoků závisí na síti. Pasivní útočníci se snaží získat informace o stranách zapojených do protokolu. Shromažďují zprávy procházející mezi různými stranami a pokoušejí se je šifrovat. Aktivní útoky na druhou stranu mohou mít mnohem rozmanitější cíle. Útočník by mohl mít zájem o získání informací, snížení výkonu systému, poškození existujících informací nebo získání neoprávněného přístupu ke zdrojům.

Aktivní útoky jsou mnohem závažnější, zejména v protokolech, ve kterých si různé strany navzájem nemusí nutně důvěřovat. Útočník nemusí být úplný outsider. Mohl by být legitimním uživatelem systému. Může být správcem systému. Mohlo by dokonce existovat mnoho aktivních útočníků, kteří spolupracují. Zde si roli zlomyslného aktivního útočníka zahraje Mallory.

Je také možné, že útočníkem může být jedna ze stran zapojených do protokolu. Při protokolu může lhát nebo protokol nedodržovat vůbec. Tento typ útočníka se nazývá cheater. Pasivní podvodníci postupují podle protokolu, ale snaží se získat více informací, než je protokol zamýšlí.

Aktivní podvodníci narušují probíhající protokol ve snaze podvádět. Je velmi obtížné udržet zabezpečení protokolu, pokud většina zúčastněných stran jsou aktivní podvodníci, ale někdy je možné, že legitimní strany zjistí, že aktivní podvádění probíhá. Protokoly by samozřejmě měly být zabezpečené proti pasivnímu podvádění.

Komunikace s použitím symetrické šifry

Jak spolu dvě strany bezpečně komunikují? Svou komunikaci samozřejmě šifrují. Kompletní protokol je složitější. Podívejme se, co se musí stát, aby Alice poslala zašifrovanou zprávu Bobovi.

  1. Alice a Bob se dohodnou na kryptosystému.

  2. Alice a Bob se dohodnou na klíči.

  3. Alice vezme svou textovou zprávu a zašifruje ji pomocí šifrovacího algoritmu a klíče. Tím se vytvoří šifrovaná textová zpráva.

  4. Alice pošle šifrovanou zprávu Bobovi.

  5. Bob dešifruje šifrovanou zprávu pomocí stejného algoritmu a klíče a přečte ji.

Co se může Eva, sedící mezi Alicí a Bobem, naučit z naslouchání tomuto protokolu? Pokud slyší pouze přenos v kroku (4), musí se pokusit šifrovaný text analyzovat. Tento pasivní útok je útok pouze na šifrovaný text; máme algoritmy, které jsou odolné (pokud víme) vůči jakékoli výpočetní síle, kterou by Eve mohla reálně přinést k řešení problému.

Eva však není hloupá. Také chce poslouchat kroky (1) a (2). Pak by znala algoritmus a klíč – stejně dobře jako Bob. Když se zpráva dostane přes komunikační kanál v kroku (4), vše, co musí udělat, je dešifrovat ji sama.

Dobrý kryptosystém je takový, ve kterém je veškerá bezpečnost závislá na znalosti klíče a žádná není závislá na znalosti algoritmu. To je důvod, proč je správa klíčů v kryptografii tak důležitá. Se symetrickým algoritmem mohou Alice a Bob provést krok (1) veřejně, ale krok (2) musí provést tajně. Klíč musí zůstat tajný před protokolem, během něj a po něm – pokud zpráva musí zůstat tajná – jinak zpráva již nebude bezpečná. (Kryptografie s veřejným klíčem řeší tento problém jiným způsobem a bude probrána v další části.)

Mallory, aktivní útočník, mohl dělat pár dalších věcí. Mohl by se pokusit přerušit komunikační cestu v kroku (4), čímž by zajistil, že Alice nebude moci s Bobem vůbec mluvit. Mallory mohl také zachytit Aliciny zprávy a nahradit je svými. Pokud by znal klíč (zachycením komunikace v kroku (2) nebo prolomením kryptosystému), mohl zašifrovat svou vlastní zprávu a poslat ji Bobovi místo zachycené zprávy. Bob by neměl jak vědět, že zpráva nepřišla od Alice. Pokud Mallory neznal klíč, mohl vytvořit pouze zprávu o umístění, která by se dešifrovala na blábol. Bob, který si myslel, že zpráva přišla od Alice, by mohl dojít k závěru, že buď síť, nebo Alice mají nějaké vážné problémy.

A co Alice? Co může udělat, aby narušila protokol? Může dát kopii klíče Evě. Teď může Eva číst, co říká Bob. Může přetisknout jeho slova v The New York Times. Ačkoli je to vážné, není to problém s protokolem. Alici nic nebrání v tom, aby Evě poskytla kopii otevřeného textu kdykoli během protokolu. Bob samozřejmě také mohl dělat cokoliv, co Alice. Tento protokol předpokládá, že Alice a Bob si navzájem důvěřují.

Stručně řečeno, symetrické kryptosystémy mají následující problémy:

  • Klíče musí být distribuovány tajně. Jsou stejně cenné jako všechny zprávy, které šifrují, protože znalost klíče dává znalost všech zpráv. Pro šifrovací systémy, které pokrývají celý svět, to může být skličující úkol. Kurýři často nosí klíče do svých destinací.

  • Pokud dojde ke kompromitaci klíče (ukradení, uhádnutí, vydírání, podplacení atd.), může Eva dešifrovat veškerý přenos zpráv zašifrovaný tímto klíčem. Může také předstírat, že je jednou ze stran a produkovat falešné zprávy, aby oklamala druhou stranu.

  • Za předpokladu, že je pro každý pár uživatelů v síti použit samostatný klíč, celkový počet klíčů se rychle zvyšuje s rostoucím počtem uživatelů. Síť \$n\$ uživatelů vyžaduje \$frac{n*(n - 1)}{2}\$ klíčů. Například 10 uživatelů vyžaduje 45 různých klíčů, aby spolu mohli komunikovat, a 100 uživatelů vyžaduje 4950 klíčů. Tento problém lze minimalizovat udržováním malého počtu uživatelů, ale to není vždy možné.

Jednosměrná funkce

Pojem jednosměrné funkce je ústředním prvkem kryptografie s veřejným klíčem. I když se nejedná o protokoly samy o sobě, jednosměrné funkce jsou základním stavebním kamenem většiny protokolů probíraných v této knize.

Jednosměrné funkce se poměrně snadno počítají, ale podstatně hůře se dají obrátit (invertovat). Nemůžeme nalézt inverzní funkci. To znamená, že vzhledem k \$x\$ je snadné vypočítat \$f(x)\$, ale vzhledem k \$f(x)\$ je obtížné vypočítat \$x\$. V této souvislosti je „tvrdé“ definováno jako něco jako: Vypočítat \$x\$ z \$f(x)\$ by trvalo miliony let, i kdyby k problému byly přiřazeny všechny počítače na světě.

Rozbití talíře je dobrým příkladem jednosměrné funkce. Je snadné rozbít talíř na tisíc malých kousků. Není však snadné poskládat všechny tyto malé kousky zpět a slepit z nich talíř.

To zní dobře, ale je to hodně kouře a zrcadel. Pokud jsme rigidní matematici, nemáme žádný důkaz, že jednosměrné funkce existují, ani žádný skutečný důkaz, že je lze sestavit. Přesto mnoho funkcí vypadá a voní jednosměrně: Dokážeme je efektivně vypočítat a zatím neznáme žádný snadný způsob, jak je obrátit. Například v konečném poli je snadné vypočítat \$x^2\$, ale \$sqrt{x}\$ je mnohem těžší. Po zbytek této části budu předstírat, že existují jednosměrné funkce.

K čemu jsou tedy jednosměrné funkce dobré? Nemůžeme je použít pro šifrování tak, jak jsou. Zpráva zašifrovaná jednosměrnou funkcí není užitečná; nikdo to nedokázal dešifrovat. (Cvičení: Napište zprávu na talíř, rozbijte talíř na malé kousky a pak dejte kousky příteli. Požádejte svého přítele, aby si zprávu přečetl. Všimněte si, jak na něj udělal dojem jednosměrná funkce.) Pro kryptografii s veřejným klíčem potřebujeme něco jiného (ačkoli existují kryptografické aplikace pro jednosměrné funkce.

Jednosměrná funkce s pastičkou je speciální typ jednosměrné funkce s tajnou pastí. Je snadné ji počítat v jednom směru a obtížné počítat ve druhém směru. Ale pokud znáte tajemství, můžete snadno vypočítat funkci v opačném směru. To znamená, že je snadné vypočítat \$f(x)\$ z daného \$x\$ a obtížné vypočítat \$x\$ z daného \$f(x)\$. Existuje však nějaká tajná informace, \$y\$, taková, že vzhledem k \$f(x)\$ a \$y\$ je snadné vypočítat \$x\$.

Rozložení hodinek je dobrým příkladem jednosměrné funkce s pastičkou. Hodinky je snadné rozebrat na stovky nepatrných kousků. Je velmi obtížné poskládat tyto drobné kousky zpět do fungujících hodinek. S tajnými informacemi – návodem k sestavení hodinek – je však mnohem snazší dát hodinky zpět dohromady.

Jednosměrná hashovací funkce

Jednosměrná hašovací funkce má mnoho názvů: kompresní funkce, kontrakční funkce, výtah zprávy (message digest), otisk prstu (fingerprint), kryptografický kontrolní součet, kontrola integrity zprávy (MIC) a kód detekce manipulace (MDC). Ať už to nazýváte jakkoli, je to ústřední prvek moderní kryptografie. Jednosměrné hašovací funkce jsou dalším stavebním kamenem mnoha protokolů.

Hashovací funkce se v informatice používají již dlouhou dobu. Hashovací funkce je funkce, matematická nebo jiná, která přebírá vstupní řetězec proměnné délky (nazývaný předobraz) a převádí jej na výstupní řetězec s pevnou délkou (obecně menší) (tzv. hash hodnota). Jednoduchá hashovací funkce by byla funkce, která vezme předobraz a vrátí bajt skládající se z XOR všech vstupních bajtů.

Jde o to, otisknout předobraz: vytvořit hodnotu, která udává, zda kandidátský předobraz bude pravděpodobně stejný jako skutečný předobraz. Protože hašovací funkce jsou obvykle mnoho ku jedné, nemůžeme je použít k tomu, abychom s jistotou určili, že jsou dva řetězce stejné, ale můžeme je použít k získání přiměřené jistoty přesnosti.

Jednosměrná hašovací funkce je hašovací funkce, která funguje jedním směrem: Je snadné vypočítat hašovací hodnotu z předobrazu, ale je těžké vygenerovat předobraz, který hašuje na konkrétní hodnotu. Výše zmíněná hašovací funkce není jednosměrná: Vzhledem k určité hodnotě bajtu je triviální generovat řetězec bajtů, jehož XOR je tato hodnota. S jednosměrnou hashovací funkcí to udělat nemůžete. Dobrá jednosměrná hašovací funkce je také bez kolizí: Je těžké vygenerovat dva předobrazy se stejnou hašovací hodnotou.

Hašovací funkce je veřejná; v procesu není žádné tajemství. Zabezpečení jednosměrné hashovací funkce je její jednosměrnost. Výstup není nijak rozpoznatelným způsobem závislý na vstupu. Jediná bitová změna v předběžném obrazu změní v průměru polovinu bitů v hašovací hodnotě. Vzhledem k hodnotě hash je výpočetně neproveditelné najít předobraz, který se na tuto hodnotu hashuje.

Berte to jako způsob snímání souborů otisků prstů. Pokud chcete ověřit, že někdo má konkrétní soubor (který máte také vy), ale nechcete, aby vám jej posílal, zeptejte se ho na hodnotu hash. Pokud vám pošle správnou hodnotu hash, pak je téměř jisté, že daný soubor má. To je užitečné zejména při finančních transakcích, kde nechcete, aby se výběr 100 Kč změnil na výběr 1000 Kč někde v síti. Normálně byste použili jednosměrnou hashovací funkci bez klíče, aby si kdokoli mohl hash ověřit. Pokud chcete, aby hash mohl ověřit pouze příjemce, přečtěte si další část.

Kódy pro ověření zpráv

Autentizační kód zprávy (MAC), známý také jako autentizační kód dat (DAC), je jednosměrná hašovací funkce s přidáním tajného klíče. Hodnota hash je funkcí předobrazu i klíče. Teorie je úplně stejná jako hashovací funkce, až na to, že hodnotu hash může ověřit pouze někdo, kdo má klíč. MAC můžete vytvořit z hašovací funkce nebo blokovacího šifrovacího algoritmu; existují také vyhrazené MAC.

Komunikace s použitím šifry s veřejným klíčem

Představte si symetrický algoritmus jako trezor. Klíčová je kombinace. Někdo s touto kombinací může trezor otevřít, vložit do něj dokument a zase ho zavřít. Někdo jiný s touto kombinací může otevřít sejf a vytáhnout dokument. Každý, kdo tuto kombinaci nemá, je nucen naučit se otvírat trezory jinak (třeba autogenem).

V roce 1976 Whitfield Diffie a Martin Hellman toto paradigma kryptografie navždy změnili. (NSA tvrdila, že o tomto konceptu věděla již v roce 1966, ale nepředložila žádný důkaz.) Popsali kryptografii s veřejným klíčem. Používali dva různé klíče – jeden veřejný a druhý soukromý. Je výpočetně obtížné odvodit soukromý klíč od veřejného klíče. Každý, kdo má veřejný klíč, může zprávu zašifrovat, ale ne dešifrovat. Zprávu může dešifrovat pouze osoba se soukromým klíčem. Je to, jako by někdo proměnil kryptografický trezor na poštovní schránku. Vkládání pošty do poštovní schránky je obdobou šifrování pomocí veřejného klíče; může to udělat každý. Stačí otevřít slot a vložit jej. Získávání pošty z poštovní schránky je analogické s dešifrováním pomocí soukromého klíče. Obecně je to těžké; potřebujete svařovací hořáky. Pokud však máte tajemství (fyzický klíč k poštovní schránce), je snadné dostat poštu z poštovní schránky.

Matematicky je tento proces založen na dříve diskutovaných jednosměrných funkcích padacích dveří. Šifrování je snadný směr. Pokyny pro šifrování jsou veřejný klíč; kdokoli může zašifrovat zprávu. Dešifrování je tvrdý směr. Je to natolik těžké, že lidé s počítači Cray a tisíce (dokonce miliony) let nedokázali zprávu dešifrovat bez tajemství. Tajemství, nebo padací dveře, je soukromý klíč. S tímto tajemstvím je dešifrování stejně snadné jako šifrování. Takto může Alice poslat zprávu Bobovi pomocí kryptografie s veřejným klíčem:

  1. Alice a Bob se dohodnou na kryptosystému s veřejným klíčem.

  2. Bob pošle Alici svůj veřejný klíč.

  3. Alice zašifruje svou zprávu pomocí Bobova veřejného klíče a pošle ji Bobovi.

  4. Bob dešifruje Alicinu zprávu pomocí svého soukromého klíče.

Všimněte si, jak kryptografie veřejného klíče řeší problém správy klíčů u symetrických kryptosystémů. Předtím se Alice a Bob museli tajně dohodnout na klíči. Alice si mohla vybrat jednu náhodně, ale stejně ji musela dostat k Bobovi. Mohla by mu to předat někdy předem, ale to vyžaduje předvídavost. Mohla by mu to poslat bezpečným kurýrem, ale to chce čas. Šifrování s veřejným klíčem to usnadňuje. Bez předchozího domluvy může Alice poslat Bobovi zabezpečenou zprávu. Eva, která naslouchá celé výměně, má Bobův veřejný klíč a zprávu v tomto klíči zašifrované, ale nemůže obnovit Bobův soukromý klíč ani zprávu.

Častěji se síť uživatelů dohodne na kryptosystému s veřejným klíčem. Každý uživatel má svůj vlastní veřejný klíč a soukromý klíč a všechny veřejné klíče jsou někde zveřejněny v databázi. Nyní je protokol ještě jednodušší:

  1. Alice získá Bobův veřejný klíč z databáze.

  2. Alice zašifruje svou zprávu pomocí Bobova veřejného klíče a pošle ji Bobovi.

  3. Bob poté Alicinu zprávu dešifruje pomocí svého soukromého klíče.

V prvním protokolu musel Bob poslat Alici svůj veřejný klíč, než mu mohla poslat zprávu. The druhý protokol je spíše jako tradiční pošta. Bob není zapojen do protokolu, dokud sám nebude chtít přečíst jeho zprávu.

Hybridní kryptosystémy

První algoritmy veřejného klíče se staly veřejnými ve stejnou dobu, kdy se o DES diskutovalo jako o navrhovaném standardu. To vedlo k určité stranické politice v kryptografické komunitě. Jak to popsal Diffie [494]:

Nadšení, které kryptosystémy s veřejným klíčem vyvolaly v populárním a vědeckém tisku, však neodpovídalo odpovídajícímu přijetí v kryptografickém establishmentu. Ve stejném roce, kdy byla objevena kryptografie s veřejným klíčem, Národní bezpečnostní agentura (NSA) navrhla konvenční kryptografický systém navržený společností International Business Machines (IBM) jako federální standard pro šifrování dat (DES). Marty Hellman a já (Bruce Schneier) jsme kritizovali návrh na základě toho, že jeho klíč je příliš malý, ale výrobci se připravovali na podporu navrhované normy a naši kritiku mnozí považovali za pokus narušit proces tvorby norem ve prospěch nás samotných. Kryptografie s veřejným klíčem byla napadena jak v prodejní literatuře [1125], tak v technických novinách [849,1159], spíše jako by šlo o konkurenční produkt než o nedávný výzkumný objev. To však NSA neodradilo od nároku na svůj podíl na úvěru. Její ředitel, slovy Encyclopedia Britannica [1461], poukázal na to, že „dvouklíčová kryptografie byla v agentuře objevena o deset let dříve“, ačkoli žádný důkaz pro toto tvrzení nebyl nikdy veřejně nabídnut.

V reálném světě nejsou algoritmy veřejného klíče náhradou za symetrické algoritmy. Nejsou používány k šifrování zpráv; používají se k šifrování klíčů. Důvody jsou dva:

  1. Algoritmy veřejného klíče jsou pomalé. Symetrické algoritmy jsou obecně nejméně 1000krát rychlejší než algoritmy s veřejným klíčem. Ano, počítače jsou stále rychlejší a rychlejší a za 15 let budou počítače schopny provádět kryptografii s veřejným klíčem rychlostí srovnatelnou s dnešní symetrickou kryptografií. Ale požadavky na šířku pásma se také zvyšují a vždy bude potřeba šifrovat data rychleji, než to zvládne kryptografie s veřejným klíčem.

  2. Kryptosystémy s veřejným klíčem jsou zranitelné vůči vybraným útokům v otevřeném textu. Jestliže \$C = E(P)\$, když \$P\$ je jeden otevřený text ze sady \$n\$ možných otevřených textů, pak musí kryptoanalytik pouze zašifrovat všech \$n\$ možných otevřených textů a porovnat výsledky s \$C\$ (nezapomeňte, že šifrovací klíč je veřejný). Nebude schopen tímto způsobem obnovit dešifrovací klíč, ale bude schopen určit \$P\$.

Zvolený útok v prostém textu může být zvláště účinný, pokud existuje relativně málo možných zašifrovaných zpráv. Pokud by například P byla částka v dolarech nižší než 1 000 000 $, tento útok by fungoval; kryptoanalytik zkouší všechny milionové možné částky v dolarech. (Problém řeší pravděpodobnostní šifrování) I když P není tak dobře definované, může být tento útok velmi účinný. Užitečná informace může být pouhá informace, že šifrovaný text neodpovídá konkrétnímu otevřenému textu. Symetrické kryptosystémy nejsou tímto útokem zranitelné, protože kryptoanalytik nemůže provádět zkušební šifrování s neznámým klíčem.

Ve většině praktických implementací se k zabezpečení a distribuci klíčů relace používá kryptografie veřejného klíče; tyto klíče relace se používají se symetrickými algoritmy k zabezpečení provozu zpráv [879]. Někdy se tomu říká hybridní kryptosystém.

  1. Bob pošle Alici svůj veřejný klíč.

  2. Alice vygeneruje náhodný klíč relace \$K\$, zašifruje jej pomocí Bobova veřejného klíče a odešle ho Bobovi \$E_B(K)\$.

  3. Bob dešifruje Alicinu zprávu pomocí svého soukromého klíče, aby obnovil klíč relace. \$D_B(E_B(K))=K\$

  4. Oba šifrují svou komunikaci pomocí stejného klíče relace.

Použití kryptografie veřejného klíče pro distribuci klíčů řeší velmi důležitý problém správy klíčů. U symetrické kryptografie klíč pro šifrování dat sedí, dokud není použit. Pokud to Eve někdy dostane do rukou, dokáže dešifrovat zprávy zašifrované pomocí něj. U předchozího protokolu je klíč relace vytvořen, když je potřeba k šifrování komunikace, a je zničen, když už není potřeba. To výrazně snižuje riziko ohrožení klíče relace. Soukromý klíč je samozřejmě zranitelný vůči kompromitaci, ale je vystaven menšímu riziku, protože je použit pouze jednou za komunikaci k zašifrování klíče relace.

Merkleovy hádanky

Ralph Merkle vynalezl první konstrukci kryptografie s veřejným klíčem. V roce 1974 se zapsal do kurzu počítačové bezpečnosti na Kalifornské univerzitě v Berkeley, který vyučoval Lance Hoffman. Téma jeho semestrální práce, předložené na začátku semestru, se zabývalo problémem „bezpečné komunikace přes nezabezpečené kanály“ [1064]. Hoffman nechápal Merkleův návrh a Merkle nakonec kurz upustil. Pokračoval v práci na problému, přestože se mu stále nedařilo porozumět jeho výsledkům.

Merkleova technika byla založena na „hádankách“, které bylo snazší vyřešit pro odesílatele a příjemce než pro odposlecha. Zde je návod, jak Alice pošle zašifrovanou zprávu Bobovi, aniž by si s ním musela nejprve vyměnit klíč.

  1. Bob vygeneruje \$2^20\$ neboli asi milion zpráv ve tvaru: „Toto je hádanka číslo \$x\$. Toto je číslo tajného klíče \$y\$,“ kde \$x\$ je náhodné číslo a \$y\$ je náhodný tajný klíč. \$x\$ i \$y\$ se pro každou zprávu liší. Pomocí symetrického algoritmu zašifruje každou zprávu jiným 20bitovým klíčem a všechny pošle Alici.

  2. Alice náhodně vybere jednu zprávu a provede útok hrubou silou, aby obnovila otevřený text. To je velké, ale ne nemožné, množství práce.

  3. Alice zašifruje svou tajnou zprávu pomocí klíče, který získala, a nějakého symetrického algoritmu a pošle ji Bobovi spolu s \$x\$.

  4. Bob ví, který tajný klíč \$y\$ zašifruje ve zprávě \$x\$, takže může zprávu dešifrovat.

Eva může tento systém prolomit, ale musí udělat mnohem víc práce než Alice nebo Bob. Aby obnovila zprávu v kroku (3), musí provést útok hrubou silou proti každé z Bobových \$2^20\$ zpráv v kroku (1); tento útok má složitost \$2^40\$. Hodnoty x Evě také nepomohou; byli přiřazeni náhodně v kroku (1). Obecně platí, že Eva musí vynaložit přibližně druhou mocninu úsilí, které vynakládá Alice. Tato výhoda \$n\$ až \$n^2\$ je podle kryptografických standardů malá, ale za určitých okolností může stačit. Pokud Alice a Bob mohou vyzkoušet deset tisíc klíčů za sekundu, každý jim zabere minutu, než provedou své kroky, a další minutu, než sdělí hádanky od Boba Alici po pomalé lince. Kdyby měla Eve srovnatelné počítačové vybavení, trvalo by jí asi rok, než by systém rozbila. Jiné algoritmy je ještě těžší prolomit.

Digitální podpis

Ruční podpisy se odedávna používají jako důkaz autorství nebo alespoň souhlasu s obsahem dokumentu. Co je na podpisu tak přesvědčivé [1392]?

  1. Podpis je autentický. Podpis přesvědčí příjemce dokumentu, že podepisující dokument podepsal záměrně.

  2. Podpis je nezfalšovatelný. Podpis je důkazem, že podepisující a nikdo jiný dokument úmyslně podepsal.

  3. Podpis není znovu použitelný. Podpis je součástí dokumentu; bezohledná osoba nemůže přesunout podpis do jiného dokumentu.

  4. Podepsaný dokument je neměnný. Poté, co je dokument podepsán, nelze jej měnit.

  5. Podpis nelze odmítnout. Podpis a dokument jsou fyzické věci. Podepsaný nemůže později tvrdit, že to nepodepsal.

Ve skutečnosti žádné z těchto tvrzení o podpisech není zcela pravdivé. Podpisy mohou být padělány, podpisy mohou být zvednuty z jednoho kusu papíru a přesunuty na jiný a dokumenty mohou být po podpisu pozměněny. Jsme však ochotni s těmito problémy žít kvůli obtížnosti podvádění a riziku odhalení. Rádi bychom něco takového dělali na počítačích, ale jsou tu problémy. Za prvé, kopírování počítačových souborů je triviální. I kdyby bylo obtížné zfalšovat podpis osoby (například grafický obrázek písemného podpisu), bylo by snadné vyjmout a vložit platný podpis z jednoho dokumentu do druhého. Pouhá přítomnost takového podpisu nic neznamená. Zadruhé, počítačové soubory se po podepsání snadno upravují, aniž by zanechávaly stopy po úpravě.

Podepisování dokumentů pomocí symetrických kryptosystémů a arbitra

Alice chce podepsat digitální zprávu a poslat ji Bobovi. S pomocí Trenta a symetrického kryptosystému to dokáže.

Trent je mocný, důvěryhodný arbitr. Dokáže komunikovat s Alicí i Bobem (a se všemi ostatními, kteří mohou chtít podepsat digitální dokument). Sdílí tajný klíč \$K_A\$ s Alicí a jiný tajný klíč \$K_B\$ s Bobem. Tyto klíče byly vytvořeny dlouho před zahájením protokolu a lze je opakovaně použít pro vícenásobné podepisování.

  1. Alice zašifruje svou zprávu Bobovi pomocí \$K_A\$ a pošle ji Trentovi.

  2. Trent dešifruje zprávu pomocí \$K_A\$ .

  3. Trent vezme dešifrovanou zprávu a prohlášení, že tuto zprávu obdržel od Alice, a zašifruje celý balíček pomocí \$K_B\$.

  4. Trent pošle zašifrovaný balíček Bobovi.

  5. Bob dešifruje svazek pomocí \$K_B\$. Nyní si může přečíst zprávu i Trentovo potvrzení, které mu Alice poslala.

Jak Trent ví, že zpráva je od Alice a ne od nějakého podvodníka? Odvozuje to ze šifrování zprávy. Protože pouze on a Alice sdílejí svůj tajný klíč, pouze Alice mohla pomocí něj šifrovat zprávu. Je to tak dobré jako papírový podpis? Podívejme se na vlastnosti, které chceme:

  1. Tento podpis je autentický. Trent je důvěryhodný arbitr a Trent ví, že zpráva přišla od Alice. Trentova certifikace slouží Bobovi jako důkaz.

  2. Tento podpis je nezfalšovatelný. Pouze Alice (a Trent, ale všichni mu věří) zná \$K_A\$, takže pouze Alice mohla poslat Trentovi zprávu zašifrovanou pomocí \$K_A\$. Pokud by se někdo pokusil vydávat za Alici, Trent by si to okamžitě uvědomil v kroku (2) a nepotvrdil by její pravost.

  3. Tento podpis nelze znovu použít. Kdyby se Bob pokusil vzít Trentův certifikát a připojit ho k jiné zprávě, Alice by plakala odporně. Rozhodce (může to být Trent nebo to může být úplně jiný rozhodce s přístupem ke stejným informacím) požádá Boba, aby vytvořil zprávu i Alicinu zašifrovanou zprávu. Rozhodce pak zašifroval zprávu pomocí \$K_A\$ a zjistil, že se neshoduje se zašifrovanou zprávou, kterou mu dal Bob. Bob samozřejmě nemohl vytvořit zašifrovanou zprávu, která by se shodovala, protože nezná \$K_A\$.

  4. Podepsaný dokument je neměnný. Kdyby se Bob pokusil změnit dokument po obdržení, Trent by dokázal prokázat nečestnou hru přesně stejným způsobem, jaký byl právě popsán.

  5. Podpis nelze odmítnout. I když Alice později tvrdí, že zprávu nikdy neposlala, Trentova certifikace říká něco jiného. Pamatujte, že Trentovi všichni důvěřují; co říká, je pravda.

Pokud chce Bob ukázat Carol dokument podepsaný Alicí, nemůže jí prozradit svůj tajný klíč. Musí znovu projít Trentem:

  1. Bob vezme zprávu a Trentovo prohlášení, že zpráva přišla od Alice, zašifruje je pomocí \$K_B\$ a pošle je zpět Trentovi.

  2. Trent dešifruje svazek pomocí \$K_B\$.

  3. Trent zkontroluje svou databázi a potvrdí, že původní zpráva přišla od Alice.

  4. Trent znovu zašifruje balíček pomocí tajného klíče, který sdílí s Carol, \$K_C\$ , a pošle ho Carol.

  5. Carol dešifruje svazek pomocí \$K_C\$ . Nyní si může přečíst zprávu i Trentovo potvrzení, které jí Alice poslala.

Tyto protokoly fungují, ale pro Trenta jsou časově náročné. Musí trávit své dny dešifrováním a šifrováním zpráv a fungovat jako prostředník mezi každou dvojicí lidí, kteří si chtějí posílat podepsané dokumenty. Musí vést databázi zpráv (i když se tomu lze vyhnout zasláním kopie zašifrované zprávy odesílatele). Je úzkým hrdlem v jakémkoli komunikačním systému, i když je to bezduchý softwarový program.

Ještě těžší je vytvořit a udržovat někoho, jako je Trent, někoho, komu všichni v síti důvěřují. Trent musí být neomylný; pokud udělá byť jen jednu chybu z milionu podpisů, nikdo mu nebude věřit. Trent musí být v naprostém bezpečí. Pokud by se jeho databáze tajných klíčů dostala ven nebo kdyby se někomu podařilo upravit jeho programování, podpisy všech by byly úplně k ničemu. Mohou se objevit falešné dokumenty, které byly údajně podepsány před lety. Výsledkem by byl chaos. Vlády by se zhroutily. Zavládla by anarchie. Teoreticky to může fungovat, ale v praxi to příliš nefunguje.

Stromy digitálního podpisu

Ralph Merkle navrhl schéma digitálního podpisu založené na kryptografii s tajným klíčem, které produkovalo nekonečné množství jednorázových podpisů pomocí stromové struktury [1067,1068]. Základní myšlenkou tohoto schématu je umístit kořen stromu do nějakého veřejného souboru, a tím jej ověřit. Kořen podepíše jednu zprávu a ověří její poduzly ve stromu. Každý z těchto uzlů podepisuje jednu zprávu a ověřuje její poduzly a tak dále.

Podepisování dokumentů pomocí kryptografie s veřejným klíčem

Existují algoritmy veřejného klíče, které lze použít pro digitální podpisy. V některých algoritmech – příkladem je RSA lze pro šifrování použít veřejný nebo soukromý klíč. Zašifrujte dokument pomocí svého soukromého klíče a máte zabezpečený digitální podpis. V ostatních případech – příkladem je DSA (viz oddíl 20.1) – existuje samostatný algoritmus pro digitální podpisy, který nelze použít pro šifrování. Tuto myšlenku poprvé vymysleli Diffie a Hellman [496] a dále ji rozšířili a rozvedli v dalších textech [1282,1328,1024,1283,426]. Viz [1099] pro dobrý přehled pole.

Základní protokol je jednoduchý:

  1. Alice zašifruje dokument svým soukromým klíčem, čímž dokument podepíše.

  2. Alice pošle podepsaný dokument Bobovi.

  3. Bob dešifruje dokument Aliciným veřejným klíčem, čímž ověří podpis.

Tento protokol je mnohem lepší než předchozí. Trent není potřeba k podepisování ani ověřování podpisů. (Je potřeba, aby potvrdil, že Alicein veřejný klíč je skutečně její veřejný klíč.) Strany ani nepotřebují Trenta k řešení sporů: Pokud Bob nemůže provést krok (3), pak ví, že podpis není platný.

Tento protokol také splňuje vlastnosti, které hledáme:

  1. Podpis je autentický; když Bob ověří zprávu pomocí veřejného klíče Alice, ví, že ji podepsala.

  2. Podpis je nezfalšovatelný; pouze Alice zná její soukromý klíč. 3. Podpis nelze znovu použít; podpis je funkcí dokumentu a nelze jej přenést na žádný jiný dokument.

  3. Podepsaný dokument je neměnný; pokud dojde k jakékoli změně dokumentu, podpis již nelze ověřit na veřejnosti Alice klíč.

  4. Podpis nelze odmítnout. Bob nepotřebuje pomoc Alice, aby ověřil její podpis.

Podepisování dokumentů a časových razítek

Ve skutečnosti může Bob za určitých okolností Alici podvést. Může znovu použít dokument a podpis společně. To není problém, pokud Alice podepsala smlouvu, ale může být velmi vzrušující, pokud Alice podepsala digitální šek. Řekněme, že Alice pošle Bobovi podepsaný digitální šek na 100$. Bob vezme šek do banky, která ověří podpis a přesune peníze z jednoho účtu na druhý. Bob, který je bezohledná postava, si uloží kopii digitálního šeku. Následující týden jej znovu odnese do banky (nebo možná do jiné banky). Banka ověří podpis a přesune peníze z jednoho účtu na druhý. Pokud Alice nikdy nevyrovná svou šekovou knížku, Bob to může udržovat roky. V důsledku toho digitální podpisy často obsahují časová razítka. Datum a čas podpisu jsou připojeny ke zprávě a podepsány spolu se zbytkem zprávy. Banka ukládá toto časové razítko do databáze. Nyní, když se Bob podruhé pokusí proplatit Aliciin šek, banka zkontroluje časové razítko ve své databázi. Protože banka již proplatila šek od Alice se stejným časovým razítkem, banka zavolá policii. Bob poté stráví 15 let ve vězení Leavenworth čtením kryptografických protokolů.

Podepisování dokumentů pomocí kryptografie s veřejným klíčem a jednosměrných hashovacích funkcí

V praktických implementacích jsou algoritmy veřejného klíče často příliš neefektivní při podepisování dlouhých dokumentů. Pro úsporu času jsou protokoly digitálního podpisu často implementovány s jednosměrnými hašovacími funkcemi. Místo podpisu dokumentu Alice podepíše hash dokumentu. V tomto protokolu jsou předem dohodnuty jak jednosměrná hašovací funkce, tak algoritmus digitálního podpisu.

  1. Alice vytvoří jednosměrný hash dokumentu.

  2. Alice zašifruje hash svým soukromým klíčem, čímž dokument podepíše.

  3. Alice pošle dokument a podepsaný hash Bobovi.

  4. Bob vytvoří jednosměrný hash dokumentu, který poslala Alice. Poté pomocí algoritmu digitálního podpisu dešifruje podepsaný hash pomocí veřejného klíče Alice. Pokud se podepsaný hash shoduje s hashem, který Bob vygeneroval, je podpis platný.

Rychlost se drasticky zvyšuje, a protože šance, že dva různé dokumenty mají stejný 160bitový hash, jsou pouze \$1:2^160\$, kdokoli může bezpečně ztotožnit podpis hashe s podpisem dokumentu. Pokud by byla použita nejednosměrná hašovací funkce, bylo by snadné vytvořit více dokumentů, které by byly hašovány na stejnou hodnotu, takže každý, kdo podepíše konkrétní dokument, bude podveden k podepsání velkého množství dokumentů.

Tento protokol má další výhody. Za prvé, podpis lze uchovávat odděleně od dokumentu. Za druhé, požadavky příjemce na úložiště dokumentu a podpisu jsou mnohem menší. Archivní systém může tento typ protokolu použít k ověření existence dokumentů, aniž by ukládal jejich obsah. Centrální databáze by mohla ukládat pouze hashe souborů. Nemusíme vidět soubory vůbec; uživatelé odešlou své hash do databáze a databáze označí odeslání a uloží je. Pokud v budoucnu dojde k nějaké neshodě o tom, kdo a kdy vytvořil dokument, databáze by to mohla vyřešit nalezením hashe ve svých souborech. Tento systém má rozsáhlé důsledky týkající se soukromí: Alice by mohla mít na dokument autorské právo, ale přesto dokument uchovávala v tajnosti. Pouze pokud by chtěla prokázat svá autorská práva, musela by dokument zveřejnit.

Algoritmy a terminologie

Existuje mnoho algoritmů digitálního podpisu. Všechny z nich jsou algoritmy s veřejným klíčem s tajnými informacemi pro podepisování dokumentů a veřejnými informacemi pro ověřování podpisů. Někdy se proces podepisování nazývá šifrování pomocí soukromého klíče a proces ověřování se nazývá dešifrování pomocí veřejného klíče. To je zavádějící a platí to pouze pro jeden algoritmus, RSA. A různé algoritmy mají různé implementace. Například jednosměrné hašovací funkce a časová razítka někdy přidávají další kroky k procesu podepisování a ověřování. Mnoho algoritmů lze použít pro digitální podpisy, ale ne pro šifrování.

Obecně budu odkazovat na procesy podepisování a ověřování bez jakýchkoliv podrobností o použitých algoritmech. Podepsání zprávy soukromým klíčem K je:

\$S_K(M)\$

a ověření podpisu pomocí odpovídajícího veřejného klíče je:

\$V_K(M)\$

Bitový řetězec připojený k dokumentu při podpisu (v předchozím příkladu jednosměrný hash dokumentu zašifrovaného soukromým klíčem) se bude nazývat digitální podpis nebo jen podpis. Celý protokol, kterým je příjemce zprávy přesvědčen o identitě odesílatele a integritě zprávy, se nazývá autentizace.

Více podpisů

Jak by mohli Alice a Bob podepsat stejný digitální dokument? Bez jednosměrných hashovacích funkcí existují dvě možnosti. Jedním z nich je, že Alice a Bob podepisují samostatné kopie samotného dokumentu. Výsledná zpráva by byla dvakrát větší než původní dokument. Druhým je, že Alice nejprve podepíše dokument a poté Bob podepíše Alicin podpis. To funguje, ale je nemožné ověřit podpis Alice, aniž byste zároveň ověřili Bobův podpis.

S jednosměrnými hašovacími funkcemi je více podpisů snadné:

  1. Alice podepíše hash dokumentu.

  2. Bob podepíše hash dokumentu.

  3. Bob pošle svůj podpis Alici.

  4. Alice pošle dokument, svůj podpis a Bobův podpis Carol.

  5. Carol ověřuje podpis Alice i Bobův podpis.

Alice a Bob mohou dělat kroky (1) a (2) buď paralelně, nebo v sérii. V kroku (5) může Carol ověřit jeden podpis, aniž by musela ověřovat druhý.

Nepopiratelnost a digitální podpisy

Alice může podvádět s digitálními podpisy a nedá se s tím nic udělat. Může podepsat dokument a později tvrdit, že to neudělala. za prvé, dokument normálně podepíše. Poté si anonymně zveřejnit soukromý klíč, pohodlně jej ztratí na veřejném místě nebo jen předstírá, že dělá obojí jeden. Alice pak tvrdí, že její podpis byl kompromitován a že ostatní ho používají a předstírají, že jsou ona. Distancuje se od podpisu dokumentu a dalších ostatní, které podepsala pomocí tohoto soukromého klíče. Tomu se říká odmítnutí. Časová razítka mohou omezit účinky tohoto druhu podvádění, ale Alice může vždy tvrdí, že její klíč byl vyzrazen dříve. Pokud Alice načasuje věci dobře, může podepsat dokument a poté úspěšně tvrdit, že to neudělala. To je důvod, proč tam se tolik mluví o soukromých klíčích uložených v modulech odolných proti neoprávněné manipulaci – takže Alice se k ní nemůže dostat a zneužít ji. I když s tímto možným zneužíváním nelze nic dělat, lze podniknout kroky zaručit, že staré podpisy nebudou znehodnoceny akcemi provedenými v rámci sporu nováčci. (Například Alice mohla „ztratit“ svůj klíč, aby nezaplatila Bobovi za to nevyžádané auto, které jí včera prodal a při tom zneplatnil její banku Řešením je, aby její měl příjemce podepsaného dokumentu časové razítko [453].

Obecný protokol je uveden v [28]:

  1. Alice podepíše zprávu.

  2. Alice vygeneruje hlavičku obsahující nějaké identifikační informace.Zřetězí hlavičku s podepsanou zprávou, podepíše ji a pošle do Trentovi.

  3. Trent ověří vnější podpis a potvrdí identifikaci informace. K Alicině podepsané zprávě a identifikačním údajům přidám časové razítko. Pak to všechno podepíše a pošle oběma Alici i Bobovi.

  4. Bob ověří Trentův podpis, identifikační údaje a podpis Alice.

  5. Alice ověří zprávu, kterou Trent poslal Bobovi. Pokud nevznikla zpráva, promluví rychle. Další schéma používá Trent po faktu [209]. Po obdržení podepsaného může Bob poslat kopii Trentovi k ověření. Trent může potvrdit platnost podpisu Alice.

Aplikace digitálních podpisů

Jednou z prvních navrhovaných aplikací digitálních podpisů bylo usnadnit ověřování smlouvy o zákazu jaderných zkoušek. Spojené státy a Sovětský svaz (kdo si pamatuje Sovětský svaz?) si vzájemně dovolili umístit seismometry na půdu toho druhého, aby monitorovaly jaderné testy. Problém byl v tom, že se každá země potřebovala ujistit, že hostitelská země nemanipuluje s údaji z monitorovacích národních seismometrů. Současně se hostitelský národ potřeboval ujistit, že monitor odesílá pouze specifické informace potřebné pro monitorování. První problém mohou vyřešit konvenční autentizační techniky, ale pouze digitální podpisy vyřešit oba problémy. Hostitelský stát může číst data ze seismometru, ale ne je měnit a monitorovací národ ví, že s údaji nebylo manipulováno.

Digitální podpis se zašifrováním

Kombinací digitálních podpisů a kryptografie s veřejným klíčem můžeme vyvinout protokol, který kombinuje bezpečnost šifrování s pravostí digitálních podpisů. Vzpomeňte si na dopis od vaší maminky: Podpis poskytuje důkaz o autorství a obálka poskytuje soukromí.

  1. Alice podepíše zprávu svým soukromým klíčem.

    \$S_A(M)\$

  2. Alice zašifruje podepsanou zprávu Bobovým veřejným klíčem a pošle ji Bobovi.

    \$E_B(S_A(M))\$

  3. Bob dešifruje zprávu svým soukromým klíčem.

    \$D_B(E_B(S_A(M)))=S_A(M)\$

  4. Bob ověří pomocí veřejného klíče Alice a obnoví zprávu.

    \$V_A(S_A(M)) = M\$

Podepisování před šifrováním se zdá přirozené. Když Alice napíše dopis, podepíše ho a pak ho vloží obálky. Pokud by vložila dopis do obálky nepodepsaný a pak obálku podepsala, pak Bob by se mohl obávat, že byl dopis skrytě nahrazen. Kdyby Bob ukázal Carol dopis od Alice a obálku, Carol by mohla obvinit Boba, že lhal o tom, který dopis přišel v jaké obálce.

I v elektronické korespondenci je podepisování před šifrováním obezřetnou praxí. Nejen je to bezpečnější – protivník nemůže ze zašifrované zprávy odebrat podpis a přidat svůj vlastní – existují však právní úvahy. Pokud podepisující text, který má být podepsán, není viditelný pro podepisujícího při podpisu, pak může mít podpis malou právní sílu. A existují kryptoanalytické útoky proti této technice s RSA podpisy (signaturami).

Není důvod, proč by Alice musela používat stejný pár veřejný/soukromý klíčů pro šifrování a pro podepisování. Může mít dva páry klíčů: jeden pro šifrování a druhý pro podpisy. Separace má jenom výhody: může předat svůj šifrovací klíč policii, aniž by ji ohrozila podpis, lze jeden klíč uložit do úschovy, aniž by to ovlivnilo druhý, a klíče mohou mají různé velikosti a mohou vypršet v různou dobu.

S tímto protokolem by se samozřejmě měla používat časová razítka, aby se zabránilo opětovnému použití zpráv. Časová razítka také mohou chránit před dalšími potenciálními nástrahami, jak je to popsáno níže.

Opětovné odeslání zprávy jako potvrzení

Uvažujme implementaci tohoto protokolu s doplňkovou funkcí potvrzovacích zpráv. Kdykoli Bob obdrží zprávu, vrátí ji jako potvrzení o přijetí.

  1. Alice podepíše zprávu svým soukromým klíčem, zašifruje ji Bobovým veřejným klíčem a odešle k Bobovi.

    \$E_B(S_A(M))\$

  2. Bob dešifruje zprávu svým soukromým klíčem a ověří podpis pomocí Alice veřejný klíč, čímž ověří, že Alice zprávu podepsala, a zprávu obnoví.

    \$V_A(D_B(E_B(S_A(M)))) = M\$

  3. Bob podepíše zprávu svým soukromým klíčem, zašifruje ji Aliciným veřejným klíčem a odešle zpět k Alici. \$E_A(S_B(M))\$

  4. Alice dešifruje zprávu svým soukromým klíčem a ověří podpis pomocí Bobova veřejného klíče. Pokud je výsledná zpráva stejná jako ta, kterou poslala Bobovi, ví, že Bob přijal zprávu přesně.

Pokud je pro šifrování i ověřování digitálního podpisu použit stejný algoritmus, je možný útok [506]. V těchto případech je operace digitálního podpisu opakem operace šifrování: \$V_X=E_X\$ a \$S_X=D_X\$.

Předpokládejme, že Mallory je legitimní uživatel systému s vlastním veřejným a soukromým klíčem. Teď pojďme a sledujme, jak čte Bobovu poštu. Nejprve nahraje Alicinu zprávu Bobovi v kroku (1). Potom o něco později pošle tu samou zprávu Bobovi a bude tvrdit, že přišla od něj (Mallory). Bob si myslí je legitimní zpráva je od Malloryho, takže zprávu dešifruje svým soukromým klíčem a poté to zkusí ověřit Malloryho podpis dešifrováním Malloryho veřejným klíčem. Výsledná zpráva, což je čistý blábol, je:

\$E_M(D_B(E_B(D_A(M))))=E_M(D_A(M))\$

A tak Bob pokračuje v protokolu a posílá Mallorymu potvrzení:

\$E_M(D_B(E_M(D_A(M))))\$

Vše, co Mallory musí udělat, je dešifrovat zprávu svým soukromým klíčem a zašifrovat ji Bobovým veřejným klíčem, znovu jej dešifrujte svým soukromým klíčem a zašifrujte jej veřejným klíčem Alice. Voilà! Mallory má zpávu M.

Není nerozumné si představit, že Bob může Mallorymu automaticky odesílat potvrzení. Tento protokol může být například zabudován do jeho komunikačního softwaru a automaticky odesílat potvrzení. A je to právě tato ochota uznat příjem nesmyslů, která vytváří bezpečnostní problém. Pokud by Bob zkontrolovat zprávu, že je srozumitlná, před odesláním potvrzení , mohl se tomuto bezpečnostnímu problému vyhnout.

Existuje ještě vylepšení tohoto útoku, která Mallorymu umožňují poslat Bobovi jinou zprávu než je ta, kterou odposlechnul. Nikdy nepodepisujte svévolné zprávy od jiných lidí ani svévolně nedešifrujte zprávy a nepředávejte tyto výsledky dalším lidem.

Zmaření opakovaného útoku

Právě popsaný útok funguje, protože operace šifrování je stejná jako operace ověření podpisu a operace dešifrování je stejná jako operace podpisu. Bezpečný protokol by pro šifrování a digitální podpisy používal i trochu jinou operaci. Použitím různých klíčů pro každou operaci řeší problém, stejně tak použití různých algoritmů pro každou z nich; stejně tak to řeší časová razítka, která odlišují příchozí a odchozí zprávu; a také to řeší digitální podpisy s jednosměrnými hašovacími funkcemi.

Obecně je tedy následující protokol bezpečný, když se používá algoritmus veřejného klíče:

  1. Alice podepíše zprávu.

  2. Alice zašifruje zprávu a podpis Bobovým veřejným klíčem (pomocí jiného šifrovací algoritmus než pro podpis) a odešle jej Bobovi.

  3. Bob dešifruje zprávu svým soukromým klíčem.

  4. Bob ověřuje podpis Alice.

Útoky proti kryptografii s veřejným klíčem

Ve všech těchto šifrovacích protokolech s veřejným klíčem jsem přehlédli, jak Alice získává Bobův veřejný klíč. Nejjednodušší způsob, jak získat něčí veřejný klíč, je z nějaké zabezpečené databáze. Databáze má být veřejná, takže kdokoli může získat veřejný klíč kohokoli jiného. Databáze musí být také chráněna tak, aby do ní mohl zapisovat jenom Trent; jinak by Mallory mohl nahradit Bobův veřejný klíč jakýmkoli jiným veřejným klíčem. Poté, co by se to Mallorymu podařilo, Bob by již nemohl číst zprávy adresované jemu, ale Mallory ano.

I když jsou veřejné klíče uloženy v zabezpečené databázi, stále může Mallory jeden klíč nahradit druhým během přenosu. Abychom tomu zabránili, Trent může podepsat každý veřejný klíč svým vlastním soukromým klíčem. Trent, je-li používán tímto způsobem, je často známý jako Key Certification Authority nebo Key Distribution Centrum (KDC). V praktických implementacích KDC podepisuje složenou zprávu skládající se z jméno uživatele, jeho veřejného klíče a dalších důležitých informací o uživateli. Tato podepsaná složená zpráva je uložena v databázi KDC. Když Alice získá Bobův klíč, ověří jeho podpis pomocí podpisu KDC, aby se ujistila o platnosti klíče.

V konečném důsledku to Mallorymu nic neznemožní, jenon ztíží. Alice musí mít někde uložený veřejný klíč KDC. Mallory může nahradit tento veřejný klíč KDC svým vlastním veřejným klíčem, poškodit databázi a nahradit platné klíče jeho vlastními klíči (vše je podepsané jeho soukromým klíčem, jako by byl KDC), a má je v hrsti. Ale i papírové podpisy mohou být padělané, pokud se Mallory dostane do problémů. Výměna klíčů bude podrobně popsána dále.

Generátory a pseudogenerátory náhody

Proč se vůbec obtěžovat s generováním náhodných čísel ve výkladu o kryptografii? Přece existuje a generátor náhodných čísel zabudovaný do většiny kompilátorů, jako pouhé volání funkce. Proč to nevyužít, že? Bohužel tyto generátory náhodných čísel téměř rozhodně nejsou dostatečně kryptograficky bezpečné a pravděpodobně ani ne příliš náhodné. Většina z nich je trapně špatná. Generátory náhodných čísel nejsou náhodné, protože nemusejí být. Nejjednodušší aplikace, stejně jako počítačové hry potřebují tak málo náhodných čísel, že si jich sotva všimnou. Nicméně kryptografie je extrémně citlivá na vlastnosti generátorů náhodných čísel. Použijete-li blbý generátor náhodných čísel, začnete dostávat podivné korelace a podivné výsledky. Pokud jste závislí na vašem generátoru náhodných čísel pro zabezpečení, jsou podivné korelace a podivné výsledky tou poslední věci, kterou chcete.

Problém je v tom, že generátor náhodných čísel nevytváří náhodnou sekvenci. Pravděpodobně neprodukuje nic, co by jen vzdáleně vypadalo jako náhodná sekvence. Samozřejmě, že je nemožné vytvořit něco skutečně náhodného na počítači. Donald Knuth cituje Johna von Neumann říká: „Každý, kdo uvažuje o aritmetických metodách vytváření náhodných číslic, je samozřejmě ve stavu těžkého hříchu“ [863]. Počítače jsou deterministické bestie: Věci směřují k jednomu konci, úplně uvnitř probíhají předvídatelné operace a na druhém konci vycházejí různé věci. Vložte stejné věci při dvou různých příležitostech a pokaždé vyjde to samé. Dejte to samé do dvou identických počítačů a z obou vyleze to samé. Počítač může být pouze v konečnám počtu stavů (velké konečné číslo, ale přesto konečné číslo) a údaje, které z něj budou vystupovat budou vždy deterministickou funkcí dat, které se dostaly dovnitř, do současného stavu počítače. To znamená, že jakýkoli generátor náhodných čísel na počítači (alespoň na konečném automatu) je podle definice periodický. Vše, co je periodické, je z definice předvídatelné. A pokud něco je předvídatelné, nemůže to být náhodné. Skutečný generátor náhodných čísel vyžaduje určitou náhodnost vstupu; to počítač nemůže poskytnout.

Pseudonáhodné posloupnosti (sekvence)

To nejlepší, co může počítač poskytnout, je generátor pseudonáhodné posloupnosti (sekvence). Co to znamená? Mnozí lidé se vrhli na to, aby to formálně definovali, ale tady mávneme rukou. Pseudonáhodné sekvence je taková, která vypadá náhodně. Perioda sekvence by měla být dostatečně dlouhá, aby konečná posloupnost přiměřené délky – tedy ta, která se skutečně používá – nebyla periodická. Pokud potřebujete miliardu náhodných bitů, nevybírejte sekvenční generátor, který se opakuje po pouhých šestnácti tisících bitech. Tyto relativně krátké neperiodické podsekvence by od nich měly být co nejvíce nerozeznatelné od náhodné sekvence. Například by měly mít přibližně stejný počet jedniček a nul, přibližně polovina běhů (sekvence stejného bitu) by měla mít délku jedna, čtvrtina délky dvě, jedna osmina délky tři a tak dále. Neměly by být komprimovatelné. Rozdělení délek běhů pro nuly a jedničky by měly být stejné. Tyto vlastnosti mohou být empiricky měřeny a poté porovnány se statistickými očekáváními pomocí chí-kvadrát testu.

Pro naše účely je generátor sekvencí pseudonáhodný, pokud má tuto vlastnost:

1) Vypadá to náhodně. To znamená, že projde všemi statistickými testy náhodnosti, které můžeme nalézt.

Do vytváření dobrých pseudonáhodných sekvencí na počítači bylo vynaloženo mnoho úsilí. Diskusí o generátorech je v akademické literatuře mnoho, spolu s různými testy náhodnosti. Všechny tyto generátory jsou periodické (není úniku); ale s potenciálními periodami \$2^256\$ bitů a vyššími, takže mohou být použity pro největší aplikace.

Problémem jsou stále ty podivné korelace a podivné výsledky. Každý generátor pseudonáhodných sekvencí je vyrábí, pokud jej používáme určitým způsobem. A to je to, co kryptoanalytik použije k útoku na systém.

Kryptograficky zabezpečené pseudonáhodné sekvence

Kryptografické aplikace vyžadují mnohem od generátoru pseudonáhodných sekvencí mnohem více, než většina ostatních aplikací. Kryptografická náhodnost neznamená pouze statistickou náhodnost, i když to k tomu patří. Aby byla sekvence kryptograficky bezpečná, musí být pseudonáhodná a musí mít také tuto vlastnost:

2) Je nepředvídatelný. Musí být výpočetně neproveditelné předpovědět, jaký bude následující náhodný bit, za předpokladu úplné znalosti algoritmu nebo hardwaru generujícího sekvenci a všech předchozích generovaných bitů v proudu.

Kryptograficky bezpečné pseudonáhodné sekvence by neměly být komprimovatelné…​pokud neznáte klíč. Klíč je obecně seed používaný k nastavení počátečního stavu generátoru. Jako každý kryptografický algoritmus jsou kryptograficky bezpečné generátory pseudonáhodných sekvencí předmětem útoku. Stejně jako je možné prolomit šifrovací algoritmus, je možné prolomit a kryptograficky bezpečný generátor pseudonáhodné sekvence. Udělat generátory odolné vůči útoku je to, o čem kryptografie je.

Skutečné náhodné sekvence

Nyní se dostáváme do sféry filozofů. Existuje něco jako náhoda? Co to je náhodná sekvence? Jak poznáte, že je sekvence náhodná? Je "101110100" náhodnější než "101010101"? Kvantová mechanika nám říká, že ve skutečnosti existuje poctivě náhodný svět. Ale můžeme zachovat tuto náhodnost v deterministickém světě počítačových čipů a konečných automatů?

Pomineme-li filozofii, z našeho pohledu je generátor sekvencí skutečně náhodný , pokud má další třetí vlastnost:

3) Nelze jej spolehlivě reprodukovat. Pokud spustíte generátor sekvencí dvakrát s přesně stejným vstupem (alespoň tak přesně, jak je to v lidských silách), dostanete dvě zcela nesouvisející náhodné sekvence.

Výstup generátoru splňující tyto tři vlastnosti bude dost dobrý pro one-time pad, pro generování klíčů a jakékoli další kryptografické aplikace, které vyžadují skutečný generátor náhodných sekvencí. Potíž je v určení, zda je sekvence skutečně náhodná. Pokud opakovaně zašifrujeme řetězec pomocí DES a daného klíče, získáme pěkný, náhodně vypadající výstup; nebudeme schopni říct, že je to nenáhodné, pokud si nepronajmeme čas na crackeru NSA DES.

Poznámka nakonec

Na Slovensku v Bratislavě na Fakultě matematiky, fyziky a informatiky Univerzity Komenského se týmu vědců vedenému docentem Martinem Pleshem, PhD. podařilo dokázat, že pomocí více psedouhonáhodných generátorů lze dosáhnout dokonalé náhody. Na přednášku se můžete podívat na Youtube

Odkazy a literatura:

Bruce Schneier: Applied Cryptography 2nd edition, John Wiley & Sons Inc. 1996