Meet-in-the-middle i kompromisy czas–pamięć

Ataki MITM dzielą szyfr na dwie połowy i atakują je niezależnie. Atakujący buduje tabelę od jednego końca, a następnie od drugiego końca szuka dopasowania. Zmniejsza to złożoność ataku z O(2^{2n}) do O(2^n) kosztem pamięci O(2^n).

Double-DES stosuje DES dwukrotnie: C = DES_{K2}(DES_{K1}(P)). Przestrzeń kluczy: 2^{112}. Atak MITM: dla wszystkich 2^{56} wartości K1 oblicz DES_{K1}(P) i zapisz wynik. Dla wszystkich 2^{56} wartości K2 oblicz DES_{K2}^{-1}(C) i wyszukaj wynik w tabeli. Dopasowanie → kandydat pary (K1, K2). Łącznie potrzeba jedynie 2^{57} operacji.

Krok 1: zaszyfruj tekst jawny P za pomocą wszystkich możliwych wartości K1 → tabela T[DES_{K1}(P)] = K1. Krok 2: dla każdej wartości K2 odszyfruj szyfrogram C: v = DES^{-1}_{K2}(C). Sprawdź, czy v ∈ T. Jeśli istnieje T[v] = K1, zweryfikuj parę (K1, K2) na drugiej parze tekstu jawnego i szyfrogramu. Należy oczekiwać 1–2 fałszywych dopasowań i je odrzucić.

Triple-DES (3DES) używa trzech kluczy K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). Atak MITM nadal ma zastosowanie, ale jest mniej skuteczny: w przypadku dwukluczowego 3DES (K3=K1) wymaga pracy rzędu 2^{112}. W przypadku trzykluczowego 3DES istnieje atak MITM o koszcie 2^{112}, co wyjaśnia, dlaczego 3DES zapewnia jedynie około 112 bitów efektywnego bezpieczeństwa mimo klucza 168-bitowego.

Hellman (1980) zaproponował wstępne obliczanie tabeli łańcuchów (start_point, end_point) w celu przyspieszenia wyszukiwania kluczy offline. Dla docelowego skrótu lub szyfrogramu należy przeszukać tabelę Hellmana pod kątem łańcucha, który go zawiera. Kompromis: P = N (czas × pamięć = stała przestrzeni). To rozwiązanie stanowi podstawę tęczowych tablic.

Tęczowe tablice (Oechslin, 2003) udoskonalają tablice Hellmana, używając różnych funkcji redukcji na każdej pozycji łańcucha, co eliminuje fałszywe alarmy (połączone łańcuchy). Są skuteczne w łamaniu niesolonych skrótów haseł. Wyszukiwanie zajmuje O(table_size/chain_length) czasu.

Sól to losowa wartość dołączana do hasła przed obliczeniem skrótu: H(salt||password). Różne sole dają różne skróty dla tego samego hasła — tęczowa tablica dla „password” jest bezużyteczna, jeśli użyto innej soli. Sole muszą być przechowywane razem ze skrótem.

Ataki MITM na AES-128 (10 rund) dzielą znane konstrukcje w rundzie 5: pięć rund jest szyfrowanych w przód, pięć rund odszyfrowywanych wstecz, a następnie następuje spotkanie pośrodku łańcucha. Najlepszy znany atak, biclique, zmniejsza koszt z 2^{128} do 2^{126.1} — nie jest praktyczny, ale pokazuje, że AES nie ma marginesu bezpieczeństwa wobec podejść typu MITM.

W przypadku funkcji skrótu Merkle-Damgarda MITM może dla niektórych konstrukcji znaleźć preobrazy szybciej niż metodą brute force. Atak polega na zbudowaniu tabeli z bloków wiadomości, zaczynając od IV, a następnie na wyszukiwaniu wstecz od docelowego skrótu. W przypadku SHA-256 z pełną liczbą rund nadal jest to około 2^{255} — bez poprawy względem brute force.

Atak dissection uogólnia MITM na podział na r części. Przy podziale szyfru na 3 części należy zaszyfrować w przód 1/3 rund, spotkać się pośrodku łańcucha, a następnie odszyfrować wstecz 1/3 rund. Wymaga to czasu O(2^{n*2/3}) i pamięci O(2^{n/3}) — jest to bardziej zrównoważony kompromis.

W protokołach atakom MITM można zapobiegać poprzez używanie długich kluczy wyprowadzanych za pomocą KDF z haseł o wysokiej entropii (zmniejsza to przestrzeń kluczy, którą można przeszukać), używanie tokenów sprzętowych (FIDO2), w przypadku których klucz nigdy nie opuszcza urządzenia, lub stosowanie uwierzytelniania kluczem publicznym (brak wspólnego sekretu do przeszukania).

Ataki MITM dzielą szyfry na połowy, zmniejszając czas z 2^{2n} do 2^n przy użyciu pamięci 2^n. Łamią Double-DES, a w przypadku 3DES są ograniczone, lecz zapewniają mu jedynie 112 bitów efektywnego bezpieczeństwa. Tęczowe tablice wykorzystują logikę MITM do łamania haseł — zapobieganie temu wymaga stosowania soli. Następnie: ataki czasowe i ataki bocznokanałowe.