V minulém díle našeho seriálu jsme uvedli, že základem bezpečnosti aplikací na Internetu je nějaká metoda šifrování dat. Šifrování je, zjednodušeně řečeno, způsob, jak převést čitelný text zprávy na text jiný, bez dalších informací nečitelný. Tato další informace nutná pro rozluštění (dekódování, dešifrování) původního textu zprávy, se obvykle označuje jako (dešifrovací) klíč. Při kódování zprávy se obvykle používá (šifrovací) klíč, který nemusí být nutně totožný s dešifrovacím klíčem. (Myšlenka kupodivu poměrně nová - poprvé ji veřejně formulovali pánové Whitfield Diffie a Martin Hellman v roce 1976, i když americká agentura NSA prohlašuje, že ji znala už o deset let dříve). Tento postup se dá znázornit následujícím schématem:

Pointa je samozřejmě v tom, že text na prvním řádku tabulky je totožný s textem na druhém řádku (šifra samozřejmě také); funkce e a d zde představují kódovací respektive dekódovací algoritmy. Věda, která se zabývá různými šifrovacími schématy, se nazývá kryptografie a je založena na mnoha hlubokých poznatcích z matematiky (teorie čísel) a informatiky (teorie informace, teorie složitosti) - o některých z nich se alespoň náznakem zmíníme.

Kryptografické protokoly

Jak již víme, protokol je jakási domluva zúčastněných stran na formátu, v jakém si budou vyměňovat informace. Kryptografický protokol je tedy dohoda, jakým způsobem si partneři budou sdělovat a jaké informace, zahrnuje i kroky, které musí partneři provést, aby požadované informace získali. Cílem kryptografického protokolu je splnit nějaký úkol; dobrý protokol musí ovšem počítat s tím, že ne všechny zúčastněné strany mají totéž přání. Jednotliví partneři si nemusí navzájem důvěřovat, ani nemusí správně protokol dodržovat, každé vybočení z mezí však musí být zjistitelné a prokazatelné. Obecně řečeno, dobrý kryptografický protokol neumožňuje zúčastněným provést jiné akce nebo získat jiné informace, než protokol určuje. K dosažení tohoto cíle používají kryptografické protokoly patřičné prostředky - jedním z nich jsou šifrovací algoritmy, další jsou jednosměrné a hašovací funkce a digitální podpisy. O všech těchto prostředcích se v následujícím textu zmíníme, nejprve si ale povězme o těžkých problémech. Těžké problémy Aby byla kryptografie užitečná, musí být složité nalézt správné rozluštění zakódované zprávy bez znalosti klíče a musí být i složité nalézt správný klíč. Jinými slovy šifra musí obsahovat minimum informací o původním textu. Luštit šifry na počítači tedy musí být obtížný problém a složitostí problémů se zabývá celé jedno odvětví informatiky, do kterého si teď uděláme malou laickou exkurzi.

Možná vás to překvapí, ale přes velké rozšíření počítačů je většina problémů reálného světa na počítači špatně řešitelná v tom smyslu, že čas, který zaberou potřebné výpočty, je příliš velký nebo dokonce že takový výpočet je principiálně nemožný.

O tom, že skutečně existují problémy, které nejdou na počítači vyřešit už z principu, nás přesvědčil pan Alan Turing, jeden ze zakladatelů informatiky a autor všeobecně používaného abstraktního matematického modelu počítače (tzv. Turingův stroj). Ukázal totiž, že problém zastavení Turingova stroje je Turingovým strojem neřešitelný. Pokud jsem vás teď vyděsil, vytrvejte, jde v podstatě o "trivialitu" - uvedený problém se totiž dá popsat takto: máte napsat počítačový program, který o libovolném jiném počítačovém programu rozhodne, zda se při spuštění s konkrétními vstupními daty zastaví nebo ne. (O tom, že ne každý program se vždy zastaví, vás snad zkušenosti s výpočetní technikou a klávesami CTRL+ALT+DEL dostatečně poučily.) Ukazuje se, že tento jistě užitečný program nemůže z principu existovat.

Čas výpočtu se většinou udává jako nějaká funkce velikosti vstupních dat. Malý příklad - hledání v telefonním seznamu. Je jasné, že nalezení určité osoby nám zabere tím více času, čím je telefonní seznam větší. Teorie složitosti většinou tento vztah chápe přibližně - odpovídá na otázku, jak se změní čas výpočtu při změně velikosti vstupu (například pokud zvolíme špatnou metodu hledání v seznamu a budeme ho číst od začátku, než narazíme na správné jméno, vyjde nám, že bude-li seznam dvakrát delší, strávíme nad ním dvakrát více času).

Podle tohoto vztahu mezi velikostí vstupních dat a časem výpočtu nejlepšího existujícího algoritmu (pozor - ne každý existující algoritmus musí být známý!) lze problémy rozdělit do skupin. Některé skupiny je na počítači možné řešit snadno (sem patří například vyhledávání v seznamech, řazení, jednoduché matematické operace a podobně), některé obtížně (násobení matic), některé problémy nelze prakticky řešit vůbec, protože na výsledek bychom museli čekat miliony let. Těmto nezvládnutelným problémům se říká exponenciální a platí u nich jednoduchý vztah - pokud se vstupní data zvětší o jediný bit, vzroste čas výpočtu nejméně dvakrát (přesněji nejméně konstanta-krát). Exponenciální problémy lze v principu na počítači řešit - trvá to ale nepříjemně dlouho a pro velké problémy to nelze v reálném čase zvládnout. Dají se ale nalézt rychlejší postupy, takže i velikost reálně řešitelných exponenciálních problémů roste.

Typickým příkladem exponenciálního problému je hledání neznámého čísla - představte si, že hrajete s přítelem následující hru: on si myslí nějaké číslo od jedné do deseti a vy máte zjistit, které to je. Vy hádáte čísla a váš partner vám pouze sdělí, jestli jste uhodli nebo ne. Nezbývá vám nic jiného, než prostě vyzkoušet všechna čísla od jedné do deseti. Teď si představte, že máte inteligentnějšího přítele, který zvládá čísla až do sta - máme tedy pouze o jedinou cifru navíc a desetkrát více možností. (Z toho plyne poučení - s inteligentnějšími přáteli je někdy potíž :-)).

Existuje ještě jedna zajímavá skupina problémů - problémy, kterým se říká NP-úplné. Tento pojem nebudeme raději dešifrovat, řekněme si pouze tolik - nejlepší známý algoritmus řešení těchto problémů má exponenciální složitost (tedy nezbývá než vyzkoušet všechna možná řešení). Existence rychlejšího (polynomiálního) algoritmu není dokázána a zůstává jednou z velkých nevyřešených otázek teorie složitosti. Přitom formulace těchto problémů je jednoduchá a většina z nich vychází z reálného světa. Posuďte sami - tady jsou některé NP-úplné problémy:

• problém batohu - máte sadu závaží a batoh. Na letišti vám řeknou, že váš batoh musí vážit přesně tolik a tolik. Váš problém je pak určit, která závaží vložit do batohu a která zahodit.
• problém obchodního cestujícího - jste (kdo jiný než) obchodní cestující, který má za úkol objet všechna města (a vrátit se domů) ve svém rajónu a každé navštívit právě jednou. Musíte používat pouze železniční spoje, které mohou vést mezi městy úplně libovolně (například mezi některými městy vůbec). Váš problém je zjistit, jestli pro danou železniční síť vůbec taková cesta existuje. (Samozřejmě se předpokládá, že všechna města jsou vlakem dostupná, jinak má problém triviální řešení.)
• rozklad na prvočísla - váš učitel vám zadá nějaké číslo a vaším úkolem je rozložit ho na prvočinitele.

Všechny tyto problémy vypadají na první pohled jednoduše - jediná známá metoda řešení je ale vyzkoušet všechny možné kombinace. Je možné, že existuje rychlejší způsob, zatím ho ale nikdo nezná.

I když přece. V roce 1994 Leonard D. Adleman ukázal, že je možné efektivně vyřešit problém obchodního cestujícího. Nikoliv na počítači, ale...klonováním DNA! A dále - byl sestaven teoretický model kvantového počítače, který je schopen efektivně nalézt prvočíselný rozklad daného čísla. Zatímco první metoda je prakticky použitelná, druhá nikoliv - sestrojit kvantový počítač doopravdy se zdá nemožné. Jenže i nemožné věci se, jak známo, někdy prostě stanou.

Kryptografové by byli rádi, aby nejlepší možný algoritmus prolomení dané šifry měl exponenciální složitost; ve skutečnosti prolomení většiny existujících šifer je NP-úplný problém. I když je nepravděpodobné, že někdo najde jeho efektivní řešení, vyloučené to není. Zatím tedy zbývá pouze zkoušet všechny možné klíče. Klíče Jednou ze základních zásad moderní kryptografie je toto tvrzení:

Jinými slovy, dešifrovací klíč je jediná informace, kterou je třeba chránit před odhalením, ostatní parametry šifrovacího systému (použité algoritmy, zašifrovaný text, případně šifrovací klíč) mohou být veřejně známé. (Ve skutečnosti aby byl systém označen jako důvěryhodný, musí projít řadou testů a použité algoritmy tedy musí být veřejně dostupné.) Otázka klíčů je snad nejdůležitější v celé kryptografii - způsob, jak se klíče generují, jak se distribuují, jejich délka, omezení platnosti, to vše má vliv na bezpečnost používaného systému.

Klíčem může být v podstatě libovolná posloupnost binárních čísel (tedy 0 a 1), jejíž délka je daná používaným schématem. Tato posloupnost by měla být co nejvíce náhodná, respektive měla by mít statistické vlastnosti náhodné posloupnosti a mělo by být na počítači obtížné ji predikovat (uhodnout následující bit, známe-li všechny předcházející). Zdánlivě jednoduchá vlastnost, není ji však lehké na počítači splnit - generování opravdu náhodných čísel nelze popsat algoritmem (pak by to nebyla náhodná čísla ;-)), proto se pro generování klíčů používají informace v podstatě nenáhodné, nicméně těžko odhadnutelné (například obsah paměti v daný časový okamžik a podobně). Na klíč mohou být kladeny i další požadavky (typu musí to být prvočíslo a podobně), které jeho nalezení ztěžují. Volba klíče (kromě jeho utajení) může být velkou slabinou šifrovacího systému.

V zásadě existují dva přístupy k šifrování - šifrování s veřejným klíčem a symetrické šifrování.

Šifrování s veřejným klíčem

V systémech s veřejným klíčem má každý komunikující partner dva klíče - jeden tajný, dešifrovací, a jeden veřejný, šifrovací. Posílá-li někdo zprávu svému partnerovi, najde si jeho veřejný klíč a pomocí něj zprávu zakóduje; příjemce ji pak odkóduje svým tajným klíčem. Jiným než tajným klíčem adresáta zprávu dešifrovat nelze, odesílatel si tedy může být jist, že jeho zpráva zůstane utajena. Opravdu jist?

Představme si jednoduchý kryptografický protokol - dva partneři (A a B) navážou spojení, sdělí si navzájem své veřejné klíče a potom si posílají zašifrované zprávy. Představme si teď ale útočníka U, který má možnost vstoupit do jejich komunikace už při navazování spojení tak, že A i B jsou přesvědčeni, že hovoří spolu - ve skutečnosti ale komunikují prostřednictvím útočníka U. Jeho úloha je jednoduchá - zachytí veřejné klíče A i B a nahradí je svým vlastním, aniž to A nebo B zjistí. Potom už může v klidu číst zasílané zprávy zakódované jeho veřejným klíčem, posílat je na správnou adresu zašifrované správným veřejným klíčem a mnout si ruce. (Tento druh útoku se nazývá man-in-the-middle attack.)

V čem je chyba? A ani B zde nemají možnost, jak ověřit, že získané veřejné klíče opravdu patří jejich partnerovi. Mohou získat klíče jinak (například od nějaké důvěryhodné osoby), lepší je ale použít tak zvané certifikáty.

Certifikáty

Certifikát je vlastně veřejný klíč spolu s informacemi o jeho majiteli digitálně podepsaný certifikační autoritou. Digitální podpis, jak se později dozvíme, zabraňuje změně certifikátu a (jako každý podpis) je ověřitelný (t.j. lze zjistit a dokázat, kdo dokument podepsal). Certifikační autorita pak ručí za správnost svého podpisu. Je samozřejmě otázkou, kdo pro nás představuje natolik důvěryhodného partnera, že může sloužit jako certifikační autorita, to už ale závisí na povaze řešeného problému.

Symetrické šifry

Symetrické šifry používají pro kódování a dekódování stejný klíč. To s sebou přináší jeden problém: tento klíč musí znát jak odesílatel, tak příjemce zprávy, musí se tedy na něm buď domluvit předem, předat si ho (ovšem tak, aby ho nikdo nebyl schopen zachytit, tedy nejlépe zašifrovaný :-)) nebo musí být schopni ho nějakým způsobem odvodit (a nikdo jiný toho schopen být nesmí). Symetrické šifrovací algoritmy jsou obecně rychlejší (až tisíckrát!) než algoritmy založené na veřejném klíči, proto se často oba přístupy kombinují - pomocí šifrování s veřejným klíčem se partneři dohodnou na tajném klíči, který potom používají při další komunikaci kódované symetrickým algoritmem.

Jak již bylo řečeno, zatím jediný známý způsob, jak nějakou šifru prolomit, je zkoušet všechny možné kombinace klíčů. Ukazuje se ale, že ani toto není úplně neřešitelný problém - jak neustále roste výkonnost dostupných počítačů i jejich počet a nacházejí se nové rychlejší algoritmy, stává se tato metoda útoku celkem reálnou. Samozřejmě použití delšího klíče ji opět odsune kamsi do neznáma, nicméně také prodlouží časy pro šifrování a dešifrování. Je tedy třeba najít přijatelný kompromis. Zdá se ale, že 256-bitové klíče jsou dostatečně dlouhé na to, aby energie, kterou by spotřeboval (libovolný) počítač při probírání všech možných klíčů daleko převyšovala energii výbuchu menší supernovy. Nechat explodovat hvězdu kvůli rozluštění zprávy typu "Přijdu na rande později. M." se asi nevyplatí.

Běžně používané délky klíčů (56-bitů u DESu) jsou nicméně prolomitelné dostupnými prostředky (více o tom v kapitolce o DESu), krátké klíče je tedy možné používat pouze pro zprávy, jejichž hodnota časem (rychle) mizí. Používané šifrovací algoritmy Opusťme tedy konečně suchou teorii a povězme si něco o algoritmech, které se nejčastěji používají pro kódování dat. Začněme perfektní, nerozluštitelnou šifrou.

"One-time pad"

Předpokládejme, že máte zprávu délky n bitů a stejně dlouhý klíč, který zná i adresát. Uděláte jednoduchou věc - vytvoříte šifru opět délky n tak, že pokud jsou bity klíče a zprávy shodné, napíšete na odpovídající pozici šifry 0 a pokud se liší, napíšete 1 (tedy operace XOR). Tuto zprávu pak pošlete adresátovi, který udělá totéž s klíčem a zašifrovaným textem a obdrží tak původní zprávu. Je to jednoduché, je to perfektní a nelze to rozluštit - v čem je tedy háček? Jako klíč musíte použít naprosto náhodnou sekvenci, tedy nic, co lze vygenerovat na počítači. Náhodná sekvence přidaná k vaší zprávě vytvoří jako šifru opět čistě náhodnou sekvenci - kdo umí, ať luští. Navíc jednou použitý klíč už nikdy nesmíte použít znovu. Uvedená metoda je tedy sice perfektní, bohužel se ale nedá prakticky použít (to je druhá definice perfektnosti).

DES

DES (Data Encryption Standard) je typickým představitelem symetrických algoritmů. Byl vyvinut v roce 1975 firmou IBM na požadavek americké vlády, která chtěla jednoduchý, bezpečný, snadno použitelný a hlavně standardizovaný algoritmus šifrování dat pro státní instituce a komerční organizace. Vývoj algoritmu se neobešel bez zásahu NSA, která jednak přiměla IBM zkrátit klíč ze 128 na 56 bitů, jednak předělala jednu část algoritmu (takzvané S-boxy). NSA byla dlouho podezírána, že algoritmus modifikovala tak, aby ho mohla snadno rozluštit - kritéria pro design S-boxů byla dlouho utajována a S-boxy vykazovaly některé zvláštní vlastnosti, které se zdály obvinění potvrzovat. Bezpečnost DESu byla dlouho zkoumána různými metodami kryptoanalýzy, jako poměrně úspěšná se nakonec ukázala diferenciální kryptoanalýza - i když prakticky ji využít vyžaduje velké náklady. Je možné, že NSA metody diferenciální kryptoanalýzy znala už při tvorbě DESu, protože jejich S-boxy se zdají být proti podobnému útoku optimalizované. Po tomto objevu IBM konečně zveřejnila kritéria pro tvorbu algoritmu, což částečně přispělo k očištění NSA.

Je tedy DES bezpečný? Ne příliš. Díky malé délce klíče stroj, který je speciálně určený pro luštění DESu a stojí přibližně milion dolarů, dokáže šifru rozluštit průměrně za tři a půl hodiny. Pověsti říkají, že NSA s pomocí pouze jí známých technik a postupů to dokáže za tři až patnáct minut. Letos jsme se mohli zúčastnit mezinárodního projektu, který byl zaměřen na prolomení DESu - americká firma RSA Data Security vypsala odměnu $10000 pro toho, kdo rozluští DESem zašifrovaný text. Informace o průběhu celé akce byly k dispozici na stránkách DESCHALL a DES Coordinated Challenge, projektu (respektive obou projektů - amerického a evropského) se zúčastnily desítky tisíc počítačů na celém světě (78 000 pouze v americkém projektu); vyzkoušena byla dohromady polovina z celkového množství 7.2x10¹⁶ klíčů když rychlost testování dosáhla v závěru až 7 miliard klíčů za vteřinu. Výhercem ceny se po čtyřech měsících stal Michael K. Sanders z Utahu, který nalezl správné rozluštění na svém počítači Intel Pentium s operačním systémem FreeBSD. Zašifrované sdělení znělo: "Strong cryptography makes world a safer place."

Za poznámku stojí důvod, proč vlastně existovaly dva soupeřící projekty. Díky restrikcím americké vlády na export šifrovacích technologií nebylo možné software vytvořený americkým týmem používat mimo území USA. Švédský tým, který koordinoval konkurenční projekt DES Challenge, musel tedy vytvořit vlastní programy; přestože začal pracovat s jistým zpožděním, díky možnosti rozšířit program po celém světě záhy americký projekt dohnali.

DES je tedy snadno rozluštitelný velkými podniky a organizacemi, pro bankovnictví a podobně důležité oblasti se nehodí - pro osobní použití celkem vyhovuje. DES v současné době používá mnoho softwarových systémů - Kerberem počínaje a UNIXy obecně konče (používají ho pro šifrování hesel).

IDEA

IDEA pochází z roku 1990 a je pravděpodobně nejlepším symetrickým algoritmem, který se veřejně používá. Jeho klíče mají délku 128 bitů, jsou tedy odolnější proti odhalení než klíče DESu. K popularitě algoritmu IDEA přispělo zejména jeho použití ve volně dostupném šifrovacím balíku PGP (který zároveň svému autoru Philu K. Zimmermanovi přinesl nemálo problémů s americkou vládou). Zatím není známa žádná kryptoanalytická metoda, jež by byla úspěšná proti IDEA; algoritmus je ale poměrně nový, i když založený na pevných teoretických základech.

RSA

Algoritmus RSA nazvaný podle svých autorů pánů Rona Rivesta, Adi Shamira a Leonarda Adlemana je nejpopulárnějšim a nejrozšířenějším algoritmem, který používá šifrování s veřejným klíčem. Jeho bezpečnost je založena na problému nalezení rozkladu čísla na prvočinitele, vlastně se předpokládá, že to tak je - nikdo to totiž skutečně nedokázal a je možné, že někdo najde úplně jiný způsob prolomení RSA (je to ale dosti nepravděpodobné). I tak ovšem hledání prvočísel není tak složité, jak bývalo - algoritmy se zrychlují a matematikové hledají stále nové triky, které by faktorizaci usnadnily, což zvyšuje minimální nutnou délku klíče.

RSA je de facto standardem pro systémy s veřejným klíčem, je vhodný zejména pro distribuci sdílených symetrických klíčů a pro digitální podpisy, pro běžné šifrování dat například pro přenos po síti se nehodí (jednak je pomalý, jednak je poměrně obtížné generovat klíče - musí to být poměrně velká prvočísla). Jednosměrné a hašovací funkce Jednosměrná funkce je v podstatě způsob, jakým nějaký dokument převést na jiný tvar - takový, ze kterého je prakticky nemožné odvodit tvar původní nebo nalézt jiný dokument, který by dával po převedení jednosměrnou funkcí stejný výsledek (Zašifrovat text a zapomenout klíč je jednosměrná funkce.) Hašovací funkce je taková, kde výsledný tvar má pevnou a většinou mnohem kratší délku než původní text. K čemu se mohou jednosměrné hašovací funkce hodit? Například k ověření obsahu dokumentu. Pokud pro nějaký dokument spočítáme jeho hašovací funkci a odešleme ho po síti svému partnerovi, může spočítat hašovací funkci obdržené zprávy a porovnat ji s naší hodnotou - pokud se liší, dokument, který obdržel, je jiný. (Pokud je hodnota stejná, je vysoká pravděpodobnost, že dokument je totožný.) Digitální podpisy Digitální podpis - navzdory rozšířenému názoru - není obrázek ručního podpisu nascanovaný do počítače v nějakém grafickém formátu. Digitální podpis je způsob, jak pozměnit elektronický dokument tak, aby měl vlastnosti obyčejného podepsaného dokumentu, třeba:

• autenticitu - váš podpis na dokumentu přesvědčí adresáta, že jste dokument skutečně podepsal.
• nezfalšovatelnost - nikdo jiný váš podpis neumí napodobit.
• jednorázovost použití - podpis nelze vzít a přenést na jiný dokument.
• nezměnitelnost dokumentu - po podpisu už nelze provádět v textu žádné změny.
• nepopiratelnost - nemůžete prohlásit, že jste dokument nepodepsal, když je vámi podepsaný :-)

Je zřejmé, že obyčejné podpisy tyto vlastnosti většinou nemají. Digitální podpisy je mít mohou. Pro digitální podpisy lze využít některé algoritmy pro šifrování s veřejným klíčem, třeba RSA. (Algoritmy musí mít tu vlastnost, že šifrování a dešifrování jsou komutativní operace - t.j. text lze zašifrovat tajným klíčem a potom dešifrovat veřejným.) Dokument podepíšete jednoduše tak, že jej zašifrujete svým tajným klíčem. Tento digitální podpis splňuje všechny výše uvedené vlastnosti, má však některé praktické nevýhody - je pomalý. Proto se používá především ve spojení s jednosměrnými hašovacími funkcemi. Nepodepisujete potom samotný dokument, ale výsledek jednosměrné funkce, což má několik výhod - procedura je mnohem rychlejší, podpis je možné uložit odděleně od dokumentu (nebo i samostatně) a samotný dokument tak držet v tajnosti a podobně. Pro digitální podpisy existují i speciální algoritmy, například DSA.

Závěr (nikoliv seriálu)

Jaký tedy učinit z výše uvedených informací závěr? Tak především, bezpečnost systému závisí na všech jeho prvcích - na bezpečnosti algoritmu, protokolu, uchovávání a generování klíčů a podobně. Je zbytečné používat RSA s 1024-bitovým klíčem, jestliže své heslo máte zapsané v notýsku vedle klávesnice. Je zbytečné mít své soubory zakódované pomocí IDEA, jestliže si jako heslo zvolíte své křestní jméno. (Jedním z nejúčinnějších útoků proti heslům je útok pomocí slovníku - sestavíte seznam pravděpodobných hesel, která zkoušíte použít jako klíč k rozluštění šifry. Ve slovníku mohou být slova daného jazyka, jména oblíbených postaviček kreslených seriálů, ... možností je opravdu mnoho. Na běžných UNIXových strojích takový útok odhalí až čtyřicet procent hesel uživatelů.) Největší slabinou šifrovacích systémů jsou tedy (jako obvykle) lidé, kteří je používají.

---

Údaje v této části byly čerpány zejména z knihy Bruce Schneiera "Applied Cryptography".