V╪ci, které jsou levné, neb∞vají p²íliτ kvalitní. Kdyº ale jde o algoritmus, kter∞ se má stát τifrovacím standardem, je situace úpln╪ jiná. Musí b∞t superkvalitní a zcela zadarmo. Na jeden takov∞ se nyní podíváme podrobn╪.
µifrovací standard zdarma
V polovin╪ devadesát∞ch let nebyla situace na poli τifrovacích algoritmà ràºová. Mnozí lidé pochopili, ºe DES uº má svá nejlepτí léta dávno za sebou, ale nem╪li místo n╪j p²íliτ na vybranou. Existovalo totiº jen velmi málo alternativ. Mnohé z nich byly pouze za peníze - p²i komerƒním pouºití se za n╪ muselo platit. To byl zejména p²ípad τv∞carské τifry IDEA, americk∞ch τifer RC2, RC4, RC5 a dalτích. V této situaci p²iτla kanadská spoleƒnost Entrust Technologies s nápadem poskytnout τifrovací algoritmus, kter∞ by byl voln╪ τi²iteln∞ a pouºiteln∞ zdarma pro osobní i komerƒní úƒely. Proto sponzorovala v∞voj nového algoritmu, kter∞ by byl dostateƒn╪ variabilní a siln∞, pouºiteln∞ bez p²ehnan∞ch nárokà na sloºitost a také dostateƒn╪ sviºn∞. V∞sledek byl nazván CAST podle iniciál sv∞ch kanadsk∞ch tvàrcà (C. Adams, S. Tavares) a na internetu byl v kv╪tnu roku 1997 publikován pod oznaƒením RFC 2144 .
Americk∞, nebo kanadsk∞?
CAST tak p²inesl alternativu k algoritmu Blowfish, kter∞ ze stejn∞ch dàvodà nabídl jako freeware Ameriƒan B. Schneier o dva roky d²íve. Tím vznikla koneƒn╪ i v oblasti freewaru urƒitá konkurence a nabídka. CAST si brzo získal p²íznivce na celém sv╪t╪, stejn╪ tak jako Blowfish, a oba se díky bezplatnému pouºití brzy objevily v ²ad╪ komerƒních produktà.
V∞hodou CAST se staly dv╪ podstatné skuteƒnosti, které jej up²ednostσovaly p²ed algoritmem Blowfish. Jednak jej ve sv∞ch produktech zaƒal pouºívat Microsoft, jednak získal certifikát kvality od oficiálního kanadského ú²adu CSE (Communication Security Establishment), a dá se tak pouºít pro ochranu citliv∞ch dat v kanadsk∞ch vládních organizacích a institucích (urƒení pro stupeσ "designated information" podle kanadského systému klasifikace). Za zmínku stojí i jeho vƒlen╪ní do programu PGP (Pretty Good Privacy), kde nahradil pro komerƒní úƒely licenƒními poplatky zatíºen∞ τv∞carsk∞ algoritmus IDEA.
Je CAST podobn∞ DES?
Ano, v mnoha sm╪rech je. Pouºívá ovτem ²adu nov∞ch kryptografick∞ch myτlenek a je nesrovnateln╪ kvalitn╪jτí. S DES má spoleƒn∞ tzv. Feistelàv princip. Algoritmus Feistelova typu pracuje v cyklech totoºn∞ch operací, které se naz∞vají rundy (rounds). Kaºdá runda opakuje stejné operace se vstupem a v∞stup z jedné rundy je zároveσ vstupem do rundy následující, ale v ràzn∞ch rundách jsou pouºity odliτné tzv. rundovní klíƒe (viz téº p²ipojená schémata). Rundovní klíƒe se odvozují v inicializaƒní fázi algoritmu z vlastního τifrovacího klíƒe ràzn╪ sloºit∞m procesem (DES nap²íklad oproti CAST pouºívá velmi jednoduch∞ postup, kter∞ màºe vytvo²it i tzv. slabé klíƒe).
Feistelàv princip umoºσuje pro odτifrování pouºít stejn∞ postup jako pro zaτifrování, jen se obrátí po²adí v∞b╪ru rundovních klíƒà (zkuste si tento geniální princip rozmyslet podle obrázku). Tato vlastnost je v∞hodná zejména pro hardware a τifrovací ƒipy. Dalτí podobnost s DES je op╪t na úrovni obecného principu, kter∞m jsou tzv. substituƒn╪-permutaƒní sít╪. DES i CAST pouºívají substituce, a to ve form╪ pevn∞ch substituƒních tabulek zvan∞ch S-boxy. DES má osm S-boxà, které zobrazují τest bità na ƒty²i, u CAST to jsou ƒty²i mohutn╪jτí S-boxy S1 aº S4, které p²evád╪jí osm bità na 32. Toto "rozτí²ení" je jedním z nov∞ch prvkà, které se objevily u n╪kolika τifer devadesát∞ch let.
Dále DES pouºívá permutaci bità (p²eházení po²adí bità), která je skuteƒn∞m "zabijákem" pro softwarovou realizaci, zatímco CAST jako permutaci pouºívá cyklickou rotaci bità. Tu lze, jak známo, softwarov╪ realizovat velmi jednoduτe. Krom╪ toho CAST pouºívá aritmetické operace sƒítání a odƒítání v celé τí²i 32bitového slova, tj. v modulu 232. Uvedené operace jsou kryptologicky siln╪jτí a p²i realizaci souƒasn╪ rychlejτí. V∞sledkem je proto τifra kvalitn╪jτí a rychlejτí neº DES. Auto²i uvád╪jí, ºe rychlost τifrování dat v operaƒní pam╪ti PC je na 150MHz Pentiu asi 3 MB/s.
CAST je bezpeƒn∞
Díky v∞τe uveden∞m zesílením oproti DES si CAST získal velkou dàv╪ru. P²isp╪lo k tomu jist╪ i zve²ejn╪ní vτech kryptografick∞ch detailà a úvah o bezpeƒnosti algoritmu ve studii "Constructing Symmetric Ciphers Using the CAST Design Procedure" (viz infotipy).
CAST v∞hodn╪ vyuºívá skuteƒnosti, ºe Feistelàv princip je uº velmi dlouho pouºívan∞ a prozkouman∞, a p²itom zavádí dalτí kvalitní kryptografické operace. V∞sledkem jsou velmi dobré vlastnosti algoritmu, jako je konfuze, difuze, lavinovitost, nezávislost bità atd., coº dosv╪dƒuje i skuteƒnost, ºe dosud nebyla odhalena ºádná jeho slabina.
CAST se samoz²ejm╪ vyh∞bá vτem notoricky znám∞m neτvaràm DES, jako je vlastnost komplementárnosti nebo existence slab∞ch a poloslab∞ch klíƒà. Dalτím dàleºit∞m p²edpokladem bezpeƒnosti je délka klíƒe. Zde dává CAST uºivateli volnou ruku a umoºσuje volit délku klíƒe od 40 aº do 128 bità (po osmi bitech). Posledním - a nepochybn╪ zásadním - potvrzením jeho kvality se stalo uº zmín╪né oficiální stanovisko kanadského ú²adu CSE.
Popis algoritmu
Popis lze shrnout do ƒty² základních krokà. Oznaƒme bity otev²eného textu (vstupu algoritmu) jako m1 ... m64, bity τifrovacího klíƒe K jako k1 ... k128 (pokud je klíƒ kratτí, je do délky 128 bità dopln╪n nulami) a τifrov∞ text (tj. v∞stup algoritmu) jako c1 ... c64. Algoritmus má 12 nebo 16 rund, podle toho, zda pàvodní klíƒ má délku do 80 bità (vƒetn╪) nebo více neº 80 bità. Rundy nemají zcela totoºnou míchací funkci f (jak je znázorn╪no na obrázku Feistelova principu), ale funkce f jsou t²i. Liτí se v ràzném po²adí v∞b╪ru operací +, -, xor, které jsou v obrázku znázorσujícím míchací funkci oznaƒeny jako operace a, b, c, d. Proto rozeznáváme typ1 (f1), typ2 (f2) a typ3 (f3) této funkce. Konkrétní napln╪ní operací u funkcí f1 aº f3 je uvedeno dále v odstavci o míchací funkci f.
Protoºe se popis algoritmu m╪ní v závislosti na délce klíƒe K, zohledσuje se to také v oznaƒení algoritmu. Algoritmus se pak oznaƒuje jako CAST5-x, p²iƒemº ƒíslo za pomlƒkou udává délku klíƒe v bitech (12 moºností). Za základní verze se povaºují CAST5-40, CAST5-80 a CAST5-128. K nim jsou také definovány kontrolní p²íklady (viz infotipy).
Zaτifrování
1. krok:
P²íprava rundovních klíƒà. Z klíƒe K se vypoƒte 16 párà rundovních klíƒà {Kmi, Kri}, i = 0 ... 15, kde Kmi jsou 32bitová slova (maskovací klíƒe) a Kri p╪tibitová slova (rotaƒní klíƒe).
2. krok:
Otev²en∞ text se rozd╪lí na levé (L) a pravé (R) 32bitové slovo:
L0 = m1 ... m32, R0 = m33 ... m64.
3. krok:
Nyní následuje 16 (p²ípadn╪ 12) rund (i = 0 ... 15), v nichº se vypoƒítávají Li+1 a Ri+1 z Li a Ri podle vztahà:
Li+1 = Ri
Ri+1 = Li xor f(Ri, Kmi, Kri)
P²itom funkce f je vybíraná postupn╪ jako f1, f2, f3 a cyklicky dále.
4. krok:
Na záv╪r prob╪hne v∞m╪na po²adí L16 a R16, tj. τifrov∞ text je definován jako c1 ... c64 = (R16, L16) - nikoliv, jak by se dalo oƒekávat, jako (L16, R16).
Odτifrování
Jak uº bylo ²eƒeno, odτifrování probíhá stejn∞m postupem jako zaτifrování. Proto byl také uƒin╪n 4. krok v uvedeném popisu. Jedin∞ rozdíl p²i odτifrování oproti zaτifrování spoƒívá v obrácení po²adí v∞b╪ru párà rundovních klíƒà. Jako první se tedy pouºije ten pár rundovních klíƒà, kter∞ byl p²i zaτifrování pouºit jako poslední, atd.
Substituƒní boxy
CAST pouºívá 8 konstantních substituƒních boxà S1 aº S8, které zobrazují bajt na ƒty²bajtové slovo. Kaºd∞ S-box tedy zabírá v pam╪ti 1 KB. P²i vlastním τifrování dat ale postaƒí vyhradit pam╪£ 4 KB na S-boxy S1 aº S4, nebo£ S5 aº S8 se pouºívají pouze k p²íprav╪ párà rundovních klíƒà.
Míchací funkce f
V míchací funkci jsou pouºity b╪ºné operace intelsk∞ch procesorà, jako je sƒítání (+) a odƒítání (-) 32bitov∞ch slov v modulu 232 (tj. p²ípadné p²eteƒení se zanedbává), operace xor a cyklická rotace 32bitového slova o n bità doleva (<<< n ). Pro snadn╪jτí popis oznaƒme D vstupní 32bitové slovo funkce f a I 32bitové slovo, které vznikne jako meziv∞sledek. Jednotlivé bajty slova I oznaƒme od nejv∞znamn╪jτího Ia aº po nejmén╪ v∞znamn∞ Id. Zápis míchací funkce f je pak jednoduch∞:
Typ 1:
I = ((Kmi + D) <<< Kri)
f = ((S1[Ia] xor S2[Ib]) - S3[Ic]) + S4[Id]
Typ 2:
I = ((Kmi xor D) <<< Kri)
f = ((S1[Ia] - S2[Ib]) + S3[Ic]) xor S4[Id]
Typ 3:
I = ((Kmi - D) <<< Kri)
f = ((S1[Ia] + S2[Ib]) xor S3[Ic]) - S4[Id]
Tyto rovnice pak definují konkrétní instance operací a aº d v obrázku míchací funkce.
P²íprava rundovních klíƒà
Zb∞vá popsat, jak se vytvá²ejí rundovní klíƒe z k1 ... k128. Postup je dost podobn∞ vlastnímu procesu τifrování, ale jeho popis by vyºadoval pom╪rn╪ hodn╪ místa. Zájemce proto odkazujeme na popis uveden∞ v RFC 2144 nebo na programovou realizaci (viz infotipy). Poznamenejme, ºe zde, a práv╪ jen zde, se vyuºívají S-boxy S5 aº S8, které jsou také pevn╪ definované. V∞stupem je nakonec 12 nebo 16 párà rundovních klíƒà {Kmi, Kri}.
Záv╪r
CAST p²edstavuje zdarma standard, kter∞ je τiroce akceptován, je dostateƒn╪ rychl∞ a bezpeƒn∞ a má moºnost silné i slabé verze podle délky klíƒe. Co si p²át více? Není divu, ºe vyplnil vakuum, které existuje od "pádu" DES, a potrvá jeτt╪ jeden dva roky, neº bude vybrán nov∞ americk∞ τifrovací standard AES.
Vlastimil Klíma (vklima@decros.cz)
Infotipy
http://ds.internic.net/frc/
rfc2144 .txt
(Obsahuje definici a základní dokument - RFC 2144: CAST-128 Encryption Algorithms, C. Adams, Entrust Technologies, May 1997.)
http://www.entrust.com/library.htm
(Obsahuje studii "Constructing Symmetric Ciphers Using the CAST Design Procedure" o kryptograficko-bezpeƒnostních aspektech algoritmu.)
http://adonis.ee.queensu.ca:8000/cast/cast.html
(Obsahuje dokument "CAST Encryption Algorithm Related Publications" s dalτími informacemi k algoritmu.)
http://www.mhv.net/~mgraffam/ce/cryptography.html
(Obsahuje voln╪ τi²itelnou implementaci CAST v jazyce C.)
