SERPENT 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σ n╪jaká ta desetiletí) a bude mít dalekosáhl∞ vliv na poƒítaƒovou bezpeƒnost.
P²edstavujeme kandidáty na AES:
µifra SERPENT
Blokovou τifru SERPENT p²ihlásili do sout╪ºe Ross Anderson (UK), Eli Biham (Izrael) a Lars Knudsen (Norsko), známá esa sv╪tové kryptologie. Jako u vτech kandidátà na AES je délka vstupního a v∞stupního bloku 128 bità a podporované délky klíƒe 128, 192 a 256 bità. SERPENT pouºívá pevné substituƒní tabulky (osm S-boxà zobrazujících 4 bity na 4 bity) a pracuje v rundách podobn╪ jako DES, má vτak dvojnásobn∞ poƒet rund (32). Se 128bitov∞m blokem a 256bitov∞m klíƒem je p²ibliºn╪ stejn╪ rychl∞ jako DES, je ale bezpeƒn╪jτí neº TripleDES.
Návrh τifry je dost konzervativní. Auto²i necht╪li pouºít ºádné nové prvky (datov╪ závislé rotace, násobení nebo sƒítání místo operace ? apod.), a proto v∞hodn╪ aplikovali osv╪dƒené principy tak, aby se τifra dala dob²e hardwarov╪ i softwarov╪ implementovat. Zejména, jak uvidíme dále, je kladen dàraz na moºnost paralelního zpracování jednotliv∞ch bità a moºnost v∞poƒtu rundovních klíƒà za chodu ("on-the-fly"). Díky tomu, ºe návrh je bitov╪ orientovan∞, umoºσuje optimalizovat programov∞ kód pro ràzné mikroprocesory. Odτifrování (je popsáno v hlavním dokumentu; viz infotipy) zde vτak probíhá trochu jinak neº zaτifrování, takºe nelze pouºít stejn∞ hardware jako u τifry MARS.
Postup p²i zaτifrování
P²ed operací zaτifrování nebo odτifrování anebo v jejím pràb╪hu se vypoƒítá 33 rundovních klíƒà. Jsou to 128bitové hodnoty K[i], i = 0..32, z nichº kaºdou chápeme jako z²et╪zení ƒty² 32bitov∞ch slov k4*i+0 , k4*i+1 , k4*i+2 , k4*i+3 (jejich v∞poƒet popíτeme dále). Otev²en∞ text se naplní do 128bitového bloku B[0] a v kaºdé z 32 rund (i = 0..31) se z B[i] vypoƒte B[i+1]. V∞sledn∞ τifrov∞ text je uloºen v B[32].
Runda i se skládá z následujících krokà (viz téº obrázek 1). Na vstupní 128bitov∞ blok B[i] se "naxoruje" rundovní klíƒ K[i]. Ob╪ prom╪nné jsou chápány jako ƒty²i 32bitová slova, takºe také v∞sledek B[i] ? K[i] je moºné chápat jako ƒty²i 32bitová slova. Nyní se tato slova se²adí tak, ºe jejich bity vytvá²ejí "ƒty²²ad" (viz obr. 2), takºe na prvním míst╪ stojí za sebou první bity slov, na druhém míst╪ druhé bity atd. Nyní aplikujeme substituƒní box Si postupn╪ na vτech 32 popsan∞ch ƒtve²ic bità (v i-té rund╪ pouºijeme jeden S-box Si). Protoºe rund je 32 a S-boxà osm, pouºívají se S-boxy "dokola", tedy Si = Si mod 8.
V∞stupem S-boxu jsou ƒty²i bity, které zase uloºíme do ƒty²²adu tak, jak byl se²azen vstup. ¼ty²i nov╪ vzniklá 32bitová slova (tvo²ící ony ƒty²i ²ady) si oznaƒme x0, x1, x2, x3 . Dosavadní operace pak màºeme zapsat ve tvaru (x0, x1, x2, x3) = Si (B[i] ? K[i]). S nov∞mi hodnotami slov x nyní provedeme lineární transformaci L podle pseudokódu na obrázku 1 a obdrºíme nové hodnoty 32bitov∞ch slov x = L(x0, x1, x2, x3). Ty uº tvo²í v∞stup z i-té rundy B[i+1] = (x0, x1, x2, x3). Jeτt╪ poznamenejme, ºe u 32. rundy je lineární transformace nahrazena operací XOR s rundovním klíƒem K[32].
P²íprava klíƒà
Rundovní klíƒe se vytvá²ejí pom╪rn╪ jednoduτe. Pokud τifrovací klíƒ (128, 192 nebo 256 bità) nemá délku 256 bità, doplní se na ni bitem 1 a dále nulov∞mi bity. Ten se naplní po ²ad╪ do osmi 32bitov∞ch prom╪nn∞ch w-8, w-7, ..., w-1 a ty se dále expandují aº do w131 podle vzorce wi = (wi- 8 ? wi- 5 ? wi- 3 ? wi- 1 ? ? ? i) <<< 11, i = 0..131;
zde w <<< r znamená rotaci slova w o r bità doleva a ? je hexadecimální konstanta 0x9e37799b (auto²i tvrdí, ºe tento vzorec vyluƒuje vznik slab∞ch klíƒà).
Nyní na ƒtve²ici slov (w0, w1, w2, w3) aplikujeme S-box (jako první pouºijeme S3) stejn∞m zpàsobem jako na obrázku 2 - vzniklá slova jsou uº jednotlivá slova rundovního klíƒe K[0] = (k0, k1, k2, k3). Dalτí klíƒ K[1] = (k4, k5, k6, k7) získáme aplikací boxu S2 na (w4, w5, w6, w7) atd. (indexy u S-boxà se sniºují o 1, modulo 8), aº vytvo²íme poslední rundovní klíƒ K[32] = (k128, k129, k130, k131 ). Jeτt╪ dodejme, ºe S-boxy jsou konstantní a byly vygenerovány tak, aby schéma co nejvíce odolávalo diferenciální a lineární kryptoanal∞ze (blíºe viz základní dokument v infotipech).
Implementace a rychlost
Jak je z²ejmé z definice zpracování klíƒe, rychlost τifry nezávisí na jeho délce. Dále je vid╪t, ºe rundovní klíƒe lze poƒítat za chodu. Zaτifrování jednoho 128bitového bloku dat spot²ebuje cca 1830 - 1940 instrukcí (je to pochopiteln╪ závislé na typu procesoru). Navíc, díky bitov╪ orientovanému návrhu, nap²íklad 1940 instrukcí na Pentiu vyºaduje jen 1738 hodinov∞ch cyklà. Podstatné je, ºe na referenƒním PC s 200MHz Pentiem Pro (p²i implementaci v jazyce C) auto²i odhadují rychlost τifrování na 14,7 Mb/s. Na osmibitovém procesoru (nap²íklad 3,5MHz 6805, pouºívaném v ƒipov∞ch kartách) záleºí na moºnosti optimalizovat kód na úkor pam╪ti. Tak nap²íklad s vyuºitím 1 KB pam╪ti je moºné dosáhnout rychlosti jen 12,8 Kb/s, zatímco s 2 KB pam╪ti je to uº 40,7 Kb/s.
Bezpeƒnost
Na základ╪ pravd╪podobností, vypoƒítan∞ch pro pot²eby diferenciální kryptoanal∞zy, dosp╪li auto²i k záv╪ru, ºe 16rundovní SERPENT je stejn╪ bezpeƒn∞ jako TripleDES. Z bezpeƒnostních p²íƒin vτak jeτt╪ zdvojnásobili poƒet rund na 32, coº je z hlediska dlouhodobého pouºívání τifry jist╪ velmi odpov╪dné. Pokud jde o odolnost vàƒi lineární a diferenciální kryptoanal∞ze a metod╪ p²íbuzn∞ch klíƒà, je takov∞ dotaz trochu jako p²ihrávka na smeƒ - jeden z autorà τifry SERPENT je totiº spoluobjevitelem dvou z t╪chto kryptoanalytick∞ch metod...
Záv╪r
SERPENT je konzervativní a siln╪ bezpeƒnostn╪ orientovaná τifra. To je bohuºel zaplaceno její nejniºτí rychlostí v porovnání s ostatními kandidáty na AES. Vhodná tedy bude zejména pro paralelní zpracování. Procesy τifrování a odτifrování jsou odolné vàƒi fyzick∞m typàm útokà.
Vlastimil Klíma (v.klima@decros.cz)
TWOFISH 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σ n╪jaká ta desetiletí) a bude mít dalekosáhl∞ vliv na poƒítaƒovou bezpeƒnost.
P²edstavujeme kandidáty na AES:
µifra TWOFISH
Blokovou τifru TWOFISH p²ihlásil do sout╪ºe kolektiv τesti Ameriƒanà, z nichº ƒty²i pat²í do firmy Conterpane Systems Bruce Schneiera. TWOFISH má délku vstupního a v∞stupního bloku 128 bità a podporuje délky klíƒe 128, 192 a 256 bità. V dokumentaci se tvrdí, ºe pouºívá klíƒov╪ závislé substituƒní tabulky (S-boxy) 8 bità na 8 bità. Pro p²esnost musíme dodat, ºe ve skuteƒnosti vznikají kompozicí klíƒe a pevn∞ch substitucí 4 bity na 4 bity (tzv. tabulky t0, t1, t2, t3). Nám uº známé maskování klíƒem (whitening) operací ? je pouºito jak na vstupu, tak na v∞stupu. µifra má Feistelovo schéma s 16 rundami. Její návrh vyuºívá ràznorodé operace, jako násobení prvkà v Galoisov╪ t╪lese GF(28), aritmetické sƒítání, operaci ? a substituƒní boxy. V∞hodné je, ºe umoºσuje v∞poƒet rundovních klíƒà za chodu ("on-the-fly").
Postup p²i zaτifrování
P²ed operací zaτifrování nebo odτifrování anebo v jejím pràb╪hu se vypoƒítá 40 rundovních klíƒà (postup popíτeme dále). Jsou to 32bitové hodnoty K[i], i = 0..39, z nichº první ƒty²i se "xorují" na otev²en∞ text a dalτí ƒty²i na v∞sledek 16. rundy, tj. t╪sn╪ p²ed v∞stupem τifrového textu. V kaºdé ze 16 rund (r = 0..15) se pouºijí vºdy dva rundovní klíƒe, K[8+2r] a K[9+2r]. Vstupní 128bitov∞ blok do rundy r oznaƒme jako ƒty²i 32bitová slova Br,0 , Br,1 , Br,2 , Br,3. Ta se transformují na Br+1,0 , Br+1,1 , Br+1,2 , Br+1,3 postupem podle obrázku 1.
Hlavní úlohu zde hraje funkce g, následovaná "pseudohadamardovou" transformací (PHT) a maskováním v∞stupu rundovními klíƒi (p²iƒítání, v obrázku oznaƒené +, probíhá v modulu 232). Jinak zde w <<< r znamená rotaci slova w o r bità doleva a w >>> r doprava.
Vstupem funkce g je 32bitové slovo neboli ƒty²i bajty - oznaƒme je nap²íklad (x0, x1, x2, x3 ). Kaºd∞ z nich pak prochází jemu odpovídajícím S-boxem (SBX0 aº SBX3) a transformuje se na bajt yi = SBXi(xi). V∞sledná ƒtve²ice (y0, y1, y2, y3 ) je pak dále zpracována na ƒtve²ici bajtà (z0, z1, z2, z3 ) pomocí matice MDS.
Matice MDS je typu 4 x 4 a jejími ²ádky jsou po ²ad╪ (hexadecimáln╪) konstanty (01, EF, 5B, 5B), (5B, EF, EF, 01), (EF, 5B, 01, EF) a (EF, 01, EF, 5B). Násobení prvkà matice s prom╪nn∞mi yi , nap². ve v∞razu pro z0 = 01*y0 ? EF*y1 ? 5B*y2 ? 5B*y3, p²itom neznamená násobení bajtà, ale prvkà Galoisova t╪lesa GF(28) v modulu m(x) = x8 + x6 + x5 + x3 + 1 (definicí tohoto násobení jsme se podrobn╪ji zab∞vali v ƒlánku o τif²e RIJNDAEL v minulém ƒísle).
Touto operací, která dává uº v∞stup funkce g, vlastn╪ dojde k promíchání vτech jejích 32 vstupních bità.
Z obrázku 1 je také vid╪t, ºe jsou zde pouºity dv╪ paraleln╪ pracující funkce g, které jsou op╪t propojeny pseudohadamardovou transformací PHT. Jedná se o zobrazení {a,b} -> { (a+b) mod 232, (a+2*b) mod 232 }, které zpàsobuje promíchávání bità mezi ob╪ma paralelními v╪tvemi. Následuje jeτt╪ maskování rundovními klíƒi a cyklické rotace, ale tím uº je rundovní funkce úplná. Odτifrování probíhá trochu jinak neº zaτifrování (je popsáno v hlavním dokumentu; viz infotipy), ale hlavní hardwarové prvky lze pouºít i pro n╪.
P²íprava klíƒà
Zb∞vá tvorba rundovních klíƒà z klíƒe τifrovacího. Vysv╪tlíme ji na 128bitovém klíƒi - pro dalτí dv╪ délky je tvorba principiáln╪ stejná, jen mírn╪ sloºit╪jτí. Jsou--li bajty τifrovacího klíƒe m0, ... , m15, pak definujeme 32bitová slova Mi = (m4*i+0, m4*i+1, m4*i+2, m4*i+3) pro i = 0, 1, 2 a 3. Dále pak pomocí nové konstantní matice RS 4 x 8 definujeme 32bitová slova S0 = RS*(M0, M1) a S1 = RS*(M2, M3), p²iƒemº i zde se násobí prvky Galoisova t╪lesa, tentokrát v modulu m(x) = x8 + x6 + x3 + x2 + 1.
Nyní vyuºijeme dva pevné substituƒní boxy Q0 a Q1 8 na 8 bità, které jsou bu╘ nadefinovány rovnou, nebo se dají "on-the-fly" poƒítat z menτích p²eddefinovan∞ch substituƒních boxà (t0 aº t4) 4 na 4 bity. K definici S-boxà vyuºijeme klíƒová slova S0 a S1, která na okamºik oznaƒíme jako L0 a L1. Definujeme y = SBXi(x) takto:
y = SBX0(x) = Q1 [Q0 [Q0 [x] ? L1,0] ? L0,0],
y = SBX1(x) = Q0 [Q0 [Q1 [x] ? L1,1] ? L0,1],
y = SBX2(x) = Q1 [Q1 [Q0 [x] ? L1,2] ? L0,2],
y = SBX3(x) = Q0 [Q1 [Q1 [x] ? L1,3] ? L0,3].
S vyuºitím podobn∞ch struktur se vypoƒítávají i rundovní klíƒe (viz obr. 2). Pokud v definici S-boxà pouºijeme místo slov L0 a L1 klíƒová slova M0 a M2 a v∞sledek S-boxà jeτt╪ vynásobíme maticí MDS, obdrºíme definici funkce h0. Pokud v definici S-boxà pouºijeme místo slov L0 a L1 klíƒová slova M1 a M3 a v∞sledek S-boxà vynásobíme maticí MDS, obdrºíme definici funkce h1. Kompozicí h0 a h1 s dalτími prvky (PHT, cyklická rotace) dostáváme definici funkce, která nám vypoƒítává vºdy dvojici rundovních klíƒà K8+2r a K9+2r pro r = 0..15 (obr. 2). Vstupem do funkce h0 jsou v tomto p²ípad╪ ƒty²i stejné bajty s hodnotou 2*r (r je ƒíslo rundy) a vstupem do funkce h1 jsou ƒty²i stejné bajty s hodnotou 2*r +1.
Zb∞vá definovat konstantní boxy Q0 a Q1. Ty jsou zaloºeny na substitucích 4 x 4 bity (t0 a t1). Jedno nastavení tabulek (t0 a t1) dává substituci Q0 a druhé nastavení substituci Q1. Je-li x vstup p²ísluτného Q, pak jeho v∞stupem je hodnota y poƒítaná podle vztahà na obrázku 3. A to uº je vτe.
Implementace a rychlost
Pln╪ optimalizovaná TWOFISH τifruje na referenƒním 200MHz Pentiu Pro jeden blok (128 bità) za 285 hodinov∞ch cyklà (po p²íprav╪ klíƒe trvající 12 700 hodinov∞ch cyklà). To dává rychlost τifrování 90 Mb/s. P²i zkrácení p²ípravy klíƒe na 1250 hodinov∞ch cyklà je jeden blok moºné zaτifrovat za 860 hodinov∞ch cyklà. Na ƒipové kart╪ s procesorem 6805 je po p²íprav╪ klíƒe, trvající 1750 hodinov∞ch cyklà, moºné τifrovat jeden blok (128 bità) za 29 100 hodinov∞ch cyklà. Díky tomu, ºe rundovní klíƒe lze poƒítat za chodu a schéma urychlovat p²ípravou v╪tτích tabulek, je zde ²ada moºností, jak schéma optimalizovat na ràzn∞ch procesorech s ràzn╪ velkou pam╪tí i rychlostními nároky na p²ípravu klíƒe.
Bezpeƒnost
Nejúsp╪τn╪jτí útok, nalezen∞ autory, je útok na p╪tirundovou τifru s 222.5 volen∞mi otev²en∞mi texty a 251 operacemi. Na základ╪ toho auto²i zv∞τili poƒet rund na 16, coº je z hlediska dlouhodobého pouºívání τifry urƒit╪ uºiteƒné. Auto²i také potvrzují odolnost vàƒi vτem znám∞m útokàm, zejména lineární a diferenciální kryptoanal∞ze.
Záv╪r
TWOFISH je nejen rychlá, ale i bezpeƒnostn╪ orientovaná τifra. To ji staví na jedno z p²edních míst i mezi finalisty. Návrh umoºσuje ràzné typy optimalizací mezi rychlostí a velikostí pot²ebné pam╪ti na ràzn∞ch typech procesorà. µifrování a odτifrování jsou také odolné vàƒi n╪kter∞m typàm fyzick∞ch útokà. TWOFISH je proto velmi váºn∞m kandidátem na AES.
