Ilustrowny opis standardu AES

Opublikowany: 26-12-2012 12:24 przez Krystian

Zamieszczony w tym artykule opis standardu AES wraz z ilustracjami był fragmentem mojej pracy dyplomowej.

 

Aby lepiej zrozumieć mechanizmy rządzące algorytmami kryptograficznymi trzeba zagłębić się w ich konstrukcję i poznać powody, dla których działają one w taki, a nie inny sposób. Algorytmem, który zostanie przedstawiony w tym rozdziale jest Rijndael/AES. Jest on obecnie jednym z najważniejszych szyfrów używanym zarówno w wojsku, w świecie biznesu, jak i w życiu codziennym.

 

W roku 1997 NIST (ang. National Institute of Standards and Technology) ogłosił konkurs na nowy standard federalny USA, ponieważ dotychczasowy standard federalny jeśli chodzi o szyfry - DES (ang. Data Encryption Standard) przestał być wystarczająco bezpieczny do szyfrowania informacji o najwyższym poziomie poufności. DES, a dokładniej Lucifer, bo tak nazywał się ten szyfr blokowy zanim został wybrany jako standard DES powstał w 1974 roku w laboratoriach IBM i po ponad dwudziestu latach użytkowania, ze względu na nieustannie rosnącą moc obliczeniową komputerów oraz coraz skuteczniejsze metody kryptoanalizy nie oferował już wystarczającego bezpieczeństwa, aby szyfrować nim ściśle tajne informacje. W 1997 roku do złamania wiadomości zaszyfrowanej algorytmem DES potrzeba było sprzętu wartego 250 000 dolarów pracującego przez trzy dni. 3DES - polegający na trzykrotnym użyciu normalnego algorytmu DES ze względu na bardzo słabą wydajność oraz podatność na atak typu meet in the middle był rozwiązaniem jedynie tymczasowym.

 

Nowy standard NIST miał nazywać się AES (ang. Advanced Encryption Standard). Miał być to szyfr symetryczny, blokowy - o blokach długości 128 bitów, korzystający ze 128, 192 i 256 bitowych kluczy.


Wybór standardu AES

Do ogłoszonego przez NIST konkursu zgłoszono piętnaście algorytmów szyfrujących. Do finalnej potyczki stanęły: Rijndael, RC6, Mars, Serpent oraz Twofish.

Po pięciu latach dokładnego oceniania zgłoszonych projektów ogłoszono zwycięstwo algorytmu Rijndael, który w 2002 roku stał się oficjalnie standardem federalnym i jednocześnie zyskał nową nazwę AES. Odporność na ataki kryptoanalityczne nie była jedynym wyznacznikiem w tych zmaganiach. Kryteria oceny zgłoszonych projektów były następujące:


- Ogólne bezpieczeństwo - ściśle związane z kryptoanalizą (chociażby liniową i różnicową) przeprowadzaną przez społeczność kryptologów podczas trwania procesu wyboru standardu AES. Liczne artykuły publikowane przez społeczność kryptologów na temat zgłoszonych szyfrów pozwoliły na dokładną ocenę i wyeksponowały większość wad i zalet zgłoszonych algorytmów.

- Implementacje programowe - w przypadku tego kryterium ważne były cechy takie jak: szybkość wykonywania, wydajność na różnych rodzajach platform czy zależność czasu wykonywania od długości klucza.

- Implementacje sprzętowe - podobnie jak implementacje programowe kryterium to związane jest z wydajnością na różnych platformach (w tym przypadku sprzętowych rzecz jasna). Innym, bardzo ważnym, dodatkowym czynnikiem jest rozmiar programu, który w przypadku implementacji sprzętowej przekłada się w sposób oczywisty na wzrost ewentualnych kosztów.

- Wystarczalność ograniczonej pamięci - zagadnienie związane z specyficznymi przypadkami urządzeń o bardzo ograniczonej pamięci w jakich oceniane szyfry miały być stosowane (np. karty inteligentne).

- Ataki implementacyjne - w tym przypadku chodzi o odporność na ataki na fizyczną implementację algorytmu. Przykładami tego rodzaju ataków są: atak czasowy czy analiza mocy. Możliwość przeprowadzania tego typu ataków związana jest z charakterystyką pracy układów elektronicznych - tj. mnożenie powoduje większe obciążenie niż dodawanie, co przekłada się na wzrost pobieranej przez układ mocy, podobnie jak zapis bitu o wartości 1 jest bardziej energochłonne niż zapis bitu o wartości 0, podobnie sprawa ma się z czasem wykonywania poszczególnych operacji.

- Szyfrowanie a deszyfracja - różnica między algorytmem szyfrującym i deszyfrującym. Im większa różnica między nimi tym większe zapotrzebowanie pamięciowe dla całej implementacji. Ważnym czynnikiem jest także różnica w czasie wykonywania tych dwóch algorytmów.

- Sprawność zarządzania kluczami - kryterium dotyczące wymiany kluczy oraz obliczania podkluczy, a dokładniej złożoności i zasobochłonności tego procesu.

- Potencjalne możliwości wykorzystania zrównolegleń - czyli możliwość wykorzystania przez oceniany algorytm coraz popularniejszego w dzisiejszych czasach przetwarzania równoległego oraz ewentualny narzut związany z tego typu obliczeniami.

- Wszechstronność i uniwersalność - kryterium odnoszące się głównie do elastyczności przyjmowanych przez algorytm parametrów, czyli obsługa nietypowych długości bloków, kluczy oraz możliwość sterowania ilością rund szyfrowania wewnątrz algorytmu. Drugim czynnikiem jest elastyczność implementacyjna odnosząca się do możliwości optymalizacji implementacji pod kątem konkretnych platform docelowych.
Prezentacja szyfru Rijndael/AES

Rijndael stał się pierwszym powszechnie dostępnym algorytmem szyfrującym zaaprobowanym przez NSA (ang. National Security Agency) do ochrony danych ściśle tajnych. Rijndael został zaprojektowany przez belgijskich kryptologów Vincenta Rijmena i Joana Daemena.

 

Rijndael jest szyfrem blokowym operującym na 128 bitowych blokach danych. Wykonuje 10 (klucz 128 bitów - standard przyjęty przez NIST), 12 (klucz 192 bity) lub 14 (klucz 256 bitów) rund szyfrujących typu substitution-permutation. Składają się one z substytucji wstępnej, permutacji macierzowej (mieszanie wierszy oraz mieszanie kolumn) i modyfikacji za pomocą klucza. Funkcja substytucyjna ma 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.

 

Algorytm doczekał się szeregu implementacji w bardzo wielu językach programowania. Ponadto dwaj główni producenci procesorów - Intel oraz AMD wprowadzili do swoich nowych serii procesorów ("Westmere" - Intel oraz "Bulldozer" - AMD) zestawy instrukcji przyspieszające szyfrowanie i deszyfrowanie danych algorytmem Rijndael.

 

Do tej pory nie pojawiły się ataki kryptoanalityczne, które mogłyby zapowiadać koniec tego standardu. Większość skutecznych ataków oparta jest na lukach w implementacji, a nie w samym projekcie szyfru Rijndael. Metody ataku na sam szyfr nadal mają na tyle wysoką złożoność obliczeniową, że ich zastosowanie jest niepraktyczne.


Ogólna zasada działania szyfru Rijndael/AES

Pora bliżej przyjrzeć się zasadzie działania algorytmu Rijndael. Poniższy rysunek przedstawia bardzo uproszczony schemat działania tego szyfru blokowego. Na wejściu dostajemy blok danych o długości 128 bitów (16 bajtów) oraz klucz o długości 128, 192 lub 256 bitów, którym ten blok danych zaszyfrujemy.


W zależności od długości klucza proces szyfrowania wygląda nieco inaczej. Zgodnie z danymi zawartymi w Tab 5 widzimy, że dla klucza szyfrującego o długości 128 bitów algorytm wykona 10 rund szyfrujących, dla klucza 192 bitowego 12 rund, zaś dla 256 bitowego, aż 14 rund.

 

Zmienia się również długość rozwinięcia klucza, która musi wynosić 16 bajtów razy ilość rund szyfrujących w danym wariancie +1 (ponieważ po za normalnymi rundami szyfrującymi występuje też dodatkowa operacja wymagająca jeszcze jednego podklucza szyfrującego).


W bardzo uproszczonym modelu proces szyfrowania za pomocą algorytmu Rijndael wygląda tak jak na wcześniejszym schemacie. Wejściowy tekst jawny trafia do pierwszej rundy, podobnie jak pierwszy podklucz szyfrujący. Efekt pracy pierwszej rundy szyfrującej staje się wejściem drugiej rundy szyfrującej, która przy użyciu drugiego podklucza ponownie je przetwarza, zaś wynik trafia do trzeciej rundy szyfrującej i tak dalej. Na wyjściu ostatniej rundy szyfrującej otrzymujemy ostateczną postać szyfrogramu jaki tworzy Rijndael. Kolejne dwa podrozdziały dokładniej przedstawią rundy szyfrujące oraz proces rozwijania klucza i tworzenia podkluczy dla poszczególnych rund.


Szczegółowy opis rund szyfrujących algorytmu Rijndael

Typowa runda szyfrująca w algorytmie Rijndael składa się z czterech operacji: Subbytes, ShiftRows, MixColumns i AddRoundKey. Poniższy rysunek przedstawia zarówno proces szyfrowania jak i deszyfrowania na przykładzie ze 128 bitowym kluczem i 10 rundami. Po lewej stronie widzimy kolejne operacje procesu generowania szyfrogramu z wejściowego tekstu jawnego przy wykorzystaniu klucza szyfrującego, zaś po prawej stronie proces odwrotny.


Zarówno w procesie szyfrowania jak i deszyfrowania przed pierwszą rundą wywoływana jest dodatkowa operacja AddRoundKey, zaś w ostatniej rundzie nie ma operacji MixColumns/InvMixColumns. Wszystkie przekształcenia wykonujemy na bajtowej macierzy o rozmiarach 4x4 zwanej macierzą stanu. Taka macierz stanowi zarówno wejście jak i wyjście z poszczególnych rund szyfrujących jak i z poszczególnych przekształceń wewnątrz samych rund.


Transformacje wykorzystywane przez Rijndael:

AddRoundKey

Proste przekształcenie wiążące macierz stanu danej rundy szyfrującej z odpowiednim kluczem rundy. Przeprowadzana jest operacja XOR pomiędzy kolejnymi bitami odpowiadających sobie wartości macierzy stanu i macierzy klucza rundy tak jak ilustruje to poniższy rysunek. AddRoundKey nie posiada transformacji przeciwnej, ponieważ opiera się o operację XOR, która jest samoodwrotna. Występuje więc zarówno w procesie szyfrowania jak i deszyfrowania.


Transformacja AddRoundKey jest bardzo prosta, jednak nie wpływa to w żaden sposób na bezpieczeństwo całego algorytmu, które jest oparte o złożoność pozostałych transformacji oraz o skomplikowanie procesu generowania podkluczy dla wszystkich rund.


ShiftRows i InvShiftRows

Obie transformacje są równie proste co AddRoundKey. Algorytm transformacji ShiftRows zilustrowany jest na poniższym schemacie. Pierwszy wiersz macierzy stanu pozostaje niezmieniony, drugi obracany jest cyklicznie w lewo o jeden bajt, trzeci o dwa bajty, czwarty zaś o trzy bajty.

 

Transformacja odwrotna, czyli InvShiftRows polega na wykonywaniu analogicznych obrotów w przeciwnym kierunku.


Te proste przekształcenia mają ważny wpływ na bezpieczeństwo całego algorytmu szyfrującego. Rozpraszają zawartość kolumn pomiędzy wszystkimi czterema kolumnami. Dokonują 'dezintegracji kolumn' usuwając zależność, o którą można by było oprzeć atak kryptoanalityczny.


Subbytes i InvSubbytes

Transformacja Subbytes to tak na prawdę proste podstawienie oparte o tzw. Skrzynkę Podstawieniową (ang. Substitution Box) w skrócie S-Box. S-box to macierz bajtowa o wymiarach 16x16 przedstawiona na ilustracji poniżej. Transformacja przebiega w następujący sposób: wejściowy bajt dzielony jest na dwie części, cztery najstarsze bity określają wiersz macierzy S-Box, zaś cztery najmłodsze określają kolumnę macierzy S-Box. Przykładowo - odwzorowaniem bajtu o wartości 5B jest bajt 39.

 

W procesie deszyfracji w przekształceniu InvSubbytes stosowany jest IS-Box (przedstawiony na dalszej schemacie), który dokonuje odwrotnej transformacji i przywraca pierwotne wartości. Czyli dla wspomnianego wcześniej bajtu 39 uzyskamy z transformacji InvSubbytes wartość 5B.


Zarówno S-Box jak i IS-Box nie są tworami losowymi. Gdyby tak było proces deszyfracji byłby nie możliwy. Obie macierze generowane są przez deterministyczny algorytm. Oznacza to, że dla implementacji, które nie mają ograniczeń pamięciowych S-Box i IS-Box mogą zostać wygenerowane znacznie wcześniej (lub być dołączone do programu) i być wielokrotnie wykorzystywane.







Głównym celem tego przekształcenia jest zapewnienie niskiej korelacji oraz nieliniowej zależności pomiędzy bajtami wejściowymi i wyjściowymi. W efekcie czego znacząco wzrosła odporność na ewentualne ataki kryptoanalizy liniowej.











MixColumns i InvMixColumns

Operacja MixColumns przeprowadzana jest niezależnie dla każdej kolumny. Wykorzystywane są poniższe wzory (s oznacza pierwotną wartość, a s' wartość po transformacji):


Trzeba jednak pamiętać, że w powyższych równaniach operacja mnożenia wykonywana jest zgodnie z regułami tej operacji na ciele skończonym GF(2 do potęgi 8). Również pojawiająca się w równaniach operacja XOR może zostać przedstawiona w jako odpowiadająca jej operacja dodawania na ciele skończonym GF(2 do potęgi 8). MixColumns można w skrócie przedstawić za pomocą poniższej ilustracji. Zaś przeciwna do niej operacja InvMixColumns przedstawiona jest na kolejnej ilustracji.



Głównym celem tej transformacji jest uzależnienie każdej kolumny od pozostałych kolumn oraz wymieszanie bitów w każdym bajcie macierzy stanu.

 

Cztery powyższe transformacje składają się na typową (pomijając ostatnią, w której jak wcześniej wspomniano nie ma operacji MixColumns i InvMixColumns) rundę szyfrującą/deszyfrującą. Poniższy rysunek prezentuje przebieg pojedynczej, pełnej rundy szyfrowania algorytmu Rijndael (czyli za wyjątkiem ostatniej rundy, w której nie występuje operacja MixColumns).


Na wejście rundy wprowadzana jest macierz bajtowa o rozmiarach 4x4. Wykonywana jest na niej transformacja podstawienia bajtów (Subbytes) przy użyciu macierzy S-Box. Efekt tego podstawienia w formie nowej macierzy stanu zostaje poddany przesunięciu wierszy zgodnie z charakterystyką transformacji ShiftRows. Wyjściem tej transformacji jest kolejna macierz stanu, która tym razem trafia do funkcji MixColumns, gdzie dokonywane jest mnożenie na ciele GF(2 do potęgi 8) przez przedstawioną na wcześniejszej ilustracji macierz sbox. Ostatnim etapem jest przeprowadzenie operacji XOR między kolejnymi wartościami otrzymanej wcześniej macierzy stanu, a otrzymaną z procesu rozwijania klucza macierzą podklucza dla danej rundy szyfrującej (transformacja AddRoundKey).


Szczegółowy opis procesu rozwijania klucza w algorytmie Rijndael

Proces generowania podkluczy zaczyna się od przepisania zawartości klucza do czterech pierwszych słów wektora wynikowego W. Te cztery słowa stają się zaczątkiem, który posłuży do wygenerowania pozostałych 40 słów stanowiących podklucze dla dziesięciu kolejnych rund szyfrujących. Jak można wywnioskować z treści poniższego rysunku generowana zawartość dowolnego słowa w[i] zależna jest od poprzedzających je słów w[i-1] i w[i-4]. Wyliczenie trzech zawartości ogranicza się do prostej operacji XOR tak jak widać to na ilustracji. Co czwarta wartość jest trudniejsza do otrzymania. Wymaga wyliczenia funkcji G widocznej na poniższym schemacie.


Poświęćmy chwilę na analizę funkcji G. Pierwsza operacja obraca słowo w lewo o jeden bajt (operacja RotWord). Druga operacja dokonuje podstawiania wykorzystując zawartość przedstawionego wcześniej S-boxa, jest to wersja operacji Subbytes zwana SubWord.

 

Ostatnim krokiem jest sumowanie symetryczne rezultatu powyższych dwóch operacji ze stałą rundy Rcon[n] (dla n-tej rundy). Rcon ma specyficzną konstrukcję - tylko pierwsze słowo (osiem najstarszych bitów) posiada wartość, pozostałe trzy słowa to same zera. Pierwsze słowo uzyskujemy ze wzoru RC[1] = 1, RC[n] = 2 * RC[n-1]. Wzór wyliczamy na ciele GF(2 do potęgi 8), więc kolejne wartości jakie otrzymamy dla dziesięciu rund szyfrowania to: 01, 02, 04, 08, 10, 20, 40, 80, 1B i 36.


Proces generowania kluczy stanowi o sile algorytmu Rijndael. Dzięki swojej budowie, a zwłaszcza dzięki operacjom wykonywanym w ramach funkcji G praktycznie nie występują żadne podobieństwa między kolejnymi podkluczami rund szyfrujących. Po za tym algorytm generowania podkluczy ma też inne zalety. Nie można obliczyć znaczącej części bitów podkluczy na podstawie częściowej znajomości klucza głównego, lub całego podklucza jednej z rund. Implementacja tego algorytmu jest stosunkowo prosta i wydajna, co również nie jest bez znaczenia.

 

Podsumowując w paru zdaniach ostatnie kilka podrozdziałów dotyczących algorytmu Rijndael/AES wypada zacząć od zwrócenia uwagi na generalną prostotę tego algorytmu. Nie trzeba olbrzymiego zaplecza matematycznego, żeby zrozumieć proces generowania szyfrogramu za pomocą AES'a. W tym właśnie tkwi jego siła. Jeśli algorytm jest przesadnie złożony i skomplikowany mniej osób może mu się dokładniej przyjrzeć. Ponadto przesadna komplikacja często niesie za sobą bagaż w postaci różnych ukrytych zależności, co bardzo często stanowi furtkę do skutecznych ataków kryptoanalitycznych.


bro

Ilość komentarzy: 1
Luzak A (11-04-2013 20:15)
tool crypt ma chyba graficzną reprezentacje razem z animacją. no i kiedys na wykopie było moge poszukać.