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 {
