Jednou z nejpouºívan╪jτích proudov∞ch τifer v internetové a komerƒní kryptografii je RC4. Po sedm let zàstávala zahalena obchodním tajemstvím firmy RSA. Poté ji ale rozkryl (disassembloval) jeden hacker a popis zve²ejnil na internetu. Z n╪kolika hledisek to je neobvyklá τifra. Seznámíme vás s její definicí a vlastnostmi.
µifra, která míchá karty
Popis RC4 se poprvé objevil na internetu v poτtovní konferenci "cypherpunks" v roce 1994. Byl to krátk∞ zdrojov∞ kód, kter∞ sem zaslal anonymní hacker. Definice RC4, která do té doby byla chrán╪n∞m obchodním tajemstvím spoleƒnosti RSA Data Security Inc. (dnes divize Security Dynamics Inc.), se prost²ednictvím internetu rázem roznesla po celém sv╪t╪. Ukázalo se, ºe z konstrukƒního hlediska je RC4 zajímavá a neobvyklá τifra. Je ²ádov╪ desetkrát rychlejτí neº DES a pouºívá ji ²ada programà, zejména americk∞ch. Nap²íklad je pouºita v protokolu Secure Socket Layer 3.0 firmy Netscape, v Microsoft Office, v Oracle Secure SQL, ve Windows 2000 i jinde.
Komerƒní kryptografie je obvykle ve²ejná
Souƒasn∞m sv╪tov∞m trendem v komerƒní kryptografii je pouºívání ve²ejn∞ch τifer. To je zcela v po²ádku, protoºe tyto τifry pouºívá τiroká ve²ejnost a zajiτ£ují se jimi ràzné bezpeƒnostní sluºby (dàv╪rnost, autentizace, integrita aj.); proto je také správné, aby jejich kvalita mohla b∞t ve²ejn╪ posuzována. Takov∞ch τifer je sice poƒetn╪ málo, ale v komerƒní oblasti mají velmi silné procentuální zastoupení. Dá se dokonce ²íci, ºe se o jin∞ch τifrách vlastn╪ ani neví. RC4 byla v∞jimkou, která byla nasazena ve znaƒné ƒásti softwaru, nebo£ za ní stála dostateƒn╪ silná americká spoleƒnost. Zajímavé je, ºe málokdo ji p²itom podezíral, ºe by pouºila slabou τifru.
Je kaºdá utajená τifra slabá?
Aº do svého odhalení pat²ila τifra RC4 do t²ídy tzv. proprietárních algoritmà. N╪které zkuτenosti s nepublikovan∞mi slab∞mi τiframi vedly k dosti rozτí²ené tendenci nedàv╪²ovat takov∞m τifrám a povaºovat je a priori za mén╪ hodnotné. U τifry RC4 se vτak toto vτeobecné mín╪ní z neznám∞ch p²íƒin neuplatnilo.
Je také dobré si uv╪domit, ºe ve sv╪t╪ existuje velk∞ poƒet dalτích proprietárních τifer, o kter∞ch nemáme ani tuτení a které jsou také kvalitní. Jsou to utajované τifry pouºívané v ozbrojen∞ch silách (vojsko, policie, rozv╪dka, kontrarozv╪dka), v bankovnictví a ƒásti pràmyslu, ve státní správ╪, v diplomacii i ve vlád╪. Je jich mnohem více neº τifer publikovan∞ch. Jejich utajení p²itom vàbec nepramení z obavy o kvalitu, ale je bezpeƒnostním opat²ením, které zásadn╪ znep²íjemσuje ºivot p²ípadn∞m útoƒníkàm na bezpeƒnostní systémy nebo τifrovaná data.
To byla ostatn╪ i p²íƒina utajení RC4. M╪la chránit citlivá data zákazníkà vƒetn╪ ƒísel kreditních karet, privátních dokumentà ap. Pokud bychom postupovali podle zako²en╪ného zjednoduτeného schématu "proprietární rovná se slab∞", RC4 by m╪la b∞t slabou τifrou. Je tomu ale práv╪ naopak.
RSA se zlobí
Krátce po zve²ejn╪ní údajného kódu RC4 bylo v téºe poτtovní konferenci potvrzeno, ºe se shoduje s v∞sledky τifry RC4 z oficiálního toolkitu spoleƒnosti RSA. RSA pak vydala prohláτení, ºe tento akt poruτil právo, ºe je to zneuºití internetu a ºe p²ijme opat²ení proti tomu, kdo by cht╪l naruτit duτevní vlastnictví firmy. Asi se bála, aby τifru nezaƒali pouºívat její konkurenti v komerƒních produktech, protoºe nebyla v USA patentována.
K tomu ovτem nedoτlo a nedoτlo ani k rozτí²ení τifry mimo kontrolu RSA. Nebyl totiº dàvod. Ve sv╪t╪ byla k dispozici celá ²ada jin∞ch kvalitních a jako freeware právn╪ zcela bezkonfliktních τifer. Ale i tak existuje právn╪ nenapadnutelná cesta, jak ji pouºít i v USA. Staƒí napsat, ºe se pouºívá algoritmus se jménem t²eba XRC4, kter∞ je datov╪ kompatibilní s RC4 od RSA.
Popis RC4
RC4 je klasick∞ symetrick∞ algoritmus s tajn∞m klíƒem. Je to proudová τifra, kterou navrhl Ronald Rivest (RC znamená Rivest's Cipher), jeden z vynálezcà algoritmu RSA a spoluzakladatel spoleƒnosti RSA DSI.
Vstupem RC4 je klíƒ o volitelné délce, teoreticky aº 256 bajtà. Klíƒ inicializuje koneƒn∞ automat, kter∞ pak generuje posloupnost bajtà hesla h(0), h(1), ... P²i zaτifrování se heslo "xoruje" na otev²en∞ text a p²i odτifrování na τifrov∞ text, tedy: τt(i) = ot(i) xor h(i), i = 0, 1, ...
Základem konstrukce RC4 je princip podobn∞ míchání karet. M╪jme t²eba 256 karet v n╪jakém základním zamíchání, které si oznaƒíme jako karta(0), ..., karta(255) a které vyloºíme za sebou na stàl. (Na kartách mohou také b∞t napsána ƒísla, s nimiº màºeme d╪lat ràzná kouzla, ale o tom aº pozd╪ji.) Kaºdé po²ádné míchání má b∞t náhodné, p²edpokládejme tedy, ºe máme k dispozici 256 na kartách zcela nezávisl∞ch náhodn∞ch "míchacích" (z mnoºiny 0 aº 255) ƒísel r(i), i = 0, 1, ... 255. ¼asto pouºívan∞m míchacím principem je tento postup:
1. krok: vym╪níme karty na pozici
0 a r(0);
2. krok: vym╪níme karty na pozici
1 a r(1);
3. krok: vym╪níme karty na pozici
2 a r(2);
...
256. krok: vym╪níme karty na pozici
255 a r(255).
Takto vezmeme do ruky celkem 512 karet, takºe kaºdá v pràm╪ru dvakrát zm╪ní své místo. Protoºe ƒísla r(i) jsou náhodná, budou se mezi nimi vyskytovat n╪která ƒísla z mnoºiny 0 ... 255 vícekrát, zatímco jiná vàbec. N╪které karty se tedy budou p²esunovat vícekrát, jiné jen jednou. Princip míchání zaruƒuje, ºe kaºdá karta bude vzata alespoσ jednou do ruky, ale kam a kolikrát se p²esune, to záleºí na celé posloupnosti r.
V extrémním p²ípad╪ màºe jedna karta zm╪nit své místo i 256krát, tj. v kaºdém kroku míchání. Pokud si pod kartami p²edstavíme ƒísla tak, ºe karta(i) = i, pak z poƒáteƒní identické permutace ƒísel (karet) 0 ... 255 máme na konci míchání náhodnou permutaci ƒísel 0 ... 255, jejíº prvky závisí na vτech náhodn∞ch hodnotách r. Ideální princip pro τifru! RC4 tak také, jen nepatrn╪ sloºit╪ji, vytvá²í svoji permutaci (substituƒní tabulku) S pro inicializaci generátoru hesla.
Karty míchá τifrovací klíƒ
µifrovací klíƒ RC4 (uvaºuje se zarovnan∞ na bajty) opakujeme tolikrát za sebou, aº naplníme pole 256 bajtà K(0), K(1), ... , K(255). Poté zvolíme identickou poƒáteƒní permutaci S, tj. S(i) = i, i = 0 ... 255, a promícháme ji prost²ednictvím hodnot K(i), které postupn╪ uƒiníme jeτt╪ trochu sloºit╪jτími. Jestliºe pràb╪ºn∞ index oznaƒíme i = 0 ... 255, mícháme podle tohoto pseudokódu:
j = 0
for i = 0 to 255
{
j = (j + S(i) + K(i)) mod 256
S(i) <-> S(j)
}
V kaºdém míchacím kroku se tedy vym╪σují prvky permutace S na pozicích i a j. Index i je pràb╪ºn∞, zatímco "míchací index" j závisí na klíƒi. Kdyby bylo ve vzorci pouºito jen j = K(i), byl by to p²esn╪ p²ípad míchání popsan∞ v p²edchozím odstavci. Nedosáhli bychom ale tak dobrého promíchání, protoºe posloupnost K není náhodná, ale naopak se v ní míchací bajty opakují!
Pro ilustraci zvolme ƒty²bajtov∞ klíƒ 50, 100, 131, 212. Koneƒn∞m v∞sledkem míchání je posloupnost 50, 100, 131, 212, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ..., která p²íliτ náhodn╪ nevypadá. Aby se opakování v posloupnosti K eliminovalo, míchací index j závisí nejen na K, ale na vτem, co se v kaºdém p²edchozím kroku m╪nilo, tj. na vτech (!) p²edchozích pràb╪ºn∞ch hodnotách j, S a K. Díky tomu míchací index j závisí na klíƒi velmi sloºit╪, náhodn╪ a periodiƒnost je tedy odstran╪na.
Jak se generuje heslo
Po inicializaƒní fázi se s mícháním pokraƒuje, ale tentokrát uº kaºd∞ krok produkuje jeden bajt hesla podle následujícího pseudokódu takto (vτechna sƒítání jsou v modulu 256):
j = 0, i = 0,
for t = 0 to N
{
i = i + 1
j = j + S(i)
S(i) <-> S(j)
h(t) = S(S(i) + S(j))
}
Délka klíƒe
RC4 se nejvíce pouºívá s délkou klíƒe 40 nebo 128 bità. Delτí klíƒ je pouºíván na území USA a kratτí klíƒ pro export. Práv╪ toto omezení zpàsobuje, ºe protokol SSL p²i ustavení τifrovaného kanálu u spojení mezi neamerick∞m klientem a americk∞m webem um╪le sníºí délku klíƒe na 40 bità. T╪chto 40 bità se doplní ve²ejnou náhodnou informací vym╪n╪nou mezi ob╪ma stranami na poƒátku protokolu SSL a na tento ²et╪zec se aplikuje haτovací funkce MD5 (viz téº Chip 4/99, str. 44). Z haτovacího kódu se pouºije 88 bità k dopln╪ní pàvodních 40, ƒímº je vytvo²en 128bitov∞ klíƒ pro RC4. Jeho efektivní délka ale zàstává 40 bità.
Θtok na RC4 v protokolu SSL
Vzhledem k obavám z nedostateƒné bezpeƒnosti 40bitového klíƒe byla na internetu také zve²ejn╪na v∞zva k rozluτt╪ní jedné reálné zprávy. µlo o zachycení skuteƒné komunikace mezi klientem a webov∞m serverem pomocí protokolu SSL. Bylo v ní mj. zaτifrováno i ƒíslo kreditní karty. První v∞zva byla zve²ejn╪na 14. 7. a druhá 19. 8. 1995. U první trvalo zjiτt╪ní klíƒe osm dní, u druhé 32 hodin. Byl p²itom pouºit jenom triviální útok hrubou silou, kdy byl prost╪ zkouτen jeden 40bitov∞ klíƒ za druh∞m, ale celá akce vzbudila na internetu velk∞ rozruch. µifra RC4 tím vτak nijak poτkozena nebyla.
Pro zajímavost dodejme, ºe RC4 dostala generální povolení od NSA k v∞vozu (nemuselo se ºádat na kaºd∞ p²ípad zvláτ£), pokud délka klíƒe bude redukována na 40 bità.
Nyní je uº jeden a t²i ƒtvrt╪ roku moºné vyváºet τifry s délkou klíƒe 56 bità, ale kvàli kompatibilit╪ to mnoho producentà softwaru nevyuºilo. Pràkopníkem je, zdá se, Microsoft, kter∞ do Windows 2000 implementoval bezpeƒnostní protokol Kerberos. Ten d²íve pouºíval DES, ale nyní má nov╪ vτude jako p²ednastavenou τifru definovánu práv╪ RC4 s 56 bity klíƒe (pro Ameriƒany 128).
Kryptografická kvalita
Tém╪² vτechny dosud publikované proudové τifry jsou zaloºeny na lineárních posuvn∞ch registrech se zp╪tnou vazbou a následnou nelineární funkcí nebo nepravideln∞m nelineárním krokováním registrà. Tyto konstrukce mají v∞hodu, ºe je u nich teoreticky dob²e zvládnuta otázka periodiƒnosti, lineární sloºitosti a statistick∞ch vlastností. To se ale o RC4 ²íci nedá. Ta je zaloºena na principu koneƒného automatu, p²iƒemº geniální myτlenka míchání pochází z roku 1965 od MacLarena a Marsaglii, kte²í na ní jako první zaloºili generátor pseudonáhodn∞ch ƒísel (blíºe viz Chip 6/98, str. 46).
Vnit²ní stav automatu lze charakterizovat indexy i a j a obsahem permutace S. Automat p²echází z jednoho stavu do druhého a na základ╪ kaºdého vnit²ního stavu se vypoƒte jeden bajt hesla.
Vτech jeho moºn∞ch stavà je
256*256*(1*2*3* ... *256),
coº je maximální moºná délka periody hesla. Toto ƒíslo je p²ibliºn╪ rovné 2M , kde M = 1700.
RC4 je automatem, v n╪mº se z následujícího stavu dá p²ejít do stavu p²edcházejícího jednoznaƒn∞m zpàsobem. O t╪chto automatech víme, ºe jejich stavy mohou tvo²it seskupení ràzn╪ dlouh∞ch cyklà o délkách 1, 2, ... , 2M, p²iƒemº vτechny cykly jsou stejn╪ pravd╪podobné. V tomto seskupení se typicky objevuje jeden velk∞ cyklus s délkou kolem 2M-1 a zbytek tvo²í menτí cykly ràzn∞ch délek. Pràm╪rná perioda je z pravd╪podobnostního hlediska 2M-1, coº u RC4 je dostateƒn╪ velké ƒíslo 21699. O dalτích vlastnostech toho není mnoho známo.
V∞sledky teoretického v∞zkumu
Zatím byly publikovány dv╪ zajímavé práce, které zkoumaly RC4 analyticky. Jde o Goliƒàv p²ísp╪vek "Linear Statistical Weakness of Alleged RC4 keystream Generator", p²ednesen∞ na konferenci Eurocrypt∩97, a o p²ísp╪vek v╪dcà Knudsena, Meiera, Preenela, Rijnmena a Verdoolaege s názvem "Analysis Methods for (Alleged) RC4", kter∞ zazn╪l na konferenci Asiacrypt∩98.
V první práci znám∞ b╪lehradsk∞ specialista na proudové τifry zkoumá moºnost lineární aproximace produkovaného hesla. Jeho v∞sledek lze zjednoduτen╪ zformulovat následovn╪. Vezm╪me vºdy nejniºτí bit kaºdého bajtu h(i) a oznaƒme jej z(i). Posloupnost z binárn╪ dvakrát zderivujme, ƒímº obdrºíme posloupnost d(i) ? z(i) xor z(i + 2). U posloupnosti d bylo zjiτt╪no, ºe její prvky d(i) mají tendenci b∞t spíτe jedniƒka neº nula, a to s pravd╪podobností 0,5 + 0,000000447. P²itom se tato korelace dá detekovat po cca 1012 bitech. Je to velmi hezk∞ teoretick∞, ale, jak jist╪ vidíte, prakticky nepouºiteln∞ v∞sledek.
Druh∞ p²ísp╪vek se snaºí odvodit poƒáteƒní permutaci S na základ╪ znalosti pom╪rn╪ krátkého úseku hesla (coº je oprávn╪n∞ p²edpoklad) - a auto²i vyvinuli algoritmus, kter∞ to umí. Je rychlejτí neº postupné zkouτení vτech moºn∞ch permutací, nebo£ má sloºitost blízkou odmocnin╪ vτech moºn∞ch permutací. I kdyº je to velk∞ teoretick∞ úsp╪ch, pro praktick∞ útok to znamená stále jeτt╪ p²íliτ velk∞ poƒet operací (p²es 10234).
Záv╪r
RC4 je zajímavá, neobvyklá a v∞jimeƒná τifra - jedna z mála velice rozτí²en∞ch proprietárních τifer, která zàstávala po sedm let tajná. Vymyká se také z obecn╪ oblíbeného omylu, ºe proprietární τifry musí b∞t slabé. Kupodivu na teoretickém poli bylo o ní dosud publikováno málo v∞sledkà. Moºná je tomu tak práv╪ proto, ºe kaºdému kryptologovi je na první pohled jasné, ºe si na ní vyláme zuby.
