![]() Specializovaný týdeník o výpočetní technice |
|
![]() |
Seriál o bezpečnosti a informačním soukromí |
Část 29 - CW 40/97
IDEA & kol. -- samé rozumné myšlenkyAntonín Beneš ml.
Šifrovací algoritmus DES byl v relativně krátkém čase zlomen skupinou amatérů. Začíná být mimo veškerou pochybnost, že tento algoritmus již došel na konec své kariéry. Naskýtá se otázka, co bude dál.
Zemřel král, kolem obchází anarchie Ne, že by DES byl úplně k ničemu a dobrý leda na smetiště. Jde o lety prověřený algoritmus, na jehož prolomení bylo vynaloženo obrovské úsilí - s poněkud hubenými výsledky. Výkon počítačů se však nebezpečně přiblížil k mezím bezpečnosti, kterou je DES schopen poskytovat. A tak, zatímco můžeme nechat v klidu dožít aplikace, které tento algoritmus používají, měli bychom se poohlédnout po "něčem lepším", co se stane srdcem našich příštích systémů. Problémem nalezení nového bezpečnějšího symetrického algoritmu, který by mohl zastoupit DES, se naštěstí již řadu let zabývají odborníci po celém světě. Bylo navrženo velké množství nejrůznějších algoritmů. Mnohé z nich se zdají být velmi kvalitní. Zatím se však žádný z nich nestal všeobecně přijímaným standardem. Opravdu důkladný zmatek do celé situace zanesla americká vláda svojí snahou prosadit zavedení algoritmu Skipjack jakožto nového průmyslového standardu. Úskalí spočívalo v tom, že tento algoritmus nebyl veřejně publikován a informace o něm jsou dodnes velice kusé.
Kudy, kudy cestička Před tím, než se budeme blíže věnovat vybraným šifrovacím algoritmům, pojďme se podívat obecně, jaké jsou současné trendy návrhu symetrických šifer. Začneme pěkně od Adama, resp. od DESu. Základním nedostatkem DESu je nedostatečná délka klíče, umožňující zlomení algoritmu prostou hrubou silou. Nové algoritmy tedy používají klíč o délce až několikanásobně delší. Poznamenejme, že např. na rozdíl od algoritmu RSA, zvětšování délky klíče v případě symetrických šifer většinou nemá negativní dopad na rychlost procesu (de)šifrování. DES byl původně navrhován spíše s ohledem na možnost hardwarové implementace pomocí speciálních obvodů. Ne každý si však chce, nebo může dovolit koupit pro účely šifrování zvláštní technické zařízení. Přitom používání kryptografie se stává nezbytností i pro běžného laického uživatele. Nastává tedy zřetelný trend navrhovat algoritmy s ohledem na možnost efektivní softwarové implementace na běžně dostupném hardwaru. Algoritmy se snaží v co nejširší míře používat jednoduché operace přímo obsažené v instrukčních souborech procesorů. Povšimněme si, že veškeré operace se vykonávají nad řetězci délky 32, nebo dokonce 16 bitů, což přesně odpovídá velikosti registrů. Pro účely softwarové implementace je zvláště nevhodné používání bitových permutací. Ty jsou nahrazovány vstupy řízenými výběry z tabulek (table lookup), které mají obdobné difuzní účinky. Rovněž paralelní použití S-boxů - podobně jako v DESu -- je nahrazováno sekvenčním. Pokud algoritmus používá S-boxy, nebo jejich obdobu, bývají S-boxy zpravidla podstatně větší, než v případě DESu. Zvětšení S-boxů přináší zvýšení odolnosti proti diferenciální kryptoanalýze. Dalšího zvýšení odolnosti proti diferenciální a lineární kryptoanalýze lze docílit, pokud S-boxy nejsou konstantní, tj. je-li jejich obsah závislý na šifrovacím klíči. Dalším trikem, který vede ke zvýšení odolnosti algoritmu, je kombinování operací z různých algebraických grup (např. XOR a sčítání mod 216, násobení mod 216 + 1). Naopak z kryptografického hlediska bezcenné jsou úvodní a závěrečná permutace, které DES realizuje. V soudobých šifrovacích algoritmech je proto již nepotkáme. Změnil se rovněž způsob generování subklíčů pro jednotlivá kola práce algoritmu. Před zahájením vlastního de/šifrování provádějí algoritmy zvláštní inicializační proces. Během něho si vygenerují tabulku všech subklíčů, S-boxů a případně dalších datových struktur, které pro svoji činnost potřebují. Čas spotřebovaný na inicializaci je následně výhodně amortizován v průběhu šifrování. Velká časová náročnost procesu generování subklíčů může být výhodná, neboť zvyšuje odolnost algoritmu proti útoku hrubou silou.
Malý kryptografický herbář V této části si ukážeme tři současné šifrovací algoritmy. Každý z nich má dostatečný potenciál, aby mohl posloužit jako mezinárodní standard. Všechny uvedené algoritmy byly svými tvůrci předloženy odborné veřejnosti k oponentuře. Dosud však není znám úspěšný útok proti některému z nich, což dává rozumnou naději, že jde o opravdu kvalitní šifry.
IDEA Autory algoritmu publikovaného v roce 1991 původně pod názvem IPES byli X. Lai a J. Massey. Současný název je akronymem za International Data Encryption Algorithm. Jde o blokovou šifru s délkou bloku 64 bitů, pracující s klíčem o délce 128 bitů. IDEA vznikla jako vylepšená verze svého předchůdce, algoritmu PES poté, co byla publikována metoda jeho zlomení. IDEA již začala úspěšně pronikat do praxe, velmi pravděpodobně ji používáte i vy. Ať již v rámci protokolu SSL, který používají třeba webové browsery, nebo jako součást populárního PGP. Blok otevřeného textu je rozdělen na čtyři části, každá o délce šestnáct bitů. Poté je provedeno osm kol šifrovacího procesu. V každém kole jsou jednotlivé bloky XORovány, násobeny a sčítány mezi sebou navzájem a šesti šestnáctibitovými subklíči. Na závěr je ještě každý blok kombinován s jedním subklíčem. Strukturu jednoho kola šifrovacího procesu a závěrečné fáze ukazuje obr. 1. Algoritmus použije celkem 52 subklíčů. Ty jsou z klíče odvozeny následujícím způsobem. Rozdělením klíče na osm částí vznikne prvních osm subklíčů. Poté je provedena rotace klíče vlevo o 25 bitů. Vzniklý řetězec je opět rozdělen na osm částí -- subklíčů. Opakováním tohoto postupu získáme potřebné množství subklíčů. Pro dešifrování se používá stejného algoritmu jako pro šifrování. Rozdíl je pouze v použitých subklíčích. Předpokládejme, že pro šifrování použijeme v i-tém (i = 1, ..., 8) kole klíčů
Z1(i), Z2(i), Z3(i), Z4(i), Z5(i), Z6(i)
vygenerovaných postupem popsaným v předchozím odstavci. Potom pro dešifrování použijeme klíčů ve tvaru
Z1(10 - i) - 1, -Z2(10 - i), -Z3(10 - i), Z4(10 - i) - 1, Z5(9 - i), Z6(9 - i)
IDEA může být používána v libovolném pracovním modu pro blokové šifry, zejména v modech ECB, CBC, OFB, CFB, ve kterých bývá používán DES. Pokud by někdo byl velmi podezíravý a nespokojil se s délkou klíče 128 bitů, může používat trojnásobné šifrování EDE Triple-IDEA. Při tomto postupu potřebujeme dva 128bitové klíče. Otevřený text je nejprve zašifrován prvním klíčem, výsledek je dešifrován druhým klíčem a na závěr je blok znovu šifrován prvním klíčem. Je možné vynechat proces generování subklíčů a místo toho použít 52 nezávislých řetězců. Tímto způsobem pravděpodobně nedojde k oslabení algoritmu. Je zajímavé, že pokud bychom algoritmus upravili tak, že zvětšíme délku všech řetězců, se kterými pracuje, na dvojnásobek, dojde ke ztrátě bezpečnosti.
Blowfish B. Schneier algoritmus publikoval v roce 1993. Jde o blokovou šifru s délkou bloku 64 bitů. Algoritmus pracuje s klíči různé délky až do maximální velikosti klíče 448 bitů. Jeho výhodou je, že na rozdíl od všech ostatních popisovaných algoritmů není patentován a je tedy možné jej volně používat. Jde o velmi rychlý, jednoduchý algoritmus, který je možno efektivně implementovat i na malých procesorech, nebo dokonce čipových kartách. Při pečlivém naprogramování se to všechno včetně všech svých datových struktur vejde do interní cache procesoru i486. Pokud používáte Secure shell, což je jeden z mála prostředků umožňujících bezpečný vzdálený přístup k unixovým strojům, můžete k šifrování komunikace použít právě Blowfish. Blok otevřeného textu je nejprve rozdělen na dvě poloviny. Následuje šestnáct kol šifrovacího procesu. V i-tém kole je levá polovina XORována s i-tým subklíčem. Následně je použita jako vstup pro výpočet ireverzibilní funkce. Při výpočtu této funkce se uplatní čtyři na klíči závislé S-boxy se vstupem o šíři 8 bitů a operace sčítání a XOR. Výsledek této funkce je XORován s pravou polovinou. Na konci kola jsou obě poloviny prohozeny. V závěrečné fázi jsou z technických důvodů opět prohozeny obě poloviny. Každá z nich je potom XORována s dalším subklíčem. Strukturu jednoho kola šifrovacího procesu a závěrečné fáze ukazuje obr. 2. Algoritmus ke své činnosti používá pole 18 subklíčů a čtyři na klíči závislé S-boxy. Tyto struktury jsou připraveny při inicializaci algoritmu. Nejprve jsou pole subklíčů a všechny S-boxy vyplněny konstantním řetězcem -- autoři doporučují použít část zápisu Ludolfova čísla. Potom je postupně obsah pole subklíčů a S-boxů XORován klíčem - k tomu můžeme používat klíče různých délek. Když takto vyplníme všechny řídicí struktury algoritmu, provedeme zašifrování bloku samých nul. Výsledek tohoto kroku uložíme do pole subklíčů na místo prvního a druhého subklíče. Získaný řetězec znovu zašifrujeme a uložíme jej na místo třetího a čtvrtého subklíče. Opakováním tohoto postupu postupně vyplníme všechny subklíče a všechny čtyři S-boxy. Tím je algoritmus připraven k šifrování. Dešifrování je stejné jako šifrování, pouze jednotlivé subklíče jsou používány v opačném pořadí. Algoritmus je opět použitelný ve všech běžných pracovních modech vhodných pro blokové šifry. Míru dosažené bezpečnosti lze regulovat délkou použitého klíče. Rovněž lze omezit počet kol šifrovacího procesu. Snížení počtu kol vede k jistému snížení odolnosti vůči lineární a diferenciální kryptoanalýze, výhodou je ovšem vyšší rychlost šifrování. Naopak se nezdá, že by další zvyšování počtu kol mělo zásadní vliv na zvýšení bezpečnosti algoritmu.
RC5 Se svojí troškou do mlýna přispěchal v roce 1994 i R. Rivest, známý jako spoluautor algoritmu RSA. RC5 přináší novou myšlenku použití rotací závislých na datech. Jde o velmi pružný algoritmus s celou řadou parametrů. Kromě délky šifrovacího klíče (0 až 255 bytů) lze nastavit počet kol šifrovacího procesu (opět 0 až 255). Z hodnot 16, 32, 64, ale i vyšších můžeme zvolit délku slova, přičemž algoritmus zpracovává bloky o délce dvojnásobku slova. I tento algoritmus již našel své praktické využití. Můžeme jej potkat třeba ve webowých browserech. Bohužel se stal obětí exportní politiky americké vlády. Zatímco občané Spojených států a Kanady se mohou těšit jeho plné ochraně, mezinárodní verze programů jsou dodávány s umělým omezením délky klíče na 40 tajných bitů. Ostatní bity klíče jsou známé. Proslýchá se, že firmě Netscape se podařilo získat povolení používat v mezinárodní verzi svého Navigatoru klíč s 56 tajnými bity. RC5 je taková paráda, že to ani slovy nelze vylíčit. Pomůžeme si proto zápisem pomocí pseukódu, který je podobný jazyku C. Zde znak 0+0 označuje bitové XOR, + značí sčítání modulo délka slova, -- odčítání, x <- y znamená rotaci řetězce x vlevo o y bitů a symbol -> používáme pro rotaci opačným směrem. Samozřejmě, smysl má provádět pouze rotaci o y mod (délka slova), vše ostatní je pouze zbytečné "obíhání okolo". Předpokládejme prozatím, že máme k dispozici pole subklíčů S. Nechť se blok otevřeného textu skládá ze dvou částí A a B. Šifrování probíhá dle následujícího předpisu: A = A + S[0]; B = B + S[1]; for i = 1 to <počet_kol> do A = ((A 0+0 B) <- B) + S[2i]; B = ((B 0+0 A) <- A) + S[2i + 1]; Pro dešifrování je tentokrát třeba použít postupu poněkud odlišného, než pro šifrování: for i = <počet_kol> downto 1 do B = ((B -- S[2i + 1]) -> A) 0+0 A); A = ((A -- S[2i]) -> B) 0+0 B); B = B -- S[1]; A = A -- S[0]; Zbývá popsat, jakým způsobem získáme ze šifrovacího klíče pole subklíčů S. K tomu budeme potřebovat pomocné pole L o velikosti tolik slov, aby se do něj "vešel" klíč a dvě magická čísla: Pw = Odd((e -- 2)2w) a Qw = Odd((fí -- 2)2w) kde e je základ přirozeného logaritmu (2,718281...), fí je tzv. zlatý řez (1,618033...) a w značí délku slova. Funkce Odd vrací nejbližší liché celé číslo. Do pole L zkopírujeme od začátku šifrovací klíč, a na konci případně doplníme nulami. Pole S naplníme dle předpisu S[0] = Pw; for i = 1 to 2 * (<počet_kol> + 1) -- 1 do S[i] = S[i -- 1 + Qw]; a proces generování subklíčů dokončíme promícháním obou polí: i = j = 0; A = B = 0; for k = 1 to 3 * max(s, l) do A = S[i] = (S[i] + A + B) <- 3; B = L[j] = (L[j] + A + B) <- (A + B ); i = (i + 1) mod(s); j = (j + 1) mod(l); kde s resp. l jsou velikosti polí S, resp. L. Pro své použití lze algoritmus přizpůsobit vhodnou volbou parametrů. Velikost slova je rozumné volit v závislosti na velikosti slova používaného procesoru, 128 bitů je to správné číslo, chceme-li algoritmus používat pro hašování. Zvětšování počtu kol vede ke zvyšování bezpečnosti algoritmu na úkor rychlosti. Šest kol postačí pro nenáročné aplikace, 32 pro ty nejnáročnější. Samozřejmě, čím delší klíč, tím lepší, ale nezapomeňte, že jej také musíte vygenerovat, dopravit na místo určení a tam uskladnit. Prakticky je jedno, jestli útočník před sebou má 1030, nebo 1050 roků usilovného počítání. Jako rozumná se jeví volba délka slova 32 bitů, 12 kol, 16bytový klíč, což krátce zapíšeme RC5-32/12/16.
Na dobrou noc Problém nalezení vhodného standardu je opravdu velmi palčivý. Komerční organizace musí investovat nemalé úsilí a finanční částky do výměny technologie. Změna musí být provedena všude, aby jednotlivé firmy byly schopny mezi sebou komunikovat. Vzhledem k její mimořádné náročnosti není čas na pokusy. Nezbývá nám než věřit, že se podaří najít volně distribuovatelný, dostatečně bezpečný a důvěryhodný algoritmus v co nejkratší době. Myslete na to. Seriál je rovněž dostupný na www.idg.cz/computerworld/bvsk/
| COMPUTERWORLD - seriál o bezpečnosti | COMPUTERWORLD | IDG CZ homepage | |