æifrovac¡ standard AES
VìbØr nov‚ho çifrovac¡ho standardu AES pro týet¡ tis¡cilet¡ u§ je ve fin le. V srpnu americkì standardizaŸn¡ £ýad NIST vybral z 15 kandid t… pØt nejvhodnØjç¡ch. Jeden z nich se stane standardem - kterì to bude, to z vis¡ na pr…bØhu druh‚ho kola posuzov n¡, je§ pr vØ zaŸalo. V tomto a dalç¡ch Ÿ¡slech Chipu v s s finalisty postupnØ sezn m¡me.

Bitva o tr…n vrchol¡

V Ÿervencov‚m Chipu jsme v s v Ÿl nku "Bitva o tr…n" (str. 52) informovali o Ÿasov‚m pl nu NIST pro vìbØr AES. NIST sl¡bil, §e uprostýed l‚ta vybere nØkolik finalist…, co§ tak‚ 9. srpna uŸinil. KromØ toho vydal "Zpr vu o prvn¡m kole vìvoje AES", v n¡§ zcela otevýenØ popsal sv…j postup pýi vìbØru finalist…. Zpr va je, stejnØ jako vçe kolem AES, veýejn  a je k dispozici tak‚ na internetu (viz infotipy). Jm‚na finalist… uv d¡me v tabulce, kde najdete tak‚ nØkter‚ vlastnosti, kter‚ NIST uvedl ve "Zpr vØ", a pro porovn n¡ pýipojujeme tak‚ nØkter‚ rychlostn¡ charakteristiky. VìznamnØjç¡ pozn mky NIST k jednotlivìm kandid t…m najdete d le.

Rychlost a platformy
Vìkon nØkterìch algoritm… podstatnØ z vis¡ na architektuýe procesoru. Rijndael a Twofish maj¡ vìborn‚ vìkony na vçech platform ch. Serpent je platformovØ nez vislì stejnØ jako oba uveden‚, ale nen¡ tak rychlì. Naproti tomu MARS a RC6 jsou platformovØ z visl‚ - jsou rychl‚ jen tam, kde se rychle prov dØj¡ 32bitov‚ operace n soben¡ a promØnn  cyklick  rotace, ale ne jinde.

VìpoŸet kl¡Ÿ…
Vçichni kandid ti pou§¡vaj¡ inicializaŸn¡ f zi, v n¡§ se ze çifrovac¡ch kl¡Ÿ… (o podporovanìch d‚lk ch 128, 192 a 256 bit…) vytv ýej¡ pomocn‚ kl¡Ÿov‚ promØnn‚ (rundovn¡ kl¡Ÿe, substituŸn¡ tabulky ap.), kter‚ se u§ pot‚ nemØn¡, i kdy§ se çifruje velkì objem dat. Se zmØnou çifrovac¡ho kl¡Ÿe se ovçem mus¡ vypoŸ¡tat novØ.
V situac¡ch, kdy se çifruj¡ mal‚ objemy dat, ale rychle se mØn¡ çifrovac¡ kl¡Ÿe, je pak Ÿas na pý¡pravu kl¡Ÿe vìznamnØjç¡ ne§ Ÿas potýebnì k çifrov n¡ dat. Pý¡kladem m…§e bìt centrum platebn¡ho syst‚mu, kter‚ v jednom okam§iku odpov¡d  na mno§stv¡ klientskìch dotaz… çifrovanìch r…znìmi kl¡Ÿi. Z tohoto pohledu jsou RC6 a Rijndael oproti ostatn¡m rychlejç¡.
Jindy je vìhodn‚, pokud çifra umo§n¡ vìpoŸty kl¡Ÿov‚ho materi lu "on-the-fly", tj. soubاnØ se çifrov n¡m dat (pý¡kladem je tato mo§nost vìpoŸtu rundovn¡ch kl¡Ÿ… u algoritmu DES). MARS a RC6 vìpoŸty nepodporuj¡, zat¡mco ostatn¡ ano.

¬ipov‚ karty a pamØœ
Na Ÿipovìch kart ch, kter‚ disponuj¡ 256 bajty RAM a 2000 bajty ROM, jsou realizovateln‚ pouze algoritmy Rijndael, Serpent a Twofish. Pro MARS a RC6 by vyhovovaly a§ karty s 512 bajty RAM a 6000 bajty ROM.

étoky
Z napaden¡, kter‚ çifr m hroz¡, jsou dnes mo§n  nejnebezpeŸnØjç¡ £toky na b zi fyzickìch metod, kter‚ sleduj¡ Ÿas prov dØn¡ jednotlivìch operac¡ nebo jejich energetickou spotýebu. Tyto metody jsou pomØrnØ nov‚ a lze se jich ob vat zejm‚na u Ÿipovìch karet. Nejv¡ce jsou z tohoto hlediska odoln‚ Rijndael a Serpent, proto§e pou§¡vaj¡ pouze booleovsk‚ operace, pr…chody pýes tabulky a pevn‚ bitov‚ posuny Ÿi rotace. Chr nit Twofish je u§ obt¡§nØjç¡ a MARS  i RC6 jsou chr nØny nejh…ýe, neboœ se nevyhnuly operac¡m, jako je n soben¡, promØnn‚ rotace a jin‚. Dalç¡ £toky jsou mo§n‚ pýi pý¡pravØ pomocnìch kl¡Ÿ… na Ÿipovìch kart ch. Tam jsou na tom zase nejh…ýe Rijndael, Serpent a Twofish. 

Z vØr
Proto§e kompletn¡ srovn n¡ finalist… by bylo pý¡liç dlouh‚, zamØýili jsme se zde jen na jejich vybran‚ charakteristiky. Tipovat,  kterì algoritmus m  nejvØtç¡ çanci vyhr t, by vçak i pýi mnohem podrobnØjç¡m pýehledu asi bylo pýedŸasn‚. Hledisek je toti§ pý¡liç mnoho a § dnì z algoritm… nepýevyçuje ostatn¡ ve vçech krit‚ri¡ch. VìbØr proto jeçtØ nØjakou dobu potrv , aby se naçlo co nejv¡ce argument… pro v¡tØze.
Druh‚ kolo veýejn‚ho posuzov n¡ kandid t… AES zaŸalo podle Ÿasov‚ho pl nu 9. z ý¡ a potrv  do 15. 5. 2000. V jeho z vØru se bude v New Yorku 13. a§ 14. dubna pý¡çt¡ho roku konat týet¡ konference AES, kde se oŸek v  hlavn¡ fin lov‚ kl n¡. Do t‚ doby v s se vçemi pØti kandid ty sezn m¡me podrobnØji. Dnes zaŸ¡n me s RC6.
Vlastimil Kl¡ma (vklima@decros.cz)

Infotipy;
Zpr va o prvn¡m kole vìvoje AES:
http://www.nist.gov/aes
Zdrojov‚ k¢dy kandid t… AES v C, ASM a dalç¡ informace:
ftp://ftp.funet.fi/pub/crypt/
cryptography/symmetric/


æifrovac¡ standard AES
RC6 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 pýedch zej¡c¡m Ÿl nku; 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 RC6

RC6 pýihl sila do soutاe spoleŸnost RSA a jej¡ algoritmus navrhli Robshaw, Sidney a Yin (RSA) a Rivest (MIT). MyçlenkovØ vych z¡ a znaŸnØ tا¡ z u§ dý¡ve navr§en‚ a nØkolika lety provØýen‚ çifry RC5. Na rozd¡l od jej¡ho 64bitov‚ho bloku m  ale RC6 ç¡ýku datov‚ho bloku dvojn sobnou - 128 bit…. Autoýi proto postavili dvØ "RC pØtky" paralelnØ vedle sebe a propojili je tak, aby ka§dì bit 128bitov‚ho vìstupn¡ho bloku z visel na ka§d‚m bitu 128bitov‚ho vstupn¡ho bloku (viz obr. 1). K tomu mj. vyu§ili i datovØ z visl‚ rotace, kter‚ RC5 zavedla jako svoji silnou kryptologickou zbraå. RC6 vçak do rotac¡ nav¡c zanesla dalç¡ nelinearitu (viz funkce g v obr. 1), kterou tak‚ ihned vyu§ila k pos¡len¡ p…vodn¡ch operac¡ RC5.

Parametry a stavebn¡ prvky
RC6 m  voliteln‚ parametry w (poŸet bit… slova), r (poŸet rund) a b (poŸet bajt… kl¡Ÿe) a podle nich se tak‚ pýesnØ oznaŸuje: RC6-w/r/b. Pro AES je stanoveno w = 32, r = 20, b volitelnØ 16, 24 nebo 32 - zde pop¡çeme pr vØ tuto variantu. Vych z¡ se z vyu§it¡ Ÿtyý 32bitovìch registr… A a§ D, s nimi§ se prov dØj¡ vçechny z kladn¡ operace, kter‚ umo§åuje 32bitov  architektura souŸasnìch procesor….
OznaŸ¡me-li registry (slova) A a B, pak A+B, A-B, A?B, A*B znamenaj¡ bاn‚ operace sŸ¡t n¡, odŸ¡t n¡, XOR a n soben¡ slov (aritmetick‚ pýeteŸen¡ se zanedb v ). Symbolem A<<<B (resp. A>>>B) oznaŸujeme cyklickou rotaci bit… slova A doleva (resp. doprava) o urŸitì poŸet bit… r, kterì se rovn  Ÿ¡slu v pØti nejni§ç¡ch bitech registru B (r = B AND 0x1F). Zm¡nØn  funkce g pýev d¡ slovo B na slovo g(B) = (B*(2B+1)) <<< 5. Je to neline rn¡, vz jemnØ jednoznaŸn  funkce, zajiçœuj¡c¡, §e se pýi operaci A <<< g(B) uplatn¡ vçechny bity slova B.

Zpracov n¡ kl¡Ÿe
æifrovac¡ kl¡Ÿ, kterì m  b (16, 24 nebo 32) bajt…, se nejprve ulo§¡ do c (4, 6 nebo 8) Ÿtyýbajtovìch slov L[0] a§ L[c-1] a pý¡padnØ se do pln‚ d‚lky slov dopln¡ nulami. Pole L se pak postupnØ st v  slo§itØjç¡m a rozçiýuje se na pole slov S[0] a§ S[43]. S je na poŸ tku naplnØno konstantou, ale krok za krokem se "zeslo§iœuje" pomoc¡ pole L a naopak pole L se "zeslo§iœuje" pomoc¡ novØ vytvoýen‚ho obsahu S. To vçe se na pol¡ch S a L opakuje ve smyŸce týikr t za sebou (viz obr. 3). Pole L se po konci procesu nemus¡ zachovat, co§ m…§e bìt nØkdy bezpeŸnostn¡ vìhoda - jeho obsah (çifrovac¡ kl¡Ÿ) toti§ nelze urŸit jen z obsahu pole S (rundovn¡ kl¡Ÿe). Pole S se vyu§ije jako rundovn¡ kl¡Ÿe, pýiŸem§ prvn¡ a posledn¡ dva slou§¡ k maskov n¡ (tzv. whitening) vstup… a vìstup… a zbyl‚ se po dvou postupnØ vyu§ij¡ ve 20 rund ch sch‚matu (viz obr. 2).

Rychlost a implementace
Pýi zaçifrov n¡ se nejprve ze çifrovac¡ho kl¡Ÿe vytvoý¡ pole S. Otevýenì text se napln¡ do registr… A a§ D a pak probØhnou operace zaçifrov n¡ podle pseudok¢du na obr. 2. Odçifrov n¡ prob¡h  trochu jinak (snadno jej odvod¡te reverz¡ operac¡ zaçifrov n¡), ale vyu§¡v  stejn‚ pole rundovn¡ch kl¡Ÿ… oznaŸen‚ S. Pokud se RC6 realizuje v 32bitov‚m assembleru, pak se projev¡ vìhoda zvolenìch operac¡ s 32bitovìmi slovy: pýi çifrov n¡ 128bitov‚ho bloku se pou§ije pouze 254 instrukc¡ a pýi pý¡pravØ kl¡Ÿe 1108 instrukc¡. To na 200MHz PC znamen  rychlost çifrov n¡ (v pamØti) cca 12,6 MB/s. Na osmibitov‚m procesoru Intel MCS51 (1 MHz) se dos hne rychlosti çifrov n¡ kolem 1,1 KB/s a pý¡prava kl¡Ÿe zabere 27 milisekund. Vìhodou je, §e cel‚ sch‚ma lze realizovat na Ÿipovìch kart ch s m‚nØ ne§ 256 bajty RAM (povçimnØte si zejm‚na "pouhìch" 176 bajt… pole S).

BezpeŸnost
N vrh ýi tvrd¡, §e analyzovali cel‚ i zjednoduçen‚ sch‚ma a nalezli pouze line rn¡ aproximace pro osmn ctirundovn¡ sch‚ma. éŸinnost diferenci ln¡ analìzy (s definic¡ diference pomoc¡ tradiŸn¡ operace XOR i s novou definic¡ pomoc¡ operace odŸ¡t n¡) se zastavila jeçtØ pýed 18 rundami. Pý¡pravu kl¡Ÿe autoýi pou§ili z RC5, kde dosud nebyly zjiçtØny § dn‚ slabiny. Nejsou tak‚ zn my § dn‚ slab‚ kl¡Ÿe ani £toky pomoc¡ pý¡buznìch kl¡Ÿ… a rundovn¡ kl¡Ÿe maj¡ vçechny znaky n hodnosti. NIST autor…m (ve srovn n¡ s ostatn¡mi kandid ty) vyŸ¡t  pouze malou bezpeŸnostn¡ rezervu, Ÿ¡m§ m  na mysli pýid n¡ pouze dvou rund nad 18, tj. nad sch‚ma, kde u§ teoreticky existuj¡ urŸit‚ slabiny.

Z vØr
RC6 je na prvn¡ pohled elegantn¡m a vysoce kvalitn¡m algoritmem. Kdybych si ale mohl vybrat, pro AES bych tuto çifru volil radØji s 32 rundami...
Vlastimil Kl¡ma (vklima@decros.cz)

B = B + S[0], D = D + S[1]
for  i  =  1  to  20  do { t  =  g(B),  u  =  g(D)
A  =  ( (A ? t)  <<<  u )  +  S[2i]
C  =  ( (C ? u)  <<<  t )  +  S[2i + 1]
(A, B, C, D)  =  (B, C, D, A) } A = A + S[42], C =  C + S[43]

S[0] = 0xB7E15163 for i = 1 to 43 
do S[i] = 0xB7E15163 + i*0x9E3779B9 A = B = i = j = 0 for s = 1 to 132 do {  
A = S[i] = (S[i] + A + B) <<< 3
B = L[j] = (L[j] + A + B) <<< (A + B)
 i = (i + 1) mod 44     j = (j + 1) mod c 
}

Infotipy:
Zdrojov‚ k¢dy v C, ASM:
ftp://ftp.funet.fi/pub/crypt/
cryptography/symmetric/rc6/
Domovsk  str nka AES:
http://csrc.nist.gov/encryption/aes/aes_home.htm