Metody różnicowej i liniowej kryptoanalizy szyfrów blokowych

Symetryczne szyfry blokowe należą do podstawowych narzędzi innowacyjnej kryptografii. Ponieważ nie są znane konstrukcje, których bezpieczeństwo można udowodnić, ocena tych szyfrów jest heurystyczna. Brane są pod uwagę tylko dotychczas znane ataki kryptograficzne. Do najważniejszych rozważanych ataków należą kryptoanaliza różnicowa i kryptoanaliza liniowa. W odróżnieniu od kryptoanalizy różnicowej, która jest w zasadzie metodą ataku kryptograficznego z wybranym tekstem jawnym, kryptoanaliza liniowa jest niezwykle metodą ataku kryptograficznego ze znanym tekstem jawnym, a dodatkowo w pewnych okolicznościach może być wykorzystana do ataku na tekst zaszyfrowany. Podstawowa idea kryptoanalizy liniowej polega na opisaniu danego algorytmu szyfrowania przy pomocy przybliżonego równania, tak zwanej aproksymacji liniowej. Przybliżone równanie opisujące wpływ szczególnych różnic w parach tekstów jawnych na różnice w odpowiadających im parach tekstów zaszyfrowanych nazywane jest aproksymacją różnicową. Dla dowolnej funkcji f o n binarnych wejściach i m binarnych wyjściach zbiór wszystkich aproksymacji różnicowych albo liniowych może być reprezentowany w postaci tablicy aproksymacji o rozmiarze O_(2n+m). Algorytmy oparte na definicji aproksymacji różnicowej albo liniowej obliczają pojedynczą wartość tablicy aproksymacji w czasie wykładniczym. Ogranicza to użycie tych podstawowych algorytmów do funkcji składowych szyfru o nieznacznej liczbie binarnych wejść i wyjść. Przedstawione w rozprawie prędkie algorytmy obliczają najlepszą niezerową aproksymację różnicową i liniową w co najwyżej liniowym czasie O_(n+m) dla pojedynczego elementu bez angażowania pamięci potrzebnej do przechowania całych tablic. Pożądana jest konstrukcja specjalizowanych algorytmów dla pewnych klas funkcji składowych szyfrów blokowych. Dla struktur z selektorami sformułowano algorytm obliczania pojedynczego elementu tablicy liniowych aproksymacji struktury w czasie O(k ⋅ 2_k), jak również algorytm obliczania całej tablicy aproksymacji struktury w czasie O(k) dla pojedynczego elementu, gdzie k oznacza liczbę bitów adresowych selektora. Oba algorytmy są oparte na ogólnym wyniku, który pozwala obliczyć wartości tablicy aproksymacji struktury na podstawie wstępnie obliczonych tablic aproksymacji jej funkcji składowych. Dla losowo wybranych n-bitowych permutacji i dowolnych funkcji rozważono dwuwymiarowe (tj. Różnicowo-liniowe) rozkłady najlepszych aproksymacji niezerowych. Dla obu klas funkcji rozkłady te są podobne. Uzyskane wyniki świadczą o tym, iż począwszy od pewnej wartości n, liniowa aproksymacja funkcji S-bloków staje się bardziej efektywna od aproksymacji różnicowej. Ta przewaga efektywności aproksymacji liniowej rośnie wraz ze wzrostem n, a przy wymiarach S-bloków algorytmu DES nie jest jeszcze zauważalna. Wykazano, iż wśród trzech losowo wybranych S-bloków dwa z nich nie są gorsze od najlepszego S-bloku algorytmu DES. W rozkładach jednowymiarowych porównano następujące rodzaje najlepszej aproksymacji liniowej: aproksymację z sumą modulo 2 bitów wyjściowych, aproksymację z dowolnym bitem wyjściowym i aproksymację z pojedynczym bitem wyjściowym. Do wykorzystywanych składników składowych szyfrów blokowych należą funkcje sumy i różnicy arytmetycznej. Dla tych funkcji sformułowano wielomianowe w czasie algorytmy obliczania wartości tablic aproksymacji i rozkładów wartości w tych tablicach, jak również algorytm generowania listy efektywnych aproksymacji, uporządkowanej malejąco według miary efektywności. Zaimplementowana metoda umożliwia rozwiązanie wielu innych problemów generacji, standardowych dla obliczeń wielorundowych charakterystyk szyfrów blokowych. Algorytmy służące do obliczania w czasie O_(n) pojedynczej wartości tablicy różnicowych lub liniowych aproksymacji funkcji n-bitowej sumy lub różnicy arytmetycznej są przykładami algorytmów specjalizowanych. Ocenę szyfrów blokowych ograniczono do przypadku kryptoanalizy liniowej. Jako kryterium jakości przyjęto efektywność najlepszej aproksymacji niezerowej. Jakość szyfru porównywana jest z jakością algorytmu porównawczego o tej samej długości bloku. Wyróżnia się trzy metody oceny szyfru blokowego: zgrubną, pośrednią i staranną. Metoda zgrubna jest oparta na założeniu, iż najlepsza niezerowa aproksymacja szyfru jest złożeniem najlepszej niezerowej aproksymacji pojedynczej iteracji. Metodę tę zaimplementowano do szyfru rodzaju DES i szyfru PP-1, który jest skalowalną siecią podstawieniowo-permutacyjną (SPN). W metodzie pośredniej dla szyfru konstruowany jest graf G aproksymacji zerowo- niezerowych. Algorytm SP oblicza najkrótszą ścieżkę o określonej długości w grafie G. Ta ścieżka określa najlepszą zerowo-niezerową aproksymację szyfru spełniającą warunki aproksymacji. Efektywność tej aproksymacji stanowi podstawę oceny szyfru. Wykazano, że efektywność trafna dla 64-bitowego szyfru blokowego uzyskiwana jest przez 48-rundowy rodzaj algorytmu DES z poprawionymi S-blokami. Metoda dokładna polega na wyznaczeniu najlepszej niezerowej aproksymacji szyfru. Obliczenie najbardziej efektywnej aproksymacji przeprowadzane jest z zasady w dwóch krokach. Najpierw, w wyniku kompilacji aproksymacji funkcji składowych, obliczane są efektywne aproksymacje pojedynczej iteracji. Następnie, w efekcie kompozycji aproksymacji kolejnych iteracji, uzyskiwana jest aproksymacja całego szyfru. Metoda staranna powinna być użytkowana w odniesieniu do istniejących szyfrów. Pozostałe dwie metody, w których pomijane są detale konstrukcji szyfru, są {pomocn|przydatn)e na etapie jego konstruowania. Rozważono różnicową i liniową kryptoanalizę algorytmów DES o zredukowanej liczbie rund. Wiele uwagi poświęcono wyznaczaniu charakterystyk aproksymacji. W szczególności przedstawiono optymalne różnicowe i liniowe charakterystyki r-rundowego algorytmu DES, gdzie r jest ograniczone, odpowiednio, przez 6 i 7, jak również optymalne cykliczne liniowe charakterystyki o długości cyklu od 2 do 5, które umożliwiają identyfikację klucza w przypadku większej liczby rund. Dla tych charakterystyk są formułowane warunki aproksymacji, uzyskiwane przez rozwiązanie właściwego dla algorytmu zbioru równań. Ten sam zbiór równań jest używany do wyznaczenia ogólnej postaci aproksymacji. Najlepsze charakterystyki odpowiadają najbardziej efektywnym aproksymacjom wykorzystywanym w różnych typach ataków kryptograficznych.