Advanced Encryption Standard

Zaawansowany Standard Szyfrowania (AES)

Advanced Encryption Standard (w skrócie AES, oryginalna nazwa: Rijndael) to symetryczny szyfr blokowy, który został przyjęty przez NIST jako standard FIPS-197 po ogłoszeniu konkursu w 1997 roku. W 2001 roku standard ten został oficjalnie zatwierdzony.

AES oparty jest na algorytmie Rijndael, stworzonym przez belgijskich kryptografów Joan Daemen oraz Vincent Rijmen. Ich propozycja szyfru została przedstawiona w ramach konkursu ogłoszonego przez NIST. Rijndael to rodzina szyfrów, która oferuje różne długości klucza oraz różnorodne rozmiary bloków.

Dla standardu AES, NIST wybrał trzy algorytmy z rodziny Rijndaela, z których każdy operuje na tym samym rozmiarze bloku (128 bitów), ale z różnymi długościami klucza: 128, 192 oraz 256 bitów.

AES został zaakceptowany przez rząd amerykański i obecnie jest stosowany na całym świecie. Szyfr ten stanowi następcę algorytmu DES, który został opracowany w 1977 roku. AES jest szyfrem symetrycznym, co oznacza, że do szyfrowania i odszyfrowywania używa się tego samego klucza.

W Stanach Zjednoczonych AES został ogłoszony przez NIST jako PUB 197 (FIPS 197) 26 listopada 2001 roku; przed tym wydarzeniem co pięć lat odbywały się procesy normalizacji, podczas których prezentowano i ulepszano piętnaście różnych rozwiązań.

AES stał się standardem rządu federalnego 26 maja 2002 roku, kiedy to został zatwierdzony przez Sekretarza Handlu. Szyfr ten jest dostępny w wielu różnych pakietach, a ponadto jest pierwszym (i jedynym) publicznie dostępnym szyfrem, który został zatwierdzony i wykorzystywany przez NSA do ochrony ściśle tajnych informacji.

Nazwa Rijndael jest kombinacją nazwisk jego twórców.

Standardy

AES jest zdefiniowany w następujących standardach:

FIPS PUB 197: Advanced Encryption Standard (AES) (ogłoszony 26 listopada 2001).
ISO/IEC 18033-3: Technologie informacyjne – Techniki zabezpieczeń – Algorytmy szyfrowania – Część 3: Szyfry blokowe.

Konkurs

Bezpośrednią przyczyną ogłoszenia konkursu była niewystarczająca siła algorytmu DES. W 1997 roku organizacja EFF zdołała złamać wiadomość szyfrowaną DES-em w ciągu 3 dni przy użyciu sprzętu o wartości 250 tysięcy dolarów; obecnie złamanie DES-a jest jeszcze szybsze i tańsze.

Do finału konkursu zakwalifikowało się pięć algorytmów szyfrujących: Rijndael, RC6, Mars, Serpent oraz Twofish, z szczególnym wyróżnieniem dla Rijndaela. Algorytm ten pozwala na użycie kluczy o długościach 128, 192 oraz 256 bitów i operuje na blokach danych o długości 128 bitów (oryginalna specyfikacja Rijndael dopuszczała również bloki 192- i 256-bitowe).

Algorytm

AES opiera się na zasadzie zwanej siecią substytucji-permutacji. Charakteryzuje się dużą szybkością działania zarówno w kontekście sprzętu, jak i oprogramowania. W przeciwieństwie do swojego poprzednika, algorytmu DES, AES nie wykorzystuje Sieci Feistela. AES ma zdefiniowany rozmiar bloku wynoszący 128 bitów, a rozmiar klucza wynosi 128, 192 lub 256 bitów. Funkcja substytucyjna ma unikalną konstrukcję, co sprawia, że algorytm jest odporny na znane ataki kryptoanalizy, takie jak ataki różnicowe i liniowe.

Odmiany algorytmu Rijndael, które nie są standardem AES, w zależności od długości klucza i bloku danych wykonują 12 lub 14 rund szyfrujących.

AES operuje na macierzy bajtów o wymiarach 4×4, zwanej stanem. Niektóre wersje algorytmu mogą mieć większy rozmiar bloku oraz dodatkowe kolumny w macierzy. Większość obliczeń w AES przeprowadzana jest w określonym ciele skończonym.

Na przykład, jeśli mamy 16 bajtów: b0, b1, …, b15, są one reprezentowane w następującej macierzy:

[

b0, b4, b8, b12

b1, b5, b9, b13

b2, b6, b10, b14

b3, b7, b11, b15

]

Rozmiar klucza używanego w algorytmie określa liczbę powtórzeń transformacji, które przekształcają dane wejściowe (tekst jawny) w dane wyjściowe (szyfrogram).

Liczba cykli powtórzeń jest następująca:

10 cykli powtórzeń dla klucza 128-bitowego;
12 cykli powtórzeń dla klucza 192-bitowego;
14 cykli powtórzeń dla klucza 256-bitowego.

Wszystkie rundy składają się z kilku kroków, z których każdy podzielony jest na cztery podobne (choć nie identyczne) etapy. Jeden z tych etapów jest zależny od szyfrowania samego klucza.

Wykonując operacje w odwrotnej kolejności i używając tego samego klucza, możliwe jest przekształcenie szyfrogramu z powrotem do tekstu jawnego.

Wysokopoziomowy opis algorytmu

Rozszerzenie klucza – z głównego klucza algorytmu generowane są kolejne klucze. AES wymaga osobnego klucza 128-bitowego dla każdej rundy oraz jednego dodatkowego.

Runda wstępna
Dodawanie klucza rundy – każdy bajt macierzy stanu jest mieszany z blokiem rundy za pomocą operatora bitowego XOR.
Rundy
Zamiana Bajtów – nieliniowa zamiana, w której każdy bajt jest zamieniany na inny.
Zamiana Wierszy – etap transpozycji, gdzie trzy ostatnie wiersze macierzy stanu są cyklicznie zmieniane określoną liczbę razy.
Mieszanie Kolumn – operacja dotycząca kolumn macierzy, polegająca na łączeniu czterech bajtów w każdej kolumnie.
Dodaj klucz rundy
Final Round (brak operacji Mieszania Kolumn)
Zamiana Bajtów
Zamiana Wierszy
Dodaj klucz rundy.

Kryptoanaliza

W 2006 roku opublikowano pracę, która stwierdza, że AES nie jest w pełni odporny na atak XSL, jednak oszacowanie liczby wymaganych obliczeń jest obarczone dużą niepewnością, co prowadzi do różnych ocen skuteczności tego ataku.

W 2009 roku przedstawiono dwa nowe ataki wykorzystujące klucze pokrewne (related-key attack), które redukują złożoność AES-256 do 2119. W odpowiedzi na liczne, nowe i mało prawdopodobne ataki na AES, w 2010 roku Vincent Rijmen opublikował ironiczny artykuł dotyczący „ataku nazwanego praktycznym”.

W grudniu 2009 roku ujawniono atak na niektóre sprzętowe implementacje AES, który umożliwił odtworzenie klucza ze złożonością 232 za pomocą różnicowej analizy błędów (differential fault analysis).

Zużycie zasobów sprzętowych

Wysoka szybkość działania oraz niskie zużycie pamięci były kluczowymi kryteriami wyboru algorytmu. AES działa prawidłowo na szerokim zakresie urządzeń – zarówno na 8-bitowych kartach mikroprocesorowych, jak i na komputerach o dużej mocy obliczeniowej.

Dla mikroprocesorów klasy Pentium Pro, szyfrowanie za pomocą AES-a wymaga 18 cykli zegara na każdy bajt, co przekłada się na wydajność około 11 MB/s dla procesora 200 MHz. Na procesorze klasy Pentium M o taktowaniu 1,7 GHz wydajność wynosi około 60 MB/s.

Na procesorach Intel Core i3/i5/i7, AMD APU, a także na procesorach AMD FX, które obsługują zestaw instrukcji AES, wydajność może przekroczyć 700 MB/s na każdy wątek.