æifrovac¡ standard AES
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.
Vlastimil Kl¡ma (v.klima@decros.cz)