Meet-in-the-middle og tids-hukommelses-afvejninger

MITM-angreb opdeler en cipher i to halvdele og angriber dem uafhængigt. Angriberen opbygger en tabel fra den ene ende og søger derefter fra den anden ende efter et match. Det reducerer angrebskompleksiteten fra O(2^{2n}) til O(2^n) på bekostning af O(2^n) hukommelse.

Double-DES anvender DES to gange: C = DES_{K2}(DES_{K1}(P)). Nøglerum: 2^{112}. MITM-angreb: For alle 2^{56} K1-værdier beregnes DES_{K1}(P), som gemmes. For alle 2^{56} K2-værdier beregnes DES_{K2}^{-1}(C), og resultatet slås op i tabellen. Match → (K1, K2)-kandidat. Kun 2^{57} beregninger i alt.

Trin 1: Krypter klarteksten P med alle mulige K1 → tabel T[DES_{K1}(P)] = K1. Trin 2: Dekryptér cipherteksten C for hvert K2: v = DES^{-1}_{K2}(C). Kontrollér, om v ∈ T. Hvis T[v] = K1 findes, skal du verificere (K1, K2) på endnu et klartekst-ciphertekst-par. Forvent 1-2 falske træffere; kassér dem.

Triple-DES (3DES) bruger tre nøgler K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM gælder stadig, men i mindre grad: Triple-DES med to nøgler (K3=K1) reduceres til 2^{112} beregningsarbejde. For Triple-DES med tre nøgler findes der et MITM-angreb på 2^{112}, hvilket forklarer, hvorfor 3DES kun giver cirka 112 bit effektiv sikkerhed trods en nøgle på 168 bit.

Hellman (1980): Forudberegn en tabel med kæder af (start_point, end_point) for at gøre offline-nøglesøgning hurtigere. Givet en mål-hash eller ciphertekst søger du i Hellman-tabellen efter en kæde, der indeholder den. Afvejning: P = N (tid × hukommelse = konstant plads). Grundlaget for regnbuetabeller.

Regnbuetabeller (Oechslin, 2003) forbedrer Hellman-tabeller ved at bruge forskellige reduktionsfunktioner ved hver kædeposition, så falske alarmer (sammenflettede kæder) elimineres. De er effektive til at knække saltfri hashværdier for adgangskoder. Et opslag tager O(table_size/chain_length) tid.

Et salt er en tilfældig værdi, der sættes foran adgangskoden før hashing: H(salt||password). Forskellige salte giver forskellige hashværdier for den samme adgangskode — en regnbuetabel for "password" er ubrugelig, hvis der blev brugt et andet salt. Salte skal gemmes sammen med hashværdien.

MITM-angreb på AES-128 (10 runder): Kendte angreb opdeler ved runde 5 — krypter 5 runder fremad, dekryptér 5 runder baglæns, og mød hinanden i midten. Det bedste kendte angreb: Biclique-angrebet reducerer 2^{128} til 2^{126.1} — ikke praktisk anvendeligt, men det viser, at AES ikke har nogen sikkerhedsmargin mod MITM-lignende metoder.

For Merkle-Damgard-hashfunktioner kan MITM finde præbilleder hurtigere end brute force i nogle konstruktioner. Angreb: Opbyg en tabel fra meddelelsesblokke med udgangspunkt i IV, og søg baglæns fra mål-hashværdien. Mod SHA-256 med alle runder er det stadig cirka 2^{255} — ingen forbedring i forhold til brute force.

Dissektionsangreb generaliserer MITM til opdelinger i r dele. Ved en opdeling af en cipher i tre dele krypteres den første tredjedel af runderne fremad, kæden mødes på midten, og den sidste tredjedel dekrypteres baglæns. Det kræver O(2^{n*2/3}) tid og O(2^{n/3}) hukommelse — en mere afbalanceret afvejning.

I protokoller kan MITM-angreb forhindres ved at bruge lange KDF-afledte nøgler fra adgangskoder med høj entropi (det reducerer det nøglerum, der kan enumereres), hardwaretokens (FIDO2), hvor nøglen aldrig forlader enheden, eller godkendelse med offentlig nøgle (ingen delt hemmelighed, der kan enumereres).

MITM-angreb opdeler ciphers i halvdele og reducerer tiden fra 2^{2n} til 2^n med 2^n hukommelse. De bryder Double-DES; 3DES er afhjulpet, men har 112 bit effektiv sikkerhed. Regnbuetabeller bruger MITM-logik til at knække adgangskoder — det forhindres med salt. Næste emne: timingangreb og sidekanalangreb.