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.

Załóżmy, że mamy parę tekstu jawnego i zaszyfrowanego (P i C) związaną następującą zależnością:

${\displaystyle C=E_{K_{2}}(E_{K_{1}}(P)),}$

gdzie ${\displaystyle K_{1}}$ i ${\displaystyle K_{2}}$ są dwoma różnymi kluczami kryptograficznymi.

A zatem:

${\displaystyle D_{K_{2}}(C)=E_{K_{1}}(P).}$

Atakujący tworzy i zapamiętuje tablicę z wynikami ${\displaystyle E_{K_{1}}(P)}$ dla wszystkich możliwych kluczy. Następnie wylicza ${\displaystyle 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 ${\displaystyle D_{K_{2}}(C)}$ i wyszukiwać pasującego ${\displaystyle 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ń.

Żeby złamać dwukrotnego DESa:

${\displaystyle C=E_{DES,K_{2}}(E_{DES,K_{1}}(P)).}$

Trzeba wykonać ${\displaystyle 2^{56}}$ szyfrowań żeby otrzymać tablicę wyników pośrednich dla wszystkich ${\displaystyle K_{1},}$ i od 1 do ${\displaystyle 2^{56}}$ (średnio ${\displaystyle 2^{55}}$) żeby znaleźć pasujący ${\displaystyle K_{2}.}$ Razem więc ${\displaystyle 2^{56}+2^{55}\approx 2^{56.58}}$ operacji.

Żeby złamać trzykrotnego DESa:

${\displaystyle 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ć:

${\displaystyle D_{DES,K_{2}}(D_{DES,K_{3}}(C))=E_{DES,K_{1}}(P).}$

Następnie tablicujemy wyniki pośrednie dla wszystkich ${\displaystyle K_{1},}$ co wymaga ${\displaystyle 2^{56}}$ i pamięci rzędu ${\displaystyle 2^{56}.}$ W końcu zgadujemy ${\displaystyle K_{1}}$ i ${\displaystyle K_{2},}$ co wymaga średnio ${\displaystyle 2^{111}}$ operacji. Ponieważ ta pierwsza liczba jest o wiele mniejsza od drugiej, oczekiwany czas to ${\displaystyle 2^{111}}$ operacji a zużycie pamięci to ${\displaystyle 2^{56}}$ bloków.

Podział w którym dwa DESy się tablicuje, a trzeci zgaduje wymagałby ${\displaystyle 2^{112}}$ operacji na przygotowanie tablicy i średnio ${\displaystyle 2^{55}}$ na zgadnięcie, razem ${\displaystyle 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 ${\displaystyle 2^{56}}$ do zupełnie gigantycznego ${\displaystyle 2^{112}.}$

Żeby złamać szyfr w którym blok najpierw szyfruje się 80-bitowym Skipjackiem, a następnie 56-bitowym DESem:

${\displaystyle C=E_{DES,K_{2}}(E_{Skipjack,K_{1}}(P)).}$

Dzielimy szyfr na dwie części:

${\displaystyle 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 ${\displaystyle 2^{56}}$), i iterować po prawej stronie ${\displaystyle 2^{80}.}$

Jeśli chcemy złamać dwukrotnego DESa, ale mamy jedynie pamięć rzędu ${\displaystyle 2^{40},}$ zamiast wymaganych ${\displaystyle 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 ${\displaystyle 2^{16}\left(2^{56}+2^{56}\right)=2^{16+57}=2^{73}.}$ Jest to więcej od pełnego meet in the middle ${\displaystyle (2^{56.58}),}$ ale mniej od naiwnego łamania 2DESa ${\displaystyle (2^{111}).}$ Zależnie od ilości pamięci, jaką dysponujemy możemy też wybrać inne kompromisowe rozwiązania.

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.

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.