╚ßst 29 - CW 40/97

IDEA & kol. -- samΘ rozumnΘ myÜlenky

èifrovacφ algoritmus DES byl v relativn∞ krßtkΘm Φase zlomen skupinou amatΘr∙. ZaΦφnß b²t mimo veÜkerou pochybnost, ₧e tento algoritmus ji₧ doÜel na konec svΘ kariΘry. Nask²tß se otßzka, co bude dßl.

Zem°el krßl, kolem obchßzφ anarchie

Ne, ₧e by DES byl ·pln∞ k niΦemu a dobr² leda na smetiÜt∞. Jde o lety prov∞°en² algoritmus, na jeho₧ prolomenφ bylo vynalo₧eno obrovskΘ ·silφ - s pon∞kud huben²mi v²sledky. V²kon poΦφtaΦ∙ se vÜak nebezpeΦn∞ p°iblφ₧il k mezφm bezpeΦnosti, kterou je DES schopen poskytovat. A tak, zatφmco m∙₧eme nechat v klidu do₧φt aplikace, kterΘ tento algoritmus pou₧φvajφ, m∞li bychom se poohlΘdnout po "n∞Φem lepÜφm", co se stane srdcem naÜich p°φÜtφch systΘm∙.

ProblΘmem nalezenφ novΘho bezpeΦn∞jÜφho symetrickΘho algoritmu, kter² by mohl zastoupit DES, se naÜt∞stφ ji₧ °adu let zab²vajφ odbornφci po celΘm sv∞t∞. Bylo navr₧eno velkΘ mno₧stvφ nejr∙zn∞jÜφch algoritm∙. MnohΘ z nich se zdajφ b²t velmi kvalitnφ. Zatφm se vÜak ₧ßdn² z nich nestal vÜeobecn∞ p°ijφman²m standardem.

Opravdu d∙kladn² zmatek do celΘ situace zanesla americkß vlßda svojφ snahou prosadit zavedenφ algoritmu Skipjack jako₧to novΘho pr∙myslovΘho standardu. ┌skalφ spoΦφvalo v tom, ₧e tento algoritmus nebyl ve°ejn∞ publikovßn a informace o n∞m jsou dodnes velice kusΘ.

Kudy, kudy cestiΦka

P°ed tφm, ne₧ se budeme blφ₧e v∞novat vybran²m Üifrovacφm algoritm∙m, poj∩me se podφvat obecn∞, jakΘ jsou souΦasnΘ trendy nßvrhu symetrick²ch Üifer. ZaΦneme p∞kn∞ od Adama, resp. od DESu.

Zßkladnφm nedostatkem DESu je nedostateΦnß dΘlka klφΦe, umo₧≥ujφcφ zlomenφ algoritmu prostou hrubou silou. NovΘ algoritmy tedy pou₧φvajφ klφΦ o dΘlce a₧ n∞kolikanßsobn∞ delÜφ. Poznamenejme, ₧e nap°. na rozdφl od algoritmu RSA, zv∞tÜovßnφ dΘlky klφΦe v p°φpad∞ symetrick²ch Üifer v∞tÜinou nemß negativnφ dopad na rychlost procesu (de)Üifrovßnφ.

DES byl p∙vodn∞ navrhovßn spφÜe s ohledem na mo₧nost hardwarovΘ implementace pomocφ specißlnφch obvod∙. Ne ka₧d² si vÜak chce, nebo m∙₧e dovolit koupit pro ·Φely Üifrovßnφ zvlßÜtnφ technickΘ za°φzenφ. P°itom pou₧φvßnφ kryptografie se stßvß nezbytnostφ i pro b∞₧nΘho laickΘho u₧ivatele. Nastßvß tedy z°eteln² trend navrhovat algoritmy s ohledem na mo₧nost efektivnφ softwarovΘ implementace na b∞₧n∞ dostupnΘm hardwaru. Algoritmy se sna₧φ v co nejÜirÜφ mφ°e pou₧φvat jednoduchΘ operace p°φmo obsa₧enΘ v instrukΦnφch souborech procesor∙. PovÜimn∞me si, ₧e veÜkerΘ operace se vykonßvajφ nad °et∞zci dΘlky 32, nebo dokonce 16 bit∙, co₧ p°esn∞ odpovφdß velikosti registr∙.

Pro ·Φely softwarovΘ implementace je zvlßÜt∞ nevhodnΘ pou₧φvßnφ bitov²ch permutacφ. Ty jsou nahrazovßny vstupy °φzen²mi v²b∞ry z tabulek (table lookup), kterΘ majφ obdobnΘ difuznφ ·Φinky.

Rovn∞₧ paralelnφ pou₧itφ S-box∙ - podobn∞ jako v DESu -- je nahrazovßno sekvenΦnφm. Pokud algoritmus pou₧φvß S-boxy, nebo jejich obdobu, b²vajφ S-boxy zpravidla podstatn∞ v∞tÜφ, ne₧ v p°φpad∞ DESu. Zv∞tÜenφ S-box∙ p°inßÜφ zv²Üenφ odolnosti proti diferencißlnφ kryptoanal²ze. DalÜφho zv²Üenφ odolnosti proti diferencißlnφ a lineßrnφ kryptoanal²ze lze docφlit, pokud S-boxy nejsou konstantnφ, tj. je-li jejich obsah zßvisl² na Üifrovacφm klφΦi.

DalÜφm trikem, kter² vede ke zv²Üenφ odolnosti algoritmu, je kombinovßnφ operacφ z r∙zn²ch algebraick²ch grup (nap°. XOR a sΦφtßnφ mod 2¹⁶, nßsobenφ mod 2¹⁶ + 1).

Naopak z kryptografickΘho hlediska bezcennΘ jsou ·vodnφ a zßv∞reΦnß permutace, kterΘ DES realizuje. V soudob²ch Üifrovacφch algoritmech je proto ji₧ nepotkßme.

Zm∞nil se rovn∞₧ zp∙sob generovßnφ subklφΦ∙ pro jednotlivß kola prßce algoritmu. P°ed zahßjenφm vlastnφho de/Üifrovßnφ provßd∞jφ algoritmy zvlßÜtnφ inicializaΦnφ proces. B∞hem n∞ho si vygenerujφ tabulku vÜech subklφΦ∙, S-box∙ a p°φpadn∞ dalÜφch datov²ch struktur, kterΘ pro svoji Φinnost pot°ebujφ. ╚as spot°ebovan² na inicializaci je nßsledn∞ v²hodn∞ amortizovßn v pr∙b∞hu Üifrovßnφ. Velkß Φasovß nßroΦnost procesu generovßnφ subklφΦ∙ m∙₧e b²t v²hodnß, nebo¥ zvyÜuje odolnost algoritmu proti ·toku hrubou silou.

Mal² kryptografick² herbß°

V tΘto Φßsti si ukß₧eme t°i souΦasnΘ Üifrovacφ algoritmy. Ka₧d² z nich mß dostateΦn² potencißl, aby mohl poslou₧it jako mezinßrodnφ standard. VÜechny uvedenΘ algoritmy byly sv²mi tv∙rci p°edlo₧eny odbornΘ ve°ejnosti k oponentu°e. Dosud vÜak nenφ znßm ·sp∞Ün² ·tok proti n∞kterΘmu z nich, co₧ dßvß rozumnou nad∞ji, ₧e jde o opravdu kvalitnφ Üifry.

IDEA

Autory algoritmu publikovanΘho v roce 1991 p∙vodn∞ pod nßzvem IPES byli X. Lai a J. Massey. SouΦasn² nßzev je akronymem za International Data Encryption Algorithm. Jde o blokovou Üifru s dΘlkou bloku 64 bit∙, pracujφcφ s klφΦem o dΘlce 128 bit∙. IDEA vznikla jako vylepÜenß verze svΘho p°edch∙dce, algoritmu PES potΘ, co byla publikovßna metoda jeho zlomenφ.

IDEA ji₧ zaΦala ·sp∞Ün∞ pronikat do praxe, velmi pravd∞podobn∞ ji pou₧φvßte i vy. A¥ ji₧ v rßmci protokolu SSL, kter² pou₧φvajφ t°eba webovΘ browsery, nebo jako souΦßst populßrnφho PGP.

Blok otev°enΘho textu je rozd∞len na Φty°i Φßsti, ka₧dß o dΘlce Üestnßct bit∙. PotΘ je provedeno osm kol Üifrovacφho procesu. V ka₧dΘm kole jsou jednotlivΘ bloky XORovßny, nßsobeny a sΦφtßny mezi sebou navzßjem a Üesti Üestnßctibitov²mi subklφΦi. Na zßv∞r je jeÜt∞ ka₧d² blok kombinovßn s jednφm subklφΦem. Strukturu jednoho kola Üifrovacφho procesu a zßv∞reΦnΘ fßze ukazuje obr. 1.

Algoritmus pou₧ije celkem 52 subklφΦ∙. Ty jsou z klφΦe odvozeny nßsledujφcφm zp∙sobem. Rozd∞lenφm klφΦe na osm Φßstφ vznikne prvnφch osm subklφΦ∙. PotΘ je provedena rotace klφΦe vlevo o 25 bit∙. Vznikl² °et∞zec je op∞t rozd∞len na osm Φßstφ -- subklφΦ∙. Opakovßnφm tohoto postupu zφskßme pot°ebnΘ mno₧stvφ subklφΦ∙.

Pro deÜifrovßnφ se pou₧φvß stejnΘho algoritmu jako pro Üifrovßnφ. Rozdφl je pouze v pou₧it²ch subklφΦφch. P°edpoklßdejme, ₧e pro Üifrovßnφ pou₧ijeme v i-tΘm (i = 1,  ..., 8) kole klφΦ∙

Z₁⁽ⁱ⁾, Z₂⁽ⁱ⁾, Z₃⁽ⁱ⁾, Z₄⁽ⁱ⁾, Z₅⁽ⁱ⁾, Z₆⁽ⁱ⁾

a v zßv∞reΦnΘ fßzi Z₁⁽⁹⁾, Z₂⁽⁹⁾, Z₃⁽⁹⁾, Z₄⁽⁹⁾,

vygenerovan²ch postupem popsan²m v p°edchozφm odstavci. Potom pro deÜifrovßnφ pou₧ijeme klφΦ∙ ve tvaru

Z₁^{(10 - i)} - 1, -Z₂^{(10 - i)}, -Z₃^{(10 - i)}, Z₄^{(10 - i)} - 1, Z₅^{(9 - i)}, Z₆^{(9 - i)}

a v zßv∞reΦnΘ fßzi Z₁⁽¹⁾ - 1, -Z₂⁽¹⁾, -Z₃⁽¹⁾, Z₄⁽¹⁾ -- 1.

IDEA m∙₧e b²t pou₧φvßna v libovolnΘm pracovnφm modu pro blokovΘ Üifry, zejmΘna v modech ECB, CBC, OFB, CFB, ve kter²ch b²vß pou₧φvßn DES. Pokud by n∞kdo byl velmi podezφrav² a nespokojil se s dΘlkou klφΦe 128 bit∙, m∙₧e pou₧φvat trojnßsobnΘ Üifrovßnφ EDE Triple-IDEA. P°i tomto postupu pot°ebujeme dva 128bitovΘ klφΦe. Otev°en² text je nejprve zaÜifrovßn prvnφm klφΦem, v²sledek je deÜifrovßn druh²m klφΦem a na zßv∞r je blok znovu Üifrovßn prvnφm klφΦem. Je mo₧nΘ vynechat proces generovßnφ subklφΦ∙ a mφsto toho pou₧φt 52 nezßvisl²ch °et∞zc∙. Tφmto zp∙sobem pravd∞podobn∞ nedojde k oslabenφ algoritmu.

Je zajφmavΘ, ₧e pokud bychom algoritmus upravili tak, ₧e zv∞tÜφme dΘlku vÜech °et∞zc∙, se kter²mi pracuje, na dvojnßsobek, dojde ke ztrßt∞ bezpeΦnosti.

Blowfish

B. Schneier algoritmus publikoval v roce 1993. Jde o blokovou Üifru s dΘlkou bloku 64 bit∙. Algoritmus pracuje s klφΦi r∙znΘ dΘlky a₧ do maximßlnφ velikosti klφΦe 448 bit∙. Jeho v²hodou je, ₧e na rozdφl od vÜech ostatnφch popisovan²ch algoritm∙ nenφ patentovßn a je tedy mo₧nΘ jej voln∞ pou₧φvat. Jde o velmi rychl², jednoduch² algoritmus, kter² je mo₧no efektivn∞ implementovat i na mal²ch procesorech, nebo dokonce Φipov²ch kartßch. P°i peΦlivΘm naprogramovßnφ se to vÜechno vΦetn∞ vÜech sv²ch datov²ch struktur vejde do internφ cache procesoru i486.

Pokud pou₧φvßte Secure shell, co₧ je jeden z mßla prost°edk∙ umo₧≥ujφcφch bezpeΦn² vzdßlen² p°φstup k unixov²m stroj∙m, m∙₧ete k Üifrovßnφ komunikace pou₧φt prßv∞ Blowfish.

Blok otev°enΘho textu je nejprve rozd∞len na dv∞ poloviny. Nßsleduje Üestnßct kol Üifrovacφho procesu. V i-tΘm kole je levß polovina XORovßna s i-t²m subklφΦem. Nßsledn∞ je pou₧ita jako vstup pro v²poΦet ireverzibilnφ funkce. P°i v²poΦtu tΘto funkce se uplatnφ Φty°i na klφΦi zßvislΘ S-boxy se vstupem o Üφ°i 8 bit∙ a operace sΦφtßnφ a XOR. V²sledek tΘto funkce je XORovßn s pravou polovinou. Na konci kola jsou ob∞ poloviny prohozeny. V zßv∞reΦnΘ fßzi jsou z technick²ch d∙vod∙ op∞t prohozeny ob∞ poloviny. Ka₧dß z nich je potom XORovßna s dalÜφm subklφΦem. Strukturu jednoho kola Üifrovacφho procesu a zßv∞reΦnΘ fßze ukazuje obr. 2.

Algoritmus ke svΘ Φinnosti pou₧φvß pole 18 subklφΦ∙ a Φty°i na klφΦi zßvislΘ S-boxy. Tyto struktury jsou p°ipraveny p°i inicializaci algoritmu. Nejprve jsou pole subklφΦ∙ a vÜechny S-boxy vypln∞ny konstantnφm °et∞zcem -- auto°i doporuΦujφ pou₧φt Φßst zßpisu Ludolfova Φφsla. Potom je postupn∞ obsah pole subklφΦ∙ a S-box∙ XORovßn klφΦem - k tomu m∙₧eme pou₧φvat klφΦe r∙zn²ch dΘlek. Kdy₧ takto vyplnφme vÜechny °φdicφ struktury algoritmu, provedeme zaÜifrovßnφ bloku sam²ch nul. V²sledek tohoto kroku ulo₧φme do pole subklφΦ∙ na mφsto prvnφho a druhΘho subklφΦe. Zφskan² °et∞zec znovu zaÜifrujeme a ulo₧φme jej na mφsto t°etφho a ΦtvrtΘho subklφΦe. Opakovßnφm tohoto postupu postupn∞ vyplnφme vÜechny subklφΦe a vÜechny Φty°i S-boxy. Tφm je algoritmus p°ipraven k Üifrovßnφ.

DeÜifrovßnφ je stejnΘ jako Üifrovßnφ, pouze jednotlivΘ subklφΦe jsou pou₧φvßny v opaΦnΘm po°adφ.

Algoritmus je op∞t pou₧iteln² ve vÜech b∞₧n²ch pracovnφch modech vhodn²ch pro blokovΘ Üifry. Mφru dosa₧enΘ bezpeΦnosti lze regulovat dΘlkou pou₧itΘho klφΦe. Rovn∞₧ lze omezit poΦet kol Üifrovacφho procesu. Snφ₧enφ poΦtu kol vede k jistΘmu snφ₧enφ odolnosti v∙Φi lineßrnφ a diferencißlnφ kryptoanal²ze, v²hodou je ovÜem vyÜÜφ rychlost Üifrovßnφ. Naopak se nezdß, ₧e by dalÜφ zvyÜovßnφ poΦtu kol m∞lo zßsadnφ vliv na zv²Üenφ bezpeΦnosti algoritmu.

RC5

Se svojφ troÜkou do ml²na p°isp∞chal v roce 1994 i R. Rivest, znßm² jako spoluautor algoritmu RSA. RC5 p°inßÜφ novou myÜlenku pou₧itφ rotacφ zßvisl²ch na datech. Jde o velmi pru₧n² algoritmus s celou °adou parametr∙. Krom∞ dΘlky Üifrovacφho klφΦe (0 a₧ 255 byt∙) lze nastavit poΦet kol Üifrovacφho procesu (op∞t 0 a₧ 255). Z hodnot 16, 32, 64, ale i vyÜÜφch m∙₧eme zvolit dΘlku slova, p°iΦem₧ algoritmus zpracovßvß bloky o dΘlce dvojnßsobku slova.

I tento algoritmus ji₧ naÜel svΘ praktickΘ vyu₧itφ. M∙₧eme jej potkat t°eba ve webow²ch browserech. Bohu₧el se stal ob∞tφ exportnφ politiky americkΘ vlßdy. Zatφmco obΦanΘ Spojen²ch stßt∙ a Kanady se mohou t∞Üit jeho plnΘ ochran∞, mezinßrodnφ verze program∙ jsou dodßvßny s um∞l²m omezenφm dΘlky klφΦe na 40 tajn²ch bit∙. Ostatnφ bity klφΦe jsou znßmΘ. Prosl²chß se, ₧e firm∞ Netscape se poda°ilo zφskat povolenφ pou₧φvat v mezinßrodnφ verzi svΘho Navigatoru klφΦ s 56 tajn²mi bity.

RC5 je takovß parßda, ₧e to ani slovy nelze vylφΦit. Pom∙₧eme si proto zßpisem pomocφ pseuk≤du, kter² je podobn² jazyku C. Zde znak 0+0 oznaΦuje bitovΘ XOR, + znaΦφ sΦφtßnφ modulo dΘlka slova, -- odΦφtßnφ, x <- y znamenß rotaci °et∞zce x vlevo o y bit∙ a symbol -> pou₧φvßme pro rotaci opaΦn²m sm∞rem. Samoz°ejm∞, smysl mß provßd∞t pouze rotaci o y mod (dΘlka slova), vÜe ostatnφ je pouze zbyteΦnΘ "obφhßnφ okolo".

P°edpoklßdejme prozatφm, ₧e mßme k dispozici pole subklφΦ∙ S. Nech¥ se blok otev°enΘho textu sklßdß ze dvou Φßstφ A a B. èifrovßnφ probφhß dle nßsledujφcφho p°edpisu:

A = A + S[0];

B = B + S[1];

for i = 1 to <poΦet_kol> do

A = ((A 0+0 B) <- B) + S[2i];

B = ((B 0+0 A) <- A) + S[2i + 1];

Pro deÜifrovßnφ je tentokrßt t°eba pou₧φt postupu pon∞kud odliÜnΘho, ne₧ pro Üifrovßnφ:

for i = <poΦet_kol> downto 1 do

B = ((B -- S[2i + 1]) -> A) 0+0 A);

A = ((A -- S[2i]) -> B) 0+0 B);

B = B -- S[1];

A = A -- S[0];

Zb²vß popsat, jak²m zp∙sobem zφskßme ze Üifrovacφho klφΦe pole subklφΦ∙ S. K tomu budeme pot°ebovat pomocnΘ pole L o velikosti tolik slov, aby se do n∞j "veÜel" klφΦ a dv∞ magickß Φφsla:

Pw = Odd((e -- 2)2^w) a

Qw = Odd((fφ -- 2)2^w)

kde e je zßklad p°irozenΘho logaritmu (2,718281...), fφ je tzv. zlat² °ez (1,618033...) a w znaΦφ dΘlku slova. Funkce Odd vracφ nejbli₧Üφ lichΘ celΘ Φφslo.

Do pole L zkopφrujeme od zaΦßtku Üifrovacφ klφΦ, a na konci p°φpadn∞ doplnφme nulami. Pole S naplnφme dle p°edpisu

S[0] = P_w;

for i = 1 to 2 * (<poΦet_kol> + 1) -- 1 do

S[i] = S[i -- 1 + Q_w];

a proces generovßnφ subklφΦ∙ dokonΦφme promφchßnφm obou polφ:

i = j = 0;

A = B = 0;

for k = 1 to 3 * max(s, l) do

A = S[i] = (S[i] + A + B) <- 3;

B = L[j] = (L[j] + A + B) <- (A + B );

i = (i + 1) mod(s);

j = (j + 1) mod(l);

kde s resp. l jsou velikosti polφ S, resp. L.

Pro svΘ pou₧itφ lze algoritmus p°izp∙sobit vhodnou volbou parametr∙. Velikost slova je rozumnΘ volit v zßvislosti na velikosti slova pou₧φvanΘho procesoru, 128 bit∙ je to sprßvnΘ Φφslo, chceme-li algoritmus pou₧φvat pro haÜovßnφ. Zv∞tÜovßnφ poΦtu kol vede ke zvyÜovßnφ bezpeΦnosti algoritmu na ·kor rychlosti. èest kol postaΦφ pro nenßroΦnΘ aplikace, 32 pro ty nejnßroΦn∞jÜφ. Samoz°ejm∞, Φφm delÜφ klφΦ, tφm lepÜφ, ale nezapome≥te, ₧e jej takΘ musφte vygenerovat, dopravit na mφsto urΦenφ a tam uskladnit. Prakticky je jedno, jestli ·toΦnφk p°ed sebou mß 10³⁰, nebo 10⁵⁰ rok∙ usilovnΘho poΦφtßnφ. Jako rozumnß se jevφ volba dΘlka slova 32 bit∙, 12 kol, 16bytov² klφΦ, co₧ krßtce zapφÜeme RC5-32/12/16.

Na dobrou noc

ProblΘm nalezenφ vhodnΘho standardu je opravdu velmi palΦiv². KomerΦnφ organizace musφ investovat nemalΘ ·silφ a finanΦnφ Φßstky do v²m∞ny technologie. Zm∞na musφ b²t provedena vÜude, aby jednotlivΘ firmy byly schopny mezi sebou komunikovat. Vzhledem k jejφ mimo°ßdnΘ nßroΦnosti nenφ Φas na pokusy. Nezb²vß nßm ne₧ v∞°it, ₧e se poda°φ najφt voln∞ distribuovateln², dostateΦn∞ bezpeΦn² a d∙v∞ryhodn² algoritmus v co nejkratÜφ dob∞. Myslete na to.