Nsryjdtyk

L'attacco meet-in-the-middle (da non confondere con man in the middle) è un attacco crittografico che, come l'attacco del compleanno, fa uso di un compromesso costo-prestazioni. Mentre l'attacco del compleanno tenta di trovare due valori nel dominio di una funzione che si mappino sullo stesso valore nel suo codominio, l'attacco 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 dell'immagine inversa dell'altra attraverso la seconda funzione - trovandosi letteralmente nel mezzo della funzione composta.

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 l'idea 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 22n{displaystyle 2^{2n}} tentativi se ogni chiave fosse lunga n bit, confrontata con i 2n{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. L'attacco lavora crittando da un lato e decrittando dall'altro lato, incontrandosi così appunto nel mezzo.

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

C=EK2(EK1(P)){displaystyle C=E_{K_{2}}(E_{K_{1}}(P))},

dove E è la funzione di cifratura e K₁ e K₂ sono le due chiavi.

L'attaccante 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, l'insieme 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 2n+1{displaystyle 2^{n+1}} cifrature (e dimensione O(2n){displaystyle O(2^{n})}), a confronto con un attacco semplice, che necessita di 22n{displaystyle 2^{2n}} cifrature (ma solo di dimensione O(1){displaystyle O(1)}).

Bibliografia |

• W. Diffie, M. Hellman, Exhaustive Cryptanalysis of the NBS Data Encryption Standard, in Computer, vol. 10, nº 6, giugno 1977, pp. 74–84, DOI:10.1109/C-M.1977.217750.


• 
  Bruce Schneier, "Applied Cryptography", Seconda Edizione, John Wiley & Sons, 1996, ISBN 0-471-11709-9
  

Voci correlate |

• Crittografia


• 3DES

Portale Crittografia

Portale Sicurezza informatica