COMPUTERWORLD
Specializovaný týdeník o výpočetní technice

Seriál
o bezpečnosti
a informačním soukromí

Část 36 - CW 50/97

Kryptoanalýza -- základní metody

Jan Paseka

2. Kerckhoffův princip. Spolehlivost šifrovacího systému nesmí záviset na utajení algoritmu. Spolehlivost je založena pouze na utajení klíče.

Úlohou kryptoanalýzy, jak již vyplývá z vlastního názvu, je studium metod luštění šifer, tj. zašifrovaných textů, které vzniknou aplikací šifrovacího algoritmu na otevřený text (zprávu). Kryptoanalýza má v podstatě dvojí účel -- slouží nepříteli k prolomení šifry nebo naopak k dokázání míry spolehlivosti použitého šifrovacího algoritmu.

Proto je potřeba před vlastní kryptoanalýzou stanovit její výchozí podmínky. Ty lze pak zjednodušeně (za předpokladu, že kryptoanalytik je obeznámen s použitým šifrovacím algoritmem) popsat následovně:

(1) Znalost pouze šifrovacího textu -- tj. vlastní kryptoanalýzu lze provést pouze na znalosti šifrovacího textu. Přitom v jednoduchých systémech (viz BVK26), jako jsou substituční šifry, lze z celkem krátkého zašifrovaného textu dešifrovat původní zprávu na základě statistických informací o předpokládaném jazyku, ve kterém byl napsán otevřený text (četnost výskytu určitých samohlásek a souhlásek, dvojic či trojic písmen).

(2) Znalost otevřeného textu -- kryptoanalytik zná před vlastním dešifrováním určité otevřené texty spolu s jejich zašifrováním.

(3) Možnost výběru otevřeného textu -- kryptoanalytik má možnost si vybrat určité otevřené texty a obdržet jejich zašifrovanou podobu. Tento případ může nastat, pokud se bude schopen tvářit jako oprávněný uživatel šifrovacího systému. Tento typ útoku je obzvlášť účinný u asymetrických šifrovacích systémů, jestliže je počet možných zašifrovaných zpráv relativně malý. Totiž i informace, že šifrovací text nepatří k určitému otevřenému textu, může být velmi užitečná.

(4) Znalost šifrovacího klíče -- předpokládáme, že kryptoanalytik zná šifrovací algoritmus parametrizovaný klíčem K a pokouší se najít odpovídající dešifrovací algoritmus, aniž by obdržel nějakou zašifrovanou zprávu. Tento přístup je typický pro šifrovací systémy s veřejným klíčem, kde jsou tyto údaje známé. Kryptoanalytik má tedy dostatek času, aby si připravil různé výpočty na dobu vlastního luštění zachyceného zašifrovaného textu. V některých systémech (RSA) lze totiž při obzvlášť velkém štěstí najít přímo dešifrovací algoritmus, pokud umíme "uhádnout" rozklad přirozeného čísla na prvočinitele.

(5) Kryptoanalýza s pomocí násilí, resp. podplacení -- je jedním z nejúčinnějších způsobů útoku, kdy kryptoanalytik použije hrubé násilí či jemnější metody pro získání klíče. Rozumný kryptoanalytik totiž útočí proti nejslabšímu místu, což zpravidla není šifra, ale nevhodná správa klíčů nebo zaměstnanci nedbající na pravidla zachovávání utajení.

Věnujme se případu (1) pro polyabecední šifry Vigenerova typu a základním moderním metodám kryptoanalýzy (ostatní případy budou uvedeny v příštích dílech seriálu). Připomeňme, že polyabecední šifry mají tu vlastnost, že zašifrování písmene (posloupnosti písmen) závisí na jeho poloze v otevřeném textu, na rozdíl od monoabecedních šifer.

Nejstarším a nejznámějším polyabecedním šifrovacím systémem je tzv. Vigenerova šifra (B. de Vigenere, 1523--1596). Na vstupu máme otevřený text -- "NE KAZDE DESIFROVANI JE TAK SNADNE JAKO TOTO ALE RADOST Z VYLUSTENI PRINASEJI VSECHNA I USPESNA DESIFROVANI" a nějaký klíč, řekněme slovo SERIAL (budeme pracovat v abecedě o 26 písmenech bez diakritiky a interpunkcí). Postupně si otevřený text rozdělíme do bloků délky 6 (počet písmen klíčového slova) a pod ně si napíšeme klíčové slovo (pokud je délka posledního bloku menší než 6, napíšeme odpovídající počet písmen klíčového slova).

Šifrování pak probíhá následovně -- písmeno otevřeného textu zašifrujeme tak, že najdeme řádek Vigenerovy tabulky (viz obr 2) označený tímto písmenem a sloupec označený příslušným písmenem klíčového slova ležícím pod písmenem otevřeného textu. Zašifrované písmeno pak leží v průniku těchto dvou. Dešifrování probíhá opačně. Rozdělíme zašifrovaný text na bloky po 6 písmenech (případně až na poslední) a napíšeme pod ně klíčové slovo. Najdeme sloupec označený příslušným písmenem klíčového slova, v něm pak písmeno zašifrovaného textu, které nám určí příslušný řádek, na jehož začátku je naše hledané písmeno otevřeného textu.

NEKAZD EDESIF ROVANI JETAKL EHKEJA KOTOTO ALERAD OSTZVY SERIAL SERIAL SERIAL SERIAL SERIAL SERIAL SERIAL SERIAL FIBIZO WHVAIQ JSMINT BIKIKW WLBNJL CSKWTZ SPVZAO GWKHVJ

LUSTEN IPRINA SEJIVS ECHNAI USPESN ADESIF ROVANI

SERIAL SERIAL SERIAL SERIAL SERIAL SERIAL SERIAL

DYJBEY ATIQNL KIAQVD WGYVAT MWGMSY SHVAIQ JSMINT

Obr. 1

Jakým způsobem provést kryptoanalýzu tohoto šifrového textu za předpokladu, že víme, že byl zašifrován Vigenerovou šifrou? Nejdříve bude třeba odhadnout délku klíče. Za tímto účelem byly vyvinuty dvě metody - Kasiského test (F. W. Kasiski, 1805--1881) a Friedmanův test (1891--1969).

Kasiského test je založen na tom, že si všímáme výskytu dvou stejných slov v šifrovém textu (čím delší slovo, tím lépe). Můžeme pak předpokládat, že rozdíl vzdálenosti těchto slov by mohl být násobek našeho klíče. Jedná se samozřejmě o hypotézu, protože stejná slova nám mohou v šifrovém textu vzniknout i zcela náhodně. V našem příkladu vidíme, že nejdelší se opakující slovo v textu je HVAIQJSMINT a tyto dva výskyty jsou vzdálené o 60 písmen. Délka možného klíče je tedy nějaký dělitel čísla 60.

Friedmanův test nám zase umožňuje odhadnout délku klíče. V tomto testu se ptáme, s jakou pravděpodobností náhodně vybraný pár písmen ze zprávy sestává ze stejných písmen. Máme-li pevně zadán počet písmen zkoumaného textu, lze jednoduchou úvahou spočítat tuto pravděpodobnost, kterou nazveme Friedmanův index koincidence a označíme I.

Mějme nyní náš text napsán v nějakém jazyce, ve kterém známe pravděpodobnosti výskytu pi jednotlivých písmen abecedy. Pak, pro dostatečně dlouhý text, můžeme předpokládat, že pravděpodobnost toho, že vybereme náhodně dvě stejná písmena, je rovna součtu druhých mocnin těchto jednotlivých pravděpodobností. Toto číslo zřejmě závisí pouze na jazyce, ve kterém je daný text napsán. Pro češtinu je toto číslo rovno přibližně 0,058258. Protože víme, že pro každé písmeno klíčového slova jsou všechna písmena zašifrovaná pomocí něj zašifrovaná stejným způsobem, máme zašifrovaný text rozdělen do l stejně se chovajících skupin, kde l je délka klíčového slova. Lze pak odvodit vztah mezi délkou klíčového slova a indexem koincidence zašifrovaného textu a odhadnout tak délku klíčového slova. V našem příkladu se pohybuje v řádu jednotek, což celkem dobře koresponduje se skutečnou délkou klíče vzhledem ke krátké délce zašifrovaného textu.

Předpokládejme tedy, že jsme našli délku klíčového slova l. Pak můžeme zašifrovaný text rozdělit do l částí, z nichž každá má charakteristiky jazyku, ve kterém byl napsán otevřený text. Na každou z těchto částí můžeme použít analýzu nejčastěji se vyskytujících se znaků a provést dešifrování. Z průběhu naší kryptoanalýzy je však vidět, že pokud je otevřený text stejně dlouhý jako klíčové slovo (a klíčové slovo je vytvořeno náhodně), nelze náš postup aplikovat, protože každé písmeno šifrového textu má stejně pravděpodobný výskyt. Jedná se pak o perfektně bezpečnou šifru tj. takovou, že z tvaru zašifrovaného textu nelze nic usoudit o původním otevřeném textu. Perfektní bezpečnost je proto v praxi obtížně dosažitelná, protože buď je nutné pro jedno použití někde uchovávat dlouhý klíč (a to je samozřejmě riziko samo o sobě), nebo je nutno ho předat před vlastním přenosem bezpečně příjemci (ale to bychom mohli udělat i se zprávou samotnou).

Vigenerova šifra se vzhledem k potřebné délce klíče používá hlavně pro diplomatické kanály. Můžeme ji ale použít i pro podstatně delší bloky dat tak, že vygenerujeme řádově 650 MB náhodných bitů na CD-ROM, vytvoříme jeho jedinou kopii a dáme ji příjemci zprávy. Pak můžeme společně bezpečně šifrovat, dokud nevyužijeme tato (pokud možno vhodně naindexovaná, resp. zašifrovaná) data na CD-ROM. Bezpečnost této metody je založena na vytvoření co možná nejvíc náhodné posloupnosti dat -- cokoliv je vytvořeno počítačem, nemůže být nikdy zcela náhodné.

Další známou polyabecední šifrou použitou ve druhé světové válce byla rotorová šifra ENIGMA, první šifra dešifrovaná pomocí jednoduchých obrovských elektromechanických počítacích strojů velikosti šatníkových skříní. Přitom zadními vrátky byla mimo jiné znalost způsobu zápisu stručných meteorologických kódů německého ponorkového námořnictva.

Kryptoanalýza současných šifer se podstatně liší od kryptoanalýzy historických šifer. Zmiňme v krátkosti některé základní postupy. Prvním je podrobné prohledání prostoru možných klíčů (útok s použitím hrubé síly) a jejich ověření, což v případě nejčastěji používané šifry DES vedlo k jejímu prolomení pomocí Internetu. Dále je možné využít některých vad šifrovacích algoritmů, které umožní podstatně zmenšit prostor klíčů, resp. u některých rundových algoritmů použít tzv. middle attack, kdy se v podstatě zmenší počet rund (opakování algoritmu) na polovičku. Přesněji, díváme se pro danou část zašifrované zprávy v prostřední rundě na tu podčást klíče, pro kterou její změna neovlivní žádnou změnu části zašifrované zprávy v žádném směru.

Další používanou variantou je zjištění závislosti bitů zašifrované zprávy na klíči. V případě šifry DES, s menším počtem rund než standardních 16, Biham a Shamir našli útok s možností výběru otevřeného textu pomocí metody diferenciální kryptoanalýzy, který je efektivnější než obvyklý útok s použitím hrubé síly. Přitom diferenciální analýza, zjednodušeně řečeno, je založená na tom, že cíleně zkoumáme určité páry šifrovacích textů a to těch, jejichž otevřené protějšky vykazují určité diference (rozdíly). Pak se postupně zkoumá, jakým způsobem se tyto diference v průběhu šifrovacího algoritmu mění a na tomto zjištění se různým klíčům přiřadí různé pravděpodobnosti. Pokud analyzujeme dostatečně velký počet dvojic, otevřený text -- šifrovací text, obdržíme jeden klíč jako nejpravděpodobnější. Tento klíč je pak hledaný správný klíč.

Dalším kryptoanalytickým útokem je metoda lineární kryptoanalýzy, kdy šifrovací text aproximujeme vhodnou lineární funkcí otevřeného textu, resp. diferenciálně-lineární kryptoanalýza, která je kombinací diferenciální a lineární analýzy. Pro tento typ útoku stačí podstatně menší počet dvojic otevřený text -- šifrovací text, nevýhoda jako u předchozích spočívá v tom, že zůstává omezení na malý počet rund.

Jiným typem útoku je tzv. timing attack založený na přesném změření času potřebném pro operace se soukromým klíčem, neboť šifrovací systém často potřebují podstatně různé množství výpočetní doby pro různé vstupy. Při jeho aplikaci může kryptoanalytik najít exponenty v případě Diffie-Hellmanova algoritmu, faktorizovat RSA klíče a prolomit jiné šifrovací systémy. Přitom v případě zranitelných šifrovacích systémů je tento způsob útoku výpočetně nenáročný a často vyžaduje pouze známý šifrovací text.

Pokud se jedná o napadení hašovacích funkcí použitých v systémech se symetrickými šifrovacími algoritmy k zajištění autenticity a integrity zpráv, rozeznáváme dva základní typy útoku s použitím hrubé síly. V prvním typu útoku by kryptoanalytik rád našel pro hašovací funkci H a hašovací hodnotu zprávy M rovnu H(M), pokud možno smysluplnou zprávu M' tak, že H(M')= H(M). V druhém případě se kryptoanalytik snaží o nalezení dvou náhodných zpráv M a M' tak, že H(M')= H(M). V tomto případě mluvíme o kolizi. Jedná se pak o podstatně snadnější a tedy i rychlejší útok, který je založen na narozeninovém (birthday) paradoxu. Ten říká, že na to, aby alespoň dva lidé z nějaké skupiny měli stejné datum narození, stačí, aby tato skupina měla pouze 23 členů. Speciálně pak pro nalezení zprávy z prvního typu útoku o hašovací hodnotě dlouhé m bitů je třeba projít 2m možností a pro nalezení dvou kolizních zpráv stačí prověřit 2m/2 zpráv. To znamená, že chceme-li pravděpodobnost napadení pomocí kolize mít pod 1 : 2m/2, musíme použít hašovací algoritmus s hašovací hodnotou m.

Všechny tyto metody podstatně závisí na šifrovacím algoritmu, který byl použit pro zašifrování zprávy a neexistuje univerzální postup, jak provádět dešifrování. Vlastní kryptoanalýza není jen suchá matematika, ale i používaní odhadů, apriorních informací, čekání na chybu protivníka, resp. vlastní aktivní jednání umožňující vznik takovéto chyby. V podstatě je každý šifrovací systém prolomitelný, co však je rozhodující, jsou nutné systémové zdroje (stupeň výpočetní techniky, peníze, čas a lidé) potřebné k jeho prolomení. Pokud náklady na tyto zdroje převáží podstatnou měrou cenu vašich utajovaných a dobře chráněných informací, jste v bezpečí.

Seriál je rovněž k dispozici na www.idg.cz/computerworld/bvsk/

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z A
B C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
C D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
E F G H I J K L M N O P Q R S T U V W X Y Z A B C D E
F G H I J K L M N O P Q R S T U V W X Y Z A B C D E F
G H I J K L M N O P Q R S T U V W X Y Z A B C D E F G
H I J K L M N O P Q R S T U V W X Y Z A B C D E F G H
I J K L M N O P Q R S T U V W X Y Z A B C D E F G H I
J K L M N O P Q R S T U V W X Y Z A B C D E F G H I J
K L M N O P Q R S T U V W X Y Z A B C D E F G H I J K
L M N O P Q R S T U V W X Y Z A B C D E F G H I J K L
M N O P Q R S T U V W X Y Z A B C D E F G H I J K L M
N O P Q R S T U V W X Y Z A B C D E F G H I J K L M N
O P Q R S T U V W X Y Z A B C D E F G H I J K L M N O
P Q R S T U V W X Y Z A B C D E F G H I J K L M N O P
Q R S T U V W X Y Z A B C D E F G H I J K L M N O P Q
R S T U V W X Y Z A B C D E F G H I J K L M N O P Q R
S T U V W X Y Z A B C D E F G H I J K L M N O P Q R S
T U V W X Y Z A B C D E F G H I J K L M N O P Q R S T
U V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
V W X Y Z A B C D E F G H I J K L M N O P Q R S T U V
W X Y Z A B C D E F G H I J K L M N O P Q R S T U V W
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W X
Y Z A B C D E F G H I J K L M N O P Q R S T U V W X Y
Z A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Obr 2: Vigenerova tabulka


| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage |