Advanced Encryption Standard

Advanced Encryption Standard (AES, česky standard pokročilého šifrování) je standardizovaný algoritmus používaný k šifrování dat v informatice. Jedná se o symetrickou blokovou šifru šifrující i dešifrující stejným klíčem data rozdělená do bloků pevně dané délky. Norma nahradila dříve užívanou šifru DES. Je používána například pro bezdrátové Wi-Fi sítě v rámci zabezpečení WPA2 dle standardu IEEE 802.11i.

Historie

Původní název šifry AES je Rijndael (holandská výslovnost /ˈrɛindaːl/). Její název vznikl přesmyčkou jmen jejích dvou autorů Joana Daemena a Vincenta Rijmena z belgické Lovaně, kteří tuto šifru přihlásili do veřejné soutěže NIST o federální šifrovací algoritmus AES vyhlášené 2. ledna 1997. Americký úřad pro standardizaci (NIST) schválil 26. listopadu 2001 šifru AES jako nejvhodnější návrh z patnácti předložených po pěti letech schvalovací procedury. AES je první šifra dostupná široké veřejnosti, která byla zároveň uznaná Národní bezpečností agenturou NSA k šifrovaní nejtajnějších dokumentů. Dne 26. května 2002 začala být ke svému účelu používána jako federální standard USA.

Popis šifry

AES šifra je rychlá v softwaru i hardwaru (například s využitím AES-NI) a na rozdíl od svého předchůdce DES nepoužívá Feistelovu síť. Místo toho využívá tzv. SP-síť, tedy substitučně-permutační.

Zatímco AES má pevně danou velikost bloku na 128 bitů a velikost klíče na 128, 192 nebo 256 bitů, u původní šifry Rijndael je velikost bloku a velikost klíče určena jakýmkoliv násobkem 32 bitů s minimální velikostí 128 bitů. Velikost bloku je maximálně 256 bitů, kdežto velikost klíče žádné teoretické maximum nemá. AES pracuje s maticí bytů 4×4 označovanou jako stav.

Bližší popis algoritmu

1. Expanze klíče − podklíče jsou odvozeny z klíče šifry užitím programu Rijndael
2. Inicializační část
   1. Přidání podklíče (Add Round Key) − každý byte stavu je zkombinován s podklíčem za pomoci operace xor nad všemi bity
3. Iterační část - 9, 11 nebo 13 iterací (v závislosti na délce klíče)
   1. Záměna bytů (SubBytes) − nelineární nahrazovací krok, kde je každý byte nahrazen jiným podle vyhledávací tabulky (S-Box)
   2. Prohození řádků (Shift Rows) − provedení kroku, ve kterém je každý řádek stavu postupně posunut o určitý počet kroků
   3. Kombinování sloupců (Mix Columns) − zkombinuje čtyři byty v každém sloupci
   4. Přidání podklíče (Add Round Key)
4. Závěrečná část (nekombinují se sloupce)
   1. Záměna bytů (SubBytes)
   2. Prohození řádků (Shift Rows)
   3. Přidání podklíče (Add Round Key)

Záměna bytů

Při záměně bytů je každý byte v matici nahrazen pomocí 8bitového zaměňovacího boxu, Rijndeal S-boxu (nelineární substituční funkce měnící jednotlivé bity). Tato operace zajišťuje šifře nelinearitu. Aby S-box minimalizoval pravděpodobnost možných útoků založených na jednoduchých algebraických vlastnostech, je konstruován tak, aby v něm nevznikaly pevné body a žádné jejich protějšky.

Prohození řádků

Tato operace probíhá na úrovních řádků, kde jednotlivě prohazuje byty v každém řádku o určitý přesah. V případě AES je první řádek ponechán beze změn. Každý byte druhého řádku je posunut o jeden doleva. Stejným způsobem je třetí a čtvrtý řádek posunut o dvě, respektive tři pozice. Pro bloky o velikostech 128 bitů a 192 bitů je postup prohození řádků stejný. V těchto případech je každý sloupec výstupu složen z bytů z každého sloupce na vstupu.

V případě šifry Rijndael mají varianty s většími velikostmi bloků lehce odlišné přesahy. U 256bitového bloku zůstává první řádek beze změn, druhý, třetí a čtvrtý řádek je posunut o 1, 3 a 4 byty − tato změna platí pouze pro šifru Rijndael, neboť AES nepoužívá 256bitové bloky.

Kombinování sloupců

V tomto kroku kombinujeme 4 byty v každém sloupci. Tato funkce vezme čtyři byty jako vstup a vrátí čtyřbytový výstup, kde každý vstupní byte ovlivní všechny výstupní byty. Společně s předchozími kroky zajistí dostatečnou náhodnost v šifře.

Přidání podklíče

Při přidání podklíče je každý byte zkombinován s podklíčem. Pro každou iteraci je podklíč odvozen z hlavního klíče. Každý podklíč má stejnou velikost a je přidán za pomoci kombinace každého bytu stavu s odpovídajícím bytem podklíče užitím XORu nad všemi bity.

Optimalizace šifry

U systémů s 32bitovými a většími délkami slov je možné urychlit provádění této šifry pomocí zkombinování operací záměna bytů a prohození řádků s operací kombinování sloupců, přičemž se transformují do sekvencí vyhledávacích tabulek. Pro provedení této operace jsou nezbytné čtyři 32bitové tabulky o 256 vstupech. Iterace může být nyní provedena s šestnácti vyhledávacími tabulkami a dvanácti 32bitovými XOR operacemi, následovanými čtyřmi 32bitovými XOR operacemi v kroku přidání podklíče.

Bezpečnost

Do května roku 2009 byl zaznamenán jediný úspěšný publikovaný útok na plnou AES pomocí postranních kanálů dané implementace.

NSA prozkoumala všechny AES finalisty včetně Rijndael a uvedla, že všechny z nich jsou dostatečně bezpečné pro neutajovaná data vlády Spojených států. V červnu 2003 americká vláda oznámila, že AES Rijndael může být použita i pro ochranu utajovaných informací.

AES provádí 10 iterací s 128bitovými klíči, 12 iterací s 192bitovými klíči a 14 iterací s 256bitovými klíči. Do roku 2006 jsou zaznamenány tyto nejznámější útoky: na 7 iterací s 128bitovými klíči, 8 iterací s 192bitovými klíči a 9 iterací s 256bitovými klíči.

Známé útoky

Kryptologové považují za částečné prolomení šifry jakýkoliv přístup, který vede k rozluštění rychleji než vyzkoušení všech možných klíčů (metoda řešení hrubou silou). Útok hrubou silou proti AES s 256bitovým klíčem by vyžadoval 2²⁵⁶ operací, celkový výpočet by tedy trval mnohem déle než je celkové stáří celého vesmíru.

AES má poměrně jednoduchý algebraický popis. V roce 2002 provedli Nicolas Courtois a Josef Pieprzyk teoretický útok označovaný jako XSL útok, ve kterém chtěli prokázat, že šifra je kvůli své jednoduchosti prolomitelná. Pozdější publikace dokázaly, že útok, tak jak byl originálně prezentován, by nefungoval.

Během schvalovací procedury AES Bruce Schneier, vývojář zúčastněného algoritmu Twofish, napsal: „Nevěřím, že jednou někdo objeví útok, který mu dovolí číst komunikaci kódovanou šifrou Rijndael.“

Bruce Schneier 1. července 2009 na svém blogu napsal o útoku založeném na podobnosti klíčů provedeném Alexem Biryukovem a Dmitry Khorvratovichem se složitostí 2¹¹⁹. V prosinci 2009 byla tato složitost ještě vylepšena na 2^99.5.

Jiný útok byl oznámen Brucem Schneierem 30. července 2009 od autorů Alexe Biryukova, Orr Dunkelmana, Nathana Kelleryho, Dmitry Khovratoviche a Adi Shamira proti AES-256, která užívá pouze dva související klíče a čas 2³⁹ ke kompletní obnově 256bitového klíče o 9 iteracích nebo 2⁴⁵ o 10 iteracích se silnějším typem souvisejícího podklíčového útoku a nebo 2⁷⁰ o 11 iteracích. 256-AES používá 14 iterací, proto tyto útoky nejsou efektivní na plnou AES.

První útoky na plnou AES za účelem obnovy klíče byly publikovány v roce 2011 těmito autory: Andrey Bogdanov, Dmitry Khovratovich a Christian Rechberger. Klíč je obnoven z AES-128 za 2^126.1 operací. Pro AES-192 a AES-256 je potřeba 2^189.7 a 2^254.4 operací.

Útoky postranními kanály

Tento druh útoku neútočí přímo na základní šifru, a proto nemá co do činění s bezpečností šifry jako takové, ale útočí na její implementaci na daném systému, což někdy vede k únikům dat. Existuje několik známých útoků na určité implementace AES.

V dubnu roku 2005 oznámil D. J. Bernstein prolomení uživatelského serveru pomocí tzv. cache-timing útoku. Server používal OpenSSL AES šifrování a byl nastaven tak, aby poskytoval co nejvíce možných informací.

V prosinci roku 2009 byl publikován útok se složitostí 2³² na implementaci hardwaru, který použil diferenciální analýzu chyby a umožnil získání klíče.

V listopadu 2010 Endre Bangerter, David Gullasch a Stephan Krenn publikovali článek, který popisoval praktický postup jak v „téměř reálném čase“ obnovit tajné klíče z AES-128 bez potřeby šifrovaného nebo otevřeného textu. Tento postup také fungoval vůči AES-128 implementacím, které používaly zkomprimované tabulky, například OpenSSL. Jako některé dřívější útoky i tento vyžadoval možnost spuštění libovolného kódu na systému provádějící AES šifrování.

Ověřování NIST/CSEC

Validační program kryptografických modulů (CMVP) je provozován americkým úřadem NIST a kanadským Institutem komunikační bezpečnosti (CSE). Použití schválených kryptografických modulů není vyžadováno vládou Spojených států pro aplikace, které nemají přesně specifikované použití kryptografie. Kanadská vláda pro takové aplikace doporučuje použití FIPS 140 ověřených kryptografických modulů.

Ačkoliv publikace FIPS 197 vydaná organizací NIST je unikátní dokument, který popisuje AES algoritmus, obchodníci stále ještě vyžadují CMVP pod FIPS 140 a ptají se po dalších starších algoritmech (například Triple DES nebo SHA1). Z tohoto důvodu se dají jen ojediněle najít kryptografické moduly, které jsou ověřeny pouze FIPS 197, a samotný NIST se obecně moc nezabývá tím, aby umístil schválené FIPS 197 moduly odděleně na jejich webové stránky. Na místo toho je FIPS 197 ověření běžně uvedeno pouze jako „FIPS schváleno: AES“ (s uvedením FIPS 197 certifikačního čísla).

Odkazy

Reference

V tomto článku byl použit překlad textu z článku Advanced Encryption Standard na anglické Wikipedii.

Externí odkazy

• Obrázky, zvuky či videa k tématu Advanced Encryption Standard na Wikimedia Commons
• (anglicky) NIST, National Institute of Standards and Technology, Computer Security Division, csrc.nist.gov
• (anglicky) A Stick Figure Guide to the Advanced Encryption Standard (AES) - vysvětlení principu šifry AES formou komiksu srozumitelného laikům
• (česky) AES (Advanced Encryption Standard) - šifra pro třetí tisíciletí Archivováno 12. 1. 2011 na Wayback Machine., Petr Doležal