Criptoanálisis integral

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 15 de junio de 2014; las comprobaciones requieren 14 ediciones .

El criptoanálisis integral es un método de criptoanálisis que combina una serie de ataques a algoritmos criptográficos de bloques simétricos . A diferencia del criptoanálisis diferencial , que considera el efecto de un algoritmo en un par de textos sin formato, el criptoanálisis integral implica el estudio del mapeo de un conjunto de textos sin formato en un texto cifrado . Aplicado por primera vez en 1997 por Lars Knudsen .

Historia

En artículos científicos, el término " criptoanálisis integral " fue propuesto en 1999 en la publicación Criptoanálisis integral de SAFER+ (inglés) . El concepto en sí fue expresado por primera vez por Lars Knudsen al analizar el cifrado Square en 1997. Por esta razón, el término "ataques tipo cuadrado" o simplemente "ataque cuadrado" se usa a menudo en la literatura. Para 2011 no hay avances revolucionarios respecto al ataque a Square en el campo del criptoanálisis integral.

La base teórica del método

Sea un grupo abeliano finito . Entonces, tomando el 1er bloque como el conjunto de posibles textos cifrados (en el caso general, está determinado por el alfabeto elegido y el tamaño del bloque), podemos considerar un grupo de la siguiente forma, con la misma operación de grupo: . El conjunto de espacio n-dimensional así construido es el conjunto de todos los textos cifrados posibles. En consecuencia, el elemento espacial es un cierto texto cifrado, los componentes de este vector son el valor de los bloques de texto cifrado. Suponemos que la suma de vectores es un vector cuyas componentes son iguales a las sumas de las componentes correspondientes de los términos. La integral de conjunto es la suma de todos los vectores incluidos en : . ${\ estilo de visualización (G, +)}$ $GRAMO$ $GRAMO$ $G^{n}=G\veces ...\veces G$ $v=(v_{1},...,v_{n}),v\en G$ $S\subconjunto G$ $S$ ${\ estilo de visualización \ int S = \ sum _ {v \ in S} v}$

El criptoanálisis integral exitoso debería reducir el número de iteraciones de adivinación de clave . Para hacer esto, tratamos de agrupar los vectores de texto sin formato para que, en función de la agrupación, se puedan encontrar patrones. Es conveniente estudiar algoritmos basados en la siguiente partición:

$v_{i}=c,\forall v\in S$
${\ estilo de visualización \ {v_ {i}: v \ en S \} = G}$
$\sum _{v\in S}=c'$ ,

donde es un número fijo, (vector) $i$ $c,c'=const\in G$

El siguiente teorema [1] juega un papel clave :

Sea un grupo abeliano finito . Denote , y el orden de g es igual a 1 o 2. Defina . entonces _ Es más, ${\ estilo de visualización (G, +)}$ $H=\{g\in G:g+g=0\}$ $s(G)=\sum _{g\in G}g$ $s(G)=\sum_{h\in H}h$ ${\ estilo de visualización s (G) + s (G) = 0}$

Vale la pena notar un resultado importante del teorema: si ), entonces , ya que ${\displaystyle G=GF(2^{s))$ ${\ estilo de visualización s (G) = 0}$ $H=\{0\}$

Tomamos nota de una serie de notaciones que se utilizan a menudo en publicaciones sobre ataques basados en criptoanálisis integral:

Si se denota la i -ésima componente de la integral , esto significa que en todos los términos de la suma integral, la i -ésima componente es la misma ${\ matemáticas {C}}$
Del mismo modo , muestra que el componente correspondiente difiere en todos los términos. $\mathcal{A}$
$\mathcal{S}$ muestra que el componente dado de la integral se puede predecir.
? muestra que es imposible predecir el componente de la integral.

El principio general de búsqueda de vulnerabilidades en el ejemplo de la red Feistel

Considere cómo cambian las integrales sobre S si todos los elementos de este conjunto se alimentan a la entrada de la red de Feistel. Sea S un conjunto de textos cifrados en el que todos menos uno de los bloques correspondientes son iguales (pueden diferir entre sí). En el ejemplo, el texto cifrado son 16 bloques dispuestos en 2 líneas. Para cifrados como AES , también es importante considerar que el texto cifrado está dado por una matriz, ya que utilizan diferentes operaciones para filas y columnas. Considere el efecto de las células de Feistel en etapas:

Suponiendo que las celdas de Feistel produzcan asignaciones biyectivas , es obvio que los mismos bloques entre los textos cifrados se incluirán en los mismos bloques entre los textos cifrados convertidos (sin embargo, es casi seguro que los valores antiguo y nuevo diferirán). Por lo tanto, podemos escribir que la primera celda asignó un conjunto de una clase de conjuntos con componentes idénticos en conjunto a un conjunto de la misma clase.
Dado que el valor de todos los bloques en la salida de una celda de Feistel depende del valor de cada bloque en la entrada, el impacto de un solo bloque cambia cada bloque del texto cifrado en la salida. Así, los valores de los componentes de la integral se vuelven no más que predecibles [2] . $\mathcal{A}$
Dado que a la entrada de cada bloque perteneciente al texto cifrado de entrada, el conjunto de valores no coincide con el conjunto de posibles valores del bloque, es posible que su suma no se conserve durante la transformación biyectiva, por lo que se puede obtener cualquier cosa a la salida de la célula.

Incluso aplicable al ejemplo descrito, es posible reducir significativamente el número de iteraciones para la selección o proporcionar información adicional para varios tipos de criptoanálisis.

Comparación con el criptoanálisis diferencial

Al igual que con el criptoanálisis diferencial, los ataques basados en integrales se pueden clasificar como un tipo de ataque basado en texto sin formato elegido de forma adaptativa .

Lars Knudsen también notó la similitud con el ataque diferencial truncado , que tiene la idea de considerar el comportamiento de no toda la diferencia, como en el criptoanálisis diferencial, sino sus partes. Además, el criptoanálisis integral tiene superioridad en su capacidad para considerar el tercer estado del resultado - , mientras que el ataque de diferenciales truncados distingue solo dos. $\mathcal{S}$

Para atacar diferenciales de alto orden , puede ver que en el campo de Galois, la expresión para el diferencial de orden s -ésimo es similar a la integral [3] . Por lo tanto, uno puede intentar generalizar algunos métodos de criptoanálisis diferencial a métodos integrales. $GF(2^{s})$

Es de destacar que los ataques de diferenciales truncados y diferenciales de alto orden también fueron publicados por primera vez por Lars Knudsen en 1994, también en la conferencia FSE [4]

Ataques notables

Los ataques a cifrados similares a AES ( Rijndael , SQUARE , CRYPTON ) se pueden generalizar mediante el primer paso: consideración de integrales después de la tercera ronda de cifrado. Los pasos adicionales son intentos de mejorar el ataque aumentando el número de rondas, utilizando varias suposiciones que aumentar el número de iteraciones de la búsqueda, por lo tanto también la complejidad de romper.

AES

Ataque al cifrado de 4 rondas

Los puntos clave del cifrado de matriz de bytes son la transformación no lineal, el desplazamiento de filas, la transformación de columnas, la adición de texto (matriz de bytes intermedia) con matriz de clave redonda.

Considere un texto sin formato de dieciséis bytes . Que el criptoanalista tenga a su disposición 256 textos cifrados con la siguiente propiedad: se obtienen a partir de matrices de bytes en las que todos menos uno son iguales en el conjunto de estos textos cifrados. Por su número, podemos decir que un byte "desigual" tomará todos los valores posibles en un conjunto dado. Así, podemos ir a la notación anterior:

Estado inicial:

$\mathcal{A}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$
${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$
${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$
${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$

Considere el estado del texto después de cada ronda:

La conversión no lineal debido a la biyectividad no cambia el tipo de byte, solo los valores de los textos individuales.
El cambio de fila no afecta a la 1ª fila, el resto se desplazan sin cambiar la integral.
La conversión de columna hace que cada byte resultante dependa de los 4 bytes de la columna original, pero nuevamente, debido a la biyectividad de la operación, obtenemos que cada byte de la columna tomará cada uno de sus valores solo una vez.
La adición con una clave no cambiará los tipos de bytes.

Entonces, después de la primera ronda:

Después de la 1ra ronda:

$\mathcal{A}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$
$\mathcal{A}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$
$\mathcal{A}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$
$\mathcal{A}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$	${\ matemáticas {C}}$

El cambio de fila distribuye 1 byte en cada columna con tipo . $\mathcal{A}$
Como en la ronda 1, si hay un byte en la columna y el resto son , todos los bytes de la columna se convierten en . Las 4 columnas se convierten de esta manera. $\mathcal{A}$ ${\ matemáticas {C}}$ $\mathcal{A}$

Después de la segunda ronda:

Después de la 2da ronda:

$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$
$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$	$\mathcal{A}$

Usando el resultado del teorema descrito en la sección de teoría, obtenemos los valores de las integrales en cada byte ${\mathcal {S}}=0$

Después de la 3ra ronda, :

{\mathcal {S}}=0

$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$
$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$	$\mathcal{S}$

Dado que en la última ronda no hay transformación de columna (según la especificación AES), y las transformaciones restantes se convierten en , entonces para el esquema de cuatro rondas, como resultado de la última ronda, el valor de la integral no cambia hasta la etapa de suma binaria con clave redonda. En este caso, todo lo que queda es que cada byte asuma el valor del byte correspondiente de la clave de ronda, obtener el texto estimado de la 3ª ronda y verificar si la integral del bloque correspondiente es igual a cero. Si es igual, se puede considerar que se ha encontrado el byte de clave de ronda. $\mathcal{A}$ $\mathcal{A}$

Expansiones por número de rondas

El esquema se puede extender a un esquema de siete rondas considerando qué depende la transformación de la integral de un byte en particular. Sin embargo, incluso en el caso de 7 rondas, el número de iteraciones requeridas es alto, en este caso los vínculos entre las claves de ronda se buscan analizando el esquema de generación de código. [5]

Mejoras en los recursos del criptógrafo

Reducir significativamente el tiempo que lleva buscar claves, debido a la organización especial de las condiciones de búsqueda, utilizando vectores de tres bytes, permite la introducción de la llamada suma parcial. Tal modificación para un cifrado de seis rondas reduce el poder de enumeración de a . Otro enfoque es utilizar el hecho de que la integral sobre conjuntos con diferentes también se desvanece después de la codiciada tercera ronda. Este método requiere una gran cantidad de recursos de memoria y la posesión de una base muy grande de texto sin formato: texto cifrado. [6] $2^{{72}}$ $2^{{44}}$ ${\ matemáticas {C}}$

Usando sumas parciales, es posible implementar un truco del sistema de ocho rondas, pero la complejidad de este truco es incluso mayor que la de la enumeración exhaustiva .

Cuadrado

El ataque básico en el cifrado Square es prácticamente el mismo que el ataque de cuatro rondas en AES, también le permite ampliar la cantidad de rondas. Quizás la única diferencia significativa es la presencia de la primera ronda de encriptación y, como resultado, dos métodos de expansión (uno hacia la última ronda, el otro hacia la primera). Los desarrolladores del cifrado, mientras lo investigaban, pudieron construir un ataque contra el cifrado de seis rondas .

Se han publicado los siguientes resultados [7] :

Ataques a la Plaza:

Ataque	Número de textos abiertos	Tiempo	costo de memoria
Por 4 rondas	$2^{{9}}$	$2^{{9}}$	Pocos
Por 5 rondas en la 1ra manera	$2^{11}$	$2^{40}$	pocos
Por 5 rondas en la 2da vía	$2^{32}$	$2^{40}$	$2^{32}$
Por 6 rondas	$2^{32}$	$2^{{72}}$	$2^{32}$

Notas

↑ Herstein, Temas de álgebra, 2.ª ed., 1975, página 116
↑ Dolgov, Golovashich, Ruzhentsev. “Análisis de la fuerza criptográfica del cifrado Tornado” (2003), p.7
↑ Lars Knudsen (2001). "Cripanálisis integral (resumen extendido), p. 118"
↑ Lars Knudsen (1994). "Diferenciales truncados y de orden superior"
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner y Doug Whiting. "Cryptoanálisis mejorado de Rijndael" (2001), págs. 2-3
↑ Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner y Doug Whiting. "Cryptoanálisis mejorado de Rijndael" (2001), págs. 4-7
↑ Joan Daemen, Lars Knudsen, Vincent Rijmen. "The Block Cipher Square" (1997), página 15

Enlaces

Lars Knudsen y David Wagner. Criptoanálisis integral (resumen extendido) (neopr.) . — 2003.
Niels Ferguson, John Kelsey, Stefan Lucks, Bruce Schneier, Mike Stay, David Wagner y Doug Whiting. Criptoanálisis mejorado de Rijndael (neopr.) . - 2001. Archivado el 8 de enero de 2009. Archivado el 8 de enero de 2009 en Wayback Machine .
Joan Daemen, Lars Knudsen, Vincent Rijmen (enero de 1997). El bloque de cifrado cuadrado (PDF) . Cuarto taller internacional sobre cifrado rápido de software (FSE '97), volumen 1267 de Lecture Notes in Computer Science. Haifa: Springer-Verlag. páginas. 149-165.