Advanced Encryption Standard

Advanced Encryption Standard

Rodzaj algorytmu	symetryczny szyfr blokowy
Data stworzenia	1998
Autorzy	Vincent Rijmen, Joan Daemen
Wielkość bloku wejściowego	128 bitów
Wielkość bloku wyjściowego	128 bitów
Długość klucza	128, 192, 256 [bit]
Liczba rund	zależna od klucza: 10 dla 128-bitowego 12 dla 192-bitowego 14 dla 256-bitowego

Advanced Encryption Standard (krócej AES, nazwa oryginalna: Rijndael) – symetryczny szyfr blokowy przyjęty przez NIST jako standard FIPS-197 w wyniku konkursu ogłoszonego w 1997 roku. W 2001 roku został przyjęty jako standard.

AES jest oparty na algorytmie Rijndaela, którego autorami są belgijscy kryptografowie, Joan Daemen i Vincent Rijmen. Zaprezentowali oni swoją propozycję szyfru Instytucji NIST w ramach ogłoszonego konkursu. Rijndael jest rodziną szyfrów o różnych długościach klucza oraz różnych wielkościach bloków.

W przypadku AES, NIST wybrał trzy algorytmy z rodziny Rijndaela, z których każdy miał tę samą wielkość bloku (128 bitów), ale miały różne długości klucza: 128, 192 i 256 bitów.

AES został przyjęty przez rząd amerykański i obecnie jest używany na całym świecie. Jest on następcą algorytmu DES, opracowanego w 1977. AES jest szyfrem symetrycznym, tzn. do szyfrowania i do odszyfrowywania wykorzystywany jest ten sam klucz.

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

AES stał się standardem rządu federalnego 26 maja 2002, gdy został zaaprobowany przez Sekretarza Handlu. Szyfr ten jest dostępny w wielu różnych pakietach. Ponadto jest pierwszym (i jedynym) dostępnym publicznie szyfrem, który był zatwierdzony i wykorzystywany przez NSA do ochrony ściśle tajnych informacji. Nazwa Rijndael jest kombinacją nazwisk twórców szyfru.

Standardy

AES jest zdefiniowany w standardach:

• FIPS PUB 197: Advanced Encryption Standard (AES) (ogłoszony 26 listopada 2001.)
• ISO/IEC 18033-3: Information technology – Security techniques – Encryption algorithms – Part 3: Block ciphers

Konkurs

Bezpośrednią przyczyną rozpisania konkursu była niewystarczająca siła algorytmu DES. W roku 1997 organizacja EFF była w stanie złamać wiadomość zaszyfrowaną DES-em w ciągu 3 dni sprzętem o wartości 250 tysięcy dolarów; obecnie można złamać DES-a jeszcze szybciej i taniej.

Do finału konkursu zakwalifikowało się pięć algorytmów szyfrujących (Rijndael, RC6, Mars, Serpent oraz Twofish), ze szczególnym wskazaniem na algorytm Rijndael. Możliwe jest w nim użycie kluczy o długościach 128, 192 i 256 bitów i operuje on na blokach danych o długości 128 bitów (oryginalna specyfikacja Rijndael dopuszczała również bloki 192- i 256-bitowe).

Algorytm

AES bazuje na zasadzie, zwanej siecią substytucji-permutacji. Wykazuje się dużą szybkością pracy zarówno w przypadku sprzętu komputerowego, jak i oprogramowania. W przeciwieństwie do swego poprzednika, algorytmu DES, AES nie używa Sieci Feistela. AES posiada określony rozmiar bloku – 128 bitów, natomiast rozmiar klucza wynosi 128, 192, lub 256 bitów. Funkcja substytucyjna ma bardzo oryginalną konstrukcję, która uodparnia ten algorytm na znane ataki kryptoanalizy różnicowej i liniowej.

Odmiany algorytmu Rijndael niebędące 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, nazywaną stanem. Jednak niektóre wersje algorytmu dysponują większym rozmiarem bloku oraz dodatkowymi kolumnami w macierzy. Większość obliczeń AES dokonywanych jest w konkretnym ciele skończonym.

Przykładowo, jeżeli mamy 16 bajtów, b0,b1,...,b15, są one reprezentowane w przedstawionej macierzy:

${\begin{bmatrix}b_{0}&b_{4}&b_{8}&b_{12}\\b_{1}&b_{5}&b_{9}&b_{13}\\b_{2}&b_{6}&b_{10}&b_{14}\\b_{3}&b_{7}&b_{11}&b_{15}\end{bmatrix}}$

Rozmiar klucza używany w algorytmie określa liczbę powtórzeń transformacji, które przekształcają dane wejściowe (czyli 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 rozłożony jest na cztery podobne (lecz nie identyczne) etapy. Jeden z tych etapów jest zależny od szyfrowania samego klucza.

Wykonując operacje w odwrotnej kolejności, używając tego samego klucza, można przekształcić szyfrogram z powrotem w tekst jawny.

Wysokopoziomowy opis algorytmu

1. Rozszerzenie klucza – z głównego klucza algorytmu „tworzy się” kolejne klucze. AES wymaga osobnego klucza 128-bitowego dla każdej rundy, plus jeden dodatkowy.
2. runda wstępna
   1. Dodawanie klucza rundy – każdy bajt macierzy stanu jest mieszany z blokiem rundy za pomocą operatora bitowego XOR.
3. Rundy
   1. Zamiana Bajtów – nieliniowa zamiana, podczas której każdy bajt jest zamieniany innym.
   2. Zamiana Wierszy – etap transpozycji, podczas którego trzy ostatnie wiersze macierzy stanu są cyklicznie zmieniane określoną ilość razy.
   3. Mieszanie Kolumn – Operacja odnosi się do kolumn macierzy. Polega na łączeniu czterech bajtów w każdej kolumnie.
   4. Dodaj klucz rundy
4. Final Round (brak operacji Mieszania Kolumn)
   1. Zamiana Bajtów
   2. Zamiana Wierszy
   3. Dodaj klucz rundy.

Kryptoanaliza

W 2006 opublikowana została praca, w której twierdzi się, że AES nie jest w pełni odporny na atak XSL, ale oszacowanie ilości koniecznych obliczeń obarczone jest dużą niepewnością, w związku z tym oceny, na ile skuteczny jest ten atak, są różne.

W 2009 opublikowane zostały dwa nowe ataki z użyciem kluczy pokrewnych (related-key attack) redukujące złożoność AES-256 do 2¹¹⁹. Wobec licznie pojawiających się nowych i mało prawdopodobnych ataków na AES w 2010 roku, Vincent Rijmen opublikował ironiczny artykuł opisujący „atak nazwany praktycznym”.

W grudniu 2009 opublikowano atak na niektóre sprzętowe implementacje AES umożliwiający odtworzenie klucza ze złożonością 2³² przez zastosowanie różnicowej analizy błędów (differential fault analysis).

Zużycie zasobów sprzętowych

Duża szybkość działania oraz niskie zużycie pamięci były głównymi kryteriami, na podstawie których wybierano algorytm. Algorytm AES funkcjonuje prawidłowo na szerokim zakresie urządzeń – zarówno na 8-bitowych kartach mikroprocesorowych, jak i na komputerach o wysokiej mocy obliczeniowej.

W przypadku mikroprocesorów klasy Pentium Pro, szyfrowanie za pomocą AES-a wymaga 18 cykli zegara na każdy bajt, co jest równoznaczne z wydajnością rzędu 11 MB/s dla procesora 200 MHz. Z kolei na procesorze klasy Pentium M o szybkości 1,7 GHz wydajność wynosi ok. 60 MB/s.

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

Linki zewnętrzne

• Kody źródłowe różnych algorytmów szyfrowania (także algorytmu Rijndael) na stronie Schneiera