CRIPTOGRAFÍA

El algoritmo Berlekamp-Massey es un algoritmo que encontrará el registro de desplazamiento de retroalimentación lineal más corto (LFSR) para una secuencia de salida binaria dada. El algoritmo también encontrará el polinomio mínimo de una secuencia lineal recurrente en un campo arbitrario . El requisito de campo significa que el algoritmo Berlekamp-Massey requiere que todos los elementos distintos de cero tengan un inverso multiplicativo. ^[1] Reeds y Sloane ofrecen una extensión para manejar un anillo . ^[2]

Elwyn Berlekamp inventó un algoritmo para decodificar códigos Bose – Chaudhuri – Hocquenghem (BCH) . ^[3] [4] James Massey reconoció su aplicación a los registros de desplazamiento de retroalimentación lineal y simplificó el algoritmo. ^[5] [6] Massey denominó al algoritmo Algoritmo de síntesis LFSR (Algoritmo iterativo de Berlekamp), ^[7] pero ahora se conoce como el algoritmo Berlekamp-Massey.

Descripción del algoritmo [ editar ]

El algoritmo Berlekamp – Massey es una alternativa al decodificador Reed – Solomon Peterson para resolver el conjunto de ecuaciones lineales. Se puede resumir como encontrar los coeficientes Λ _j de un polinomio Λ ( x ) de modo que para todas las posiciones i en un flujo de entrada S :

$${\ displaystyle S_ {i + \ nu} + \ Lambda _ {1} S_ {i + \ nu -1} + \ cdots + \ Lambda _ {\ nu -1} S_ {i + 1} + \ Lambda _ {\ nu } S_ {i} = 0.}

En los ejemplos de código a continuación, C ( x ) es una instancia potencial de Λ ( x ). El polinomio de localización de errores C ( x ) para errores L se define como:

$${\ displaystyle C (x) = C_ {L} x ^ {L} + C_ {L-1} x ^ {L-1} + \ cdots + C_ {2} x ^ {2} + C_ {1} x +1}

o invertido:

$${\ displaystyle C (x) = 1 + C_ {1} x + C_ {2} x ^ {2} + \ cdots + C_ {L-1} x ^ {L-1} + C_ {L} x ^ { L}.}

El objetivo del algoritmo es determinar el grado mínimo L y C ( x ) que da como resultado todos los síndromes

$${\ displaystyle S_ {n} + C_ {1} S_ {n-1} + \ cdots + C_ {L} S_ {nL}}

siendo igual a 0:

$${\ displaystyle S_ {n} + C_ {1} S_ {n-1} + \ cdots + C_ {L} S_ {nL} = 0, \ qquad L \ leq n \ leq N-1.}

Algoritmo: C ( x ) se inicializa a 1, L es el número actual de errores asumidos y se inicializa a cero. N es el número total de síndromes. n se usa como el iterador principal y para indexar los síndromes de 0 a N −1. B ( x ) es una copia de la última C ( x ) desde que L se actualizó e inicializó a 1. b es una copia de la última discrepancia d (explicada a continuación) desde que L se actualizó e inicializó a 1. m es el número de iteraciones desde L ,B ( x ) yb se actualizaron e inicializaron a 1.

Cada iteración del algoritmo calcula una discrepancia d . En la iteración k esto sería:

$${\ displaystyle d \ obtiene S_ {k} + C_ {1} S_ {k-1} + \ cdots + C_ {L} S_ {kL}.}

Si d es cero, el algoritmo supone que C ( x ) y L son correctas por el momento, incrementa m y continúa.

Si d no es cero, el algoritmo ajusta C ( x ) para que un recálculo de d sea ​​cero:

$${\ displaystyle C (x) \ obtiene C (x) - (d / b) x ^ {m} B (x).}

El x ^m plazo turnos B (x) de modo que sigue los síndromes correspondientes a b . Si la actualización anterior de L ocurrió en la iteración j , entonces m = k - j , y una discrepancia recalculada sería:

$${\ displaystyle d \ obtiene S_ {k} + C_ {1} S_ {k-1} + \ cdots - (d / b) (S_ {j} + B_ {1} S_ {j-1} + \ cdots) .}

Esto cambiaría una discrepancia recalculada a:

$${\ displaystyle d = d- (d / b) b = dd = 0.}

El algoritmo también necesita aumentar L (número de errores) según sea necesario. Si L es igual al número real de errores, a continuación, durante el proceso de iteración, las discrepancias se convertirá en cero antes de que n se hace mayor que o igual a 2 l . De lo contrario, L se actualiza y el algoritmo actualizará B ( x ), b , aumentará L y restablecerá m = 1. La fórmula L = ( n + 1 - L ) limita L al número de síndromes disponibles utilizados para calcular las discrepancias, y también maneja el caso donde L aumenta en más de 1.

Código de muestra [ editar ]

El algoritmo de Massey (1969 , p. 124) para un campo arbitrario:

  polinomio ( campo  K )  s ( x )  =  ...  / * coeffs son s_j; secuencia de salida como polinomio de grado N-1) * / 
  / * polinomio de conexión * / 
  polinomio ( campo  K )  C ( x )  =  1 ;   / * coeffs son c_j * / 
  polinomio ( campo  K )  B ( x )  =  1 ; 
  int  L  =  0 ; 
  int  m  =  1 ; 
  campo  K b  =  1 ; 
  int  n ;

  / * pasos 2. y 6. * / 
  para  ( n  =  0 ;  n  <  N ;  n ++ )  { 
      / * paso 2. calcular la discrepancia * / 
      campo  K  d  =  s_n  +  \ Sigma_ { i = 1 } ^ L  c_i  *  s_ { n - i };

      if  ( d  ==  0 )  { 
          / * paso 3. la discrepancia es cero; la aniquilación continúa * / 
          m  =  m  +  1 ; 
      }  else  if  ( 2  *  L  <=  n )  { 
          / * paso 5. * / 
          / * copia temporal de C (x) * / 
          polinomio ( campo  K )  T ( x )  =  C ( x );

          C ( x )  =  C ( x )  -  d  b ^ { - 1 }  x ^ m  B ( x ); 
          L  =  n  +  1  -  L ; 
          B ( x )  =  T ( x ); 
          b  =  d ; 
          m  =  1 ; 
      }  else  { 
          / * paso 4. * / 
          C ( x )  =  C (x )  -  d  b ^ { - 1 }  x ^ m  B ( x ); 
          m  =  m  +  1 ; 
        } 
    } 
  devuelve  L ;

El algoritmo para el campo binario [ editar ]

El siguiente es el algoritmo de Berlekamp-Massey especializado para el campo binario finito F ₂ (también escrito GF (2)). Los elementos de campo son '0' y '1'. Las operaciones de campo '+' y '-' son idénticas y equivalentes a la operación 'exclusiva u', XOR. El operador de multiplicación '*' se convierte en la operación AND lógica. El operador de división se reduce a la operación de identidad (es decir, la división de campo solo se define para dividir entre 1 y x / 1 = x).

1. Dejar $${\ displaystyle s_ {0}, s_ {1}, s_ {2} \ cdots s_ {N-1}}ser los pedazos de la corriente.
2. Inicializar dos matrices $${\ displaystyle b} y $${\ displaystyle c} cada uno de longitud $${\ displaystyle N} ser ceros, excepto $${\ displaystyle b_ {0} \ leftarrow 1, c_ {0} \ leftarrow 1}
3. asignar $${\ displaystyle L \ leftarrow 0, m \ leftarrow -1}.
4. por $${\ displaystyle n = 0} paso 1 mientras {\ displaystyle n :
   • Dejar discrepancia $${\ displaystyle d} ser $${\ displaystyle s_ {n} \ oplus c_ {1} s_ {n-1} \ oplus c_ {2} s_ {n-2} \ oplus \ cdots \ oplus c_ {L} s_ {nL}}.
   • Si $${\ displaystyle d = 0}, a continuación, $${\ displaystyle c} ya es un polinomio que aniquila la porción de la corriente de $${\ displaystyle nL} a $${\ displaystyle n}.
   • más :
     • Dejar $${\ displaystyle t} ser una copia de $${\ displaystyle c}.
     • Conjunto $${\ displaystyle c_ {nm} \ leftarrow c_ {nm} \ oplus b_ {0}, c_ {n-m + 1} \ leftarrow c_ {n-m + 1} \ oplus b_ {1}, \ dots} hasta $${\ displaystyle c_ {N-1} \ leftarrow c_ {N-1} \ oplus b_ {N-n + m-1}} (dónde $${\ displaystyle \ oplus}es el exclusivo u operador).
     • Si $${\ displaystyle L \ leq {\ frac {n} {2}}}establecer $${\ displaystyle L \ leftarrow n + 1-L}establecer $${\ displaystyle m \ leftarrow n}, y deja $${\ displaystyle b \ leftarrow t}; de lo contrario dejar$${\ displaystyle L}, $${\ displaystyle m} y $${\ displaystyle b} solo.

Al final del algoritmo, $${\ displaystyle L} es la longitud del LFSR mínimo para la transmisión, y tenemos $${\ displaystyle c_ {L} s_ {a} \ oplus c_ {L-1} s_ {a + 1} \ oplus c_ {L-2} s_ {a + 2} \ oplus \ cdots = 0} para todos $${\ displaystyle a}.

BestCrypt es una aplicación comercial de cifrado de disco para Windows, Linux y OS X, desarrollada por Jetico Inc, Oy. BestCrypt viene en dos ediciones: edición Volume Encryption, que cifra volúmenes de disco completos ; y la edición Encryption de contenedor, que cifra los discos virtuales almacenados como archivos de computadora. También proporciona la utilidad complementaria de borrado de datos BCWipe .

Algoritmos criptográficos [ editar ]

BestCrypt admite una amplia variedad de algoritmos de cifrado de bloques que incluyen AES , Serpent , Blowfish , Twofish , DES , Triple DES , GOST 28147-89 . Todos los cifrados admiten los modos de operación CBC y LRW , mientras que AES, Twofish y Serpent también admiten el modo XTS .

Características [ editar ]

• Cree y monte una unidad virtual encriptada usando AES , Blowfish , Twofish , CAST-128 ^[3] y varios otros métodos de encriptación. BestCrypt v.8 y superior puede montar alternativamente una subcarpeta en un disco NTFS en lugar de una unidad. Las imágenes de disco virtual cifradas son compatibles en Windows, Linux y Mac OS X.
• Cifre un conjunto de archivos en un único archivo autoextraíble.
• Cifre de forma transparente particiones o volúmenes completos junto con la autenticación previa al inicio para particiones de inicio cifradas.
• Autenticación de dos factores .
• Soporte para contenedores dinámicos de tamaño eficiente con la tecnología Smart Free Space Monitoring. ^[4]
• Cifrado acelerado por hardware.
• Funciones anti-keylogging para proteger las contraseñas de contenedores y volúmenes.
• Utilidad de borrado de datos BCWipe para borrar copias de datos sin protección para complementar el cifrado.
• Métodos de autenticación de uso compartido secreto y clave pública además de la autenticación básica basada en contraseña.

Un ataque biclique es una variante del método de criptoanálisis de encuentro en el medio (MITM) . Utiliza una estructura biclique para extender el número de rondas posiblemente atacadas por el ataque MITM. Dado que el criptoanálisis biclique se basa en ataques MITM, es aplicable tanto a los cifrados de bloque como a las funciones hash (iteradas) . Los ataques bicliques son conocidos por haber roto tanto el AES completo ^[1] como la IDEA completa , ^[2] aunque solo con una ligera ventaja sobre la fuerza bruta. También se ha aplicado a la resistencia de cifrado y preimagen KASUMI del Skein-512 yFunciones hash SHA-2 . ^[3]

El ataque biclique sigue siendo (a partir de abril de 2019 ) el ataque de clave única más conocido públicamente en AES . La complejidad computacional del ataque es$${\ displaystyle 2 ^ {126.1}}, $${\ displaystyle 2 ^ {189.7}} y $${\ displaystyle 2 ^ {254.4}}para AES128, AES192 y AES256, respectivamente. Es el único ataque de clave única conocido públicamente en AES que ataca el número completo de rondas. ^[1] Los ataques anteriores han atacado variantes redondas reducidas (típicamente variantes reducidas a 7 u 8 rondas).

Como la complejidad computacional del ataque es $${\ displaystyle 2 ^ {126.1}}, es un ataque teórico, lo que significa que la seguridad de AES no se ha roto, y el uso de AES sigue siendo relativamente seguro. Sin embargo, el ataque biclique es un ataque interesante, que sugiere un nuevo enfoque para realizar criptoanálisis en cifrados de bloque. El ataque también ha dado más información sobre AES, ya que ha puesto en tela de juicio el margen de seguridad en el número de rondas utilizadas en el mismo.

Historia [ editar ]

El ataque MITM original fue sugerido por primera vez por Diffie y Hellman en 1977, cuando discutieron las propiedades criptoanalíticas del DES. ^[4] Argumentaron que el tamaño de la clave era demasiado pequeño y que volver a aplicar DES varias veces con diferentes claves podría ser una solución para el tamaño de la clave; sin embargo, desaconsejaron el uso de doble DES y sugirieron triple DES como mínimo, debido a los ataques MITM (los ataques MITM se pueden aplicar fácilmente a doble DES para reducir la seguridad de$${\ displaystyle 2 ^ {56 * 2}} para sólo $${\ displaystyle 2 * 2 ^ {56}}, ya que uno puede aplicar fuerza bruta de forma independiente al primer y al segundo cifrado DES si tienen texto sin cifrar).

Desde que Diffie y Hellman sugirieron ataques MITM, han surgido muchas variaciones que son útiles en situaciones en las que el ataque MITM básico no es aplicable. La variante de ataque biclique fue sugerida por primera vez por Dmitry Khovratovich , Rechberger y Savelieva para su uso con el criptoanálisis con función hash. ^[5]Sin embargo, fueron Bogdanov, Khovratovich y Rechberger quienes mostraron cómo aplicar el concepto de bicliques a la configuración de clave secreta, incluido el criptoanálisis de cifrado en bloque, cuando publicaron su ataque a AES. Antes de esto, los ataques MITM en AES y muchos otros cifrados de bloques habían recibido poca atención, principalmente debido a la necesidad de bits clave independientes entre los dos 'subcifradores MITM' para facilitar el ataque MITM, algo que es difícil de lograr con muchos horarios clave modernos, como el de AES.

El biclique [ editar ]

Para una explicación general de lo que es una estructura biclique, vea el artículo para bicliques .

En un ataque MITM, las teclas $${\ displaystyle K_ {1}} y $${\ displaystyle K_ {2}}, pertenecientes al primer y segundo subcifrador, deben ser independientes; es decir, deben ser independientes entre sí, de lo contrario, los valores intermedios coincidentes para el texto simple y cifrado no se pueden calcular de forma independiente en el ataque MITM (existen variantes de ataques MITM, donde los bloques pueden tener bits clave compartidos. Ver el ataque MITM de 3 subconjuntos ). Esta propiedad es a menudo difícil de explotar en un mayor número de rondas, debido a la difusión del cifrado atacado.
En pocas palabras: cuantas más rondas ataques, más subcifras tendrás. Cuantos más subcifradores tenga, menos bits de clave independientes entre los subcifradores tendrá que aplicar fuerza bruta de forma independiente. Por supuesto, el número real de bits-clave independientes en cada subcifrador depende de las propiedades de difusión de la programación de claves.

La forma en que el biclique ayuda a abordar lo anterior, es que permite, por ejemplo, atacar 7 rondas de AES usando ataques MITM, y luego utilizando una estructura biclique de longitud 3 (es decir, cubre 3 rondas del cifrado), puede asignar el estado intermedio al comienzo de la ronda 7 al final de la última ronda, por ejemplo, 10 (si es AES128), atacando así el número completo de rondas de la cifra, incluso si no fuera posible atacar esa cantidad de rondas con un ataque MITM básico.

El significado de biclique es, por lo tanto, construir una estructura eficaz, que pueda mapear un valor intermedio al final del ataque MITM al texto cifrado al final. A qué texto cifrado se asigna el estado intermedio al final, por supuesto, depende de la clave utilizada para el cifrado. La clave utilizada para asignar el estado al texto cifrado en biclique se basa en los bits de fuerza bruta en el primer y segundo subcifrador del ataque MITM.

La esencia de los ataques bicliques es, por lo tanto, además del ataque MITM, poder construir una estructura biclique efectivamente, que dependiendo de las teclas $${\ displaystyle K_ {1}} y $${\ displaystyle K_ {2}} puede asignar un cierto estado intermedio al texto cifrado correspondiente.

Cómo construir el biclique [ editar ]

Fuerza bruta [ editar ]

Obtener $${\ displaystyle 2 ^ {d}} estados intermedios y $${\ displaystyle 2 ^ {d}}textos cifrados, luego calcule las claves que se asignan entre ellos. Esto requiere$${\ displaystyle 2 ^ {2d}} recuperaciones de clave, ya que cada estado intermedio debe estar vinculado a todos los textos cifrados.

Diferenciales independientes de clave relacionada [ editar ]

(Bogdanov, Khovratovich y Rechberger sugirieron este método en su artículo: Criptoanálisis Biclique del AES completo ^[1] )

Preliminar:
recuerde que la función del biclique es mapear los valores intermedios,$${\ displaystyle S}, a los valores de texto cifrado, $${\ displaystyle C}, basado en la clave $${\ displaystyle K [i, j]} tal que:
$${\ displaystyle \ forall i, j: S_ {j} {\ xrightarrow [{f}] {K [i, j]}} C_ {i}}

Procedimiento:
Paso uno: un estado intermedio ($${\ displaystyle S_ {0}}), un texto cifrado ($${\ displaystyle C_ {0}}) y una clave ($${\ displaystyle K [0,0]}) se elige de modo que: $${\ displaystyle S_ {0} {\ xrightarrow [{f}] {K [0,0]}} C_ {o}}, dónde $${\ displaystyle f}es la función que asigna un estado intermedio a un texto cifrado usando una clave dada. Esto se denota como el cálculo base.

Paso dos: dos conjuntos de claves de tamaño relacionadas$${\ displaystyle 2 ^ {d}}esta elegido. Las claves se eligen de manera que:

• El primer conjunto de claves son claves, que cumplen los siguientes requisitos diferenciales sobre $${\ displaystyle f} con respecto al cálculo base: $${\ displaystyle 0 {\ xrightarrow [{f}] {\ Delta _ {i} ^ {K}}} \ Delta _ {i}}
• El segundo conjunto de claves son claves, que cumplen los siguientes requisitos diferenciales sobre $${\ displaystyle f} con respecto al cálculo base: $${\ displaystyle \ nabla _ {j} {\ xrightarrow [{f}] {\ nabla _ {j} ^ {K}}} 0}
• Las teclas se eligen de tal manera que los senderos de la $${\ displaystyle \ Delta _ {i}}- y $${\ displaystyle \ nabla _ {j}}Los diferenciales son independientes, es decir, no comparten ningún componente no lineal activo.

En otras palabras:
una diferencia de entrada de 0 debería correlacionarse con una diferencia de salida de$${\ displaystyle \ Delta _ {i}} bajo una diferencia clave de $${\ displaystyle \ Delta _ {i} ^ {K}}. Todas las diferencias son con respecto al cálculo base.
Una diferencia de entrada de$${\ displaystyle \ nabla _ {j}} debe correlacionarse con una diferencia de salida de 0 bajo una diferencia clave de $${\ displaystyle \ nabla _ {J} ^ {K}}. Todas las diferencias son con respecto al cálculo base.

Paso tres: Dado que los senderos no comparten ningún componente no lineal (como las cajas S), los senderos se pueden combinar para obtener:
$${\ displaystyle 0 {\ xrightarrow [{f}] {\ Delta _ {i} ^ {K}}} \ Delta _ {i} \ oplus \ nabla _ {j} {\ xrightarrow [{f}] {\ nabla _ {j} ^ {K}}} 0 = \ nabla _ {j} {\ xrightarrow [{f}] {\ Delta _ {i} ^ {K} \ oplus \ nabla _ {j} ^ {K}} } \ Delta _ {i}},
que se ajusta a las definiciones de ambos diferenciales del paso 2.
Es trivial ver que la tupla$${\ displaystyle (S_ {0}, C_ {0}, K [0,0])}desde el cómputo base, también se ajusta por definición a ambos diferenciales, ya que los diferenciales son con respecto al cómputo base. Sustituyendo$${\ displaystyle S_ {0}, C_ {0}} $${\ displaystyle K [0,0]} en cualquiera de las dos definiciones, rendirá $${\ displaystyle 0 {\ xrightarrow [{f}] {0}} 0} ya que $${\ displaystyle \ Delta _ {0} = 0, \ nabla _ {0} = 0} y $${\ displaystyle \ Delta _ {0} ^ {K} = 0}.
Esto significa que la tupla del cómputo base también se puede hacer XOR en los senderos combinados: $${\ displaystyle S_ {0} \ oplus \ nabla _ {j} {\ xrightarrow [{f}] {K [0,0] \ oplus \ Delta _ {i} ^ {K} \ oplus \ nabla _ {j} ^ {K}}} C_ {0} \ oplus \ Delta _ {i}}

Paso cuatro: es trivial ver que:
$${\ displaystyle S_ {j} = S_ {0} \ oplus \ nabla _ {j}}
$${\ displaystyle K [i, j] = K [0,0] \ oplus \ Delta _ {i} ^ {K} \ oplus \ nabla _ {j} ^ {K}}
$${\ displaystyle C_ {i} = C_ {0} \ oplus \ Delta _ {i}}
Si esto se sustituye en los senderos diferenciales combinados anteriores, el resultado será:
$${\ displaystyle S_ {j} {\ xrightarrow [{f}] {K [i, j]}} C_ {i}}
Lo que es lo mismo que la definición, había anteriormente antes para un biclique:
$${\ displaystyle \ forall i, j: S_ {j} {\ xrightarrow [{f}] {K [i, j]}} C_ {i}}

Por lo tanto, es posible crear una biclique de tamaño $${\ displaystyle 2 ^ {2d}} ($${\ displaystyle 2 ^ {2d}} puesto que todos $${\ displaystyle 2 ^ {d}} teclas del primer conjunto de teclas, se pueden combinar con el $${\ displaystyle 2 ^ {d}}claves del segundo conjunto de claves). Esto significa una biclique de tamaño$${\ displaystyle 2 ^ {2d}} se puede crear usando solo $${\ displaystyle 2 * 2 ^ {d}} cálculos de los diferenciales $${\ displaystyle \ Delta _ {i}} y $${\ displaystyle \ nabla _ {j}} terminado $${\ displaystyle f}. Si$${\ displaystyle \ Delta _ {i} \ neq \ nabla _ {j}} para {\ displaystyle i + j> 0} entonces todas las llaves $${\ displaystyle K [i, j]} También será diferente en el biclique.

Así es como se construye el biclique en el ataque biclique líder en AES. Hay algunas limitaciones prácticas en la construcción de bicliques con esta técnica. Cuanto más larga es la biclique, más rondas tiene que cubrir los senderos diferenciales. Las propiedades de difusión del cifrado, por lo tanto, juegan un papel crucial en la efectividad de la construcción del biclique.

Otras formas de construir el biclique [ editar ]

Bogdanov, Khovratovich y Rechberger también describen otra forma de construir el biclique, llamado 'Intercalar senderos diferenciales de clave relacionada' en el artículo: "Criptoanálisis biclique del AES completo ^[1] ".

Procedimiento de criptoanálisis biclique [ editar ]

Paso uno: el atacante agrupa todas las claves posibles en subconjuntos de claves de tamaño$${\ displaystyle 2 ^ {2d}} para algunos $${\ displaystyle d}, donde la clave en un grupo se indexa como $${\ displaystyle K [i, j]} en una matriz de tamaño $${\ displaystyle 2 ^ {d} \ times 2 ^ {d}}. El atacante divide el cifrado en dos subcifrados,$${\ displaystyle f} y $${\ displaystyle g} (tal que $${\ displaystyle E = f \ circ g}), como en un ataque MITM normal. El conjunto de claves para cada uno de los sub-cifrados es de cardinalidad.$${\ displaystyle 2 ^ {d}}y se llama $${\ displaystyle K [i, 0]} y $${\ displaystyle K [0, j]}. La clave combinada de los subcifrados se expresa con la matriz mencionada anteriormente.$${\ displaystyle K [i, j]}.

Paso dos: el atacante construye un biclique para cada grupo de$${\ displaystyle 2 ^ {2d}}llaves. El biclique es de dimensión-d, ya que mapea$${\ displaystyle 2 ^ {d}} estados internos, $${\ displaystyle S_ {j}}, a $${\ displaystyle 2 ^ {d}} textos cifrados, $${\ displaystyle C_ {i}}, utilizando $${\ displaystyle 2 ^ {2d}}llaves. La sección "Cómo construir el biclique" sugiere cómo construir el biclique usando "Diferenciales independientes de clave relacionada". La biclique se construye en ese caso utilizando los diferenciales del conjunto de teclas,$${\ displaystyle K [i, 0]} y $${\ displaystyle K [0, j]}, perteneciente a los subcifrados.

Paso tres: el atacante toma el$${\ displaystyle 2 ^ {d}} posibles textos cifrados, $${\ displaystyle C_ {i}}, y le pide a un oráculo de descifrado que proporcione los textos claros coincidentes, $${\ displaystyle P_ {i}}.

Paso cuatro: el atacante elige un estado interno,$${\ displaystyle S_ {j}} y el texto plano correspondiente, $${\ displaystyle P_ {i}}y realiza el ataque MITM habitual sobre $${\ displaystyle f} y $${\ displaystyle g} atacando desde el estado interno y el texto sin formato.

Paso cinco: siempre que se encuentre un candidato clave que coincida$${\ displaystyle S_ {j}} con $${\ displaystyle P_ {i}}, esa clave se prueba en otro par de texto plano / cifrado. Si la clave se valida en el otro par, es muy probable que sea la clave correcta.

Ejemplo de ataque [ editar ]

El siguiente ejemplo se basa en el ataque biclique en AES del artículo "Criptoanálisis Biclique del AES completo ^[1] ".
Las descripciones en el ejemplo usan la misma terminología que usaron los autores del ataque (es decir, para nombres de variables, etc.).
Por simplicidad, el ataque a la variante AES128 se trata a continuación.
El ataque consiste en un ataque MITM de 7 rondas con el biclique cubriendo las últimas 3 rondas.

Particionamiento de claves [ editar ]

El espacio clave se divide en $${\ displaystyle 2 ^ {112}} grupos de claves, donde cada grupo consiste en $${\ displaystyle 2 ^ {16}}llaves.
Para cada uno de los$${\ displaystyle 2 ^ {112}} grupos, una clave base única $${\ displaystyle K [0,0]}para el cálculo base está seleccionado.
La clave base tiene dos bytes específicos establecidos en cero, que se muestran en la tabla a continuación (que representa la clave de la misma manera que AES en una matriz 4x4 para AES128):

{\ displaystyle {\ begin {bmatrix} - & - & - & 0 \\ 0 & - & - & - \\ - & - & - & - \\ - & - & - & - \ end {bmatrix}}}

Luego se enumeran los 14 bytes restantes (112 bits) de la clave. Esto produce$${\ displaystyle 2 ^ {112}}teclas base únicas; uno para cada grupo de llaves.
Lo ordinario$${\ displaystyle 2 ^ {16}}Las teclas de cada grupo se eligen con respecto a su clave base. Se eligen de modo que sean casi idénticos a la clave base. Solo varían en 2 bytes (ya sea$${\ displaystyle i}'s o el $${\ displaystyle j}'s) de los siguientes 4 bytes mostrados:

{\ displaystyle {\ begin {bmatrix} - & - & i & i \\ j & - & j & - \\ - & - & - & - \\ - & - & - & - \ end {bmatrix}}}

Esto da $${\ displaystyle 2 ^ {8} K [i, 0]} y $${\ displaystyle 2 ^ {8} K [0, j]}, que combinado da $${\ displaystyle 2 ^ {16}} diferentes llaves, $${\ displaystyle K [i, j]}. estas$${\ displaystyle 2 ^ {16}} Las claves constituyen las claves del grupo para una clave base respectiva.

Construcción biclique [ editar ]

$${\ displaystyle 2 ^ {112}}bicliques se construye utilizando la técnica "Diferenciales independientes de clave relacionada", como se describe en la sección "Cómo construir la biclique".
El requisito para usar esa técnica era que los senderos diferenciales hacia adelante y hacia atrás que debían combinarse no compartían ningún elemento no lineal activo. ¿Cómo se sabe que este es el caso?
Debido a la forma en que se eligen las teclas en el paso 1 en relación con la tecla base, las pistas diferenciales$${\ displaystyle \ Delta _ {i}} usando las teclas $${\ displaystyle K [i, 0]} nunca comparta ningún cuadro S activo (que es el único componente no lineal en AES), con los senderos diferenciales $${\ displaystyle \ nabla _ {j}} usando la llave $${\ displaystyle K [0, j]}. Por lo tanto, es posible XOR los senderos diferenciales y crear el biclique.

Ataque MITM [ editar ]

Cuando se crean los bicliques, el ataque MITM casi puede comenzar. Antes de hacer el ataque MITM, el$${\ displaystyle 2 ^ {d}} valores intermedios del texto sin formato:
$${\ displaystyle P_ {i} {\ xrightarrow [{}] {K [i, 0]}} {\ xrightarrow [{v_ {i}}] {}}},
el$${\ displaystyle 2 ^ {d}} valores intermedios del texto cifrado:
$${\ displaystyle {\ xleftarrow [{v_ {j}}] {}} {\ xleftarrow [{}] {K [0, j]}} S_ {j}},
Y los correspondientes estados intermedios y sub-claves$${\ displaystyle K [i, 0]} o $${\ displaystyle K [0, j]}, sin embargo, se calculan y almacenan previamente.

Ahora el ataque MITM puede llevarse a cabo. Para probar una clave$${\ displaystyle K [i, j]}, solo es necesario recalcular las partes del cifrado, que se sabe que variará entre $${\ displaystyle P_ {i} {\ xrightarrow [{}] {K [i, 0]}} {\ xrightarrow [{v_ {i}}] {}}} y $${\ displaystyle P_ {i} {\ xrightarrow [{}] {K [i, j]}} {\ xrightarrow [{v_ {i}}] {}}}. Para el cálculo hacia atrás desde$${\ displaystyle S_ {j}} a $${\ displaystyle {\ xleftarrow [{v_ {j}}] {}}}, estos son 4 S-boxes que necesitan ser recalculados. Para el cálculo hacia adelante desde$${\ displaystyle P_ {i}} a $${\ displaystyle {\ xrightarrow [{v_ {i}}] {}}}, es solo 3 (se puede encontrar una explicación detallada de la cantidad de recálculo necesario en "Criptoanálisis Biclique del documento completo AES ^[1] ", de donde se toma este ejemplo).

Cuando los valores intermedios coinciden, un candidato clave $${\ displaystyle K [i, j]} Entre $${\ displaystyle P_ {i}} y $${\ displaystyle S_ {j}}es encontrado. El candidato clave se prueba en otro par de texto simple / cifrado.

Resultados [ editar ]

Este ataque reduce la complejidad computacional de AES128 a $${\ displaystyle 2 ^ {126.18}}, que es 3-5 veces más rápido que un enfoque de fuerza bruta. La complejidad de los datos del ataque es$${\ displaystyle 2 ^ {88}} y la complejidad de la memoria es $${\ displaystyle 2 ^ {8}}.