8. Vybíráme nový standard



Vybíráme nový standard


Po cvičeních s maticemi, které budeme u následujícího typu šifrování potřebovat, si představíme soutěž, která předcházela výběru nového šifrovacího standardu.

Abyste mohli porovnat jednotlivé kandidáty na toto prestižní místo, budou vám blíže představeni finalisté, kteří se dostali do druhého kola této soutěže.

Potřebujeme tedy najít vhodný algoritmus, který bude především bezpečný, a nahradí již prolomený standard DES.


Algoritmus DES již dále nebyl udržitelný - proto NIST (National Institute of Standards and Technology) vyhlásil 2. 1. 1997 veřejnou soutěž o přijetí nové šifry AEA (Advanced Encryption Algorithm), která by se následně stalanovým šifrovacím standardem AES (Advanced Encryption Standard). Vítězná šifra se tedy bude jmenovat AES. Tato soutěž byla plně veřejná a otevřená komukoli, kdo podal vlastní návrh, a byl schopen dodržet kritéria daná NIST.

Cílem bylo navrhnout a získat novou velmi silnou šifru pro vládní i komerční použití.


Požadavky NIST

Hlavní požadavky, které NIST položil na novou šifru, byly takové, že AEA bude bloková symetrická šifra s délkoubloku 128 bitů, která musí podporovat délky klíčů 128, 192 a 256 bitů. Při výběru se posuzovala zejménabezpečnost, cena (v širokém smyslu slova - například cena při hardwarové implementaci) a softwarové vlastnosti, popřípadě kompatibilita. Vítaným plusem byly samozřejmě i vlastnosti nad rámec požadavků NIST.


Autorská práva

Protože AES představuje otevřený standard, určený i pro komerční účely, a tedy zaměřený na podporu informačních technologií jejich aplikací a dalšímu rozvoji, byla v podmínkách soutěže zakotvena i povinnost účastníků zřeknout se licenčních poplatků, autorských práv a vyřešit veškeré patentové ochrany tak, aby jejich algoritmus mohl býtkýmkoliv bezplatně použit.


Někteří kandidáti

Zde je výpis některých algoritmů, jejichž autoři poslali svůj návrh do soutěže o nový šifrovací standard


  • Algoritmus Rijndael, jehož autoři jsou Joan Deamen a Vincent Rijmen (Belgie)

    • šipka

    • RC6, jehož autory jsou RSA Laboratories (USA)
    • Twofish, o který se zasloužil tým autorů Bruce Scheiner, John Keisey, Dough Whiting, David Wagner, Chris Hall, Niels Ferguson (USA)
      • Magenta od Deutsche Telecom AG (Německo)

        • MARS vyvinutý společností IBM (USA)
        • Serpent od autorů Ross Anderson, Eli Biham, Lars Knudsen (UK, Izrael, Norsko)

          • šipka

          • Crypton od firmy Future Systems, Inc. (Korea)
          • a samozřejmě několik dalších....

9. června 1999 bylo do druhého kola vybráno pět finalistů. Staly se jimi algoritmy MARS, RC6, Rijndael, Serpent aTwofish. Nyní si tyto finalisty trochu představíme.

Twofish

Algoritmus Twofish je další z řady symetrických algoritmů, které používají Feistelovo schéma. Pamatujete si, jak vypadalo Feistelovo schéma z minulých článků a studijních aktivit?Twofish pracuje s bloky, které projdou 16 rundamiupravené jednobitovou rotací. Tento algoritmus používá různorodé operace, jako násobení, aritmetické sčítání, XOR aS-boxy (substituční boxy).Rundovní funkce používá zmiňované operace na 32bitových slovech, které projdou S-boxy, transformací a přičtením klíče.Substituční tabulky jsou závislé na klíči, který může být volitelně až 256 bitů dlouhý.

MARS

Dle požadavků NIST má MARS volitelnou délku klíče a to 128, 192 nebo 256 bitů. Pracuje s 32bitovými bloky dat.Zašifrování i dešifrování se provádí obdobně, obě činnosti se liší pouze opačným řazením rundovních podklíčů.MARS má několik fází přičítání a odčítání klíčů v 32 rundách, 8 rund dopředného mixování (bez účasti klíče), 16 rund přičítání a odčítání klíčů (za použití klíče) a 8 rund zpětného mixování (bez účasti klíče).Rundy, kde nejsou použity klíče, užívají sčítání a operaci XOR a dvou S-boxů navržených tak, aby odolávaly lineární a diferenciální kryptoanalýze. Klíčované rundy užívají 32bitové násobení a sčítání klíčů a datově závislé rotace (zřetězené rotace).

RC6-w/r/b

Tato šifra má několik volitelných parametrů: w (počet bitů slova), r (počet rund) a b (počet bytů klíče), proto se podle nich přesně označuje jako RC6-w/r/b. Pro kandidáta do soutěže AES bylo stanoveno

w = 32,r = 20,b volitelně 16, 24 nebo 32

Myšlenka RC6 těží z již dříve navržených a prověřených šifer RC5 a RC4 (taktéž z dílny RSA Laboratories). Autoři RC6 tedy postavili dvě RC5 paralelně vedle sebe a propojili je tak, aby každý bit slova 128bitového výstupního bloku závisel na všech bitech 128bitového slova vstupního bloku. K tomu byly využity datově závislé rotace řízené kvadratickou funkcí.RC6 má rundovní schéma vycházejícího též z Feistelova principu. V každé rundě se využije 32bitového násobení a sčítání, XOR a součet klíčů.

Rijndael

Rijndael podporuje volitelně i větší datové bloky a klíče, než požaduje NIST, nicméně pro AES byla na základě požadavků NIST stanovena délka datového bloku na 128 bitů. Délka klíče je pak 128, 192 nebo 256 bitů. Rijndael je velmi flexibilní návrh, který si popíšeme bytově s ohledem na další studijní aktivity, kde budeme rovněž pracovat v tomto typu šifrování s byty.Algoritmus samotný představuje vlastně substitučně-lineární transformační postup s 10, 12 nebo 14 rundami v závislosti na délce klíče (10, 12 nebo 14 rund bylo stanoveno pro odpovídající délky klíče 128, 192 a 256 bitů pro AES, lze pro další modifikace počet rund měnit).V jednotlivých rundách se vstupní blok dělí na pole bytů, které prochází šifrovými bytovými operacemi. Runda osahuje S-box, dvě mixovací lineární vrstvy a XOR rundovních klíčů na výsledné bytové pole, přičemž tento krok je vynechán u poslední rundy.

Serpent

Serpent, podobně jako Rijndael, je substitučně-lineární tranformační algoritmus pracující ve 32 rundách. Podporované jsou libovolné délky klíče do 256 bitů. Návrh šifry je dosti konzervativní, autoři nechtěli použít žádné inovativní prvky jako datově závislé rotace, násobení nebo sčítání místo operace XOR apod.Místo toho aplikovali osvědčené principy tak, aby šifra byla dobře hardwarově i softwarově implementovatelná, důraz byl položen na dobré zpracování jednotlivých bitů a výpočet rundovních klíčů.Runda se skládá ze tří operací: naXORování klíče, aplikace jednoho z 8 S-boxů a lineární transformace. V poslední rundě se místo lineární transformace použije ještě jedno XORování klíče.Dne2. října 2000 NIST ustanovil na základě diskuse a výsledků algoritmus Rijndael vítězem soutěže.Rijndael má podle NIST adekvátní úroveň bezpečnosti. A v současné době je platným standardem pro ochranu dat. Rijndael se tedy stal vítězem celé soutěže o šifrovací standard, a byl přejmenován na AES. A právě AES se budeme věnovat v následujících studijních aktivitách.

Shrnutí

Po úspěšném prolomení DES bylo zapotřebí najít jiný šifrovací algoritmus, který by DES nahradil. Proto NIST vyhlásil veřejnou soutěž, jejímž cílem bylo najít algoritmus, který dokáže zabezpečit data vysokým stupněm ochrany. Tato soutěž byla zcela veřejná a přihlásilo se několik kandidátů. Z nich bylo vybráno pět a vyhrál algoritmus Rijndael. Celá soutěž trvala čtyři roky a Rijndael byl podrobován všemožným testům, aby byl odolný vůči lineární i diferenciální kryptoanalýze. Výsledkem je, že je používán dodnes a je doporučován ve všech svých modifikacích (se 128, 192 i 256 bity dlouhým klíčem).

Zdroje

DOSTÁLEK, Libor a Marta VOHNOUTOVÁ. Velký průvodce infrastrukturou PKI a technologií elektronického podpisu. vyd. 1. Brno: Computer Press, 2006, 534 s. ISBN 80-251-0828-7.