Meet-in-the-middle og avveiinger mellom tid og minne

MITM-angrep deler et chiffer i to halvdeler og angriper dem uavhengig av hverandre. Angriperen bygger en tabell fra den ene enden og søker deretter fra den andre enden etter et treff. Dette reduserer angrepskompleksiteten fra O(2^{2n}) til O(2^n), på bekostning av O(2^n) minne.

Double-DES bruker DES to ganger: C = DES_{K2}(DES_{K1}(P)). Nøkkelrommet er 2^{112}. MITM-angrep: For alle 2^{56} K1-verdier beregnes DES_{K1}(P), og resultatet lagres. For alle 2^{56} K2-verdier beregnes DES_{K2}^{-1}(C), og resultatet slås opp i tabellen. Treff → (K1, K2)-kandidat. Totalt kreves bare 2^{57} arbeid.

Trinn 1: Krypter klarteksten P med alle mulige K1-verdier → tabell T[DES_{K1}(P)] = K1. Trinn 2: Dekrypter chifferteksten C for hver K2-verdi: v = DES^{-1}_{K2}(C). Sjekk om v ∈ T. Hvis T[v] = K1 finnes, verifiser (K1, K2) på et annet klartekst–chiffertekst-par. Forvent 1–2 falske treff, og forkast dem.

Triple-DES (3DES) bruker tre nøkler K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM gjelder fortsatt, men i svakere grad: 3DES med to nøkler (K3=K1) reduseres til 2^{112} arbeid. For 3DES med tre nøkler finnes det et MITM-angrep på 2^{112}, noe som forklarer hvorfor 3DES bare gir omtrent 112 bits effektiv sikkerhet, til tross for en nøkkel på 168 bit.

Hellman (1980): Forhåndsberegn en tabell med kjeder av (startpunkt, sluttpunkt) for å fremskynde et frakoblet nøkkelsøk. Gitt en målhash eller chiffertekst søker du i Hellman-tabellen etter en kjede som inneholder den. Avveining: P = N (tid × minne = konstant produkt). Dette er grunnlaget for regnbuetabeller.

Regnbuetabeller (Oechslin, 2003) forbedrer Hellman-tabeller ved å bruke ulike reduksjonsfunksjoner på hver kjedeposisjon, slik at falske alarmer (sammensmeltede kjeder) elimineres. De er effektive for å knekke usaltede passordhasher. Et oppslag tar O(table_size/chain_length) tid.

Et salt er en tilfeldig verdi som settes foran passordet før hashing: H(salt||password). Ulike salter gir ulike hasher for det samme passordet – en regnbuetabell for "password" er ubrukelig hvis et annet salt ble brukt. Salter må lagres sammen med hashen.

MITM-angrep på AES-128 (10 runder): Kjente angrep deler ved runde 5 – krypter fremover gjennom 5 runder, dekrypter bakover gjennom 5 runder, og møt i midten. Det beste kjente angrepet reduserer 2^{128} til 2^{126.1} med et biclique-angrep – ikke praktisk gjennomførbart, men det viser at AES ikke har noen sikkerhetsmargin mot MITM-lignende metoder.

For Merkle-Damgård-hasher kan MITM finne preimages raskere enn brute force i enkelte konstruksjoner. Angrepet bygger en tabell fra meldingsblokker som starter ved IV, og søker bakover fra målhashen. Mot SHA-256 med alle runder kreves det fortsatt omtrent 2^{255} arbeid – ingen forbedring sammenlignet med brute force.

Disseksjonsangrep generaliserer MITM til oppdelinger i r deler. For en 3-veis oppdeling av et chiffer krypteres først 1/3 av rundene fremover, deretter møtes man midt i kjeden, før 1/3 av rundene dekrypteres bakover. Det krever O(2^{n*2/3}) tid og O(2^{n/3}) minne – en mer balansert avveining.

I protokoller kan MITM-angrep hindres ved å bruke lange, KDF-avledede nøkler fra passord med høy entropi (noe som reduserer nøkkelområdet som kan enumereres), bruke maskinvaretokenheter (FIDO2) der nøkkelen aldri forlater enheten, eller bruke autentisering med offentlig nøkkel (ingen delt hemmelighet å enumerere).

MITM-angrep deler chiffere i to, og reduserer tidsforbruket fra 2^{2n} til 2^n med 2^n minne. Dette bryter Double-DES, mens 3DES reduserer problemet, men bare har 112 bits effektiv sikkerhet. Regnbuetabeller bruker MITM-logikk til passordknekking – dette hindres med salting. Neste: tidsangrep og sidekanalangrep.