En criptografía , una S-box ( caja de sustitución ) es un componente básico de los algoritmos de clave simétrica que realiza la sustitución. En los cifrados en bloque , normalmente se utilizan para oscurecer la relación entre la clave y el texto cifrado , asegurando así la propiedad de confusión de Shannon . Matemáticamente, una S-box es una función booleana vectorial no lineal [1] . [2]
En general, una S-box toma una cierta cantidad de bits de entrada , m , y los transforma en una cierta cantidad de bits de salida, n , donde n no es necesariamente igual a m . [3] Una caja S m × n se puede implementar como una tabla de búsqueda con 2 m palabras de n bits cada una. Normalmente se utilizan tablas fijas, como en el Estándar de cifrado de datos (DES), pero en algunos cifrados las tablas se generan dinámicamente a partir de la clave (por ejemplo, los algoritmos de cifrado Blowfish y Twofish ).
Un buen ejemplo de tabla fija es la S-box de DES (S 5 ), que asigna una entrada de 6 bits a una salida de 4 bits:
Dada una entrada de 6 bits, la salida de 4 bits se encuentra seleccionando la fila usando los dos bits externos (el primero y el último bit) y la columna usando los cuatro bits internos. Por ejemplo, una entrada " 0 1101 1 " tiene bits externos " 01 " y bits internos "1101"; la salida correspondiente sería "1001". [4]
Cuando DES se publicó por primera vez en 1977, los criterios de diseño de sus S-boxes se mantuvieron en secreto para evitar comprometer la técnica del criptoanálisis diferencial (que aún no era conocida públicamente). Como resultado, la investigación sobre qué hacía que las S-box fueran buenas era escasa en ese momento. Más bien, las ocho cajas S de DES fueron objeto de intenso estudio durante muchos años debido a la preocupación de que se pudiera haber colocado una puerta trasera (una vulnerabilidad conocida sólo por sus diseñadores) en el cifrado. Como las cajas S son la única parte no lineal del cifrado, comprometerlas comprometería todo el cifrado. [5]
Los criterios de diseño de la S-box finalmente se publicaron (en Coppersmith 1994) después del redescubrimiento público del criptoanálisis diferencial, demostrando que habían sido cuidadosamente ajustados para aumentar la resistencia contra este ataque específico de modo que no fuera mejor que la fuerza bruta . Biham y Shamir descubrieron que incluso pequeñas modificaciones en una S-box podrían debilitar significativamente el DES. [6]
Cualquier S-box en la que cualquier combinación lineal de bits de salida se produzca mediante una función doblada de los bits de entrada se denomina S-box perfecta . [7]
Las cajas S se pueden analizar mediante criptoanálisis lineal y criptoanálisis diferencial en forma de tabla de aproximación lineal (LAT) o transformada de Walsh y tabla de distribución de diferencias (DDT) o tabla de autocorrelación y espectro. Su fuerza puede resumirse en la no linealidad (doblada, casi doblada) y la uniformidad diferencial (perfectamente no lineal, casi perfectamente no lineal). [8] [9] [10] [2]