MARS je jedním z p╪ti kandidátà na Advanced Encryption Standard (AES). O celém v∞b╪rovém ²ízení se podrobn╪ji dozvíte v úvodu k této sérii struƒn∞ch popisà vτech finalistà, a to v ƒlánku "Bitva o tràn vrcholí" v Chipu 10/99; zde se uº v╪nujeme p²ímo technickému popisu τifry. P²ipomeσme jen, ºe AES se stane τifrovacím standardem pro p²íτtí století (nebo alespoσ pro n╪jaká ta desetiletí) a bude mít dalekosáhl∞ vliv na poƒítaƒovou bezpeƒnost.
P²edstavujeme kandidáty na AES:
µifra MARS
Blokovou τifru MARS p²ihlásila do sout╪ºe spoleƒnost IBM a algoritmus navrhl její jedenáctiƒlenn∞ autorsk∞ kolektiv. P²ipomeσme, ºe τifra pracuje se 128bitov∞m vstupem a v∞stupem a délka jejího klíƒe je voliteln╪ 16, 24 nebo 32 bajtà. MARS pracuje se slovy o 32 bitech a vychází z osv╪dƒen∞ch kryptografick∞ch operací, které obohacuje n╪kolika nov∞mi zajímav∞mi myτlenkami. Pat²í k nim nap²íklad teze, ºe st²ed algoritmu má v╪tτí v∞znam neº jeho zaƒátek a konec. To sice vypadá dost astrologicky, ale u schémat konkrétních typà to vskutku má své opodstatn╪ní.
Jin∞m v∞znamn∞m rysem je vyuºití tzv. Feistelova schématu typu 3 tak, ºe v kaºdé rund╪ jedno datové slovo ze ƒty² (ev. klíƒov∞ materiál) ovlivσuje zb∞vající t²i datová slova (viz obr. 2) - to je zásadní rozdíl od ƒastého principu, kdy se práv╪ obdrºené nejsloºit╪jτí slovo okamºit╪ pouºije k modifikaci dalτího slova. Tento princip také umoºnil návrhá²àm podpo²it dàkazy kvality τifry. Její dalτí velmi podstatnou vlastností je skuteƒnost, ºe zaτifrování i odτifrování se provádí na stejném hardwaru - ob╪ ƒinnosti se liτí pouze v opaƒném ²azení rundovních klíƒà (jako u DES).
Postup p²i zaτifrování
Oznaƒíme-li registry (slova) A a B, pak MARS vyuºívá operací A+B, A-B, A?B, A*B, to znamená operací sƒítání, odƒítání, XOR a násobení slov (aº na XOR vτe v modulu 232), a dále cyklické rotace bità slova A doleva (resp. doprava), A<<<B (resp. A>>>B), o poƒet bità r dan∞ p╪ti nejniºτími bity obsaºen∞mi v registru B (r = B AND 0x1F).
P²i zaτifrování se nejprve ze τifrovacího klíƒe (pole k[]) vytvo²í rundovní klíƒe (pole K[]). Otev²en∞ text se naplní do ƒty² datov∞ch registrà (pole D[]) a potom prob╪hnou operace zaτifrování podle pseudokódu na obrázku 2: nejprve se na data naƒtou první ƒty²i rundovní klíƒe K[0..3], pak prob╪hne dop²edné mixování (bez úƒasti klíƒe), poté kryptografické jádro o 16 rundách (zde se zásadn╪ vyuºije 16*2 rundovních klíƒà K[4..35] a funkce E, viz obr. 1), pak následuje zp╪tné mixování a nakonec p²ekrytí dat rundovními klíƒi K[36..39] (tzv. "whitening" s operací "-").
Substituƒní tabulky
Ve schématu se ve fázi dop²edného a zp╪tného mixování pouºívá dvoukilobajtové pole S. Je to pevná substituƒní tabulka, která byla vygenerována tak, aby co nejvíce zabraσovala lineární a diferenciální kryptoanal∞ze. Popis její tvorby je dosti sloºit∞ a je obsaºen v základním dokumentu definujícím MARS (viz infotipy). S je vyuºíváno bu╘ jako jedna tabulka "9 na 32 bità" (tj. 29 32bitov∞ch poloºek), nebo jako dv╪ tabulky S0 a S1 "8 na 32 bità" uloºené za sebou.
Zpracování klíƒe
Auto²i akceptovali p²ipomínku vzeτlou z ve²ejné diskuse a zm╪nili pàvodní expanzi klíƒe. µifrovací klíƒ o n slovech (AES vyºaduje n = 4, 6 a 8, MARS je definován i pro n = 4..14) je napln╪n do pomocného pole T o 16 slovech. Poté se ve ƒty²násobném cyklu obsah pole T vºdy nejprve lineárn╪ transformuje, naƒeº se promíchá s obsahem tabulky S. ¼ást meziv∞sledku se pak uloºí do pole rundovních klíƒà - slov K[0...39] - viz obr. 3. Po ukonƒení hlavního cyklu se upraví klíƒe K[5, 7, 9, ..., 35], které se v expanzní funkci E pouºívají k násobení. Θprava je op╪t znaƒn╪ komplikovaná a jejím úƒelem je zabránit pouºití slab∞ch klíƒà.
Implementace a rychlost
Souƒasné implementace τifry MARS v jazyce C dosahují τifrovací rychlosti 65 aº 85 Mb/s (na 200MHz PC) a v hardwaru lze oƒekávat rychlost asi desetkrát vyττí. Pokud se MARS realizuje v 32bitovém asembleru, pak se projeví v∞hoda 32bitov∞ch operací a τifrování 128bitového bloku spot²ebuje cca 375 hodinov∞ch cyklà. Na "smart kartách" s osmibitov∞m procesorem a taktem 20 MHz lze oƒekávat rychlost τifrování cca 500 Kb/s. Pam╪£ové nároky p²edstavují n╪co p²es 160 bajtà RAM (na klíƒ K) a 2 KB ROM (na S a na dalτí konstanty).
Bezpeƒnost
Návrhá²i v╪novali velkou pozornost dàkazàm o kvalit╪ stavebních blokà schématu i lineární a diferenciální kryptoanal∞ze. Protoºe vτak schéma pro zaτifrování i odτifrování (v hardwaru) je stejné, hrají zde v∞znamnou roli tzv. slabé klíƒe (dvojím zaτifrováním se obdrºí pàvodní data). Tvorba rundovních klíƒà zde sice nezaruƒuje, ºe se náhodn╪ nevytvo²í slabé klíƒe, ale tato pravd╪podobnost je zcela mizivá. U rundovních klíƒà, kter∞mi se násobí datová slova, je zaruƒeno, ºe data nedegenerují.
Záv╪r
MARS je robustním algoritmem s velmi dobr∞m a ov╪²en∞m kryptografick∞m zázemím. P²ipomeσme jen, ºe IBM tuto ve²ejnou sout╪º jiº p²ed 25 lety vyhrála s algoritmem DES; MARS sice t╪ºí z kryptoanal∞zy zaloºené de facto na DES, ale oproti ní je nesrovnateln╪ bezpeƒn╪jτí.
Vlastimil Klíma (vklima@decros.cz)
Infotipy:
Zdrojové kódy v C, ASM:
ftp://ftp.funet.fi/pub/crypt/
cryptography/symmetric/MARS/
Popis vƒetn╪ inovované p²ípravy klíƒe:
http://csrc.nist.gov/encryption/aes/aes_home.htm
RIJNDAEL je jedním z p╪ti kandidátà na Advanced Encryption Standard (AES). O celém v∞b╪rovém ²ízení se podrobn╪ji dozvíte v úvodu k této sérii struƒn∞ch popisà vτech finalistà, a to v ƒlánku "Bitva o tràn vrcholí" v Chipu 10/99; zde se uº v╪nujeme p²ímo technickému popisu τifry. P²ipomeσme jen, ºe AES se stane τifrovacím standardem pro p²íτtí století (nebo alespoσ pro n╪jaká ta desetiletí) a bude mít dalekosáhl∞ vliv na poƒítaƒovou bezpeƒnost.
µifra RIJNDAEL
Blokovou τifru RIJNDAEL p²ihlásili do sout╪ºe známí kryptologové Joan Daemen a Vincent Rijmen. Aƒkoliv jejich τifra podporuje i v╪tτí bloky, pro AES je délka vstupního a v∞stupního bloku definována jako 128 bità. Délka klíƒe je voliteln╪ 128, 192 a 256 bità, coº je Nk (= 4, 6 nebo 8) 32bitov∞ch slov.
RIJNDAEL je velmi flexibilní. I kdyº jeho popis uvedeme v bajtech, lze jej elegantn╪ zapsat i v 32bitov∞ch slovech. Návrh je p²ímoƒar∞ a za základ jsou pouºity operace v ràzn∞ch algebraick∞ch strukturách. Pracuje se s prvky Galoisova t╪lesa GF(28) a s polynomy, jejichº koeficienty jsou prvky z GF(28). P²ísluτné operace s nimi lze provád╪t bu╘ tabulkov╪, nebo v∞poƒtem p²ímo, coº je v prvním p²ípad╪ v∞hodné pro implementaci softwarovou a v druhém p²ípad╪ pro hardwarovou. Bajtov╪ orientovan∞ návrh také umoºσuje optimalizovat programov∞ kód pro ràzné mikroprocesory. Pro operace zaτifrování a odτifrování sice není moºné vyuºít úpln╪ totoºn∞ hardware (jako tomu bylo u τifry MARS), znaƒnou ƒást jeho prvkà vτak pouºít lze.
Neº p²istoupíme k základním operacím, vysv╪tlíme si nejnutn╪jτí pojmy. Prvky v Galoisov╪ t╪lese GF(28) mají osm bità (b7, ..., b0), nereprezentují vτak bajty, n∞brº polynomy (b7x7 + ... + b1x1 + b0). Násobení t╪chto prvkà je proto zavedeno nikoli jako násobení bajtà, ale jako násobení jim odpovídajících polynomà, a to modulo m(x) = x8 + x4 + x3 + x1 + 1.
Takºe nap²íklad ∩57∩ (v apostrofech píτeme b╪ºné hexadecimální vyjád²ení bità b7, ..., b0) krát ∩83∩ je rovno ∩C1∩, nebo£
RIJNDAEL pracuje v rundách. Jejich poƒet Nr = 10, 12 a 14 je urƒen podle toho, jak dlouh∞ je τifrovací klíƒ, a odpovídá hodnotám Nk = 4, 6 a 8. Pro delτí klíƒ se tedy pouºije více rund. P²ed operací zaτifrování (nebo v jejím pràb╪hu, tzv. "on-the-fly") se vypoƒítá 4 + Nr*4 rundovních klíƒà (32bitov∞ch slov). První ƒty²i se "naxorují" na otev²en∞ text (tzv. "whitening"). Potom prob╪hne Nr rund a v kaºdé z nich se pouºijí 4 rundovní klíƒe. Na poƒátku se 16 bajtà otev²eného textu naplní postupn╪ po sloupcích (tj. shora dolà a zleva doprava) do matice bajtà A = (aij) i=0..3, j=0..3 a na n╪ se ve stejném po²adí postupn╪ "naxoruje" 16 bajtà tvo²ících první ƒty²i rundovní klíƒe.
Poté prob╪hne Nr rund podle pseudokódu na obr. 1, kde "State" znamená stav matice A. P²ipomeσme, ºe prvky matice A jsou sice bajty, ale p²i násobení jsou chápány jako prvky GF(28). "Sƒítání" t╪chto prvkà (p²i operaci MixColumn) je b╪ºná operace XOR. V∞sledn∞ τifrov∞ text se op╪t vybírá po sloupcích z matice A.
Hlavní transformace
Vτechny rundy jsou stejné, aº na poslední, kde je malá zm╪na - neprovádí se operace mixování MixColumn. Nyní k jednotliv∞m operacím z obrázku 1:
ByteSub je bajtová substituce (a?b), kterou aplikujeme na kaºd∞ bajt ai, j matice A. Nejprve vypoƒteme multiplikativní inverzi prvku a, tj. c = a-1 mod m(x), a poté bajt c transformujeme na b substitucí S podle obr. 1. Substituci nemusíme poƒítat podle tohoto vzorce, ale màºeme si ji uloºit jako pevnou tabulku.
ShiftRow vykoná v matici A cyklickou rotaci jejích prvkà v jednotliv∞ch ²ádcích doleva, a to tak, ºe první ²ádek ponechá beze zm╪ny, druh∞ rotuje o jednu pozici, t²etí o dv╪ a ƒtvrt∞ o t²i pozice.
MixColumn zesloºití prvky v rámci kaºdého sloupce matice A. Vstupem této transformace jsou vτechny prvky daného sloupce (na obrázku je oznaƒen a) a v∞stupem jejich nové hodnoty (b). Tak bude nap²íklad b0 = ∩02∩*a0 ? ∩03∩*a1 ? ∩01∩*a2 ? ∩01∩*a3.
Nakonec se operací AddRoundKey na prvky matice A (op╪t po sloupcích) "naxorují" po ²ad╪ jednotlivé bajty ƒty² rundovních klíƒà, které jsou na ²ad╪. A to je celé.
Odτifrování probíhá trochu jinak neº zaτifrování, ale vyuºívá jeho stavební prvky (popis je uveden v hlavním dokumentu popisujícím τifru; viz infotipy). Zb∞vá popsat v∞poƒet rundovních klíƒà ze τifrovacího klíƒe.
Zpracování klíƒe
µifrovací klíƒ key (viz obr. 2) o Nk 32bitov∞ch slovech (4, 6 nebo 8) se naplní na poƒátek pomocného pole 32bitov∞ch slov W[0 ... Nk-1]. Toto pole se poté expanduje tak, ºe kaºdé nové W je vypoƒítáno jako W[i] = W[i - Nk] ? temp, kde temp je W[i - 1] nebo jeho modifikace - viz obrázek 2. P²i modifikaci se vyuºívá operace cyklického posuvu bajtà slova temp o jeden doprava (RotByte), dále nám známé substituce bajtà SubByte, a to aplikované na kaºd∞ bajt prom╪nné temp, a pole konstant Const??.
Implementace a rychlost
Dneτní implementace τifry RIJNDAEL v jazyce C na referenƒním PC s Pentiem Pro 200MHz dosahují rychlosti τifrování cca 70/60/50 Mb/s p²i délkách klíƒe 128/192/256 bità. Rychlost τifrování m╪²ená poƒtem cyklà na jeden 128bitov∞ blok je 363/432/500 cyklà (pro tytéº délky klíƒe); jde tedy zhruba o 3 - 5 cyklà na jeden bit. Na osmibitovém procesoru Intel 8051 trvá zaτifrování jednoho bloku cca 3000 - 5000 cyklà (1 cyklus = 12 period oscilátoru) a na ƒipu Motorola 68HC08 (1 cyklus = 1 perioda oscilátoru) je to cca 8000 - 12 000 cyklà. Spot²eba pam╪ti RAM je pouh∞ch 52 bajtà (!), nebo£ u obou t╪chto implementací byly rundovní klíƒe poƒítány on-the-fly. Délka kódu je v obou p²ípadech do 1 KB. Odτifrování trvá vºdy cca o 30 % déle neº zaτifrování.
Bezpeƒnost
Oba auto²i dokazují skv╪lé vlastnosti stavebních blokà schématu i odolnost vàƒi lineární a diferenciální kryptoanal∞ze. Protoºe schéma pro zaτifrování i odτifrování (v hardwaru) se liτí, není tu riziko slab∞ch klíƒà. Ekvivalenci klíƒà (coº je p²ípad, kdy ràzné τifrovací klíƒe dávají stejné sady rundovních klíƒà) brání podle autorà nelineární expanze.
Záv╪r
U τifry RIJNDAEL je cen╪n její pràzraƒn∞ návrh, zaloºen∞ na ràzn∞ch algebraick∞ch operacích. µifra je flexibilní p²i realizaci na ràzn∞ch typech procesorà s velmi mal∞mi nároky na pam╪£ i velikost kódu, a p²itom vykazuje jeτt╪ dostateƒnou rychlost. Je vhodná i pro paralelní zpracování a je odolná vàƒi fyzick∞m typàm útokà. Z mého pohledu jsou vτak navrºené stavební prvky i jejich kompozice pom╪rn╪ nové a osobn╪ bych byl p²ekvapen, kdyby RIJNDAEL zvít╪zil.
