Meet-in-the-middle en time-memory trade-offs

MITM-aanvallen splitsen een versleutelingsalgoritme in twee helften en vallen die onafhankelijk aan. De aanvaller bouwt vanaf één kant een tabel en zoekt vervolgens vanaf de andere kant naar een overeenkomst. Dit verlaagt de complexiteit van O(2^{2n}) naar O(2^n), ten koste van O(2^n) geheugen.

Double-DES past DES tweemaal toe: C = DES_{K2}(DES_{K1}(P)). Sleutelruimte: 2^{112}. MITM-aanval: bereken voor alle 2^{56} waarden van K1 DES_{K1}(P) en sla het resultaat op. Bereken voor alle 2^{56} waarden van K2 DES_{K2}^{-1}(C) en zoek het resultaat op in de tabel. Overeenkomst → kandidaat (K1, K2). In totaal zijn slechts 2^{57} bewerkingen nodig.

Stap 1: versleutel plaintext P met alle mogelijke waarden van K1 → tabel T[DES_{K1}(P)] = K1. Stap 2: ontsleutel voor elke K2 de cijfertekst C: v = DES^{-1}_{K2}(C). Controleer of v ∈ T. Als T[v] = K1 bestaat, controleer je (K1, K2) met een tweede plaintext-cijfertekstpaar. Verwacht 1 à 2 valse overeenkomsten; gooi die weg.

Triple-DES (3DES) gebruikt drie sleutels K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM blijft van toepassing, maar minder sterk: two-key 3DES (K3=K1) vereist 2^{112} bewerkingen. Voor three-key 3DES bestaat er een MITM-aanval van 2^{112}, wat verklaart waarom 3DES ondanks een sleutel van 168 bits slechts ongeveer 112 bits effectieve beveiliging biedt.

Hellman (1980): bereken vooraf een tabel met ketens van (startpunt, eindpunt) om offline zoeken naar sleutels te versnellen. Gegeven een doelhash of cijfertekst zoek je in de Hellman-tabel naar een keten die deze bevat. Afweging: P = N (tijd × geheugen = constante ruimte). Dit vormt de basis voor regenboogtabellen.

Regenboogtabellen (Oechslin, 2003) verbeteren Hellman-tabellen door op elke positie in een keten verschillende reductiefuncties te gebruiken, waardoor valse alarmen (samengevoegde ketens) worden geëlimineerd. Ze zijn efficiënt voor het kraken van wachtwoordhashes zonder salt. Een opzoeking duurt O(table_size/chain_length) tijd.

Een salt is een willekeurige waarde die vóór het wachtwoord wordt geplaatst voordat het wordt gehasht: H(salt||password). Verschillende salts leveren verschillende hashes op voor hetzelfde wachtwoord — een regenboogtabel voor "password" is nutteloos als een andere salt is gebruikt. Salts moeten naast de hash worden opgeslagen.

MITM-aanvallen op AES-128 (10 rondes): bekende aanvallen splitsen bij ronde 5 — versleutel 5 rondes vooruit, ontsleutel 5 rondes achteruit en kom in het midden samen. De beste bekende aanval is de biclique-aanval, die 2^{128} verlaagt naar 2^{126.1} — niet praktisch, maar wel een aanwijzing dat AES geen veiligheidsmarge heeft tegen MITM-achtige benaderingen.

Voor Merkle-Damgard-hashes kan MITM in sommige constructies pre-images sneller vinden dan brute force. Aanval: bouw een tabel op vanuit berichtblokken die beginnen bij IV; zoek vanaf de doelhash achteruit. Tegen SHA-256 met volledige rondes is dit nog steeds ongeveer 2^{255} — geen verbetering ten opzichte van brute force.

Een ontledingsaanval veralgemeent MITM naar splitsingen in r delen. Bij een driedelige splitsing van een versleutelingsalgoritme versleutel je het eerste derde van de rondes vooruit, kom je in het midden van de keten samen en ontsleutel je het laatste derde achteruit. Dit vereist O(2^{n*2/3}) tijd en O(2^{n/3}) geheugen — een evenwichtigere afweging.

In protocollen kun je MITM-aanvallen voorkomen door lange, door een KDF afgeleide sleutels uit wachtwoorden met hoge entropie te gebruiken (dit verkleint de sleutelruimte die kan worden opgesomd), hardwaretokens (FIDO2) te gebruiken waarbij de sleutel het apparaat nooit verlaat, of authenticatie met openbare sleutels te gebruiken (er is dan geen gedeeld geheim om op te sommen).

MITM-aanvallen splitsen versleutelingsalgoritmen in helften en verlagen de tijd van 2^{2n} naar 2^n met 2^n geheugen. Ze breken Double-DES; 3DES beperkt de impact, maar heeft een effectieve beveiliging van 112 bits. Regenboogtabellen gebruiken MITM-logica voor het kraken van wachtwoorden en worden tegengegaan door salts. Volgende onderwerp: timingaanvallen en zijkanaalaanvallen.