Cajas S-Box

Una Caja de Sustitución o S-Box, es una transformación no lineal implementada como una tabla que hace que las correlaciones entre la clave y el texto cifrado sean complejas (se introduce Confusión), también hablamos de las las cajas P-Box que agregan Difusión, permutando los bits de entrada, ambas se usan en la mayoría de los algoritmos de clave simétrica y también de clave pública. Otro de sus usos es probar los algoritmos de cifrado frente al criptoanálisis diferencial y las transformaciones lineales, obteniéndose como resultado si el algoritmo es fuerte o no.

 

Las Cajas S y P  son la única parte no lineal del cifrado y de ella depende toda la fuerza criptográfica de los algoritmos, es el núcleo de la seguridad, por esta razón, un buen diseño es imperativo.

 

Se denotan como  p * q,  p bits de entrada y q bits de salida, la siguiente tabla muestra una S-Box de 4 bits en hexadecimal, S(x) es la entrada y las distintas Sn(x) son el resultado de la operación:

 

x 0 1 2 3 4 5 6 7 8 9 a b c d e f
S (x) f e b c 6 d 7 8 0 3 9 a 4 2 1 5
S1(x) 1 0 1 0 0 1 1 0 0 1 1 0 0 0 1 1
S2(x) 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 0
S3(x) 1 1 0 1 1 1 1 0 0 0 0 0 1 0 0 1
S4(x) 1 1 1 1 0 1 0 1 0 0 1 1 0 0 0 0

 

Otros ejemplos de utilización:

 

  • DES usa ocho cajas 6 * 4.
  • AES, SAFER y SHARK usan cajas de 8 * 8, con una estructura matemática sobre un campo finito de Galois.
  • Blowfish, CAST, Snefru y SQUARE usan cajas de 8 * 32
  • Snefru utiliza selección al azar de p y q.
  • En la imagen la utilizada en Whirlpool
S- BOX utilizada en Whirlpool
S- BOX utilizada en Whirlpool

 

Debemos tener encuenta que se ha encontrado que las S-Boxes son vehículos potenciales para la inserción de una puerta trasera en un algoritmo asimétrico, algo, en cierta manera insospechado. Kenneth G. Paterson, en 1.999, diseñó una variante de puerta trasera para DES con S-Boxes modificadas. Este año, 2.016, Arnaud Bannier, Nicolas Bodin y Eric Filiol han publicado un refinado del desarollo de Paterson, pueden construir un cifrado de bloque que incorpora una trampa que consiste en asignar una partición del espacio de texto simple a una partición del espacio de texto cifrado. Esta puerta trasera permite recuperar la clave K, con solo un par de textos en claro y sus cifrados y con un esfuerzo 2κ/2 evaluaciones.

 

A partir de ahora las referencias que hacemos a distintos algoritmos, tipos o subtipos están condicionados por sus versiones. Es común que las primeras versiones sean modificadas para mejorarlas, esto hace algunos algoritmos de cifrado tengan cajas estáticas y luego cambien a dinámicas, cambien el número de rondas o el número de bits de entrada y salida.

 

Propiedades.

Las propiedades básicas que deben contener las S y P-Box son la difusión y confusión obtenidas fundamentalmente a través de:

  • La no linealidad (NL, Non-linearity)
  • El Criterio de independencia de bits (BIC,Bit Independence criterion)
  • El criterio de avalancha (AVAL, Avalanche Criteria)
  • El criterio estricto de avalancha (SAC, Strict Avalanche Criteria)
  • Criterio de integridad o completitud (Completeness Criteria).
  • Probabilidad lineal y diferencial. Linear probability (LP) y differential probability (DP)

Las ideas de integridad y el efecto avalancha se introdujeron por primera vez por J.B.Kam y G.I.Davida en 1.979. El concepto SAC lo introducen A.F.Webster y S.E.Tavares en 1.985, que posteriormente determinan el BIC.

 

 

Construcción.

Se pueden construir de dos maneras distintas:

  1. Estática (Pre-definida). No hay relación con la clave de cifrado, por tanto, los contenidos no dependen de ella. La clave se usa solo para cambiar la dirección de S-Box y producirá la misma salida en cada ronda, la consecuencia es que es fácil de criptoanalizar, Camelia o DES.
  2. Dinámica. Tiene relación con la clave y la salida cambia en cada ronda (Blowfisho, Twofish o IDEA). Por lo tanto, es más segura que la consrucción estática, pero más lentas. El S-Box dinámico puede ser generado por un algoritmo generador de secuencias seudoaleatorias.

También se han utilizado otras formas más complejas para construirlas, con funciones booleanas (BF) de 4 bits y de 8 bits, cajas basadas en el Caos y polinomios irreducibles sobre el campo de Galois GF (pq) casi binario. La construcción que más suscita interes son las:

 

Basadas en el Caos. Recientemente se han propuesto muchos métodos para diseñar cajas S basadas en el caos, esto es debido a que los sistemas caóticos producen resultados muy dispares con pequeñas diferencias en las condiciones iniciales del sistema, lo que hace que la predicción a largo plazo de su comportamiento sea imposible de prever.  Algunos de los métodos son:

  • En 2.001 G. Jakimoski y L. Kocarev proponen el primer método para crear cajas S caóticas basado en un mapa caótico exponencial y logístico. El proceso de cuatro pasos se basa en la (N) enésima iteración de un mapa, donde N = 1.000.
  • En 2.005, G. Tang, X. Liao y Y. Chen propusieron un método basado en el mapa de Baker. En este método, al iterar un mapa logístico caótico, se genera una secuencia de 8 bits de variables aleatorias binarias a partir de la obtención de una trayectoria de valor real y la convierten en un entero decimal en el rango de 0-2, obteniendo una tabla de enteros, por último, toman un mapa de Baker y utiliza una permutación dependiente de la clave para barajar la caja.
  • En 2.005 G. Tang y X. Liao, basándose en un mapa caótico-discreto proponen:
    1. Obtener una secuencia entera de forma arbitraria y considerarla como clave K, K = X0 = {1, 2,…, 2n}.
    2. Tomando M = 2n y A, el mapa se itera más de k veces con el valor inicial X0, de aquí podemos obtener una secuencia entera permutada {X}.
    3. Al pasar {X} a una tabla (2n/2 × 2n/2), se obtiene la S-box.
  • En 2.007 G. Chen, Y. Chen, y X. Liao proponen obtener cajas S de 8 × 8 en tres pasos empleando un mapa de Chebyshev y un mapa 3D de Baker. Es una modificación con correcciones del propuesto por G. Tang, X. Liao y Y. Chen en 2.005.
  • En 2.007 M. Asim y V. Jeoti proponen otro basado en la propiedad de mezcla del mapa caótico lineal por partes PLCM (Piecewise Linear Chaotic Map). En este método el rango de salida [0,1 – 0,9] se divide en 256 intervalos de igual longitud. Se etiqueta cada región secuencialmente de 0 a m, donde m es igual a 255. Se iterar el PLCM utilizando una condición inicial. Cuando el PLCM visite una región en particular, se almacena ese número en una caja S.
  • En 2.009, R.Yin, propone un S-box dependiente de la clave basado en la iteración de mapas logísticos caóticos continuos.
  • En 2.010 F. Özkanak y A.B. Özer, proponen un método basado en sistema caótico de Lorenz.
  • En 2.012 Y. Wang, K. Wong, C. Li y Yang Li, proponen un método basado en mapa caótico y algoritmo genético.
  • En 2.012 J. Peng, S. Jin, L. Lei y  R. Jia, proponen un método para generar cajas S basadas en el sistema hipercaótico de Chen. Primero se asigna la clave a la condición inicial y al parámetro de control para el sistema hipercaótico. Luego itera el sistema, Chen, para generar una secuencia hipercaótica que posteriormente se usará para construir la caja S.
  • En 2.013 M. Dara y K. Manochehri, proponen otro método basado en un mapa logístico caótico.
  • En 2.015 F. J. Luma, H. S. Hilal y A. Ekhlas, proponen un método para diseñar cajas de S dependientes de claves dinámicas basadas en un mapa logístico 2D y otro mapa cruzado 2D.

 

Tipos de Cajas.

Es muy frecuente encontrar la denominación “Caja S” para referirse a cualquiera de los dos tipos: de Sustitución o de Permutación. Dentro de ellas hay otra clasificación, según sea el número de bits de salida respecto de la entrada: Si es menor (Compresión), mayor (Expansión) o igual (Recta).


Cajas de sustitución. Las cajas S agregan confusión. Sustituye bits de entrada por bits de la tabla de referencias para obtener la salida, en el supuesto de que solo realicemos esta obtendríamos un cifrado de sustitución. En la tabla siguiente ponemos un ejemplo sencillo de compresión 6 * 4:

 

S-BOX 0
 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
Entrada 0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
Referencias                                
00 0010 1100 0100 0001 0111 1010 1011 0110 1000 0101 0011 1111 1101 0000 1110 1001
01 1110 1011 0010 1100 0100 0111 1101 0001 0101 0000 1111 1010 0011 1001 1000 0110
10 0100 0010 0001 1011 1010 1101 0111 1000 1111 1001 1100 0101 0110 0011 0000 1110
11 1011 1000 1100 0111 0001 1110 0010 1101 0110 1111 0000 1001 1010 0100 0101 0011

 

Elegimos la entrada 6 (0110), esta tiene el último bit de la columna anterior a (1) y el primer bit de la entrada posterior a (0), estas dos son las referencias. Tomamos la referencia 10 y sustituimos el valor de la entrada por el valor correspondiente a la intersección entre la entrada y la referencia, obtenemos 0111.

 

 

Cajas de Permutación. Las cajas P agregan Difusión, permutando los bits de entrada. Sí solo realizamos esta operación, obtendríamos simplemente un cifrado de trasposición. No tiene ningún sentido operar una caja P-Box con solo permutación, para ello se han incorporado cajas S-Box a cada una de las rondas, denominándose al conjunto como Red de sustitución-permutación o SPN (substitution–permutation network), de todas formas a estas las llamaremos P-Box. La P-Box comienza trabajando como una caja S, toma las salidas de todas las cajas S de una ronda, permuta los bits y los introduce en las cajas S de la siguiente ronda, en la última ronda termina con una caja S.

Cajas de Permutación P-BOX Permutation Box

 

Cajas dependientes de la clave.

Los algoritmos para la generación de Cajas S-box dependientes de la clave ( SboxC ), utilizan permutaciones, sin repetición y dependientes de la clave, de los elementos de la caja inicial ( SboxI ). En cualquier caso, el remitente y el destinatario deben conocer las cajas SboxI.

 

Los valores de la tabla inicial SboxI pueden ser los números ordenados o mezclados de longitud n, supongamos de 0 a 255. También suponemos que las cajas se organizan de acuerdo con filas de vectores de tamaño n (256), es decir, la caja de sustitución inicial SboxI (n) y SboxC (n) tienen la misma longitud, n = 0,1,…, 255  vectores de tamaño 256, en el intervalo [0, 255]. En el proceso de cifrado los índices de los vectores SboxI y SboxC se intercambian por sus valores correspondientes.

 

La forma de identificar la calidad de la caja generada se basa en métricas que nos dan la distancia (coeficiente de correlación, es un concepto estadístico) entre SboxI y SboxC. Cuanto mayor sea el valor de la distancia normalizada, más distintas serán SboxI y SboxC, es lo que nos interesa.

 

Distancia de Hamming. La distancia de Hamming (H) entre dos cajas se define como un número de elementos no iguales en las mismas posiciones entre la caja SboxI y la caja SboxC.

 

 

 

 

 La media de la distancia es igual a (N + 1) / 2. La distancia máxima es igual a N. La distancia normalizada se obtiene al dividir la distancia dH por la máxima distancia H:

 

 

Distancia de Kendall. La distancia de Kendall (K) está dada por:

 

 

Esta distancia es igual al número de permutaciones adyacentes por pares requeridas para transformar SboxI en SboxC. La media de la distancia K es igual a N2 / 4. El valor máximo de la distancia K es ( N2 – N) / 2. La distancia normalizada de K se encuentra en el intervalo [0,1] y se define como:

 

En el supuesto de que la distancia K sea 0,20, esto nos indica que el 20% de los pares de elementos entre las SboxI y SboxC difieren.

 

 

Distancia de Pearson. La fórmula del coeficiente de correlación de Pearson (P) es:

 

 

La distancia entre el SboxI y el SboxC se puede reajustar a una medida de distancia del rango [0 – 1] mediante:

 

La distancia entre SboxI y SboxC es dP = 1 si el coeficiente de correlación r es igual a cero. dP = 0 si el coeficiente de correlación r es igual a ±1.

 

 

Distancia de Spearman. La distancia de Spearman (S) es una distancia absoluta entre dos vectores de rango:

S es la suma de las diferencias absolutas entre dos rangos de todos los elementos iguales de SboxI y SboxC. La media de la distancia S es igual a N2 / 3. La distancia S es máxima entre SboxI y SboxI invertido y es igual a N2 / 2 para N par y  (N2 -1)/ 2 para N impar. La distancia normalizada para N par está definida por:

La fórmula utilizada para cuando no hay rangos iguales:

donde d i = diferencia en rangos pareados y n = número de casos. La fórmula a utilizar cuando hay rangos iguales es:

donde i = puntuación del emparejamiento.

 

 

 

Ejemplos básicos, en Java, de coeficientes de correlación.

 

Kendall

Ejemplo Kendall en Java S-BOX

 

 

 

Pearson

 

 

 

Spearman. Ejemplo en hoja de cálculo, datos sin ningún vínculo:

 

SboxI SboxC Rango (SboxI) Rango (SboxC) Dif. Dif. 2 Cálculo
44 33 10 10 0 0
49 60 9 6 3 9
51 56 8 8 0 0
55 62 7 4 3 9
60 62 6 5 1 1
63 53 5 9 4 16
66 57 4 7 3 9
71 70 3 2 1 1
75 64 2 3 1 1
95 84 1 1 0 0
Σ 46