╚ßst 36 - CW 50/97

Kryptoanal²za -- zßkladnφ metody

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

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 2^m mo₧nostφ a pro nalezenφ dvou koliznφch zprßv staΦφ prov∞°it 2^m/2 zprßv. To znamenß, ₧e chceme-li pravd∞podobnost napadenφ pomocφ kolize mφt pod 1 : 2^m/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