Ataque clave adivinado

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 21 de marzo de 2015; las comprobaciones requieren 24 ediciones .

El ataque de clave elegida es uno de los métodos de ataque criptoanalítico , que monitorea el funcionamiento de un algoritmo de cifrado que utiliza varias claves secretas . Un criptoanalista inicialmente solo tiene información sobre una determinada relación matemática que vincula las claves.

Descripción

De acuerdo con el principio de Kerckhoff , el criptoanalista tiene toda la información necesaria sobre el sistema de encriptación utilizado, a excepción de un determinado conjunto de parámetros secretos llamado clave. Un criptoanalista solo conoce la relación entre un par de claves. Utiliza el texto cifrado y la proporción dada para adivinar ambas claves. Se conocen dos tipos de ataques de clave elegida: el ataque de clave elegida y texto claro conocido, en el que el criptoanalista sólo especifica la relación entre el par de claves, y el ataque de clave elegida y texto claro, en el que el criptoanalista establece tanto la relación entre el par de claves y el propio texto sin formato, que se va a cifrar. [una]

Un ataque basado en una clave seleccionada se lleva a cabo de la misma manera en todos los criptosistemas, incluida la llamada "caja negra", en la que se desconocen todas las propiedades. Esta "caja negra" utiliza la función de encriptación , que se elige de la misma manera para permutaciones aleatorias de mensajes. Los bits de la clave se eligen al azar, de modo que el conocimiento del texto cifrado no puede decirnos nada sobre el texto cifrado de la clave . ${\ Displaystyle E_ {k}}$ $k$ $E_{k}(m)$ $E_{h}(m')$ ${\ Displaystyle h \ neq k}$

El algoritmo de ataque basado en la tecla seleccionada en la "caja negra", además de las operaciones estándar, en cualquier momento del cálculo puede requerir:

cifrar o descifrar utilizando la clave secreta y el mensaje coincidente y el vector de inversión , $E_{k\oplus l}(m)$ $E_{k\oplus l}^{-1}(m)$ $k$ $metro$ $yo$
use la "caja negra" para el cálculo o con la ayuda de una tecla (que no es una función ) para recoger un mensaje . ${\ estilo de visualización E_ {h} (m)}$ $E_{h}^{-1}(m)$ $h$ $k$ $metro$

Además, el algoritmo puede tener acceso a un generador de bits aleatorios. Al final del cálculo, se emite la clave estimada . [2] $k$

Así, si el usuario utiliza una clave secreta y un criptosistema público ( criptosistema de clave pública ), entonces en cualquier momento el criptoanalista puede elegir un mensaje y un vector de inversión y realizar el cifrado o descifrado . La aplicación principal de un ataque de clave adivinada es verificar sistemas, pero bajo ciertas circunstancias este ataque puede aplicarse en la práctica. Si se usa un cifrado de flujo para transferir una clave de sesión de un usuario a otro , y el criptoanalista obtiene el control de la línea de transmisión, entonces puede cambiar cualquier parte de la clave a su gusto y recibirá la clave modificada en lugar de . Luego, cuando comience la transmisión con la clave incorrecta, recibirá un mensaje distorsionado y comenzará el procedimiento de recuperación. Mientras tanto, el criptoanalista recibirá el texto cifrado con la clave. (Una buena criptoprotección puede evitar tales ataques mediante el uso de nuevas claves de sesión independientes o agregando bits de detección de errores no lineales a la clave de sesión siempre que se necesite un procedimiento de recuperación. Sin embargo, la historia muestra que una buena criptoprotección no siempre sigue esto y es deseable tener un sistema que no se cuelgue bajo tal ataque) [3] . $k$ $mi$ $metro$ $yo$ $E_{{k\o más l}}$ $E_{{k\oplus l}}^{-1}}$ $k$ $A$ $B$ $B$ $k\o más l$ $k$ $B$ $A$ $k\o más l$

El principal tipo de ataque basado en una clave elegida

En esta parte, consideraremos un ataque que no depende de una debilidad específica en la función de cifrado. Es un ataque man-in-the-middle ( MITM ). Este tipo de ataque permite reducir el tiempo de búsqueda avanzada, dependiendo del número de inversiones de clave permitidas [4] .

Teorema. Sea un cifrado de bloques con una clave de n bits. Suponga que el criptoanalista puede realizar inversiones y tiene palabras de memoria. Entonces podrá descifrar el cifrado en pasos adicionales [4] . $mi$ $2^{p}$ $2^{p}$ $mi$ $2^{{np}}$

Prueba:

El analista reemplaza los últimos bits de la clave de todas las formas posibles. Por ejemplo, encripta los valores $pags$ $2^{p}$

E_{k}(m),E_{{k\oplus (00\dots 01)}}(m),\dots ,E_{{k\oplus j}}(m),\ldots ,E_{{k\ oplus (00\puntos 011\puntos 1)}}(m)

donde está la clave privada del usuario y cualquier mensaje adecuado. Crea una tabla hash a partir de los valores [4] . $k$ $metro$ $2^{p}$ $(E_{{k\o más j}},j)$

Luego realiza el cifrado cambiando los primeros bits de la clave y restableciendo los últimos bits: $2^{{np}}$ $notario público$ $pags$

E_{{(00\puntos 0)}}(m),E_{{(00\puntos 10\puntos)}}(m),\puntos,E_{{(11\puntos 10\lpuntos 0)}}( metro)

Después de todos los cálculos, cada valor se compara con la tabla hash [4] .

Si se descifra la clave original , donde consta de los últimos bits, la entrada coincidirá con el resultado a través del cifrado en la segunda etapa. Cuando se encuentra una coincidencia, será una clave candidata. Son posibles varias falsas alarmas si varias claves coinciden con el mensaje , pero, como en un ataque de texto coincidente , es casi seguro que uno o dos bloques adicionales de texto sin formato conocido las descartarán, con poco impacto en el tiempo de ejecución [4] . $k$ $(a, b)$ $b$ $pags$ $(E_{{k\o más b}},b)$ $un^{{th}}$ $(a, b)$ $metro$

Conclusión: Utilizando un número ilimitado de ataques de clave elegida, cualquier cifrado de bloque con una clave de n bits se puede descifrar utilizando no más que cálculos en memoria [4] . $O(2^{{n/2}})$

Prueba: Elijamos . $p=n/2$

Nota: Para una gran cantidad de ejemplos y una gran cantidad de memoria disponible, será mucho más eficiente intercambiar las dos etapas en la demostración del teorema. Calcular y almacenar cifrados en la memoria. Para cada tarea, realice inversiones y verifique el cumplimiento de la tabla. Por lo tanto, se gastarán iteraciones en cada tarea adicional [4] . $2^{{np}}$ $2^{p}$ $2^{p}$

Vulnerabilidad del código de bloque al ataque basado en la clave elegida

Demostraremos las capacidades de este tipo de ataque en un criptosistema, que ha demostrado ser extremadamente resistente contra un ataque de texto coincidente [3] .

Sea un cifrado de bloque secreto con un tamaño de clave de bits. Definamos un nuevo cifrado de bloque . $mi$ $norte$ $F$

F_{k}(m)=E_{k}(m)

si el primer bit es 0

k

F_{k}(m)=E_{{k'}}(m)\oplus k

en otros casos, donde el resultado de la inversión del primer bit es, por ejemplo, .

k'

k

k'=k\oplus(1,0,\ldots,0)

F

cifrado de bloque legítimo:

F_{k}^{{-1}}(m)=E_{k}^{{-1}}(m)

si el primer bit de la clave es 0

k

F_{k}^{{-1}}(m)=E_{{k'}}^{{-1}}(m\o más k)

, en otros casos

Si el cifrado principal tiene una buena protección de n bits, romper el cifrado con un ataque de análisis de texto requiere una búsqueda avanzada en el espacio de bits clave. En otras palabras, si el analista no tiene información sobre el cifrado , entonces puede obtener la información necesaria si cifra o descifra con las claves o [3] . $mi$ $F$ $n-1$ $mi$ $k$ $k'$

Aunque el cifrado es difícil de romper con un ataque de texto elegido, es muy fácil de romper con un ataque clave elegido. El analista necesita dos cifras: y para algún mensaje adecuado . Si el primer bit es cero, entonces $F$ $F_{k}(m)$ $F_{{k'}}(m)$ $metro$ $k$

F_{k}(m)\oplus F_{{k'}}(m)=E_{k}(m)\oplus (E_{{k''}}(m)\oplus k')=k'

En otros casos,

F_{k}(m)\oplus F_{{k'}}(m)=(E_{{k'}}(m)\oplus k)\oplus (E_{{k'}}(m)=k

[3] .

Así, el analista recibe inmediatamente todos los bits de la clave , excepto el primero, y puede completar la operación, ya que conoce el texto en claro [4] . $k$

Ejemplos de ataques

Ataque a LOKI89

En el cifrado LOKI89, cada elección de dos subclaves , una de un ciclo par y otra de un ciclo impar, tiene una clave correspondiente de 64 bits. Dado que todos los algoritmos para obtener dos subclaves de las dos anteriores son iguales, la ubicación de los ciclos en los que se encuentran las dos subclaves actuales no afecta la salida de las siguientes subclaves. Si arreglamos dos subclaves y claves y definimos la segunda clave seleccionando y , entonces los valores de las subclaves de la clave serán los mismos que las siguientes subclaves de la clave . En ese caso, . Esta relación se conserva para dos claves elegidas de esta manera: si la información anterior al segundo ciclo de cifrado con la clave es la misma que la información anterior al primer cifrado con la clave , entonces la información y los datos de entrada de la función son los mismos en ambas operaciones desplazadas en un ciclo. En este caso, si el texto sin formato está cifrado con la clave , el texto cifrado antes del segundo ciclo será . Los datos recibidos son los mismos que se encontraron antes del primer ciclo de cifrado con la clave , cuyo valor será , y por lo tanto en este par ${\ estilo de visualización K2}$ ${\ estilo de visualización K3}$ $k$ $K^{*}$ $K1^{*}=K2$ $K2^{*}=K3$ $Ki^{*}$ $K^{*}$ ${\ estilo de visualización K (i + 1)}$ $k$ $K^{*}=(K2,K3)=(K_{R},ROL12(K_{L}))$ $k$ $K^{*}$ $F$ $PAGS$ $k$ $(P_{R}\oplus K_{R},P_{L}\oplus K_{L}\oplus F(P_{R}\oplus K_{R},K_{L}))$ $K^{*}$ $P^{*}\oplus K^{*}=(P_{R}^{*}\oplus K_{L},P_{R}^{*}\oplus ROL12(K_{L}))$

PAGS ∗ = ( PAGS R , PAGS L ⊕ k L ⊕ R O L 12 ( k L ) ⊕ F ( PAGS R ⊕ k R , k L ) ) {\displaystyle P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))}

P^{*}=(P_{R},P_{L}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{R}\oplus K_{R},K_ {L}))

Puedes ver que el lado derecho de la expresión es el mismo que el lado izquierdo de la expresión y la proporción de las otras dos partes depende de la clave. En tal par, existe una relación similar entre los textos cifrados:

PAGS

P^{{*}}

C ∗ = ( C R ⊕ k L ⊕ R O L 12 ( k L ) ⊕ F ( C L ⊕ k R , k L ) , C L ) . {\displaystyle C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).}

C^{*}=(C_{R}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(C_{L}\oplus K_{R},K_{L}), C_{L}).

Los gráficos describen la relación entre las subclaves de las dos claves y la relación entre los valores durante el proceso de cifrado.

ESQUEMA

Un ataque de texto sin formato con coincidencia de clave que se basa en estas propiedades selecciona un valor de 32 bits , textos sin formato cuyos lados derechos son y cuyas mitades izquierdas de 32 bits se eligen aleatoriamente, y textos sin formato cuyos lados izquierdos son y cuyas mitades izquierdas son aleatorias. los lados de la derecha se eligen al azar. Se utilizan dos claves asociadas desconocidas para cifrar los datos de texto sin formato en el sistema en estudio: la clave se utiliza para cifrar los primeros textos sin formato y la clave se utiliza para cifrar los textos sin formato restantes . Para cada par de textos sin formato y se garantiza que , y con alta probabilidad hay dos textos sin formato tales que . Para tal par, los datos siguen siendo los mismos si ambas ejecuciones se desplazan en un ciclo. Tal par se puede seleccionar fácilmente, si existe, verificando la igualdad.La probabilidad de pasar esta prueba al azar es , por lo que solo unos pocos pares podrán pasarla. $P_{R}$ $2^{16}$ ${\ estilo de visualización P_{0},...,P_{65535}}$ $P_{R}$ $2^{16}$ $P_{0}^{*},...,P_{65535}^{*}$ $P_{R}$ $k$ $2^{16}$ $K^{*}=(K_{R},ROL12(K_{L}))$ $2^{16}$ $Pi}}$ $P_{j}^{*}$ $P_{jL}^{*}=P_{iR}$ $P_{jR}^{*}=P_{iL}\oplus K_{L}\oplus ROL12(K_{L})\oplus F(P_{iR}\oplus K_{R},K_{L} )$ $C_{R}^{*}=C_{L}.$ ${\ estilo de visualización 2^{-32}}$

Los pares que tienen estas propiedades de texto sin formato y texto cifrado cumplen los requisitos clave (1) y (2). Así, para este par se cumple la relación , en la que el valor es la única incógnita . De todos los valores posibles, solo unos pocos satisfacen la ecuación. Utilizando técnicas de optimización y criptoanálisis diferencial , se puede encontrar un valor en unas pocas operaciones. Una vez que se ha encontrado el valor , es fácil calcular usando las fórmulas (1) y (2) para obtener y . $F(P_{R}\oplus K_{R},K_{L})\oplus F(C_{L}\oplus K_{R},K_{L})=P_{R}^{*} \oplus P_{L}\oplus C_{L}^{*}\oplus C_{R}$ $K_{L}\oplus K_{R}$ $2^{32}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus K_{R}$ $K_{L}\oplus ROL12(K_{L})$ $k$ $K^{*}$

Un ataque de texto sin formato conocido con clave elegida similar utiliza textos sin formato conocidos cifrados con una clave desconocida y textos sin formato cifrados con una clave relacionada . Un par con estas propiedades se puede identificar fácilmente mediante 32 bits comunes de texto sin formato y 32 bits comunes de texto cifrado. Este par se puede utilizar para buscar claves de la misma manera que en una clave elegida y un ataque de texto sin formato elegido. [una] $2^{32}$ $Pi}}$ $k$ $2^{32}$ $P_{j}^{*}$ $K^{*}=(K_{R},ROL12(K_{L}))$

Comparación con otros tipos de ataques

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

Ataque usando solo texto cifrado.
Una autopsia utilizando texto sin formato.
Un ataque utilizando el texto sin formato seleccionado.
Ataque adaptativo utilizando texto sin formato.
Ataca usando el texto cifrado seleccionado.
Apertura con la tecla seleccionada.
Criptoanálisis de bandidos .

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. [una]

Un ataque de clave coincidente es más fuerte que un ataque de texto coincidente. Instantáneamente descifra un cifrado de bloque especialmente diseñado que es seguro contra otros ataques. Para cualquier cifrado de bloque, un ataque de clave elegido puede acelerar el proceso de búsqueda avanzada según la cantidad de inversiones de clave permitidas. Para un ataque de clave adivinada sin restricciones, la cantidad de trabajo se puede reducir como una raíz cuadrada. Estos resultados son los mejores posibles para un ataque general que no se basa en ningún cifrado de bloque en particular.

Notas

↑ 1 2 3 Biham, 1993 .
↑ Winternitz y Hellman, 1987 .
↑ 1 2 3 4 Winternitz y Hellman, 1987 , pág. 17
↑ 1 2 3 4 5 6 7 8 Winternitz y Hellman, 1987 , pág. Dieciocho
↑ Schneier, 2003 .

Literatura

Robert Winternitz, Martín Hellman . Ataques de clave elegida en un cifrado de bloque // Cryptologia : journal. - 1987. - No. 11:1 . - P. 16-20 . -doi : 10.1080/ 0161-118791861749 .
Eli Biham. Nuevos tipos de ataques criptoanalíticos utilizando claves relacionadas // Helleseth T. (eds) Avances en criptología . — EUROCRIPTA '93. EUROCRYPT 1993. Lecture Notes in Computer Science, vol 765. Springer, Berlín, Heidelberg, 1993. doi : 10.1007/3-540-48285-7_34 .
B. Schneier. Criptografía aplicada. - Triunfo, 2003. - 816 p. - ISBN 5-89392-055-4 .