Red SP
En criptografía, una red SP, o red de sustitución-permutación (SPN), es una serie de operaciones matemáticas enlazadas que se utilizan en algoritmos de cifrado por bloques como AES (Rijndael), 3-Way, Kalyna, Kuznyechik, PRESENT, SAFER, SHARK y Square.
Una red de este tipo toma un bloque del texto plano y la clave como entradas, y aplica varias "rondas" o "capas" alternas de cajas de sustitución (cajas S) y cajas de permutación (cajas P) para producir el bloque de texto cifrado. Las cajas S y P transforman los (sub)bloques de bits de entrada en bits de salida. Es habitual que estas transformaciones sean operaciones eficientes de realizar en el hardware, como el or exclusivo (XOR) y la rotación a nivel de bits. La clave se introduce en cada ronda, normalmente en forma de "claves de ronda" derivadas. (En algunos diseños, las propias cajas S dependen de la clave).
El descifrado se realiza simplemente invirtiendo el proceso (utilizando los inversos de las cajas S y P y aplicando las claves redondas en orden inverso).
Una caja S sustituye un pequeño bloque de bits (la entrada de la caja S) por otro bloque de bits (la salida de la caja S). Esta sustitución debe ser uno a uno, para garantizar la invertibilidad (y por tanto el descifrado). En particular, la longitud de la salida debe ser la misma que la de la entrada (la imagen de la derecha tiene cajas S con 4 bits de entrada y 4 de salida), lo que es diferente de las cajas S en general que también podrían cambiar la longitud, como en el DES (Data Encryption Standard), por ejemplo. Una caja S no suele ser simplemente una permutación de los bits. Más bien, una buena caja S tendrá la propiedad de que al cambiar un bit de entrada cambiará aproximadamente la mitad de los bits de salida (o un efecto de avalancha). También tendrá la propiedad de que cada bit de salida dependerá de cada bit de entrada.
Una caja P es una permutación de todos los bits: 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. Una buena caja P tiene la propiedad de que los bits de salida de cualquier caja S se distribuyen en el mayor número posible de entradas de caja S.
En cada ronda, la clave de la ronda (obtenida a partir de la clave con algunas operaciones simples, por ejemplo, utilizando cajas S y cajas P) se combina utilizando alguna operación de grupo, normalmente XOR.
Una sola caja S típica o una sola caja P por sí sola no tiene mucha fuerza criptográfica: una caja S podría considerarse como un cifrado de sustitución, mientras que una caja P podría considerarse como un cifrado de transposición. Sin embargo, una red SP bien diseñada con varias rondas alternas de cajas S y P ya satisface las propiedades de confusión y difusión de Shannon:
- La razón de la difusión es la siguiente: Si uno cambia un bit del texto plano, entonces se introduce en una caja S, cuya salida cambiará en varios bits, luego todos estos cambios son distribuidos por la caja P entre varias cajas S, por lo que las salidas de todas estas cajas S vuelven a cambiar en varios bits, y así sucesivamente. Haciendo varias rondas, cada bit cambia varias veces de ida y vuelta, por lo tanto, al final, el texto cifrado ha cambiado completamente, de manera pseudo-aleatoria. En particular, para un bloque de entrada elegido al azar, si se invierte el i-ésimo bit, la probabilidad de que el j-ésimo bit de salida cambie es aproximadamente la mitad, para cualquier i y j, lo que constituye el Criterio de Avalancha Estricto. A la inversa, si se cambia un bit del texto cifrado y se intenta descifrarlo, el resultado es un mensaje completamente diferente del texto plano original.
- La razón de la confusión es exactamente la misma que la de la difusión: el cambio de un bit de la clave cambia varias de las claves de la ronda, y cada cambio en cada clave de la ronda se difunde sobre todos los bits, cambiando el texto cifrado de una manera muy compleja.
- Incluso si un atacante obtiene de algún modo un texto plano correspondiente a un texto cifrado -un ataque de texto plano conocido o, peor aún, un ataque de texto plano elegido o de texto cifrado elegido-, la confusión y la difusión dificultan la recuperación de la clave por parte del atacante.
Aunque un grafo Feistel que utiliza cajas S (como el DES) es bastante similar a los grafos SP, existen algunas diferencias que hacen que uno u otro sean más aplicables en determinadas situaciones. Para una cantidad dada de confusión y difusión, una red SP tiene más "paralelismo inherente" y por ello -dada una CPU con muchas unidades de ejecución- puede calcularse más rápido que una red Feistel. Las CPU con pocas unidades de ejecución -como la mayoría de las tarjetas inteligentes- no pueden aprovechar este paralelismo inherente. Además, los cifrados SP requieren que las cajas S sean invertibles (para realizar el descifrado); las funciones internas Feistel no tienen esa restricción y pueden construirse como funciones unidireccionales.
