Red de sustitución-permutación

En criptografía , una red SP , o red de sustitución-permutación ( SPN ), es una serie de operaciones matemáticas vinculadas que se utilizan en algoritmos de cifrado por bloques como AES (Rijndael) , 3-Way , Kalyna , Kuznyechik , PRESENT , SAFER , SHARK y Square .

Dicha red toma como entrada un bloque del texto plano y la clave , 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 subbloques de bits de entrada en bits de salida. Es común que estas transformaciones sean operaciones eficientes para su ejecución en hardware, como la operación XOR ( o exclusivo ) y la rotación de bits . La clave se introduce en cada ronda, generalmente en forma de " claves de ronda " derivadas de ella. (En algunos diseños, las propias cajas S dependen de la clave).

El descifrado se realiza simplemente invirtiendo el proceso (utilizando las inversas de las cajas S y P y aplicando las claves de ronda 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 biunívoca para garantizar la invertibilidad (y, por lo tanto, el descifrado). En particular, la longitud de la salida debe ser la misma que la de la entrada (la imagen de la derecha muestra cajas S con 4 bits de entrada y 4 de salida), lo que difiere de las cajas S en general, que también pueden cambiar de longitud, como en el Estándar de Cifrado de Datos (DES), por ejemplo. Una caja S no suele ser simplemente una permutación de los bits. En cambio, en una buena caja S, cada bit de salida se ve afectado por cada bit de entrada. Más precisamente, en una buena caja S, cada bit de salida cambia con una probabilidad del 50 % por cada bit de entrada. Dado que cada bit de salida cambia con una probabilidad del 50 %, aproximadamente la mitad de los bits de salida cambian realmente con un cambio en un bit de entrada (véase el criterio de avalancha estricto ). ^{[ 1 ]}

Una P-box es una permutación de todos los bits: toma las salidas de todas las S-boxes de una ronda, permuta los bits y los introduce en las S-boxes de la siguiente ronda. Una buena P-box tiene la propiedad de que los bits de salida de cualquier S-box se distribuyen a la mayor cantidad posible de entradas de S-boxes.

En cada ronda, la clave de 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í solas no tienen mucha fuerza criptográfica: una caja S podría considerarse un cifrado de sustitución , mientras que una caja P podría considerarse 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 se cambia un bit del texto plano, este se introduce en una caja S, cuya salida cambia en varios bits; luego, la caja P distribuye todos estos cambios entre varias cajas S, por lo que las salidas de todas estas cajas S vuelven a cambiar en varios bits, y así sucesivamente. Al realizar varias rondas, cada bit cambia varias veces de un lado a otro, por lo que, al final, el texto cifrado ha cambiado por completo, de forma pseudoaleatoria . En particular, para un bloque de entrada elegido al azar, si se invierte el i -ésimo bit, la probabilidad de que cambie el j -ésimo bit de salida es aproximadamente la mitad, para cualquier i y j , que es el criterio de avalancha estricto . A la inversa, si se cambia un bit del texto cifrado y luego se intenta descifrarlo, el resultado es un mensaje completamente diferente del texto plano original: los cifrados SP no son fácilmente maleables .
• La razón de la confusión es exactamente la misma que la de la difusión: cambiar un bit de la clave cambia varias de las claves de ronda, y cada cambio en cada clave de ronda se difunde a través de todos los bits, cambiando el texto cifrado de una manera muy compleja.
• Si un atacante consigue de alguna manera un texto plano que corresponda 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 que el atacante recupere la clave.

Aunque una red Feistel que utiliza cajas S (como DES ) es bastante similar a las redes SP, existen algunas diferencias que hacen que una u otra sea más aplicable en ciertas situaciones. Para una cantidad dada de confusión y difusión , una red SP tiene más "paralelismo inherente" ^{[ 2 ]} y, por lo tanto, dado un procesador con muchas unidades de ejecución , puede calcularse más rápido que una red Feistel. ^{[ 3 ]} Los procesadores 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 de Feistel no tienen tal restricción y pueden construirse como funciones unidireccionales .

• Red Feistel
• Cifrado de producto
• Cuadrado (cifrado)
• Algoritmo Internacional de Cifrado de Datos

• Katz, Jonathan; Lindell, Yehuda (2007). Introducción a la criptografía moderna . CRC Press. ISBN 9781584885511.
• Stinson, Douglas R. (2006). Criptografía. Teoría y práctica (Tercera  ed.). Chapman & Hall/CRC. ISBN 1584885084.