Crypto-IT

Atak meet-in-the-middle to jeden z rodzajów ataków ze znanym tekstem jawnym. Napastnik musi znać fragmenty tekstu jawnego i odpowiadające im szyfrogramy. Za pomocą ataków tego typu można łamać szyfry, które używają dwóch lub więcej różnych kluczy do wielokrotnego szyfrowania za pomocą tego samego algorytmu. Przykładem takiego szyfrowania jest szyfr 3DES. Atak meet-in-the-middle został po raz pierwszy zademonstrowany przez kryptologów Diffie'go i Hellman'a przy okazji analizy algorytmu DES.

Dla tak zdefiniowanego szyfru, można zapisać następujące równanie:
    D_b(k_b, C) = E_a(k_a, P)
Gdzie C to znany napastnikowi szyfrogram odpowiadający znanej napastnikowi wiadomości P.

Pierwszy krok ataku polega na utworzeniu tabeli wszystkich możliwych wartości dla jednej ze stron równania. Można wyliczyć więc wszystkie możliwe szyfrogramy znanego tektu jawnego P, powstałe po zakodowaniu go przy użyciu pierwszego z sekretnych kluczy, czyli E_a(k_a,P). Tablica będzie miała długość równą liczbie możliwych sekretnych kluczy. Dobrze jest potem posortować otrzymaną tablicę względem otrzymanych wartości szyfrogramów E_a(k_a,P), w celu ułatwienia jej późniejszego przeszukiwania.

Drugim krokiem ataku jest wyliczanie wartości D_b(k_b,C) dla drugiej strony równania. Należy porównywać je z otrzymanymi wsześniej i przechowywanymi w tabeli wartościami wyliczonymi dla pierwszej strony równania. Atakujący szuka takiej pary sekretnych kluczy k_a i k_b, dla których znaleziona w tabeli wartość E_a(k_a,P) i aktualnie wyliczona wartość D_b(k_b,C) są równe.

Schemat ataku meet-in-the-middle

Atakowane mogą być również szyfry, dla których oba algorytmy szyfrujące E są różne (i używają kluczy o niekoniecznie takiej samej wartości). W takim wypadku, tablicę w pierwszym kroku tworzy się dla słabszego z dwóch algorytmów szyfrujących.

Atak meet-in-the-middle umożliwia dużo szybsze złamanie zabezpieczeń niż przy użyciu zwykłego ataku siłowego. Złożoności czasowa i obliczeniowa zależą od wielkości dwóch kluczy szyfrujących k_a i k_b. Można je przedstawić jako sumę dwóch iloczynów:

    2^dł(k_a) log(2^dł(k_a)) + 2^dł(k_b) log(2^dł(k_a))

• 2^dł(k_a) - tworzenie tabeli zawierającej wszystkie możliwe wartości E_a(k_a,P),
• log(2^dł(k_a)) - sortowanie tabeli zawierającej wszystkie wartości E_a(k_a,P),
• 2^dł(k_b) - obliczanie wszystich możliwych wartości D_b(k_b,C),
• log(2^dł(k_a)) - przeszukiwanie posortowanej tabeli zawierającej wartości E_a(k_a,P).

Jeśli długości kluczy k_a i k_b są równe i wynoszą dk, to złożoność obliczeniową ataku meet-in-the-middle można przedstawić jako O(2^dk+1). Wykorzystanie pamięci wynosi natomiast O(2^dk). Złożoność obliczeniowa zwykłego ataku siłowego jest dużo większa, wynosi bowiem O(2^dk+dk). Z drugiej strony atak siłowy wykorzystuje jedynie O(1) pamięci.

Można rozważać sytuację, w której w procesie działania algorytmu szyfrującego da się wyodrębnić pewien stan przejściowy. Jeżeli wielkość tego stanu przejściowego jest mniejsza niż długość klucza, atakując go można zastosować tak zwany dwuwymiarowy atak meet-in-the-middle. We współczesnych szyfrach blokowych przypadek operowania na niewielkich blokach danych przy użyciu długiego klucza jest bardzo częsty.

Oznaczając stan przejściowy jako S można przedstawić złożony szyfr jako:
    C = E₁(k₁, E₂(k₂, P))
    P = D₂(k₂, D₁(k₁, C))
Gdzie wartości E₂(k₂,P) należą do zbioru zawierającego wszystkie możliwe wartości stanu przejściowego S.

Oba algorytmy szyfrujące E₁ i E₂ można łamać za pomocą dwuwymiarowego ataku meet-in-the-middle. Schemat ataku przedstawiony jest na poniższym rysunku:

W calu złamania szyfru za pomocą dwuwymiarowego ataku meet-in-the-middle należy wykonać następujące kroki:

1. Obliczyć wszystkie możliwe wartości E_a1(k_a1,P) (dla znanego P i wszystkich możliwych wartości klucza k_a1), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_a1. Tabela powinna być posortowana względem wyliczonych wartości E_a1(k_a1,P).
2. Obliczyć wszystkie możliwe wartości D_b2(k_b2,C) (dla znanego C opowiadającego P i wszystkich możliwych wartości klucza k_b2), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_b2. Tabela powinna być posortowana względem wyliczonych wartości D_b2(k_b2,C).
3. Dla każdej możliwej wartości stanu pośredniego S:
   1. Obliczyć wszystkie możliwe wartości D_b1(k_b1,S) (dla wszystkich możliwych wartości klucza k_b1), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_b1. Tabela powinna być posortowana względem wyliczonych wartości D_b1(k_b1,S).
   2. Obliczyć wszystkie możliwe wartości E_a2(k_a2,S) (dla wszystkich możliwych wartości klucza k_a2), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_a2. Tabela powinna być posortowana względem wyliczonych wartości E_a2(k_a2,S).
   3. Porównać wartości w czterech utworzonych tabelach, poszukując równości E_a1(k_a1,P) = D_b1(k_b1,S) (uzyska się w ten sposób parę kluczy (k_a1,k_b1)) oraz E_a2(k_a2,S) = D_b2(k_b2,C) (para kluczy (k_a2,k_b2)). Wszystkie kombinacje tych dwóch par kluczy stanowią kandydatów na poszukiwany sekretny klucz całego szyfru. Należy wybrać właściwą kombinację par poprzez sprawdzenie uzyskanego klucza na innych znanych fragmentach tekstu jawnego i szyfrogramu.

Zwykle cztery wyodrębnione klucze k_a1, k_b1, k_a2 i k_b2 mają niektóre bity wspólne. Sposobem, który umożliwia kryptoanalizę w takim przypadku jest traktowanie każdego bitu oddzielnie i przyporządkowanie mu niezależnej zmiennej.

Opisane postępowanie można uogólnić do przypadku, kiedy szyfr złożony jest dzielony na większą ilość prostszych szyfrów. W ogólnym przypadku należy założyć, że da się wyodrębnić n stanów przejściowych oraz n+1 algorytmów szyfrujących możliwych do złamania za pomocą metody meet-in-the-middle. Taka sytuacja jest przedstawiona na schemacie poniżej:

W calu złamania szyfru za pomocą wielowymiarowego ataku meet-in-the-middle należy wykonać następujące kroki:

1. Obliczyć wszystkie możliwe wartości E_a1(k_a1,P) (dla znanego P i wszystkich możliwych wartości klucza k_a1), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_a1. Tabela powinna być posortowana względem wyliczonych wartości E_a1(k_a1,P).
2. Obliczyć wszystkie możliwe wartości D_bn+1(k_bn+1,C) (dla znanego C opowiadającego P i wszystkich możliwych wartości klucza k_bn+1), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_bn+1. Tabela powinna być posortowana względem wyliczonych wartości D_bn+1(k_bn+1,C).
3. Dla każdej możliwej wartości stanu pośredniego S₁:
   1. Obliczyć wszystkie możliwe wartości D_b1(k_b1,S₁) (dla wszystkich możliwych wartości klucza k_b1), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_b1. Tabela powinna być posortowana względem wyliczonych wartości D_b1(k_b1,S₁).
   2. Obliczyć wszystkie możliwe wartości E_a2(k_a2,S₁) (dla wszystkich możliwych wartości klucza k_a2), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_a2. Tabela powinna być posortowana względem wyliczonych wartości E_a2(k_a2,S₁).
   3. Dla każdej możliwej wartości stanu pośredniego S₂:
      1. Obliczyć wszystkie możliwe wartości D_b2(k_b2,S₂) (dla wszystkich możliwych wartości klucza k_b2), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_b2. Tabela powinna być posortowana względem wyliczonych wartości D_b2(k_b2,S₂).
      2. ...powtarzać analogiczne operacje aż do przejściowego stanu S_n...
      3. Dla każdej możliwej wartości stanu pośredniego S_n:
         1. Obliczyć wszystkie możliwe wartości D_bn(k_bn,S_n) (dla wszystkich możliwych wartości klucza k_bn), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_bn. Tabela powinna być posortowana względem wyliczonych wartości D_bn(k_bn,S_n).
         2. Obliczyć wszystkie możliwe wartości E_an+1(k_an+1,S_n) (dla wszystkich możliwych wartości klucza k_an+1), a następnie umieścić je w tabeli razem z wartościami odpowiadających im kluczy k_an+1. Tabela powinna być posortowana względem wyliczonych wartości E_an+1(k_an+1,S_n).
         3. Przeanalizować wartości we wszystkich utworzonych tabelach, porównując odpowiednie wielkości E_ai z D_bi. Wynikiem będzie pewna ilość kombinacji par odpowiadających sobie kluczy (k_ai,k_bi). Należy wybrać właściwą kombinację par poprzez sprawdzenie uzyskanego klucza na innych znanych fragmentach tekstu jawnego i szyfrogramu.

Kolejność analizowania poszczególnych stanów przejściowych może być dowolnie wybrana. Z racji tego, że stany przejściowe mają mniejszą wielkość niż klucze szyfrujące, tworzone tabele zajmują mniej więcej tyle samo miejsca co tabele tworzone podczas zwykłego jednowymiarowego ataku meet-in-the-middle.