Atac Meet-in-the-middle

L'atac per trobada a mig camí o meet-in-the-middle és un atac similar a l'atac d'aniversari, que utilitza un compromís entre temps i espai.

Mentre que l'atac d'aniversari tracta de trobar dos valors del domini d'una funció que tenen com a imatge el mateix resultat, aquest atac tracta de trobar un valor en el rang del domini de composició de dues funcions, de tal manera que la imatge de la primera funció és igual que la imatge inversa de la segona funció - d'aquí el nom de l'atac-.

Va ser desenvolupat el 1977 per Whitfield Diffie i Martin Hellman, en un intent d'expandir un bloc xifrat. En la recerca d'una millor seguretat del xifrat d'un bloc, es podria intentar la idea d'utilitzar simplement dues claus criptogràfiques per a xifrar dues vegades les dades. A priori, es podria pensar que això hauria elevar al quadrat la seguretat de l'esquema de doble xifrat.

Certament, una recerca exhaustiva de totes les claus possibles requeriria $2^{2n}$ intents, si cada clau fora de n bits, comparat amb els $2^{n}$ intents requerits per a una clau única.

No obstant això, Diffie i Hellman van trobar un compromís entre temps i memòria que podria trencar el xifrat en només el doble de temps.^[1]L'atac es basa en el xifrat per un extrem i el desxifrat per l'altre, buscant una trobada a mig camí.

Suposem que l'atacant coneix el text P i el seu xifrat C, és a dir: $C=E_{K_{2}}(E_{K_{1}}(P))$ , on K ₁ i K ₂ són les dues claus.

L'atacant, aleshores, pot calcular E _K ( P ) per a totes les claus possibles K i guardar els resultats en memòria. Després, pot calcular D _K ( C ) per a cada clau K i comparar-la amb la taula en memòria. Si arriba a una coincidència, és plausible que l'atacant hagi descobert dues claus, i pot comprovar-ho un segon parell de text original i text xifrat.

Si la longitud de clau és n , aquest atac només necessita $2^{n+1}$ xifrats (i un espai de l'ordre de $O(2^{n})$ claus), comparat amb l'atac de força bruta, el qual necessita un espai de $O(1)$ claus a costa d'executar $2^{2n}$ xifrats.

Vegeu també

Atac d'aniversari
Atac Man-in-the-middle - un atac amb un nom similar però en un context diferent.
Triple DES

Bibliografia

W. Diffie and M. E. Hellman «Exhaustive Cryptanalysis of the NBS Data Encryption Standard». Computer, 10, 6-1977, pàg. 74-84.

[1]