Reklama
Dzisiaj jest 9 stycznia 2025 r.
Chcę dodać własny artykuł
Reklama
Reklama
Reklama

Meet in the middle

Meet in the middle – jest rodzajem ataku kryptograficznego z jawnym tekstem, autorstwa Merkle’a i Hellmana (1981). Do jego przeprowadzenia konieczna jest znajomość zarówno tekstu jawnego, jak i zaszyfrowanego (atak ze znanym tekstem jawnym). Algorytmami podatnymi na tego rodzaju ataki są algorytmy używające dwóch lub więcej kluczy do wielokrotnego szyfrowania tym samym algorytmem np. 3DES.

Reklama

Metoda ataku

Załóżmy, że mamy parę tekstu jawnego i zaszyfrowanego (P i C) związaną następującą zależnością:
: C=E_{K_2}(E_{K_1}(P)),
gdzie K_1 i K_2 są dwoma różnymi kluczami kryptograficznymi.
A zatem:
: D_{K_2}(C)=E_{K_1}(P).
Atakujący tworzy i zapamiętuje tablicę z wynikami E_{K_1}(P) dla wszystkich możliwych kluczy. Następnie wylicza D_{K_2}(C) dla kolejnych kluczy i sprawdza, czy otrzymany wynik znajduje się już w tablicy z pierwszego kroku. W przypadku znalezienia identycznych wyników obu funkcji otrzymuje parę kluczy użytą do zaszyfrowania atakowanej wiadomości.
Alternatywnie atakujący może stworzyć i zapamiętać tablicę z wynikami D_{K_2}(C) i wyszukiwać pasującego E_{K_1}(P). Jeśli kolejne szyfry są różne, to żeby uzyskać lepszą wydajność powinno się tworzyć tablicę dla słabszego z nich.
Atak meet in the middle wymaga dużo pamięci, ale można go modyfikować, uzyskując dowolny kompromis między ilością potrzebnej pamięci a ilością potrzebnych obliczeń.

Przykłady

2DES

Żeby złamać dwukrotnego DESa:
: C=E_{DES,K_2}(E_{DES,K_1}(P)).
Trzeba wykonać 2^{56} szyfrowań żeby otrzymać tablicę wyników pośrednich dla wszystkich K_1, i od 1 do 2^{56} (średnio 2^{55}) żeby znaleźć pasujący K_2. Razem więc 2^{56}+2^{55} \approx 2^{56.58} operacji.

Reklama

3DES

Żeby złamać trzykrotnego DESa:
: C=E_{DES,K_3}(E_{DES,K_2}(E_{DES,K_1}(P))).
Dzielimy go najpierw na mniejszą część, którą będziemy tablicować i większą którą będziemy zgadywać:
: D_{DES,K_2}(D_{DES,K_3}(C)) = E_{DES,K_1}(P).
Następnie tablicujemy wyniki pośrednie dla wszystkich K_1, co wymaga 2^{56} i pamięci rzędu 2^{56}. W końcu zgadujemy K_1 i K_2, co wymaga średnio 2^{111} operacji. Ponieważ ta pierwsza liczba jest o wiele mniejsza od drugiej, oczekiwany czas to 2^{111} operacji a zużycie pamięci to 2^{56} bloków.
Podział w którym dwa DESy się tablicuje, a trzeci zgaduje wymagałby 2^{112} operacji na przygotowanie tablicy i średnio 2^{55} na zgadnięcie, razem 2^{112}, czyli dwukrotnie więcej operacji.
Taki wzrost ilości operacji nie jest wielkim problemem, ale wymagania pamięciowe wzrastają z rozsądnego choć dość dużego 2^{56} do zupełnie gigantycznego 2^{112}.

Różne szyfry

Żeby złamać szyfr w którym blok najpierw szyfruje się 80-bitowym Skipjackiem, a następnie 56-bitowym DESem:
: C=E_{DES,K_2}(E_{Skipjack,K_1}(P)).
Dzielimy szyfr na dwie części:
: D_{DES,K_2}(C) = E_{Skipjack,K_1}(P).
W tym wypadku opłaca się bardziej stablicować wszystkie możliwe deszyfracje lewej strony (tablica rozmiaru 2^{56}), i iterować po prawej stronie 2^{80}.

Ograniczona ilość pamięci

Jeśli chcemy złamać dwukrotnego DESa, ale mamy jedynie pamięć rzędu 2^{40}, zamiast wymaganych 2^{56}, możemy zastosować następujący sposób:
: Iterujemy po wszystkich możliwych 16-bitowych prefiksach, i dla każdego z nich:
:* Generujemy tablicę, ale zachowujemy tylko tę część której elementy zaczynają się od aktualnie wybranego prefiksu
:* Szukamy klucza.
Wymagana ilość operacji to 2^{16} \left(2^{56} + 2^{56}\right) = 2^{16+57} = 2^{73}.
Jest to więcej od pełnego meet in the middle (2^{56.58}), ale mniej od naiwnego łamania 2DESa (2^{111}). Zależnie od ilości pamięci, jaką dysponujemy możemy też wybrać inne kompromisowe rozwiązania.

Przykładowe obliczenia

Załóżmy, że mamy następujący 16-bitowy szyfr (16-bitowe szyfry mogą służyć jedynie jako przykład obliczeń, nie do poważnych zastosowań):
: Szyfrujemy blok za pomocą AES, przy czym ostatnie 8 bitów klucza AESa to pierwsza połowa naszego klucza, reszta bitów wynosi 0.
: Szyfrujemy otrzymany wynik za pomocą AES, przy czym ostatnie 8 bitów klucza AESa to druga połowa naszego klucza, reszta bitów wynosi 0.
Szyfrowanie bloku tym algorytmem można wykonać następująco (xxyy to klucz):
$ echo -n 'WiadomośćWiadomo’ | openssl enc -aes-128-ecb -K 000000000000000000000000000000xx -iv 0 -nopad -nosalt
| openssl enc -aes-128-ecb -K 000000000000000000000000000000yy -iv 0 -nopad -nosalt >WYNIK
Podsłuchaliśmy komunikacji zaszyfrowanej tym szyfrem i wiemy, że blok 57 69 6b 69 70 65 64 69 61 20 31 32 33 34 35 36 (Wikipedia 123456) to po zaszyfrowaniu 00 6f 08 ea df 08 00 7c 53 c8 3c 90 b5 81 f3 6e.
Generujemy więc wszystkie wyniki pośrednie po pierwszym AESie (kod w Perlu wywołuje szyfrowanie OpenSSLa i formatuje wyniki):

for(0..255){
  $k=sprintf "%02x", $_;
  $b=`echo -n "Wikipedia 123456" | openssl enc -aes-128-ecb -K 000000000000000000000000000000$k -iv 0 -nopad -nosalt`;
  printf "$k => %s\n", join(" ", map{sprintf "%02x", $_} unpack("C32", $b))
}

Następnie próbujemy zgadywać drugi podklucz, aż otrzymamy wartość z powyższej tabelki (kod w Perlu).

for(0..255){
  $k=sprintf "%02x", $_;
  $b=`echo -en "\\x00\\x6f\\x08\\xea\\xdf\\x08\\x00\\x7c\\x53\\xc8\\x3c\\x90\\xb5\\x81\\xf3\\x6e"
     | openssl enc -aes-128-ecb -d -K 000000000000000000000000000000$k -iv 0 -nopad -nosalt`;
  printf "$k => %s\n", join(" ", map{sprintf "%02x", $_} unpack("C32", $b))
}

Wartości pośrednie dla 4d z pierwszej tabeli i b7 z drugiej są takie same i równe 87 b3 37 3b 07 20 fe 40 24 54 7f eb 1b 0e ad 4b. Klucz wynosi więc 4db7.

Wpływ na bezpieczeństwo

W przypadku użycia szyfrowania wielokrotnego można by sądzić, że siła 3DES wzrośnie w stosunku do DES trzykrotnie, jednak dzięki wykorzystaniu ataku meet in the middle siła ta wzrasta zaledwie dwukrotnie.
Kategoria:Kryptoanaliza

Reklama
Reklama