Meet-in-the-Middle e compromessi tempo-memoria

Gli attacchi MITM dividono un cifrario in due metà e le attaccano indipendentemente. L'attaccante costruisce una tabella partendo da un'estremità, quindi cerca una corrispondenza partendo dall'altra. La complessità dell'attacco si riduce da O(2^{2n}) a O(2^n), al costo di O(2^n) di memoria.

Double-DES applica DES due volte: C = DES_{K2}(DES_{K1}(P)). Spazio delle chiavi: 2^{112}. Attacco MITM: per tutti i 2^{56} valori di K1, calcolare DES_{K1}(P) e memorizzarlo. Per tutti i 2^{56} valori di K2, calcolare DES_{K2}^{-1}(C) e cercarlo nella tabella. Corrispondenza → candidato (K1, K2). Solo 2^{57} operazioni complessive.

Passaggio 1: cifrare il testo in chiaro P con tutti i possibili K1 → tabella T[DES_{K1}(P)] = K1. Passaggio 2: per ogni K2, decifrare il testo cifrato C: v = DES^{-1}_{K2}(C). Verificare se v ∈ T. Se esiste T[v] = K1, verificare (K1, K2) su una seconda coppia testo in chiaro-testo cifrato. Sono attese 1-2 corrispondenze false; scartarle.

Triple-DES (3DES) usa tre chiavi K1,K2,K3: C = DES_{K3}(DES^{-1}_{K2}(DES_{K1}(P))). Il MITM è ancora applicabile, ma in modo meno efficace: 3DES a due chiavi (K3=K1) si riduce a 2^{112} operazioni. Per 3DES a tre chiavi esiste un attacco MITM da 2^{112}, il che spiega perché 3DES fornisca soltanto circa 112 bit di sicurezza effettiva nonostante una chiave da 168 bit.

Hellman (1980): precalcolare una tabella di catene (punto_iniziale, punto_finale) per velocizzare la ricerca offline delle chiavi. Dato un hash o testo cifrato obiettivo, cercare nella tabella di Hellman una catena che lo contenga. Compromesso: P = N (tempo × memoria = costante dello spazio). È la base delle tabelle rainbow.

Le tabelle rainbow (Oechslin, 2003) migliorano le tabelle di Hellman usando funzioni di riduzione diverse a ogni posizione della catena, eliminando i falsi allarmi (catene unite). Sono efficienti per violare gli hash delle password senza salt. Una ricerca richiede O(table_size/chain_length) di tempo.

Un salt è un valore casuale anteposto alla password prima dell'hashing: H(salt||password). Salt diversi producono hash diversi per la stessa password: una tabella rainbow per "password" è inutile se è stato usato un salt diverso. I salt devono essere memorizzati insieme all'hash.

Gli attacchi MITM su AES-128 (10 round): gli attacchi noti dividono il cifrario al round 5: si cifrano in avanti 5 round, si decifrano all'indietro 5 round e ci si incontra al centro. Il migliore attacco noto, basato su bicliques, riduce 2^{128} a 2^{126.1}: non è pratico, ma mostra che AES non ha margine di sicurezza contro approcci di tipo MITM.

Per le funzioni hash Merkle-Damgård, il MITM può trovare preimmagini più velocemente della forza bruta in alcune costruzioni. Attacco: costruire una tabella dai blocchi del messaggio partendo dall'IV; cercare all'indietro dall'hash obiettivo. Contro SHA-256 con tutti i round: si arriva comunque a circa 2^{255}, senza miglioramenti rispetto alla forza bruta.

L'attacco di dissezione generalizza il MITM a divisioni in r parti. Per una divisione in 3 parti di un cifrario: cifrare in avanti 1/3 dei round, incontrarsi al centro della catena, quindi decifrare all'indietro 1/3. Richiede O(2^{n*2/3}) di tempo e O(2^{n/3}) di memoria, con un compromesso più equilibrato.

Nei protocolli, gli attacchi MITM possono essere prevenuti usando: chiavi lunghe derivate con un KDF da password ad alta entropia (riduce lo spazio delle chiavi enumerabile), token hardware (FIDO2) in cui la chiave non lascia mai il dispositivo, oppure l'autenticazione a chiave pubblica (non c'è alcun segreto condiviso da enumerare).

Qual è la sicurezza effettiva di Double-DES (2x DES, chiave combinata da 112 bit) contro un attacco MITM?

Gli attacchi MITM dividono i cifrari in metà, riducendo il tempo da 2^{2n} a 2^n con 2^n di memoria. Spezzano Double-DES; 3DES li mitiga, ma offre una sicurezza effettiva di 112 bit. Le tabelle rainbow usano la logica MITM per violare le password e vengono sconfitte dall'uso del salt. Prossimo argomento: gli attacchi temporali e gli attacchi side-channel.