Atac Meet-in-the-middle
L'atac per trobada a mig camí, també conegut pel seu terme anglés meet-in-the-middle o per les seues sigles en anglés MITM, consistix en aprofitar el disseny d'un sistema G modelant-ho com una seqüència de dos processos A i B, en el que l'eixida de serà l'entrada de B. L'objectiu de l'atac consistix en, donats els valors preestablits d'entrada i eixida I i S del sistema global G, trobar la definició dels processos A i B de tal forma que hi haja un I tal que, en eixecutar A en l'entrada I, s'obtinga I, i en eixecutar B en l'entrada I, s'obtinga S.
Expressat en llenguage formal: Es tracta de trobar un valor en el ranc del domini de composició de dos funcions, de tal manera que l'image de la primera funció done lo mateix que l'image inversa de la segona funció. Per tant per a poder aplicar este atac és necessari conéixer l'inversa del procés B.
La forma en la que funciona l'atac és el següent: S'ataquen de forma independent abdós funcions, A i B, per força bruta sobre l'espai de claus obtenint per un costat el conjunt de possibles valors d'I que pot produir com a valor entrada I (provant totes les claus) i per l'atre costat s'obté el conjunt de possibles valors I que poden produir com a valor d'eixida S (provant totes les claus). Si entre estos dos conjunts de possible valors d'I, trobem un valor que està en abdós, llavors provablement hajam trobat les claus correctes. Per a verificar que les claus són les correctes caldria provar en atres valors d'I i S i comprovar que els resultats coincidixen.
Observar que l'atac meet-in-the-middle és un clar eixemple d'algoritme que reduïx el temps d'eixecució a costa de tindre més necessitats de memòria (cal almagasenar els valors resultat de provar en tots les possibles claus del procés A). És una situació de compromís espai-temps.
Ideat en 1977 per Whitfield Diffie i Martin Hellman aplicat per a reduir la seguritat de cifradores simètrics per blocs obtinguts a partir de 2 cifradores simètrics en bloc iguals posats un a continuació un de l'atre, lo que se sol implementar per mig de 2 rondes de sifrat. És dir, els cridats doble sifrat (en anglés double encryption). Posteriorment este esquema s'ha aplicat per a atacar la seguritat d'atres tipos de sistemes com les funcions hash criptogràfiques cridades 'còdics de detecció de modificacions'.
Eixemples d'àrees d'aplicació
Dos àrees de la criptografia en les que més s'ha aplicat l'atac meet-in-the-middle han segut són el sifrat simètric per bloc múltiple i la funcions hash criptogràfiques cridades còdics de detecció de manipulacions.
Sifrat simètric per blocs múltiple
[1] Supongam un cifrador simètric per blocs implementat per doble sifrat d'un cifrador per blocs, A, que la seua clau kes de la forma , en n la llongitut de la clau del cifrador (i. i. k tindrà llongitut 2n), i pot ser modelizado pel següent esquema:
Si fem directament un atac per força bruta provant en totes les possibles combinacions de la clau fins a donar en aquelles que a partir de x produïx i, tenim que provar com a màxim 22n possibilitats (les possible claus).
Observar que en un sistema de sifrat simètric per blocs invertir la funció consistix en dessifrar i per a dessifrar s'usa la mateixa clau que per a sifrar. Per tant conegut l'algoritme de sifrat és immediat conéixer l'algoritme de dessifrat.
Si fem un atac meet-in-the-middle podem realisar menys comprovacions. Si primer ataquem per força bruta el sifrat de l'esquerra, tenim que comprovar 2n claus. Este conjunt de valors cal guardar-los en una taula. Si ara operem en el sifrat de la dreta realisem atres 2n i segons anem obtenint els valors comprovem si cada valor està en la taula prèvia almagasenat. Els valors que estan en abdós conjunts corresponen en possibles claus correctes del sistema (caldrà tornar a verificar com és la correcta en un test posterior en nous valors d'entrada i eixida). Per tant podem obtindre la clau del sistema fent 2n+ 2n= 2n+1 operacions en lloc de les 22n si operaramos directament. Per tant es millora molt la complexitat computacional. Observar que estem ignorant les múltiples comprovacions i busques que cal fer sobre si un valor obtingut en la segona fase està entre els valors almagasenats en la primera fase. No obstant, el cost adicional de computació i l'increment en les necessitats d'almagasenament (la taula en els primers 2n valors obtinguts) és compensat en molt per la reducció en la complexitat computacional del procediment d'atac.
cal preguntar-se, ¿Quina provabilitat hi ha de que valors que coincidixen en el punt mig no siguen solucions que realment es corresponen en la solució correcta? i per tant ¿Una volta trobada una solució és 'molt' necessari trobar totes les restants?. És dir, cal medir els falsos positius produïts per claus falses. Per a això podem recolzar-nos en la següent Teorema:[2]
- Siga un sifrat simètric per blocs en una llongitut de clau de k bits, un tamany de bloc de n bits i en t pares de valors (text pla, text sifrat). En este cas el número esperat de claus falses en les quals el text pla es correspon en un text sifrat dau és .
Aplicant esta teorema a un doble sifrat en DES obtenim que el número claus falses és . Este valor és molt chicotet i per tant és factible l'us d'atacs meet-in-the-middle. Si en lloc de doble sifrat usem triple sifrat la provabilitat es reduïx encara més.
Per l'us d'este tipo d'atacs no es deuria usar doble sifrats. Este tipo d'atac es pot reduir en gran mida fent triple sifrat en lloc de doble sifrat. Per esta raó és per eixemple molt més comuna l'algoritme de sifrat triple DES que el doble DES.
Còdic de detecció de manipulacions
En l'àmbit dels còdics de detecció de manipulacions els atacs meet in the middle se solen usar per a realisar atacs preimagen, és dir, l'objectiu de l'atac és trobar un valor (preimagen) l'image del qual colisione en el valor hash dau.
[3][4][5] En este tipo d'atacs, lo que es fa és partir l'algoritme en dos parts. Per un costat es tenen els passos que van cap a avant fins a aplegar a un punt intermig. En eixe punt s'obté un conjunt de resultats intermijos. Per un atre costat es computen una série de passos cap a arrere fins a aplegar al mateix punt intermig i ahí s'obtenen un atre conjunt de resultats intermijos. Els dos conjunts de resultats tenen que ser independents uns d'uns atres. Estos dos conjunts es comparen per a aixina obtindre els que coincidixen i que seran els que es posen d'acort en la solució concreta.
Vore també
Referències
- ↑ Christof Paar, Jan Pelzl,"Understanding cryptography,A Textbook for Students and Practitioners". Springer 2010
- ↑ Christof Paar, Jan Pelzl, "Understanding cryptography". Springer 1998.
- ↑ Bart Preneel,"Cryptographic Primitives for Information Authentication-State fo the Art", Katholieke Universiteit Leuven. Heverlee, Belgium
- ↑ Kazumaro Aoki, Yu Sasaki,"Meet-in-the-middle preimage Attacks Against Reduced SHA-0 and SHA-1" In Proceedings of the 29th Annual International Cryptology Conference on Advances in Cryptology, 2009, pp. 70-89
- ↑ JINMIN ZHONG AND XUEJIA LAI,"Preimage Attack on Reduced DHA-256",JOURNAL OF INFORMATION SCIENCE AND ENGINEERING 27
Referències
- Este artícul conté una traducció derivada de «Ataque Meet-in-the-middle» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.