Merkly’s puzzle
Říká se, že Merklyho skládačky byly prvním pokusem o bezpečnou distribuci hesla, tedy o to, aby se dva subjekty nemusely bát, že se někdo dozví šifrovací klíč při jeho domluvě (tento požadavek je hnací motor vynálezu as. k.). Zakládá se na následujícím jednoduchém principu. Alice si vytvoří a uschová (dlouhý) seznam potencionálních klíčů. Tyto klíče budeme nazývat komunikační. Dále vezme generátor (pseudo)náhodných čísel a vygeneruje stejně početnou množinu klíčů dočasných. Každý komunikační klíč zašifruje jedním klíčem dočasným a výsledný „balík“ odešle Bobovi Ten si vybere z balíku náhodnou položku (jeden komunikační klíč zašifrovaný dočasným klíčem) a dešifruje ho hrubou silou (předpokládá se, že Alice použila skutečně dobrý šifrovací algoritmus, takže Bob může použít pouze tento druh útoku). Dostane heslo, tj. dešifrovaný komunikační klíč, kterým heslem zašifruje dohodnutou zprávu (nemusí být tajná) a pošle ji Alici. Ta sice neví jaké heslo si Bob vybral, ale může se odkázat na původní nezašifrovaný seznam jí vymyšlených komunikačních hesel a všechny je vyzkoušet, čímž si právě dohodli heslo. Případný útočník by musel dešifrovat hesla všechna. Přestože je tato metoda zajímavá, je jasné, že je v praxi nepoužitelná, a to hned z několika důvodů. Předně čas nutný k získání dohodnutého klíče (při odposlechu spojení) roste pouze lineárně s počtem Alicí odeslaných klíčů. Při exponenciálním růstu výkonu počítačů (1,7x za rok) by to znamenalo stejný růst velikosti přenášeného souboru, pokud bychom chtěli zachovat stejnou bezpečnost. Vzhledem ke zmiňované linearitě také celý systém zhavaruje při použití distribuovaných výpočtů.
The Knapsack algorithm
Tzv. batohový algoritmus (založen na batohovém problému) je jeden z prvních pokusů jak se vyrovnat s popisovanou hlavní nevýhodou symetrické kryptografie – s nutností bezpečného přenosu šifrovacího klíče předtím, než se vlastní šifra použije. Matematické schéma, na kterém systém stojí, patří do kategorie tzv. NP-complete (non-polynomial, tedy kompletně nepolynomiálních) problémů. Řešení takovýchto úloh není zatím známé v polynomiálním, nýbrž pouze v exponenciálním čase. Všechny takovéto problémy jsou na sebe navzájem převoditelné. Pokrok v řešení jednoho z nich se tedy promítne na všech ostatních.
Nutno ovšem podotknout, že algoritmus byl záhy po svém zveřejnění rozbit. Samotný problém ale vyřešen nebyl. Navržené kryptografické schéma totiž neodpovídalo matematickému problému úplně. Privátní klíč, jak se po zkoumání zjistilo, je možné možné vypočítat z klíče veřejného i bez řešení příslušné obtížné úlohy, tj. batohu v dané konfiguraci (viz dále).
Mějme k dispozici množinu věcí, každou o určité kladné hmotnosti. Naším úkolem je vybrat takovou podmnožinu, aby její celková "hmotnost" byla rovna nějaké hodnotě w. Jak se úloha může jevit na první pohled jednoduchá, ve skutečnosti čas potřebný k řešení narůstá exponenciálně s celkovým počtem předmětů. Na druhou stranu existují batohy, jejichž řešení je triviální. Je to v případě, že hmotnost každé položky není nižší, než hmotnost položek předcházejících dohromady. Tento batoh nazýváme superrostoucí (superincreasing).
Při jeho řešení nejprve vezmeme nejtěžší objekt. Pokud je jeho hmotnost menší než celková požadovaná suma w, zařadíme jej do “použitých” věcí a od w jeho hmotnost odečteme. Pokud ne, necháme jej být a pokračujeme dále. Pokud jsme po prozkoušení všech věcí nedosáhli chtěné hmotnosti (tj. když w se nerovná 0), nemá úloha s tímto zadáním řešení.
Konverze z tajného klíče, tj. ze superrostoucího batohu, na klíč veřejný, tj. na normální obtížně řešitelný batoh) bude probíhat následujícím způsobem. Zvolíme modulo m, což bude číslo větší než celkový součet hodnot ("hmotnost") w. Dále zvolíme druhé číslo n tak, že (n,m)=1, jinými slovy v a m odečteme jsou nesoudělná. Vynásobíme každou hodnotu prvku množiny číslem n (mod m) a k zašifrování jednoho bitu použijeme 1, pokud jsme příslušný objekt do batohu zahrnuli a 0 pokud ne.
Příjemce vynásobí hodnoty zašifrovaného textu z mod m, což představuje inverzi n mod m a použije vzniklý superrostoucí batoh k dešifrování zprávy. Pokud tedy platí, že a*z je kongruentní s 1 (mod m), snadno ukážeme, že (a*n mod m)*z mod m = a. Tohoto vztahu budeme využívat při vzájemném přepočítávání (tj. vlastně šifrování a dešifrování) z normálního batohu do superrostoucího a naopak.
Uvažme tedy batoh [3,4,9,19,38,77]. Zvolíme modul m, například 155. Jako s m nesoudělné n zvolíme třeba 27. Nyní vypočítáme hodnoty obtížně řešitelného batohu. 3*27 mod 155 = 81, 4*27 mod 155 = 108 apod, celkově budeme šifrovat s veřejným klíčem [81,108,88,48,96,64].
Budeme chtít zašifrovat zprávu 100110 001101 010001. Podíváme-li se na první blok, nalezneme hodnoty 1 na prvním, čtvrtém a pátém místě. To odpovídá číslům 81, 48 a 96 ve veřejném batohu, zašifrovaný text tedy bude 81+48+96=225. Obdobně 001101 odpovídá 88+48+64=200 a 010001 odpovídá 108+64=172. Výsledný zašifrovaný text je tedy [255,200,172]. Jak už bylo řečeno, pro dešifrování musíme znát z pro které platí n*z = = 1 (mod m) (= = zde představuje kongruenci). S pomocí tohoto čísla jednoduše pro každý blok spočítáme b*z (mod m). V našem případě z=23.
225*23 mod 155 = 60 = 3+19+38 = 100110, 200*23 mod 155 = 105 = 9+19+77 = 001101 a 172*23 mod 155 = 81 = 4+77 = 010001. Dostali jsme výslednou hodnotu 100110 001101 010001, která odpovídá původní zprávě.
Později bylo batohové schéma „obohaceno“ o možnost digiálního podpisu dokumentů, obdobně jak je tomu možné jako například u algoritmu RSA. O prolomení tohoto schématu si můžete přečíst například na http://www.cs.wm.edu/~hallyn/public_key/break.html (z tohoto webu byl převzat příklad). Později byl tento algoritmus zkoušen jako iterační. Říká se, že se Ralph Merkle vsadil o tisíc dolarů, že nikdo nerozluští zprávu 40ti-násobně zašifrovanou. Prohrál.
Man in the middle attack
Schéma, které jsme si zatím nastínili, bohužel pohoří na některých situacích, které by mohli v praxi reálně nastat. Man-in-the-middle attack je jeden z nejznámějších problémů v informační bezpečnosti, na který se při vývoji asymetrických kryptografických technik primárně bralo ohled. Poznejme tedy, v čem je jeho síla a pokusme si vysvětlit, jaká opatření je možné udělat.
Alice nejenže neumí šachy, ale ani je nikdy nehrála a tedy nezná pravidla. Přesto ovšem existuje způsob, jakým může porazit šachového velmistra. Představte si, že osloví nezávisle na sobě Kasparova a Karpova, přičemž ani jeden z nich neví o oslavení toho druhého. Posadí je do dvou oddělených místností a dá před ně dvě (různé) šachovnice tak, aby jeden z nich měl bílé a druhý černé, tedy právě jeden z nich bude začínat. K tomu si sedne a počká až zahraje první tah. Zapamatuje si ho, odejde do druhé místnosti a zahájí partii odkoukaným tahem. Počká na odpověď a tu zahraje opět v první místnosti. Takto bude pokračovat dokud s jedním z nich nevyhraje (s druhým prohraje), nebo dokud obě partie neskončí remízou.
Problém šachistů z tohoto příkladu (tzv. Chess-grandmaster problem) je v tom, že nemají žádný důkaz, že skutečně hrají s Alicí. Jak by také mohli, když ve skutečnosti hrají oba spolu a Alice je jenom jakýmsi prostředníkem. Obdobný problém se objevuje v moderní kryptografii odjakživa: Alice a Bob spolu chtějí bezpečně komunikovat a jelikož znají principy asymetrického šifrování tak vědí, že je to možné, aniž by si museli předem dohodnout symetrický šifrovací klíč. Ukažme si, jak by v případě neznalosti popisovaného problému postupovali.
1. Alice pošle Bobovi svůj veřejný klíč.
2. Bob pošle Alici svůj veřejný klíč. Tím mají navzájem svoje klíče a můžou bezpečně komunikovat.
3. Jeden posílá druhému stejným kanálem tajné zašifrované zprávy.
Případný útočník M (Mallory) uprostřed obejde obě strany velmi jednoduše:
1. Alice pošle svůj veřejný klíč.
2. Mallory ho zachytí a místo toho Bobovi odešle svůj veřejný klíč.
3. Bob pošle svůj veřejný klíč.
4. Mallory ho zachytí a místo toho Alici odešle svůj veřejný klíč.
Nyní, stejně jako v případu dvou šachistů, každá ze stran komunikuje ve skutečnosti s jiným subjektem, než si myslí. Alice považuje obdržený klíč za Bobův, Bob za Alicin. Místo toho ale obě mají klíč Mallory. Jakákoliv poslaná data Mallory zachytí, dešifruje svým tajným klíčem, přečte si to (popř. změní), zašifruje veřejným klíčem druhé strany a odešle dále. Příjemce (Bob) nic nepozná, dokonce ani v případě, že by zpráva byla Alicí digitálně podepsána, neboť Mallory to může udělat totiž stejně tak.
Interlock protokol
Přesně takovémuto druhu útoku se říká Man-in-the-middle Attack, od toho také M, Mallory. Interlock protokol je zajímavý protokol, který tento nepříjemný útok dokáže osobě uprostřed přenosu ztížit možnost změny zprávy. Celý systém, vynalezený Ronem Rivestem a Adi Shamirem, probíhá podle následujícího schématu.
1. Alice pošle Bobovi svůj veřejný klíč
2. Bob pošle Alici svůj veřejný klíč
3. Alice zašifruje svojí zprávu Bobovým veřejným klíčem a pošle mu první polovinu
4. Bob zašifruje svojí zprávu Aliciným veřejným klíčem a pošle jí polovinu
5. Alice pošle Bobovi druhou polovinu.
6. Bob sestaví zprávy dohromady, dešifruje je a pošle Alici druhou část své zprávy.
Nejdůležitější vlastnost schématu je, že zprávy nesmí být čitelná, resp. dešifrovatelné, pokud nejsou k dispozici obě poloviny. Jedna (jakákoliv) polovina zprávy sama o sobě nesmí znamenat nic. Toho se může dosáhnout například tak, že zašifrovaná zpráva se prostě rozdělí na sudé a liché bity a ty budou tvořit dvě "poloviny". Popřípadě pokud je dešifrovací proces závislý na inicializačním vektoru, může tento vektor být ve druhé polovině, než vlastní zpráva.
Pokud vám není jasné, jak jsme tím ztížili Mallory(mu) man-in-the-middle útok, pokuste se protokol podvrhnou (tj. změnit přenášená data, prostý odposlech je samozřejmě stále možný). Případný útočník samozřejmě stále může podvrhnout veřejné klíče obou stran ve krocích 1 a 2. Jenže v kroku 3 má v ruce pouze jednu polovinu zprávy určené pro Boba a s ní nemůže nic dělat. Pokud jí nechce poslat, musí vytvořit zbrusu novou zprávu a tu odeslat místo původní. V kroku 4 má úplně stejný problém se zprávou pro Alici. Opět musí vymyslet jinou, vlastní zprávu. Až v kroku 5 a 6 odchytne druhé poloviny zpráv, bude už pozdě na to, aby zfalšoval poloviny první, protože ty už budou dávno odeslány. Nezbude mu nic jiného, než odeslat druhé poloviny svých vymyšlených zpráv. Pokud by dokázal předpovídat jaké zprávy budou Alice nebo Bob posílat, může protokol samozřejmě "přechytračit". Ale udržovat smysluplnou komunikaci mezi Alicí a Bobem, kdy obě strany díky mezičlánku vlastně mluví "jinou řečí", je rozhodně podstatně obtížnější, než jen tak sedět na drátě a poslouchat.
Digitální podpisy
Digitální podpisy jsou jedním z hlavních přínosů asymetrické kryptografie. Mimo všude tak proklamované posílání daňových přiznání na úřady apod. se podílejí na obraně proti útoku z jednoho z minulých odstavců, jehož řešení jsem zatím nechal otevřené.
Digitální podpis je v praxi jen sekvence čísel za určitým dokumentem. Oproti ručnímu podpisu je ovšem zvláštní rozdíl v tom, že ruční podpisy jednoho člověka na dvou různých dokumentech jsou ne-li stejné tak alespoň podobné, vedle toho digitální podpisy jednoho člověka pod dvěma různými dokumenty jsou naprosto odlišné. Vedle matematického pozadí digitální podpisů tomu tak je ze zřejmých důvodů. To, co můžeme udělat ve skutečnosti, např. okopírovat něčí podpis na jakýkoliv dokument, bychom mohli na počítači udělat ještě snáze, navíc by byl padělek od originálu naprosto k nerozeznání.
Klíčovým pojmem, nutným k porozumění filosofii digitálních podpisů je tzv. bezpečný výtah zprávy (angl. message diegest, hash). Výtah zprávy (dále jen výtah či hash) je algoritmus, který z jakkoliv dlouhé posloupnosti znaků (čísel) vytvoří číslo s konstantní délkou a to za stanovených podmínek. Pojem hashování se objevuje například i v oblasti databází. Jedná se o použití podobných technik, ovšem s odlišnými nároky na vlastnosti.
Pro naše účely požadujeme především tzv. kryptografickou bezpečnost hashovacího algoritmu, což v praxi znamená takzvanou jednocestnost vytvořené funkce. Spočítat hash jakékoliv zprávy musí být velmi jednoduché, ale vymyslet zprávu tak, aby měla nějaký konkrétní hash musí být obtížné. To je základní rozdíl mezi hashi a kontrolními součty. Nejznámější v kryptografii používané algoritmy jsou MDx (Message Diegest 2, 4, 5), SHA (Secure Hash Algorithm) a RIPE-MD. Bezpečnost hashovací funkce je přímo závislá na délce výstupního bloku, dále pak obvykle platž, že i malá změna ve vstupu způsobí velkou změnu ve výstupu.
Vlastní digitální podpis funguje v obecné rovině velmi jednoduše. Pokud chce Alice podepsat nějaký dokument, vygeneruje z něj výtah a zašifruje ho svým tajným klíčem. Toto přiloží k dokumentu, čímž ho právě podepsala. Na druhé straně Bob separuje podpis od dokumentu, spočítá výtah z textu a dešifruje podpis Aliciným veřejným klíčem. Tím dostane dvě hodnoty. Pokud se rovnají, je podpis platný (použil jsem nejjednodušší popis asymetrického algoritmu RSA).
Bezpečnost této metody vyplývá z výše uvedených vlastností. Kdyby kdokoliv chtěl podpis zfalšovat, musel by mít jeho tajný klíč. Nebo by také mohl něčí podpis přiložit pod jiný dokument. Jenže to nejde, protože by se pak neshodovaly výtahy textu a dešifrovaného podpisu. A nemožnost vymyšlení dokumentu s daným hashem plyne přímo z výše uváděné definice výtahů ze zpráv. Jak je vidět, v kryptografii s veřejným klíčem vše stojí a padá s bezpečným uschováním tajného klíče.
Po digitálním podpisu jsou požadovány tři hlavní vlastnosti, které jsou při uvedeném schématu splněny. První z nich je autentičnost zprávy, tj. příjemce musí mít možnost odhalit jakoukoliv její změnu. Toho jsme docílili použitím hashovací funkce : jakákoliv změna vstupu způsobí radikální (tj. neúměrnou) změnu výstupu a při ověřování bude podpis neplatný. Druhou požadovanou vlastností je nepopiratelnost podpisu, kterou jsme také splnili – jen a právě vlastník má k tajnému klíči (který je pro podpis potřeba) přístup. Jak ale zajistit skutečné propojení podpisu s konkrétní osobou či organizací? Máme podobný problém jako Alice a Bob v případě man-in-the-middle útoku. Digitální podpis jednoznačně spojí dokument s daným klíčem, kdo ale spojí klíč s reálným subjektem? Pokud si spustíte nějaký šifrovací program a zkusíte si vygenerovat pár klíčů, zeptá se vás mimo jiné i na vaše jméno. Každý klíč totiž musí být nositelem nějaké jmenovky (nejméně jedné), aby se poznalo, čí ten klíč je. Zde je ale kámen úrazu. Kdokoliv si může vytvořit klíče se jmenovkou třeba Billa Clintona. Může s ním šifrovat, dešifrovat, podepisovat, nebo ho třeba vystavit na nějakém veřejném serveru klíčů lidí z celého světa. Bude to mít ale jeden háček: nebude to klíč Billa Clintona, ale někoho úplně jiného, který ten klíč podvrhl.
Důvěryhodná třetí strana
Princip důvěryhodné třetí strany je zavedený i v "běžném" životě. Představují ji notáři, soudci, komise apod. Především v komerční počítačové oblasti platí, že třetí strana má co možná největší míru zájmu zůstat důvěryhodná jak jen to dlouho jde, protože takto ztracený kredit by se od klientů již velmi těžko získával zpět. Tím je zajištěno, že i tato třetí strana má mimořádný zájem na své „nepodvrženosti“, stejně jako Alice a Bob. Důvěryhodná třetí strana je v tomto případě takzvaná certifikační autorita.
Certifikační autorita je instituce-důvěryhodná třetí strana , která svým podpisem na cizím veřejném klíči stvrzuje, že klíč patří skutečně tomu subjektu, který je napsán na jmenovce. Jde o víceméně identickou operaci jako digitální podepisování dokumentů, rozdíl je pouze v interpretaci výsledku. Podpis certifikační autority pod veřejným klíčem se nazývá (digitální) certifikát.
Public Key Infrastructure
Systém certifikačních autorit, certifikátů a veřejných klíčů jednotně nazýváme Public Key Infrastructure, infrastruktura veřejných klíčů, volněji taktéž v některých případech pavučina důvěry. Bezpečnost a konzistence takovýchto struktur je založena na základě vzájemné důvěry jednotlivých článků. Z praxe bych jmenoval dva základní přístupy k budování architektury PKI : systém hierarchický a systém distribuovaný. Právě certifikační autority jsou typické pro ten prvně jmenovaný. Jednotlivé subjekty jsou uspořádány do jakéhosi (otočeného) stromu důvěry, kde úplně nahoře je takzvaná kořenová CA a v listech jsou jednotliví certifikovaní uživatelé. Mezi těmito krajními součástmi se nacházejí jednotlivé certifikační autority. Ty mají vždy certifikát od autority nadřazené a naopak vydávají certifikát jednotlivým uživatelům, popř. ostatním autoritám (tzv. křížová reference). Pár veřejný/tajný klíč může sám uživatel vytvořit a nechat si ho podepsat od CA, nebo ho může generovat CA pro něj. Tato situace předpokládá vztah důvěry mezi uživateli a CA, neboť ta má poté přístup k tajným klíčům uživatelů. Výhoda je v menším počtu starostí uživatele.Pokud dostanete klíč s certifikátem, vaše důvěra v tento klíč záleží na vaší důvěře v přiložený certifikát. Pokud věříte, že autorita, která ten certifikát vydala, podepisuje pouze platné klíče, budete věřit, že tento klíč skutečně náleží na jmenovce uvedené osobě. Pokud jí nevěříte, nemáte nic, o co byste opřeli svoji důvěru.
Systém distribuovaný je zobecněním systému hierarchického. Každý v něm zúčastněný s ubjekt považuje za důvěryhodné pouze své nejbližší sousedy. Snaha jednotlivce tedy je, získat pod svůj veřejný klíč co nejvíce podpisů a doufat, že potencionální dopisovatel bude věřit alespoň jednomu z nich. Každý je vlastně takovou malou certifikační autoritou pro lidi ze svého nejbližšího okolí. Tuto ideu představuje program PGP, naopak důvěru pouze v CA vyžadují programy jako Outlook, Internet Explorer apod.
Podpis CA na Aliciném klíči Bobovi potvrzuje, že je se skutečně jedná o klíč Alicin. Bob nemá nejmenší důvod věřit nepodepsanému podvrhnutému klíči, ve skutečnosti od Mallory. Je zde vidět, že právě na důvěryhodnosti třetí strany celý systém stojí. Pokud bude certifikační autorita podplatitelná nebo její data, technologie, servery apod. budou nedostatečně zabezpečené, Mallory bude ve skutečnosti ještě v lepší situaci, protože (falešný) podpis klíče bude tím víc Boba klamně ujišťovat o jeho pravosti.
Podepisovací a šifrovací klíče
Šifrovací program PGP ve své verzi 6.0 přišel s významnou novinkou: takzvanou podřízeností klíčů. Základní myšlenka je až geniálně jednoduchá: oddělme šifrovací a podepisovací klíče od sebe. Při přenášení těchto klíčů například e-mailem, se vše bude tvářit jako jeden soubor, ale ve skutečnosti nám bude moci certifikační agentura podepsat pouze podepisovací klíč. To ale úplně stačí protože na základě podepsání našeho veřejného šifrovacího klíče naším podepisovacím klíčem (který máme ověřen), budou všichni věřit i tomuto šifrovacímu klíči. Například při ztrátě šifrovacího klíče si stačí vygenerovat nový, podepsat ho a vystavit na serverch s veřejnými klíči. Inteligentní šifrovací programy to navíc udělají tak, že nový šifrovací klíč jakoby odsune ten starý na druhé místo, tudíž se bude implicitně šifrovat novému klíči.
Toto má také dalekosáhlé účinky na tzv. key-escrow. Key-escrow je služba poskytovaná třetí, více či méně důvěryhodnou stranou, u které si můžeme náš tajný klíč uschovat. Důvody mohou být dobrovolné (například pro případ ztráty), ale také nucené, kupříkladu velká společnost může chtít mít přístup k zaměstnancově práci v případě, že by zemřel nebo byl dlouhodobě nemocný. Pakliže má třetí strana zájem pouze o náš šifrovací klíč (což je nejčastější varianta), vyřešíme situaci jednoduše vygenerováním klíče nového. Ten bude aktuálnější, bude se používat implicitně, ale starý bude pro dešifrování stále k dispozici.