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).