Meet-in-the-middle och avvägningar mellan tid och minne

MITM-attacker delar upp en krypteringsalgoritm i två halvor och angriper dem oberoende av varandra. Angriparen bygger en tabell från ena änden och söker sedan från den andra änden efter en matchning. Detta minskar attackens komplexitet från O(2^{2n}) till O(2^n), på bekostnad av O(2^n) minne.

Double-DES tillämpar DES två gånger: C = DES_{K2}(DES_{K1}(P)). Nyckelutrymme: 2^{112}. MITM-attack: för alla 2^{56} K1-värden beräknas DES_{K1}(P) och lagras. För alla 2^{56} K2-värden beräknas DES_{K2}^{-1}(C), som sedan slås upp i tabellen. Matchning → kandidat (K1, K2). Totalt krävs endast 2^{57} arbete.

Steg 1: kryptera klartexten P med alla möjliga K1 → tabell T[DES_{K1}(P)] = K1. Steg 2: dekryptera chiffertexten C för varje K2: v = DES^{-1}_{K2}(C). Kontrollera om v ∈ T. Om T[v] = K1 finns, verifiera (K1, K2) mot ett andra klartext–chiffertext-par. Räkna med 1–2 falska matchningar och förkasta dem.

Triple-DES (3DES) använder tre nycklar K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). MITM gäller fortfarande, men i mindre utsträckning: tvånyckel-3DES (K3=K1) minskar till 2^{112} arbete. För tre nycklar finns en MITM-attack på 2^{112}, vilket förklarar varför 3DES bara ger ungefär 112 bitars effektiv säkerhet trots en nyckel på 168 bitar.

Hellman (1980): förberäkna en tabell med kedjor av (start_point, end_point) för att snabba upp offline-sökning efter nycklar. Givet en målhash eller chiffertext söker man i Hellman-tabellen efter en kedja som innehåller den. Avvägning: P = N (tid × minne = konstant utrymme). Detta utgör grunden för regnbågstabeller.

Regnbågstabeller (Oechslin, 2003) förbättrar Hellman-tabeller genom att använda olika reduktionsfunktioner vid varje position i kedjan, vilket eliminerar falsklarm (sammanslagna kedjor). De är effektiva för att knäcka osaltade lösenordshashar. En uppslagning tar O(table_size/chain_length) tid.

Ett salt är ett slumpmässigt värde som läggs framför lösenordet före hashning: H(salt||password). Olika salter ger olika hashvärden för samma lösenord – en regnbågstabell för "password" är värdelös om ett annat salt användes. Salter måste lagras tillsammans med hashen.

MITM-attacker mot AES-128 (10 ronder): kända attacker delar vid rond 5 – krypterar framåt genom 5 ronder, dekrypterar bakåt genom 5 ronder och möts i mitten. Den bästa kända attacken minskar 2^{128} till 2^{126.1} med en biclique-attack – inte praktiskt genomförbar, men den visar att AES saknar säkerhetsmarginal mot MITM-liknande metoder.

För Merkle-Damgard-hashfunktioner kan MITM hitta förbilder snabbare än brute force i vissa konstruktioner. Attacken bygger en tabell från meddelandeblock som börjar vid IV och söker bakåt från målhashen. Mot SHA-256 med fullständigt antal ronder krävs fortfarande ungefär 2^{255} arbete – ingen förbättring jämfört med brute force.

Dissektionsattacken generaliserar MITM till uppdelningar i r delar. Vid en uppdelning i tre delar av en krypteringsalgoritm krypteras den första tredjedelen framåt, man möts i mitten av kedjan och dekrypterar sedan den sista tredjedelen bakåt. Den kräver O(2^{n*2/3}) tid och O(2^{n/3}) minne – en mer balanserad avvägning.

I protokoll kan MITM-attacker förhindras genom att använda långa KDF-härledda nycklar från lösenord med hög entropi (vilket minskar det nyckelutrymme som kan genomsökas), använda hårdvarutoken (FIDO2) där nyckeln aldrig lämnar enheten eller använda autentisering med publika nycklar (ingen delad hemlighet att genomsöka).

MITM-attacker delar upp krypteringsalgoritmer i halvor och minskar tidsåtgången från 2^{2n} till 2^n med 2^n minne. De knäcker Double-DES; 3DES är motståndskraftigt i viss mån men har 112 bitars effektiv säkerhet. Regnbågstabeller använder MITM-logik för att knäcka lösenord och besegras genom saltning. Nästa avsnitt: tidsattacker och sidokanalsattacker.