Ataque de texto sin formato elegido

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de diciembre de 2017; las comprobaciones requieren 7 ediciones .

El ataque de texto sin formato elegido ( CPA ) es uno de los principales métodos de ataque criptoanalítico . El criptoanalista tiene una cierta cantidad de textos sin formato y los correspondientes textos cifrados , además, tiene la capacidad de cifrar varios textos sin formato preseleccionados [1] .

Descripción

Un criptoanalista , según el principio de Kerckhoff , tiene toda la información sobre el sistema de encriptación utilizado, excepto un determinado conjunto de parámetros llamado clave . La tarea del criptoanalista es encontrar la clave o crear un algoritmo que permita descifrar cualquier mensaje cifrado con esta clave.

Dado: $P_{1},C_{1}=E_{k}(P_{1}),\,P_{2},C_{2}=E_{k}(P_{2}),\,. ..\,P_{i},C_{i}=E_{k}(P_{i}),$

donde el texto claro elegido por el criptoanalista, el texto cifrado, la función de cifrado, la clave. $P-$ ${\ estilo de visualización C-}$ ${\ estilo de visualización E-}$ ${\ Displaystyle k-}$

Obtener: Cualquiera , o algoritmo cómo llegar desde [1] ${\ estilo de visualización k}$ $P_{i+1}$ $C_{i+1}=E_{k}(P_{i+1}).$

La capacidad de realizar un ataque de texto sin formato elegido es bastante común. Por ejemplo, un atacante podría sobornar a alguien para cifrar un mensaje seleccionado. También es posible la siguiente situación: el atacante envía un mensaje al embajador de un determinado país, y este lo envía a su tierra natal en forma encriptada [2] .

El ataque de texto sin formato elegido se refiere a ataques activos en criptosistemas. Dichos ataques violan la integridad y confidencialidad de la información transmitida [3] .

La figura 1 muestra un diagrama de un ataque basado en el texto sin formato elegido. El atacante (A) recibe el texto cifrado del usuario (C). La tarea del atacante es "adivinar" el texto sin formato . Dado que el atacante tiene acceso al bloque de cifrado , tiene la capacidad de cifrar sus mensajes y analizar los textos cifrados recibidos. . Como resultado, el atacante recoge el mensaje y lo reenvía al usuario. ${\ Displaystyle C = E (P, K)}$ $P^{'}=P$ $mi$ ${\ Displaystyle P_ {i}}$ $C_{i}=E(P_{i},K)$ ${\ Displaystyle P^{'))$

Tipos de ataques

Hay dos tipos de ataques basados en el texto sin formato elegido:

autónomo ( ing. ataque de texto sin formato elegido por lotes ): un criptoanalista prepara un conjunto de textos sin formato por adelantado, antes de recibir los textos cifrados.
Ataque de texto sin formato elegido operativo o adaptativo ( CPA2 ) : el criptoanalista selecciona los siguientes textos sin formato en función de los textos cifrados ya recibidos. Dado que la selección de los bloques subsiguientes que se enviarán para el cifrado tiene en cuenta los resultados anteriores, se produce una retroalimentación, lo que otorga a un ataque basado en texto sin formato elegido de forma adaptativa una ventaja sobre otros tipos de ataques. La implementación de este tipo de ataque es posible, por ejemplo, si el criptoanalista tiene acceso al dispositivo de cifrado durante un tiempo suficientemente largo para analizar los resultados [4] .

Comparación con otros tipos de ataques

Según Bruce Schneier , existen 4 formas principales de ataque criptoanalítico [1] :

Ataque de texto cifrado
Ataque de texto sin formato conocido
Ataque de texto sin formato elegido
Ataque de texto sin formato adaptativo

En el caso de un ataque basado en texto cifrado, el criptoanalista solo tiene acceso al texto cifrado. Este es el tipo de ataque más difícil debido a la poca información disponible.

En un ataque de texto sin formato conocido, el criptoanalista conoce tanto el texto sin formato como el texto cifrado. Este tipo de ataque es más efectivo que un ataque basado en texto cifrado debido a la mayor cantidad de información conocida sobre el criptosistema.

Un ataque de texto sin formato elegido es un tipo de ataque más potente que un ataque de texto sin formato conocido. La capacidad de preseleccionar textos sin formato brinda más opciones para extraer la clave del sistema. También es cierto que si un criptosistema es vulnerable a un ataque de texto sin formato conocido, también es vulnerable a un ataque de texto sin formato elegido [5] .

En la historia

El ataque de texto sin formato emparejado se utilizó durante la Segunda Guerra Mundial .

En 1942, los criptoanalistas de la Marina de los EE. UU. interceptaron una orden encriptada del comando japonés. Habiendo descifrado parte del mensaje, los criptoanalistas estadounidenses se enteraron del inminente ataque al misterioso "AF", pero no pudieron averiguar el lugar del ataque. Asumiendo que Midway Island era el objetivo más probable para los japoneses , los estadounidenses intentaron un truco. Redactaron un informe de que la isla carecía de agua dulce y la enviaron por un canal sin protección. Unos días después, los oficiales de inteligencia estadounidenses interceptaron un texto cifrado japonés que informaba que había poca agua dulce en el AF. Por lo tanto, el comando estadounidense sabía de antemano sobre el próximo ataque al atolón de Midway [6] .

Los criptoanalistas británicos de Bletchley Park utilizaron con éxito un ataque de texto sin formato elegido para descifrar la correspondencia alemana. Los británicos provocaron al enemigo a usar ciertas palabras y nombres en los mensajes de texto. Por ejemplo, si los alemanes limpiaron recientemente una sección de las aguas costeras de minas, los servicios de inteligencia británicos podrían anunciar que el área fue nuevamente minada. Esto provocó una corriente de mensajes encriptados del comando alemán, que incluían la palabra "minas" y el nombre del territorio. Por lo tanto, los británicos pudieron captar texto sin formato y analizar textos cifrados con bastante eficacia para descifrar los cifrados alemanes. Este ataque se puede calificar como un ataque de texto sin formato elegido de forma adaptativa , ya que los criptoanalistas británicos podrían elegir el siguiente texto sin formato para cifrar en función de los resultados ya obtenidos [7] .

Ejemplos de ataques

Criptosistemas de clave privada

Ataque al cifrado afín

Considere un ejemplo simple de un ataque a un cifrado afín usando caracteres latinos de la A a la Z.

A	B	C	D	mi	F	GRAMO	H	yo	j	k	L	METRO	norte	O	PAGS	q	R	S	T	tu	V	W	X	Y	Z
0	una	2	3	cuatro	5	6	7	ocho	9	diez	once	12	13	catorce	quince	dieciséis	17	Dieciocho	19	veinte	21	22	23	24	25

Función de cifrado: $y=mx+n\ mod\ 26.$

El criptoanalista realiza un ataque basado en el texto sin formato elegido. El texto sin formato elegido es "HAHAHA", el texto cifrado correspondiente es "NONONO". El objetivo del criptoanalista es encontrar la forma explícita de la función de cifrado, es decir, calcular los coeficientes y . $metro$ $norte$

Usando el par resultante de texto simple-texto cifrado, compondremos un sistema de ecuaciones:

${\begin{casos}m\cdot 7+n\equiv 13\ mod\ 26\\m\cdot 0+n\equiv 14\ mod\ 26\end{casos))$

Resolviendo el sistema, encontramos: ${\ estilo de visualización n = 14, \ m = 11.}$

Función de cifrado: [8] $y=11x+14\ mod\ 26.$

Criptoanálisis diferencial

El ataque de texto sin formato elegido se utiliza en un método de criptoanálisis diferencial propuesto por los criptoanalistas israelíes Eli Biham y Adi Shamir en 1990 para romper el criptosistema DES . El método se basa en el estudio de textos cifrados, cuyos textos sin formato tienen ciertas diferencias. Al analizar la evolución de las diferencias del texto cifrado durante las rondas DES, se determina una lista de claves posibles y se asigna una probabilidad a cada clave posible. En el proceso de análisis de los siguientes pares de textos cifrados, una de las claves se convertirá en la más probable [9] . Posteriormente, el método de criptoanálisis diferencial se extendió a criptosistemas como FEAL , Khafre , Lucifer , LOKI y otros [10] [11] .

Sea , textos sin formato coincidentes, , textos cifrados correspondientes. La diferencia entre textos sin formato y textos cifrados está determinada por la operación XOR : para describir posibles cambios en el valor durante el paso de las etapas DES, se introduce el concepto de una característica redonda , compuesta por diferencias en texto sin formato , texto cifrado y un conjunto de diferencias redondas (diferencias en los textos cifrados después de cada ronda intermedia) . A cada característica se le asigna la probabilidad de que un par aleatorio de textos sin formato con una diferencia produzca diferencias de ronda y diferencias de texto cifrado correspondientes a la característica después de pasar por la ronda de cifrado correspondiente. Un par de textos sin formato cuyo paso a través de una ronda DES está exactamente descrito por la característica se denomina "par correcto" ; de lo contrario, se denomina "par incorrecto". [9] $PAGS$ $P^{'}-$ $C$ $C^{'}-$ $\Delta P=P\oplus P^{'},\Delta C=C\oplus C^{'}.$ $\Delta C$ $\Delta P$ $\Delta C$ $C_{\lambda }=(\lambda _{1},\lambda _{2}...\lambda _{n})$ $\Delta P$

Para determinar la clave, se realiza un ataque basado en el texto sin formato elegido. En la etapa de recopilación de datos, el criptoanalista envía para el cifrado una gran cantidad de pares de textos sin formato con ciertas diferencias correspondientes a la característica con probabilidad (es decir, entre todos los pares de textos sin formato hay pares correctos). Luego, en la etapa de análisis de datos , se determina un conjunto de posibles claves redondas, para cada posible clave se calculan las diferencias de los textos cifrados correspondientes. Durante la última ronda de cifrado, se produce una enumeración completa de posibles claves. Para claves de ronda incorrectas, la probabilidad de una diferencia en los textos cifrados correspondientes a la característica será muy pequeña, para una clave de ronda correcta, la probabilidad será del orden de magnitud o superior. De esta manera puede determinar la clave de sistema correcta [9] [12] . $pags$ $pags$ $pags$

Cabe señalar que el método de criptoanálisis diferencial es poco práctico debido a los altos requisitos de tiempo y volumen de datos. Por ejemplo, descifrar un DES de 16 rondas requiere operaciones y textos sin formato coincidentes [9] . $2^{47}$ $2^{55}$

Criptoanálisis lineal

En 1993, el criptoanalista japonés Mitsuru Matsui propuso un método de criptoanálisis lineal para romper cifrados de bloque como DES. El método se basa en la construcción de relaciones lineales entre texto plano, texto cifrado y clave : $P_{i_{1}}\oplus P_{i_{2}}\oplus \dots \oplus P_{i_{a}}\oplus C_{j_{1}}\oplus C_{j_{2}} \oplus \puntos \oplus C_{j_{b}}=K_{k_{1}}\oplus K_{k_{2}}\oplus \puntos \oplus K_{k_{c}}$

donde están los enésimos bits del texto, el texto cifrado y la clave, respectivamente. Tales relaciones se llaman aproximaciones lineales. $P_{n},C_{n},K_{n}$

La esencia del método es calcular la probabilidad de ocurrencia de aproximaciones lineales. Si la probabilidad es diferente de , entonces es posible extraer información sobre la clave usando pares de texto simple-texto cifrado. Inicialmente, para cada ronda individual, se encuentra una aproximación lineal con la mayor probabilidad de sesgo. Luego, las aproximaciones redondas se combinan en una aproximación lineal general del criptosistema y, con la ayuda de pares de texto simple-texto cifrado, se hace una suposición sobre los valores de los bits clave [13] . $pags$ $1/2$

Inicialmente, el método de criptoanálisis lineal utilizaba un conocido ataque de texto sin formato. Por ejemplo, se necesitaron textos sin formato conocidos y 50 días para descifrar un DES de 16 rondas [13] . En 2000, Lars Knudsen propuso una variante de criptoanálisis lineal basada en textos sin formato elegidos: se necesitaban textos sin formato seleccionados para abrir 12 bits de la clave [14] . $2^{43}$ $2^{42}$

Criptosistemas de clave pública

El ataque de texto sin formato elegido se puede utilizar para romper criptosistemas asimétricos. En dichos sistemas, la clave pública está disponible para cualquier usuario, lo que le da al criptoanalista un control completo sobre el algoritmo de cifrado. Por lo tanto, siempre es posible organizar un ataque contra criptosistemas de clave pública basándose en el texto sin formato elegido [15] . Por ejemplo, si un atacante ha interceptado un texto cifrado , para descifrarlo basta con recoger otro mensaje y cifrarlo utilizando la clave pública . Si , se hace un intento más [16] . $C=E_{k}(P)$ ${\ Displaystyle P^{'))$ ${\ estilo de visualización C^{'}=E_{k}(P^{'})}$ $P\neq P^{'}$

Cifrado probabilístico

Por lo general, los criptosistemas asimétricos están diseñados para resistir ataques utilizando textos sin formato elegidos [15] . Por ejemplo, las defensas del criptosistema RSA contra ataques basados en el texto sin formato elegido se basan en la dificultad de calcular la raíz del texto cifrado mediante un módulo entero compuesto [17] . Otra forma de eliminar las fugas de información en los criptosistemas de clave pública es el cifrado probabilístico propuesto por Shafi Goldwasser y Silvio Micali . La idea principal del cifrado probabilístico es hacer coincidir varios textos cifrados seleccionados al azar con el mismo texto sin formato . Por lo tanto, si un criptoanalista trata de adivinar el texto sin formato P para descifrar , obtendrá un texto cifrado completamente diferente y no podrá verificar la exactitud de su suposición [18] . $mi$ $norte$ $PAGS$ $C_{1},C_{2},C_{3},\ldots$ $C=E_{k}(P)$ $C^{'}\neq C$

Ataque al criptosistema RSA

A pesar de la seguridad del criptosistema RSA contra los ataques de texto elegidos, hay una serie de vulnerabilidades que permiten a un criptoanalista descifrar el texto cifrado. Considere el siguiente algoritmo para atacar un sistema de firma electrónica basado en RSA propuesto por George David en 1982. El ataque se realiza bajo el supuesto de que el criptoanalista ha interceptado el texto cifrado . El objetivo del criptoanalista es obtener un mensaje abierto . Para llevar a cabo un ataque, un criptoanalista necesita poder firmar cualquier mensaje que elija [19] [20] . $C=M^{e}\mod\n$ $METRO$

En la primera etapa del ataque, el texto cifrado se descompone en factores (no necesariamente simples): . De ello se deduce que el mensaje también es representable como un producto de factores , y las igualdades son válidas: , y . $C$ ${\displaystyle C=C_{1}C_{2}...C_{t))$ $METRO$ $t$ ${\displaystyle M=M_{1}M_{2}...M_{t))$ $C=C_{1}C_{2}...C_{t}=(M_{1}M_{2}...M_{t})^{e}\ mod\ n=M_{1 }^{e}M_{2}^{e}...M_{t}^{e}\mod\n$ $M_{i}=C_{i}^{d}\mod\n$
El criptoanalista selecciona un mensaje abierto y lo envía para su firma. También pide firmar mensajes ,. La firma se realiza de la siguiente manera: , while . $X$ ${\ Displaystyle XC_ {1}}$ ${\ Displaystyle XC_ {2}}$ $...XC_{t}$ $S=X^{d}\mod\n$ $S_{i}=(XC)_{i}^{d}\mod\n,i=1...t$
Se calcula el elemento inverso . $S^{-1}=X^{-d}\mod\n$
Multiplicando la expresión resultante por es posible obtener : . ${\ Displaystyle S_ {yo}}$ $Mi}$ $S_{i}S^{-1}=(X)^{-d}(XC_{i})^{d}\ mod\ n=C_{i}^{d}\ mod\ n= Mi}$
Como resultado, se restaura el mensaje original: $M=M_{1}M_{2}...M_{t}\mod\n$

Este método no le permite abrir el criptosistema en el sentido tradicional, es decir, obtener una clave privada, pero el criptoanalista puede descifrar un mensaje específico. Por lo tanto, este ataque es más débil que el ataque de texto sin formato emparejado para criptosistemas simétricos, que le permite obtener toda la información sobre el criptosistema si tiene éxito [20] .

Notas

↑ 1 2 3 Schneier, 2003 , pág. veinte.
↑ Schneier, 2003 , pág. 21
↑ Gabidulina , pág. 25-28.
↑ Schneier, Ferguson, 2002 , pág. 48.
↑ Schneier, Ferguson, 2002 , pág. 47-49.
↑ Kahn, 2000 , pág. 106-109.
↑ Hinsley, 2001 .
↑ Stinson, 2006 , pág. 27-29.
↑ 1 2 3 4 Biham, Shamir (DES), 1990 .
↑ Biham, Shamir (FEAL), 1991 .
↑ Biham, Shamir (LOKI), 1991 .
↑ Schneier, 2003 , pág. 212-216.
↑ 12 Matsui , 1993 .
↑ Knudsen, 2000 .
↑ 1 2 Schneier, 2003 , pág. 342.
↑ Schneier, 2003 , pág. 404.
↑ Mao, 2005 , pág. 308.
↑ Schneier, 2003 , pág. 404-406.
↑ Davida, 1982 .
↑ 12 Denning , 1984 .

Literatura

B. Schneier. Criptografía aplicada. - Triunfo, 2003. - 816 p. - ISBN 5-89392-055-4 .
B. Schneier, N. Ferguson. Criptografía práctica. - Williams, 2002. - 424 págs. — ISBN 5-8459-0733-0 .
E. Gabidulin, A. Kshevetsky, A. Kolybelnikov, S. Vladimirov. Protección de Datos. Tutorial.
D. Khan. Descifradores de códigos . - Tsentrpoligraf, 2000. - 124 p. — ISBN 5-227-00678-4 .
FH Hinsley, A. Stripp. Codebreakers: La historia interna de Bletchley Park. - Oxford University Press, 2001. - 360 p. — ISBN 978-0192801326 .
D. Stinson. criptografía. Teoría y Práctica. - Chapman & Hall / CRC, 2006. - 611 p. - ISBN 978-1-58488-508-5 .
W. Mao. Criptografía moderna. Teoría y práctica.- Williams, 2005. - 768 p. — ISBN 5-8459-0847-7 .
E. Biham, A. Shamir. Criptoanálisis diferencial de criptosistemas tipo DES . - Revista de Criptología, 1990. - V. 4 .
E. Biham, A. Shamir. Criptoanálisis diferencial de Feal y N-Hash . - Avances en Criptología - EUROCRYPT '91, 1991. - V. 547 .
E. Biham, A. Shamir. Criptoanálisis diferencial de Snefru, Khafre, REDOC-II, LOKI y Lucifer . - Avances en Criptología - CRYPTO' 91, 1991.
M. Matsui. Método de Criptoanálisis Lineal para DES Cipher . - Avances en Criptología - EUROCRYPT' 93, 1993.
L. Knudsen, J. Mathiassen. Un ataque lineal de texto plano elegido en DES . - Taller Internacional sobre Cifrado Rápido de Software, 2000.
DE Denning. Firmas digitales con RSA y otros criptosistemas de clave pública . - Comunicaciones de la ACM, 1984. - T. 27 .
G. Davida. Criptoanálisis de firma elegida del criptosistema de clave pública RSA (MIT). — Departamento de Ingeniería Eléctrica e Informática, Univ. de Wisconsin, 1982.