Podstawy kryptoanalizy różnicowej

Kryptoanaliza różnicowa (Biham i Shamir, 1990) to atak z wybranym tekstem jawnym, który analizuje, jak różnice w parach tekstów jawnych propagują się przez szyfr. Znajdując różnice wejściowe, które z dużym prawdopodobieństwem powodują przewidywalne różnice wyjściowe, atakujący odzyskuje bity klucza metodami statystycznymi.

Dla szyfrów opartych na XOR: różnica ΔX = X XOR X'. Dla szyfrów opartych na dodawaniu: różnica ΔX = X - X' mod 2^n. Różnice XOR są najczęstsze, ponieważ XOR komutuje z kluczowaniem za pomocą XOR (wpływ harmonogramu klucza znosi się w parach różnicowych).

Para różnicowa (P, P') ma różnicę wejściową ΔP = P XOR P'. Po zaszyfrowaniu otrzymujemy (C, C') z różnicą wyjściową ΔC = C XOR C'. Użyteczna różnica to ΔP → ΔC o dużym prawdopodobieństwie p — oznacza to, że wiele par (P, P') o różnicy ΔP daje różnicę wyjściową ΔC.

DDT (Differential Distribution Table) zlicza, dla każdej różnicy wejściowej Δx i różnicy wyjściowej Δy, ile wejść x spełnia warunek S(x) XOR S(x XOR Δx) = Δy. Podzielenie przez 2^n daje prawdopodobieństwo. Dobry S-box ma maksymalną wartość DDT równą 2 (prawdopodobieństwo 1/2^{n-1}) — nie występują w nim silne różnice.

Dla szyfru blokowego z r rundami znajdź sekwencję ΔP → ΔU1 → ΔU2 → ... → ΔU_{r-1}, w której prawdopodobieństwo przejścia w każdej rundzie jest znane. Pomnóż prawdopodobieństwa dla kolejnych rund: prawdopodobieństwo całkowite p = p1 * p2 * ... * p_{r-1}. Atak używa 2/p par do odzyskania klucza ostatniej rundy.

Przy różnicy obejmującej r-1 rund i mającej duże prawdopodobieństwo zbierz N = 2/p par tekstów jawnych. Dla każdego kandydata na klucz ostatniej rundy K' odszyfruj oba szyfrogramy o jedną rundę, wykonaj XOR na wynikach i sprawdź, czy różnica odpowiada ΔU_{r-1}. Prawidłowy K' pasuje około ~N/2 razy, a nieprawidłowe klucze około ~N/2^{bit_size} razy.

S-box AES to odwrotność multiplikatywna w GF(2^8), po której następuje transformacja afiniczna. Jego maksymalna wartość DDT wynosi 4 (na 256), co daje prawdopodobieństwo różnicowe ≤ 4/256 = 1/64 dla pojedynczego S-boxu. AES ma 4 S-boxy w każdej rundzie, ale konstrukcja Wide Trail gwarantuje, że pełne ścieżki różnicowe mają prawdopodobieństwo mniejsze niż 2^{-100}.

Konstrukcja Wide Trail autorstwa Joana Daemena (używana w AES/Rijndael) definiuje liczbę rozgałęzień B dla MixColumns. Każda nietrywialna ścieżka różnicowa w jednej rundzie aktywuje co najmniej B aktywnych S-boxów. 4 rundy × 4 S-boxy na rundę gwarantują co najmniej ≥ 25 aktywnych S-boxów → prawdopodobieństwo < 2^{-100}.

Różnice obcięte określają tylko część różnicy, na przykład które kolumny są aktywne, a nie dokładne wartości różnic. Umożliwiają ataki na większą liczbę rund, w przypadku których pełne różnice są zbyt słabe. Stosuje się je przeciwko szyfrom AES o zmniejszonej liczbie rund, SERPENT i innym szyfrom SPN.

Niemożliwa różnica to para (ΔP, ΔC), która nie może wystąpić dla żadnego klucza. Każdy klucz, który odwzorowuje zaobserwowaną parę (P, P') o tej różnicy, zostaje wyeliminowany. Po zebraniu wystarczającej liczby par wszystkie nieprawidłowe klucze zostają wyeliminowane i pozostaje prawidłowy klucz.

Atak boomerangowy (Wagner, 1999) łączy dwie krótkie różnice w adaptacyjny atak z wybranymi tekstami jawnymi i szyfrogramami. Dzieli szyfr na dwie połowy, z których każda ma krótką różnicę o dużym prawdopodobieństwie, umożliwiając atak na większą liczbę rund, niż pozwalałaby na to pojedyncza różnica.

Kryptoanaliza różnicowa wykorzystuje propagację różnic wejściowych do wyjściowych o dużym prawdopodobieństwie. AES jest na nią odporny dzięki zoptymalizowanemu pod kątem DDT S-boxowi i konstrukcji Wide Trail. Dalej: kryptoanaliza liniowa i tabele aproksymacji.