Atak interpolacyjny

W kryptografii atak interpolacyjny jest rodzajem ataku kryptoanalitycznego na szyfry blokowe .

Po przedstawieniu dwóch ataków, kryptoanalizy różnicowej i kryptoanalizy liniowej na szyfrach blokowych, wprowadzono kilka nowych szyfrów blokowych , które okazały się bezpieczne przed atakami różnicowymi i liniowymi. Wśród nich było kilka iterowanych szyfrów blokowych, takich jak szyfr KN i szyfr SHARK . Jednak Thomas Jakobsen i Lars Knudsen wykazali pod koniec lat 90., że te szyfry były łatwe do złamania, wprowadzając nowy atak zwany atakiem interpolacyjnym.

W ataku funkcja algebraiczna jest używana do reprezentowania S-boksu . Może to być prosta kwadratowa , wielomianowa lub wymierna na polu Galois . Jego współczynniki można określić za pomocą standardowych interpolacji Lagrange'a , używając znanych tekstów jawnych jako punktów danych. Alternatywnie, wybrane teksty jawne mogą być użyte do uproszczenia równań i optymalizacji ataku.

W swojej najprostszej wersji atak interpolacyjny wyraża tekst zaszyfrowany jako wielomian tekstu jawnego. Jeśli wielomian ma stosunkowo małą liczbę nieznanych współczynników, to za pomocą zbioru par tekst jawny/tekst zaszyfrowany (p/c) wielomian można zrekonstruować. Po zrekonstruowaniu wielomianu atakujący ma reprezentację szyfrowania, bez dokładnej znajomości tajnego klucza.

Atak interpolacyjny może być również wykorzystany do odzyskania tajnego klucza.

Metodę najłatwiej opisać na przykładzie.

Przykład

Niech iterowany szyfr będzie dany przez

${\ Displaystyle c_ {i} = (c_ {i-1} \ oplus k_ {i}) ^ {3},}$

gdzie do $\ Displaystyle c_ {0}}$ jest tekstem jawnym, ${\ Displaystyle c_ {i}}$ wyjściem rundy ${\ Displaystyle i ^ {th}}$ , ${\ Displaystyle k_ {i} }}$ tajny $, ja$ klucz (wywodzący się z tajnego klucza $)$ pewnego kluczowego harmonogramu i dla okrągłego szyfru iterowanego ${\ displaystyle i ^ {th$${\ displaystyle c_ {r}}$ jest tekstem zaszyfrowanym.

Rozważ 2-rundowy szyfr. Niech $x}$${ \$ oznacza wiadomość, a oznacza zaszyfrowany tekst.

Następnie wyjście rundy 1 staje się

${\ Displaystyle c_ {1} =(x+k_{1})^{3}=(x^{2}+k_{1}^{2})(x+k_{1})=x^{3}+k_{1}^ {2}x+x^{2}k_{1}+k_{1}^{3},}$

a wyjście rundy 2 staje się

${\ Displaystyle c_ {2} = c = (c_ {1 }+k_{2})^{3}=(x^{3}+k_{1}^{2}x+x^{2}k_{1}+k_{1}^{3}+k_{ 2})^{3}}$

${\ Displaystyle = x ^ {9} + x ^ {8} k_ {1} + x ^ {6} k_ {2} + x ^ {4} k_ {1} ^{2}k_{2}+x^{3}k_{2}^{2}+x^{2}(k_{1}k_{2}^{2}+k_{1}^{4} k_{2})+x(k_{1}^{2}k_{2}^{2}+k_{1}^{8})+k_{1}^{3}k_{2}^{2 }+k_{1}^{9}+k_{2}^{3},}$

Wyrażanie tekstu zaszyfrowanego jako wielomianu wyników w postaci tekstu jawnego

${\ Displaystyle p (x) = a_{1}x^{9}+a_{2}x^{8}+a_{3}x^{6}+a_{4}x^{4}+a_{5}x^{3}+ a_{6}x^{2}+a_{7}x+a_{8},}$

gdzie ' $s są kluczowymi$ .

$,$ ile jest nieznanych współczynników w wielomianie skonstruować wielomian Można to zrobić na przykład za pomocą interpolacji Lagrange'a (patrz wielomian Lagrange'a ). $reprezentację$ określeniu nieznanych współczynników $szyfrowania$ bez tajnego

Istnienie

Biorąc pod uwagę $m}$$blokowy$ , to są możliwe teksty jawne, a zatem różne $p/c}$$\ displaystyle$$\ displaystyle$ par. $współczynniki$ będą nieznane w ${\ Displaystyle p (x)}$ . Ponieważ potrzebujemy tyle ${\ displaystyle p/c}$ par jako liczby nieznanych współczynników w wielomianie, to atak interpolacyjny istnieje tylko wtedy, gdy ${\ Displaystyle n \ równoważnik 2 ^ {m}}$ .

Złożoność czasowa

$,$ czas na skonstruowanie wielomianu $przy$ par do zaszyfrowania wymaganych tekstów jawnych. $współczynniki$ będą nieznane w ${\ Displaystyle p (x)}$ . Wtedy złożoność czasowa tego ataku wynosi ${\ displaystyle n}$ i wymaga znanego odrębnego ${\ displaystyle n}$${\ Displaystyle p / c}$ par.

Atak interpolacyjny przez Meet-In-The-Middle

Często ta metoda jest bardziej wydajna. Oto jak to się robi.

Biorąc pod uwagę $okrągły$$iterowany$ szyfr o długości bloku $<r}$ będzie $szyfru$ rundach z $}$${\ displaystyle s$ . Wyrazimy wartość $jawnego i jako$ wielomian tekstu $wielomian$ tekstu $do$ Pozwalać ${\ Displaystyle g (x) \ w GF (2 ^ {m}) [x]}$ być wyrazem z $\ Displaystyle Z}$ przez ${\ Displaystyle x}$ i niech ${\ Displaystyle h (c) \ in GF (2 ^ {m}) [c]}$ będzie wyrażeniem ${\ Displaystyle z}$ przez do $\ displaystyle c}$ . Wielomian sol $\ Displaystyle g (x)}$ uzyskuje się przez obliczenie do przodu przy użyciu iterowanej formuły szyfru aż do zaokrąglenia $)$ a wielomian ${\ Displaystyle h (c)$ uzyskuje się przez obliczenie wstecz z iterowanej formuły szyfru, zaczynając od rundy $do$ s $\ displaystyle s + 1}$ .

Więc powinno to wytrzymać

${\ Displaystyle g (x) = h (c)}$

$a$ jeśli zarówno $.$ są wielomianami o małej liczbie współczynników, to możemy rozwiązać równanie dla nieznanych

Złożoność czasowa

Załóżmy, że $h ($ współczynnikami $i$ można wyrazić $Displaystyle$$\$ { . Wtedy potrzebowalibyśmy ${\ displaystyle p + q}$ znane odrębne ${\ displaystyle p/c}$ pary, aby rozwiązać równanie, ustawiając je jako równanie macierzowe. Jednak to równanie macierzowe można rozwiązać aż do mnożenia i dodawania. Aby więc mieć pewność, że otrzymamy unikalne i niezerowe rozwiązanie, współczynnik odpowiadający najwyższemu stopniowi ustalamy na jeden, a składnik stały na zero. Dlatego $\ displaystyle p + q$ znane różne pary ${$ Zatem złożoność czasowa tego ataku wynosi ${\ Displaystyle p + q-2}$$2$$\ displaystyle p + q-2}$ znanych odrębnych p

W podejściu Meet-In-The-Middle całkowita liczba współczynników jest zwykle mniejsza niż w przypadku metody normalnej. $Dzięki$ temu metoda jest bardziej wydajna, ponieważ par

Odzyskiwanie kluczy

Możemy również użyć ataku interpolacyjnego, aby odzyskać $tajny$ .

Jeśli usuniemy ostatnią rundę $-okrągłego$ iterowanego szyfru o długości bloku $y$ wyjście szyfru stanie się $}=c_{r-1}}$$\ Displaystyle {\ tylda {y$ . Nazwij szyfr szyfrem zredukowanym. Chodzi o to, aby zgadnąć klucz ostatniej rundy $,$ aby uzyskać wynik ${\ Displaystyle {\ tylda {y}}}$ szyfru zredukowanego. Następnie, aby zweryfikować przypuszczenie, używamy ataku interpolacyjnego na zredukowany szyfr albo metodą normalną, albo metodą Meet-In-The-Middle. Oto jak to się robi.

$jako$ metodą wyrażamy wynik $szyfru$ wielomian tekstu . Nazwij wielomian ${\ Displaystyle p (x) \ in GF (2 ^ {m}) [x]}$ . Następnie, jeśli możemy wyrazić ${\ Displaystyle p (x)}$ za pomocą ${\ displaystyle n}$$współczynniki ,$$skonstruować$ używając różnych par, wielomian Aby zweryfikować odgadnięcie klucza ostatniej rundy, sprawdź za pomocą jednej dodatkowej $pary$ to

${\ displaystyle p (x) = {\ tylda {y}}.}$

Jeśli tak, to z dużym prawdopodobieństwem odgadnięcie klucza ostatniej rundy było prawidłowe. Jeśli nie, odgadnij ponownie klucz.

Metodą Meet-In-The-Middle $wyrażamy$$z$$jako$ wielomian zwykłego i wyjście zredukowanego szyfru ${\ displaystyle {\ tylda {y}}}$ . Nazwij wielomiany sol $\ Displaystyle g (x)}$ i ${\ Displaystyle h ({\ tylda {y}})}$ i niech będą wyrażone odpowiednio przez $displaystyle$ i $q}$ . Następnie $ze$ odrębnymi $_$ _ Aby zweryfikować odgadnięcie klucza ostatniej rundy, sprawdź za pomocą jednej dodatkowej $pary$ to

${\ Displaystyle g (x) = h ({\ tylda {y}}).}$

Jeśli tak, to z dużym prawdopodobieństwem odgadnięcie klucza ostatniej rundy było prawidłowe. Jeśli nie, odgadnij ponownie klucz.

Po znalezieniu właściwego ostatniego okrągłego klucza możemy kontynuować w podobny sposób z pozostałymi okrągłymi kluczami.

Złożoność czasowa

$Z$ tajnym okrągłym kluczem o $długości$ różne . $Każdy$ z prawdopodobieństwem poprawny, jeśli zostanie $właściwy$ musieli średnio zgadywać klucz

$_$ normalna metoda $_$ _ ${\ displaystyle c / p}$ , a metoda Meet-In-The-Middle ma średnią złożoność czasową ${\ Displaystyle 2 ^ {m-1} (p + q- 1)}$$p}$ wymagające znanych odrębnych do ${ \$

Aplikacja z prawdziwego świata

Atak Meet-in-the-middle może być użyty w wariancie do ataku na S-boxy, który wykorzystuje funkcję odwrotną, ponieważ z -bitowym S-boxem wtedy ${\ Displaystyle S: f (x) = x ^ {- 1} = x ^ {2 ^ {m} -2}}$${\ displaystyle m}$ w ${\ Displaystyle GF (2 ^{m})}$ .

Szyfr blokowy SHARK wykorzystuje sieć SP z S-box ${\ Displaystyle S: f (x) = x ^ {- 1}}$ . Szyfr jest odporny na kryptoanalizę różnicową i liniową po niewielkiej liczbie rund. Jednak został złamany w 1996 roku przez Thomasa Jakobsena i Larsa Knudsena za pomocą ataku interpolacyjnego. $_$ przez SHARK bity przy użyciu równoległych $-bitowych$$displaystyle$ -polek w rundach $nm}$${$ . Jakobsen i $szyfr blokowy)$ istnieje atak interpolacyjny na SHARK użyciu około $^ {21}$ wybrane teksty jawne i atak interpolacyjny na SHARK $\ Displaystyle (8,16,7)}$$($ 128-bitowy szyfr blokowy) przy użyciu około tekstów jawnych.

Również Thomas Jakobsen przedstawił probabilistyczną wersję ataku interpolacyjnego przy użyciu algorytmu Madhu Sudana w celu ulepszenia dekodowania kodów Reeda-Solomona . Ten atak może zadziałać nawet wtedy, gdy związek algebraiczny między tekstami jawnymi a tekstami zaszyfrowanymi zachodzi tylko dla ułamka wartości.

• Thomas Jakobsen , Lars Knudsen (styczeń 1997). Atak interpolacyjny na szyfry blokowe ( PDF / PostScript ) . 4th International Workshop on Fast Software Encryption (FSE '97), LNCS 1267. Haifa : Springer-Verlag . s. 28–40 . Źródło 2007-07-03 .
• Thomas Jakobsen (25 sierpnia 1998). Kryptoanaliza szyfrów blokowych z probabilistycznymi nieliniowymi relacjami niskiego stopnia (PDF/PostScript) . Postępy w kryptologii — CRYPTO '98. Santa Barbara, Kalifornia : Springer-Verlag. s. 212–222 . Źródło 2007-07-06 . ( Film prezentacji w Google Video — korzysta z Flasha )
• Shiho Moriai; Takeshi Shimoyama; Toshinobu Kaneko (marzec 1999). Ataki interpolacyjne szyfru blokowego: SNAKE (PDF) . FSE '99. Rzym: Springer-Verlag. s. 275–289. doi : 10.1007/3-540-48519-8_20 . Źródło 2022-11-06 .
• Amr M. Youssef; Guang Gong (kwiecień 2000). O atakach interpolacyjnych na szyfry blokowe (PDF) . FSE 2000. Nowy Jork : Springer-Verlag. s. 109–120 . Źródło 2007-07-06 .
• Kaoru Kurosawa; Tetsu Iwata; Viet Duong Quang (sierpień 2000). Atak interpolacyjny w poszukiwaniu korzenia (PDF/PostScript) . Materiały z 7. dorocznych międzynarodowych warsztatów na temat wybranych obszarów kryptografii (SAC 2000). Waterloo, Ontario : Springer-Verlag. s. 303–314 . Źródło 2007-07-06 .