En criptografía , una S-box ( substitution-box ) es un componente básico de los algoritmos de clave simétrica que realiza la sustitución. En los cifrados por bloques , se utilizan normalmente para ocultar la relación entre la clave y el texto cifrado , garantizando 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 S-box 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 una tabla fija es la caja S 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 obtiene seleccionando la fila que utiliza los dos bits externos (el primero y el último) y la columna que utiliza 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 cajas S se mantuvieron en secreto para evitar comprometer la técnica del criptoanálisis diferencial (que aún no era de conocimiento público). Como resultado, la investigación sobre qué hacía que las cajas S fueran buenas era escasa en ese momento. En cambio, las ocho cajas S de DES fueron objeto de un intenso estudio durante muchos años debido a la preocupación de que se pudiera haber introducido una puerta trasera (una vulnerabilidad que solo conocían sus diseñadores) en el cifrado. Como las cajas S son la única parte no lineal del cifrado, comprometerlas comprometería el cifrado completo. [5]
Los criterios de diseño de la S-box se publicaron finalmente (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 a una S-box podían debilitar significativamente el DES. [6]
Cualquier S-box donde cualquier combinación lineal de bits de salida se produce 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 fortaleza se puede resumir en la no linealidad (curvada, casi curvada) y uniformidad diferencial (perfectamente no lineal, casi perfectamente no lineal). [8] [9] [10] [2]