Kryptoanaliza liniowa i tablice aproksymacji

Kryptoanaliza liniowa (Matsui, 1993) to atak ze znanym tekstem jawnym, który znajduje aproksymacje liniowe (XOR określonych bitów) szyfru zachodzące z prawdopodobieństwem p ≠ 1/2. Przy użyciu wielu par tekst jawny–szyfrogram obciążenie statystyczne ujawnia bity klucza.

Aproksymacja liniowa dla S-boxu: suma wybranych bitów wejściowych XOR suma wybranych bitów wyjściowych = 0 (mod 2) z prawdopodobieństwem p. Wyraża się ją jako: P[a·x XOR b·y = 0] = 1/2 + ε, gdzie a,b to maski bitowe, a ε to bias (obciążenie) (|ε| >> 0 jest pożądane).

LAT zlicza, dla każdej maski wejściowej a i maski wyjściowej b, liczbę wejść x, dla których (a·x) XOR (b·S(x)) = 0. Odjęcie 2^{n-1} daje bias. Dobry S-box ma |max_bias| = 1 (prawdopodobieństwo 1/2 ± 1/2^{n/2}) — jest możliwie płaski.

Dla niezależnych aproksymacji liniowych w wielu rundach biasy mnożą się: ε_total = 2^{r-1} * ε_1 * ε_2 * ... * ε_r. Każda aproksymacja rundy zmniejsza efektywny bias o połowę. Po wielu rundach całkowity bias zbliża się do 0, co wymaga wykładniczo większej liczby par do wykrycia.

Aby zaatakować szyfr z r rundami, znajdź ścieżkę liniową ε obejmującą r-1 rund. Zbierz N = 1/ε^2 znanych tekstów jawnych. Dla każdego kandydata na bajt klucza ostatniej rundy k' częściowo odszyfruj ostatnią rundę za pomocą XOR i sprawdź, czy aproksymacja liniowa zachodzi częściej niż N/2 razy. Prawidłowy k' wykazuje właściwy bias.

W 1993 roku Matsui zaatakował 16-rundowy DES, używając 14-rundowej aproksymacji liniowej z biasem 2^{-21.4}. Wymagało to 2^{43} znanych tekstów jawnych. W fazie 1 odzyskano 26 bitów klucza, a pozostałe 30 znaleziono przez przeszukiwanie wyczerpujące. Był to pierwszy praktyczny atak szybszy niż brute force na całym DES.

S-box AES ma maksymalną wartość LAT |ε| = 4/256 = 1/64 dla pojedynczego S-boxu. Strategia Wide Trail ogranicza liczbę aktywnych S-boxów w każdej 4-rundowej ścieżce do ≥ 25. Całkowity bias ≤ (1/64)^{25/2} ≈ 2^{-75}. Wymaga to 2^{150} znanych tekstów jawnych — jest niewykonalne.

Różnicowa: znane lub wybrane pary tekstów jawnych; wykorzystuje różnice wyjściowe. Liniowa: znane teksty jawne; wykorzystuje statystyczne aproksymacje liniowe. W praktycznych atakach oba podejścia wykorzystują wybrane teksty jawne. Oba są kryteriami projektowymi: S-boxy muszą być odporne na oba rodzaje ataków (niska maksymalna wartość DDT i niska maksymalna wartość LAT).

Używaj jednocześnie wielu aproksymacji liniowych, aby zmniejszyć złożoność danych. Nyberg i Leander rozszerzyli metodę Matsui: połączenie M aproksymacji zmniejsza ilość danych o czynnik log(M). Metodę zastosowano do PRESENT, SIMON i innych szyfrów lekkich.

Aproksymacja liniowa zastosowana do szyfrów strumieniowych polega na znalezieniu korelacji między strumieniem klucza a funkcją liniową wyjścia LFSR. Taka korelacja, jeśli jest niezerowa, umożliwia szybsze niż wyczerpujące odzyskanie klucza. Zainspirowało to projektowanie nieliniowych funkcji łączących w szyfrach strumieniowych.

Kryptoanaliza całkowa (Knudsen-Wagner): wybierz zbiór tekstów jawnych, w którym określone bajty przyjmują wszystkie 256 wartości, a pozostałe są stałe. Po kilku rundach XOR wszystkich wyjść na określonych pozycjach wynosi 0 (jest zrównoważony). Metoda wykorzystuje strukturę AES i skutecznie łamie AES o zmniejszonej liczbie rund.

Co głosi lemat Piling-Up na temat łączenia aproksymacji liniowych?

Kryptoanaliza liniowa znajduje obciążone aproksymacje liniowe S-boxów. AES jest odporny dzięki zoptymalizowanemu pod kątem LAT S-boxowi i konstrukcji Wide Trail. Matsui złamał DES, używając 14-rundowej ścieżki i 2^43 znanych tekstów jawnych. Dalej: ataki urodzinowe i znajdowanie kolizji.