Advanced Encryption Standard

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
AES
AES-SubBytes.svg
Funkcja podstawieniowa
Rodzaj szyfru symetryczny szyfr blokowy
Data stworzenia 1997
Autorzy Vincent Rijmen, Joan Daemen
Wielkość bloku wejś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

AES (ang. Advanced Encryption Standard), nazwa oryginalna: Rijndael[1][2]symetryczny szyfr blokowy przyjęty przez NIST jako standard FIPS-197[3] w wyniku konkursu ogłoszonego w roku 1997. W 2001 roku został przyjęty jako standard.[4]

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

W przypadku AES'a, 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,[6] 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.[4]; 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[edytuj]

AES jest zdefiniowany w standardach:

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

Konkurs[edytuj]

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[edytuj]

AES bazuje na zasadzie, zwanej siecią substytucji-permutacji. Wykazuje się dużą szybkością pracy zarówno w przypadku sprzętu komputerowego, jak i oprogramowania. [9] 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[10].

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'a dokonywanych jest w konkretnym Ciele skończonym.

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

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[edytuj]

  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[edytuj]

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[11].

W 2009 opublikowane zostały dwa nowe ataki z użyciem kluczy pokrewnych (key related attack) redukujące złożoność AES-256 do [12]. 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"[13].

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

Zużycie zasobów sprzętowych[edytuj]

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-bit 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,[15], 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.[16]


Przypisy

  1. Rijndael. [dostęp 9 marzec 2015].
  2. a b AES Proposal: Rijndael. National Institute of Standards and Technology, 9 marzec 2003. [dostęp 21 luty 2013]. s. 1.
  3. FIPS-197: Advanced Encryption Standard. NIST.
  4. a b Announcing the ADVANCED ENCRYPTION STANDARD (AES). W: Federal Information Processing Standards Publication 197 [on-line]. United States National Institute of Standards and Technology (NIST), 26 listopad 2001. [dostęp 2 październik 2012].
  5. U.S. Selects a New Encryption Technique. . 
  6. Harold B. Westlund. NIST reports measurable success of Advanced Encryption Standard. . 
  7. http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf
  8. ISO/IEC 18033-3: Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers.
  9. Bruce Schneier, John Kelsey, Doug Whiting, David Wagner, Chris Hall: The Twofish Team's Final Comments on AES Selection. May 2000.
  10. Mirek Sopek: Szyfr Rijndael/AES.
  11. Nowe ataki na szyfry. SecurityStandard.pl, 2006.
  12. Nowy atak na AES-256. IPSec.pl, 1 lipca 2009.
  13. Vincent Rijmen: Practical-Titled Attack on AES-128 Using Chosen-Text Relations. 2010.
  14. Dhiman Saha, Debdeep Mukhopadhyay, Dipanwita RoyChowdhury: A Diagonal Fault Attack on the Advanced Encryption Standard. 2009.
  15. Performance Comparisons of the AES submissions. 1999-02-01. [dostęp 2010-12-28].
  16. Grant McWilliams: Hardware AES Showdown - VIA Padlock vs. Intel AES-NI vs. AMD Hexacore. 6 July 2011. [dostęp 2013-08-28].

Linki zewnętrzne[edytuj]