Biclique attack - Biclique attack

Biclique atak to wariant meet-in-the-middle metodą (MITM) z kryptoanalizy . Wykorzystuje biclique struktury do zwiększenia liczby rund ewentualnie zaatakowanych przez atak MiTM. Od biclique cryptanalysis opiera się na atakach MiTM, to ma zastosowanie zarówno do szyfrów blokowych i (iterować) haszowe funkcji . Ataki Biclique znane są Zerwawszy zarówno pełne AES i pełną IDEA , choć tylko z niewielką przewagą nad brutalną siłą. Stwierdzono również stosowane do Kasumi szyfru i preimage odporności pasmo-512 i SHA-2 funkcji skrótu.

Biclique atak jest wciąż (od 2015-03-13) najlepszego publicznie znanego pojedynczego klawisza ataku na AES . Złożoność obliczeniowa ataku jest , a dla AES128, AES192 oraz AES256, odpowiednio. Jest to jedyny publicznie znane single-key atak na AES, który atakuje pełną liczbę rund. Poprzednie ataki zaatakowany runda zredukowanych wariantów (warianty zazwyczaj obniżona do 7 lub 8 rund). ${\ Displaystyle 2 ^ {126,1}}$${\ Displaystyle 2 ^ {189,7}}$${\ Displaystyle 2 ^ {254,4}}$

Jak złożoność obliczeniowa ataku jest , jest to teoretyczny atak, co oznacza bezpieczeństwo AES nie został złamany, a korzystanie z AES pozostaje stosunkowo bezpieczna. Biclique ataku jest jednak ciekawy atak, który proponuje nowe podejście do wykonywania kryptoanalizy szyfrów blokowych na. Atak ma również więcej informacji o świadczonych AES, gdyż przyniósł pod znakiem zapytania bezpieczeństwo marży liczby rund użytych w nim. ${\ Displaystyle 2 ^ {126,1}}$

Historia

Oryginalny atak MITM został po raz pierwszy zaproponowany przez Diffie i Hellman w 1977 roku, kiedy omawiano kryptoanalitycznych właściwości DES. Argumentowali oni, że kluczem rozmiarze była zbyt mała, a ponowna instalacja des wielokrotnie z różnymi kluczami może być rozwiązanie kluczowego wielkości; Jednak one odradzane użyciem podwójnie DES i zasugerował potrójnego DES jako minimum, ze względu na ataki MiTM (ataki MiTM można łatwo zastosować do double-DES do zmniejszenia bezpieczeństwa ze po prostu , ponieważ można niezależnie Bruteforce pierwszy i drugi DES-szyfrowanie jeśli mają plain- i szyfrogram). ${\ Displaystyle 2 ^ {56}} 2 *$${\ Displaystyle 2 * 2 ^ {56}}$

Od Diffie i Hellman sugerował ataki MITM, wiele odmian pojawiły które są użyteczne w sytuacjach, w których podstawowy atak MITM ma zastosowania. Biclique wariant ataku po raz pierwszy zaproponowana przez Dmitrija Khovratovich , Rechberger i Savelieva do użytku z hash-function kryptoanalizy. Jednak to Bogdanow, Khovratovich i Rechberger, który pokazał, jak zastosować koncepcję bicliques do ustawienia tajnego klucza w tym bloku-szyfr kryptoanalizy, kiedy opublikowano ich atak na AES. Wcześniej ataki MiTM na AES i wiele innych szyfrów blokowych otrzymał niewiele uwagi, głównie ze względu na potrzebę niezależnych kluczowych bitów między dwoma „subciphers MiTM” w celu ułatwienia ataku MITM - coś, co jest trudne do osiągnięcia z wielu nowoczesne kluczowe harmonogramy, takie jak to z AES.

biclique

Dla ogólnego wyjaśnienia co biclique struktura jest, zobacz stronę wiki dla bicliques .

W ataku MiTM, że keybits i , należące do pierwszej i drugiej subcipher, muszą być niezależne; to znaczy, że muszą być niezależne od siebie, bo inaczej dobrane wartości pośrednie dla plain- i szyfrogram nie mogą być obliczane niezależnie w ataku MiTM (istnieją warianty ataków MiTM, gdzie bloki mogą być Shared Key-bitów. Zobacz atak MITM 3 podzbioru ). Ta właściwość jest często trudne do wykorzystania przez większą liczbę rund, ze względu na dyfuzję zaatakowany szyfru. Mówiąc wprost: im więcej rund atakujesz, większe subciphers będzie trzeba. Większe subciphers masz, tym mniej niezależne kluczowych bitów między subciphers trzeba będzie Bruteforce niezależnie. Oczywiście, faktyczna liczba niezależnych kluczowych bitów w każdym subcipher zależy od właściwości dyfuzyjnych kluczowego harmonogramem. ${\ Displaystyle K_ {1}}$${\ Displaystyle K_ {2}}$

Sposób, w jaki biclique pomaga w zwalczaniu wyżej, jest to, że pozwala on na, na przykład, zawał 7 rund AES wykorzystaniem ataków MITM, a następnie wykorzystując biclique strukturę o długości 3 (to znaczy pokrywa 3 rundy szyfru) można odwzorować stan pośredni na początku rundy 7 do końca ostatniej rundy, na przykład 10 (jeśli jest AES128), więc atakowanie pełnej liczby rund szyfru, nawet gdyby to nie było możliwe, aby zaatakować tę kwotę rund z podstawowego ataku MiTM.

Znaczenie biclique jest więc skutecznie utworzenia struktury, które mogą służyć do wartości pośredniej na koniec natarcia MiTM do szyfrogramu na końcu. Który szyfrogram stan pośredni zostanie odwzorowane na na koniec, oczywiście zależy od klucza użytego do szyfrowania. Klucz używany do odwzorowania stanu do szyfrogramu w biclique, opiera się na keybits bruteforced w pierwszym i drugim subcipher ataku MiTM.

Istotą ataków biclique jest w ten sposób, obok ataku MiTM, aby móc skutecznie zbudować biclique strukturę, że w zależności od keybits i mogą służyć do pewnego stanu pośredniego z odpowiednim zaszyfrowanego tekstu. ${\ Displaystyle K_ {1}}$${\ Displaystyle K_ {2}}$

Jak zbudować biclique

Brutalna siła

Uzyskaj stany pośrednie i szyfrogramów, następnie obliczyć klucze, że mapy między nimi. To wymaga klucza i odzyskiwania, ponieważ każdy stan pośredni musi być połączony do wszystkich zaszyfrowanych. ${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {2d}}$

Niezależne mechanizmy różnicowe kluczowymi powiązanymi

(Metoda ta została zaproponowana przez Bogdanov, Khovratovich i Rechberger w swoim artykule: Biclique Kryptoanalizy z Pełnym AES)

Wstępny:
Należy pamiętać, że funkcja biclique jest mapowanie wartości pośrednie , aby szyfrogram wartościach, oparty na kluczu takie, że:${\ S} displaystyle$${\ Displaystyle C}$${\ Displaystyle K [i, j]}$
${\ Displaystyle \ forall, j: s_ {} {J \ xrightarrow [{f}] {K [i, j]}} C_ {i}}$

Procedura:
Etap pierwszy: stan pośredni ( ) szyfrogram ( ), a przycisk ( ) jest tak dobrana, że: gdzie jest to funkcja, która odwzorowuje stan pośredni do szyfrogramu za pomocą danego przycisku. Jest to określane jako obliczenia podstawy. ${\ Displaystyle S_ {0}}$${\ Displaystyle C_ {0}}$${\ Displaystyle K [0,0]}$${\ Displaystyle S_ {0} {\ xrightarrow [{f}] {K [0,0]}} C_ {o}}$${\ Displaystyle f}$

Etap drugi: dwa zestawy kluczy związanych z wielkością jest wybrany. Klucze są tak dobrane, aby: ${\ Displaystyle 2 ^ {d}}$

• Pierwszy zestaw klawiszy są klucze, który spełnia następujące wymagania różnicowego ciągu w odniesieniu do obliczenia podstawy:${\ Displaystyle f}$${\ Displaystyle 0 {\ xrightarrow [{f}] {\ delta _ {i} ^ {k}}} \ delta _ {i}}$
• Drugi zestaw przycisków jest przyciskami, który spełnia następujące wymagania różnicowego ciągu w odniesieniu do obliczenia podstawy:${\ Displaystyle f}$${\ Displaystyle \ nabla _ {} {J \ xrightarrow [{f}] {\ nabla _} {J ^ {k}}} 0}$
• Klawisze są tak dobrane, że szlaków z - a -differentials są niezależne - czyli nie udostępnia żadnych aktywnych składników nieliniowych.${\ Displaystyle \ delta _ {i}}$${\ Displaystyle \ nabla _ {j}}$

Innymi słowy:
różnicę wejście 0 należy mapować do różnicy wyjściowej mocy kluczowej różnicy . Wszystkie różnice są w odniesieniu do obliczania podstawy. Różnicę wejściowa powinna map do różnicy wyjściowego od 0 pod klucz różnicy . Wszystkie różnice są w odniesieniu do obliczania podstawy. ${\ Displaystyle \ delta _ {i}}$${\ Displaystyle \ delta _ {i} ^ {k}}$
${\ Displaystyle \ nabla _ {j}}$${\ Displaystyle \ nabla _} {J ^ {k}}$

Krok trzeci: Ponieważ szlaki nie udostępnia żadnych składników nieliniowych (taki jak s-pudełka) szlaki mogą być połączone, aby otrzymać: , które jest zgodne z definicjami obu różnicowych z etapu 2. To jest trywialne zauważyć, że krotka z obliczenia podstawy, jest również zgodne z definicji dla obu różnicowych, ponieważ są różnice w odniesieniu do obliczenia podstawy. Podstawienie w dowolnym z dwóch definicji przyniesie od a . Oznacza to, że krotka obliczenia podstawy, może być również XOR'ed do połączonych ścieżek:
${\ Displaystyle 0 {\ xrightarrow [{f}] {\ delta _ {i} ^ {k}}} \ delta _ {i} \ Oplus \ nabla _ {j} {\ xrightarrow [{f}] {\ nabla _ {j} ^ {k}}} 0 = \ nabla _ {j} {\ xrightarrow [{f}] {\ delta _ {i} ^ {k} \ Oplus \ nabla _ {j} ^ {k}} } \ delta _ {i}}$

${\ Displaystyle (S_ {0} C_ {0} K [0,0])}$${\ Displaystyle S_ {0} C_ {0}}$ ${\ Displaystyle K [0,0]}$${\ Displaystyle 0 {\ xrightarrow [{f}] {0}} 0}$${\ Displaystyle \ Delta _ {0} = 0 \ nabla _ = {0} 0}$${\ Displaystyle \ Delta _ {0} ^ {k} = 0}$
${\ Displaystyle S_ {0} \ Oplus \ nabla _ {} {J \ xrightarrow [{f}] {K [0,0] \ Oplus \ Delta _ {i} ^ {k} \ Oplus \ nabla _ {j} ^ {k}}} C_ {0} \ Oplus \ Delta _ {i}}$

Etap czwarty: jest trywialny, aby zobaczyć, że: Jeśli jest podstawiony w wyżej połączonych ścieżek różnicowych wynik wyniesie: który jest taki sam jak w definicji nie było wcześniej miała powyżej dla biclique:
${\ Displaystyle S_ J {} = S_ {0} \ Oplus \ nabla _ {j}}$
${\ Displaystyle K [i, j] = K [0,0] \ Oplus \ Delta _ {i} ^ {k} \ Oplus \ nabla _} {J ^ {k}}$
${\ Displaystyle C_ {i} = C_ {0} \ Oplus \ Delta _ {i}}$

${\ Displaystyle S_ {} {J \ xrightarrow [{f}] {K [i, j]}} C_ {i}}$

${\ Displaystyle \ forall, j: s_ {} {J \ xrightarrow [{f}] {K [i, j]}} C_ {i}}$

Jest więc możliwe utworzenie biclique wielkości ( ponieważ wszystkie klucze pierwszego zestawu kluczy, mogą być łączone z kluczy z drugim zestawem kluczy). Oznacza to biclique wielkości mogą być tworzone przy użyciu wyłącznie obliczeń z tych różnic i ponad . Jeśli dla wtedy wszystkie klawisze będą również różne w biclique. ${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 * 2 ^ {d}}$${\ Displaystyle \ delta _ {i}}$${\ Displaystyle \ nabla _ {j}}$${\ Displaystyle f}$${\ Displaystyle \ Delta _ {i} \ neq \ nabla _ {j}}$${\ Displaystyle i + J> 0}$${\ Displaystyle K [i, j]}$

W ten sposób jest jak biclique jest skonstruowany w wiodących biclique ataku na AES. Należy zauważyć, że istnieją pewne ograniczenia praktyczne w konstruowaniu bicliques z tej techniki. Im dłużej biclique, tym więcej rund szlaki różniczkowe musi pokryć. Właściwości dyfuzji szyfr, co odgrywa kluczową rolę w skuteczności konstruowania biclique.

Inne sposoby konstruowania biclique

Bogdanow, Khovratovich i Rechberger opisuje również inny sposób na budowę w biclique, zwany „Szlaki Przeplatanie Powiązane-Key Differential” w artykule: „Biclique Kryptoanalizy z Pełnym AES”.

Procedura Biclique Kryptoanalizy

Etap pierwszy: wszystkie grupy możliwych kluczy atakujący język kluczowych wielkości podzbiorów na część , gdzie przycisk w grupie jest indeksowany jak w matrycy wielkości . Atakujący rozdziela szyfru na dwie podgrupy szyfrów i (tak, że ), tak jak w normalnej akcji MiTM. Zestaw kluczy dla każdego z podsektorów szyfrów jest liczności i nazywa i . Połączone klucz podpotoków szyfrów wyraża się ze wspomnianą matrycę . ${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle d}$${\ Displaystyle K [i, j]}$${\ Displaystyle 2 ^ {d} \ razy 2 ^ {d}}$${\ Displaystyle f}$${\ Displaystyle G}$${\ Displaystyle E = f \} g Circ$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle K [l, 0]}$${\ Displaystyle K [0, d]}$${\ Displaystyle K [i, j]}$

Krok drugi: Atakujący buduje biclique dla każdej grupy klawiszy. Biclique ma wymiar-D, ponieważ odwzorowuje to stany wewnętrzne, do zaszyfrowanych, przy użyciu klawiszy. W sekcji „Jak zbudować biclique” sugeruje, jak zbudować biclique użyciu „niezależny powiązanymi kluczowych różnic”. Biclique jest w tym przypadku zbudowany przy użyciu różnic z zestawu kluczy, a należące do podsektorów szyfrów. ${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle S_ {j}}$${\ Displaystyle 2 ^ {d}}$${\ Displaystyle C_ {i}}$${\ Displaystyle 2 ^ {2d}}$${\ Displaystyle K [l, 0]}$${\ Displaystyle K [0, d]}$

Etap trzeci: atakujący bierze możliwe szyfrogramów, i zwraca do deszyfrowania-wyrocznię na dostarczenie plaintexts dopasowanych . ${\ Displaystyle 2 ^ {d}}$${\ Displaystyle C_ {i}}$${\ Displaystyle P_ {i}}$

Etap czwarty: atakujący wybiera stan wewnętrzny i odpowiedni tekst jawny, i wykonuje zwykły atak MITM ponad i poprzez atakowanie ze stanu wewnętrznego i jawnego. ${\ Displaystyle S_ {j}}$${\ Displaystyle P_ {i}}$${\ Displaystyle f}$${\ Displaystyle G}$

Krok piąty: Ilekroć klucz kandydat zostanie stwierdzone, że mecze z , że klucz jest testowany na innej pary plain- / tekst zaszyfrowany. jeśli klucz sprawdza się w drugiej parze, to jest wysoce prawdopodobne, że jest to poprawny klucz. ${\ Displaystyle S_ {j}}$${\ Displaystyle P_ {i}}$

Przykład ataku

Poniższy przykład jest oparty na biclique ataku na AES z papieru „Biclique Kryptoanaliza Full AES”.
Opisy na przykład używa tej samej terminologii, że autorzy ataku używanego (tj dla nazw zmiennych, etc).
Dla uproszczenia jest to atak na wariantu AES128, która jest objęta poniżej.
Atak składa się z 7 rundy MiTM ataku z biclique obejmującym ostatnie 3 rundy.

klucz partycjonowania

Klucz przestrzeń jest podzielona na grupy kluczy, w których każda z grup składających się z kluczami. Dla każdej z grup, unikalna baza klucz do bazowego obliczeń wybrano. Podstawa klucz ma dwa specyficzne bajtów ustawiony na zero, pokazano w tabeli poniżej (co oznacza klucz ten sam sposób AES oznacza w matrycy 4x4 AES128)${\ Displaystyle 2 ^ {112}}$${\ Displaystyle 2 ^ {16}}$
${\ Displaystyle 2 ^ {112}}$${\ Displaystyle K [0,0]}$

${\ Displaystyle {\ {zaczynać bmatrix} - & - & - & 0 \\ 0 & - & - & - \\ - & - & - & - \\ - & - & - & - \ koniec {bmatrix}}}$

Pozostałe 14 bajtów (112 bitów) klucza jest następnie wymienić. Daje to unikalne zasadowo klucze; po jednym dla każdej grupy kluczy. Zwykłe przyciski w każdej grupie wybiera następnie pod względem ich podstawy kluczu. Są one dobrane tak, że są one niemal identyczne z base-klucza. Różnią się one jedynie 2 bajty (albo „S lub ”) o niżej podanych 4 bajtów:${\ Displaystyle 2 ^ {112}}$
${\ Displaystyle 2 ^ {16}}$${\ I} displaystyle$${\ Displaystyle J}$

${\ Displaystyle {\ {zaczynać bmatrix} - & - & i & i \\ J & - & J & - \\ - & - & - & - \\ - & - & - & - \ koniec {bmatrix}}}$

W ten sposób i , co w połączeniu zapewnia różne klucze . Te klawisze stanowią klucze w grupie za pomocą odpowiedniego klucza podstawowego. ${\ Displaystyle 2 ^ {8} K [l, 0]}$${\ Displaystyle 2 ^ {8} K [0, d]}$${\ Displaystyle 2 ^ {16}}$${\ Displaystyle K [i, j]}$${\ Displaystyle 2 ^ {16}}$

Biclique budowa

${\ Displaystyle 2 ^ {112}}$bicliques jest skonstruowany przy użyciu techniki „Niezależny powiązanymi kluczowe różnice”, jak opisano w sekcji „Jak skonstruowania biclique”.
Wymóg z zastosowaniem tej techniki, było to, że szlaki skierowanych do przodu i do tyłu różnicowe, które muszą być połączone, nie udostępniać aktywnych elementy nieliniowe. Jak wiadomo, że jest to przypadek?
Ze względu na sposób, w jaki klucze w etapie 1 jest wybrana w odniesieniu do klucza podstawowego, ślady różnicowe z użyciem klawiszy nie przekazują żadnych aktywnych skrzynki S (który jest jedynym składnikiem nieliniowym AES) z szlaków różniczkowych przy użyciu klucz . Jest zatem możliwe, aby XOR szlaki różniczkowych i stworzyć biclique. ${\ Displaystyle \ delta _ {i}}$${\ Displaystyle K [l, 0]}$${\ Displaystyle \ nabla _ {j}}$${\ Displaystyle K [0, d]}$

atak MITM

Gdy bicliques są tworzone, atak MITM może prawie zacząć. Przed wykonaniem ataku MITM, że wartości pośrednich od tekstu jawnego: , te wartości pośrednich od szyfrogram: , oraz odpowiadające im stany pośrednie i podklucze lub , są przechowywane i precomputed jednak. ${\ Displaystyle 2 ^ {d}}$
${\ Displaystyle P_ {i} {\ xrightarrow [{}] {K [l, 0]}} {\ xrightarrow [{V_ {i}}] {}}}$
${\ Displaystyle 2 ^ {d}}$
${\ Displaystyle {\ xleftarrow [{V_ {j}}] {}} {\ xleftarrow [{}] {K [0, d]}} S_ {j}}$
${\ Displaystyle K [l, 0]}$${\ Displaystyle K [0, d]}$

Teraz atak MITM mogą być przeprowadzone. W celu sprawdzenia klucza , Konieczne jest jedynie, aby przeliczyć części szyfru, który znany będzie się zmieniać między i . Dla obliczenia wstecznego od celu , to jest 4-S-box, który musi być przeliczane. Do obliczeń do przodu od celu , to tylko 3 (wyjaśnienie w głębi za kwotę potrzebną przeliczenia można znaleźć w „Biclique kryptograficznych pełnej AES” papier, gdzie ten przykład jest pobierany z). ${\ Displaystyle K [i, j]}$${\ Displaystyle P_ {i} {\ xrightarrow [{}] {K [l, 0]}} {\ xrightarrow [{V_ {i}}] {}}}$${\ Displaystyle P_ {i} {\ xrightarrow [{}] {K [i, j]}} {\ xrightarrow [{V_ {i}}] {}}}$${\ Displaystyle S_ {j}}$${\ Displaystyle {\ xleftarrow [{V_ {j}}] {}}}$${\ Displaystyle P_ {i}}$${\ Displaystyle {\ xrightarrow [{V_ {i}}] {}}}$

Gdy wartości pośrednie pasuje, kluczowym kandydatem pomiędzy i zostanie znaleziona. Klucz-kandydat jest następnie testowany na innej pary plain- / tekst zaszyfrowany. ${\ Displaystyle K [i, j]}$${\ Displaystyle P_ {i}}$${\ Displaystyle S_ {j}}$

wyniki

Ten atak zmniejsza złożoność obliczeniową do AES128 , która jest 3-5 razy szybciej niż podejście Bruteforce. Złożoność danych jest atak i złożoność pamięci . ${\ Displaystyle 2 ^ {126,18}}$${\ Displaystyle 2 ^ {88}}$${\ Displaystyle 2 ^ {8}}$

Referencje