Advanced Encryption Standard
Advanced Encryption Standard (AES) je symetrická bloková šifra (pro šifrování i dešifrování využívá stejný klíč na data s pevně danou délkou bloku), která nahradila dříve užívanou šifru DES.[1] Dnes 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 (vyslov [rejndál]). Její název vznikl přesmyčkou jmen jejích dvou autorů Joada 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.[2] 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 ke kódování 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[3] a na rozdíl od svého předchůdce DES nepoužívá Feistelovu síť.
Zatímco AES má pevně danou velikost bloku na 128 bitů a velikost klíče na 128, 192 nebo 256 bitů, u původní Rijndael šifry 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
Expanze klíče − podklíče jsou odvozeny z klíče šifry užitím Rijndael programu
Inicializační část
Přidání podklíče − každý byte stavu je zkombinován s podklíčem za pomoci operace xor nad všemi bity
Iterace
Záměna bytů − nelineární nahrazovací krok, kde je každý byte nahrazen jiným podle vyhledávací tabulky
Prohození řádků − provedení kroku, ve kterém je každý řádek stavu postupně posunut o určitý počet kroků
Kombinování sloupců − zkombinuje čtyři byty v každém řádku
Přidání podklíče
Závěrečná část (nekombinují se sloupce)
Záměna bytů
Prohození řádků
Přidání podklíče
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 nelinearitu v šifře. 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ě Rijndael šifry, 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 Rijndael šifru, 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.[4]
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 2200 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.[5] 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 Rijndael šifrou.“[6]
Bruce Schneier 1. července 2009 na svém blogu napsal o útoku založeném na podobnosti klíčů[7] provedeném Alexem Biryukovem a Dmitry Khorvratovichem se složitostí 2119. V prosinci 2009 byla tato složitost ještě vylepšena na 299.5.
Jiný útok byl oznámen Brucem Schneierem 30. července 2009 od autorů[8] 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 239 ke kompletní obnově 256bitového klíče o 9 iteracích nebo 245 o 10 iteracích se silnějším typem souvisejícího podklíčového útoku a nebo 270 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 2126.1 operací. Pro AES-192 a AES-256 je potřeba 2189.7 a 2254.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.[9] 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í 232 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í.
NIST/CSEC ověřování
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).