Indietro

ⓘ Attacco meet-in-the-middle




                                     

ⓘ Attacco meet-in-the-middle

L attacco meet-in-the-middle è un attacco crittografico che, come lattacco del compleanno, fa uso di un compromesso costo-prestazioni. Mentre lattacco del compleanno tenta di trovare due valori nel dominio di una funzione che si mappino sullo stesso valore nel suo codominio, lattacco meet-in-the-middle tenta di trovare un valore in ognuno degli intervalli e domini della composizione di due funzioni tali che la mappatura di uno attraverso la prima funzione sia la stessa dellimmagine inversa dellaltra attraverso la seconda funzione - trovandosi letteralmente nel mezzo della funzione composta.

                                     

1. Descrizione

Esso è stato sviluppato dapprima come attacco ad una tentata espansione della cifratura a blocchi di Diffie ed Hellman nel 1977. Tentando di migliorare la sicurezza della cifratura a blocchi, si può avere lidea di usare semplicemente due chiavi crittografiche indipendenti per cifrare i dati due volte. Ingenuamente si può pensare che ciò eleverebbe al quadrato la sicurezza dello schema a doppia cifratura. Certamente, una ricerca esaustiva di tutte le possibili combinazioni delle chiavi comporterebbe 2 n {\displaystyle 2^{2n}} tentativi se ogni chiave fosse lunga n bit, confrontata con i 2 n {\displaystyle 2^{n}} tentativi richiesti per la singola chiave.

Diffie ed Hellman, comunque, individuarono un compromesso tempo-memoria che potesse penetrare lo schema in un tempo solo doppio di quello necessario a penetrare lo schema a singola cifratura. Lattacco lavora crittando da un lato e decrittando dallaltro lato, incontrandosi così appunto nel mezzo.

Assumendo che lattaccante conosca una serie di testi in chiaro P e testi cifrati C, abbiamo:

C = E K 2 E K 1 P) {\displaystyle C=E_{K_{2}}E_{K_{1}}P)},

dove E è la funzione di cifratura e K 1 e K 2 sono le due chiavi.

Lattaccante può dunque calcolare E K P per tutte le possibili chiavi K e memorizzare i risultati in memoria. In un secondo tempo può decifrare i testi cifrati calcolando D K C per ogni chiave K. Qualsiasi corrispondenza tra questi due insiemi di risultati possono verosimilmente rivelare le chiavi corrette per accelerare la comparazione, linsieme E K P è memorizzato come tabella così che ogni elemento di D K C può essere confrontato con i valori nella suddetta tabella per trovare le chiavi candidate).

Non appena le corrispondenze sono trovate, possono essere verificate con un secondo insieme di test di testi in chiaro e testi cifrati. Se la dimensione della chiave è n, questo attacco usa solo 2 n + 1 {\displaystyle 2^{n+1}} cifrature e dimensione O 2 n {\displaystyle O2^{n}}), a confronto con un attacco semplice, che necessita di 2 n {\displaystyle 2^{2n}} cifrature ma solo di dimensione O 1 {\displaystyle O1}).