Redes de Feistel: cifrar con una función que no se invierte

En la lección anterior vimos que un cifrado de bloque es una familia de permutaciones y que se construye repitiendo rondas. Hablamos de dos arquitecturas, y hoy abrimos la primera: la red de Feistel, la de DES. Su truco es sorprendente. Para descifrar hay que deshacer cada ronda, y parece que para eso la función que mezcla los bits tendría que ser invertible. No hace falta. Veamos por qué, con un ejemplo de 8 bits que cabe en una hoja.

La idea

Parte el bloque en dos mitades, la izquierda $L$ y la derecha $R$. En una ronda ocurre esto:

• La mitad derecha pasa tal cual a ser la nueva mitad izquierda.
• La mitad izquierda se mezcla (XOR) con el resultado de una función $F$ aplicada a la mitad derecha y a la subclave. Eso es la nueva mitad derecha.

Una mitad se queda quieta y la otra cambia. Así, cada ronda protege la mitad que cambia con algo calculado desde la que no cambia. En la ronda siguiente los papeles se intercambian.

La idea clave es que la función $F$ solo se calcula hacia delante. En ningún momento hay que «deshacerla»: se vuelve a calcular con la misma entrada y su resultado se vuelve a sumar con XOR, y como $a\oplus a = 0$, desaparece. Eso es lo que ahorra el diseño: $F$ puede ser tan enrevesada y tan poco invertible como se quiera.

La ronda de Feistel

Sea $(L_{i-1}, R_{i-1})$ el bloque antes de la ronda $i$, con $L$ y $R$ de $n/2$ bits cada una, y sea $K_i$ la subclave de esa ronda. La ronda es

$$L_i = R_{i-1}, \qquad R_i = L_{i-1} \oplus F(R_{i-1}, K_i).$$

La función $F$ se llama función de ronda. Puede ser cualquier cosa que se calcule bien: en DES mezcla cajas S y permutaciones (lección 6); en nuestro ejemplo será mucho más sencilla.

Con $r$ rondas, el bloque de entrada $M = (L_0, R_0)$ llega hasta $(L_r, R_r)$. (Escribimos el mensaje y el criptograma de un bloque en mayúscula, $M$ y $C$, como hace el estándar de DES; en las lecciones de DES, donde $C_i$ nombra mitades de la clave, el criptograma será $c$.) En DES (y aquí) la salida es el bloque con las mitades intercambiadas:

$$C = R_r \, L_r .$$

La razón de ese intercambio final se ve enseguida: hace que descifrar sea exactamente lo mismo que cifrar.

Por qué se puede invertir

Mira la ronda desde el final. Conocemos $(L_i, R_i)$ y la subclave $K_i$. Como $L_i = R_{i-1}$, ya tenemos $R_{i-1}$. Y de la segunda ecuación, sumando $F(R_{i-1}, K_i)$ en los dos lados:

$$R_{i-1} = L_i, \qquad L_{i-1} = R_i \oplus F(L_i, K_i).$$

Solo hemos calculado $F$ hacia delante, con una entrada que ya conocemos. No hace falta invertir $F$. Por eso toda ronda de Feistel es una permutación de los bloques, sea cual sea $F$.

Descifrar es cifrar con las subclaves al revés

Supón que has cifrado con $K_1,\dots,K_r$ y obtenido $C = R_r L_r$. Para descifrar metes $C$ en la misma máquina, pero con las subclaves en orden $K_r, K_{r-1},\dots,K_1$. En la primera ronda de descifrado el bloque de entrada es $(L, R) = (R_r, L_r)$. Ojo: ahora la mitad izquierda de la entrada es $R_r$ y la derecha es $L_r$, así que $F$ se calcula sobre $L_r$. Aplicamos la ronda:

$$\text{nueva } L = L_r, \qquad \text{nueva } R = R_r \oplus F(L_r, K_r) = L_{r-1}.$$

(Usamos que $R_r = L_{r-1} \oplus F(R_{r-1}, K_r)$ y $R_{r-1} = L_r$.) El resultado es $(L_r, L_{r-1}) = (R_{r-1}, L_{r-1})$, es decir, el bloque de la ronda anterior con las mitades intercambiadas. Cada ronda de descifrado deshace una ronda de cifrado, y al acabar queda $(R_0, L_0)$. El intercambio final lo devuelve a $L_0R_0 = M$.

Esto tiene una ventaja práctica enorme: el mismo circuito (o el mismo programa) sirve para cifrar y descifrar. Solo cambia el orden de las subclaves.

Ejemplo resuelto

Usamos un Feistel de juguete con bloques de 8 bits, mitades $L$, $R$ de 4 bits y 3 rondas. La función de ronda es

$$F(R, K) = S(R \oplus K),$$

donde $S$ es la caja S de 4 bits de PRESENT, la de la lección anterior:

$$S = (\texttt{C},\texttt{5},\texttt{6},\texttt{B},\texttt{9},\texttt{0},\texttt{A},\texttt{D},\texttt{3},\texttt{E},\texttt{F},\texttt{8},\texttt{4},\texttt{7},\texttt{1},\texttt{2}).$$

(La entrada $x$, de 0 a 15, se sustituye por la posición $x$ de la lista.) Las subclaves son $K_1 = 1010$, $K_2 = 0111$ y $K_3 = 1100$. El mensaje es $M = 1011\,0010$, es decir, $L_0 = 1011$ y $R_0 = 0010$.

Cifrar

Ronda 1 ($K_1 = 1010$).

• $R_0 \oplus K_1 = 0010 \oplus 1010 = 1000$, que es el 8. $S(8) = \texttt{3} = 0011$. Luego $F = 0011$.
• $L_1 = R_0 = 0010$.
• $R_1 = L_0 \oplus F = 1011 \oplus 0011 = 1000$.

Ronda 2 ($K_2 = 0111$).

• $R_1 \oplus K_2 = 1000 \oplus 0111 = 1111$, que es el 15. $S(15) = \texttt{2} = 0010$. Luego $F = 0010$.
• $L_2 = R_1 = 1000$.
• $R_2 = L_1 \oplus F = 0010 \oplus 0010 = 0000$.

Ronda 3 ($K_3 = 1100$).

• $R_2 \oplus K_3 = 0000 \oplus 1100 = 1100$, que es el 12. $S(12) = \texttt{4} = 0100$. Luego $F = 0100$.
• $L_3 = R_2 = 0000$.
• $R_3 = L_2 \oplus F = 1000 \oplus 0100 = 1100$.

Hemos llegado a $(L_3, R_3) = (0000, 1100)$. Con el intercambio final:

$$C = R_3 L_3 = 1100\,0000.$$

Descifrar

Metemos $C = 1100\,0000$ como $(L,R) = (1100, 0000)$ y usamos las subclaves al revés: $K_3, K_2, K_1$.

Ronda con $K_3 = 1100$. $R \oplus K = 0000 \oplus 1100 = 1100$ (el 12), $F = S(12) = 0100$. Nueva $L = R = 0000$; nueva $R = 1100 \oplus 0100 = 1000$. Queda $(0000, 1000)$.

Ronda con $K_2 = 0111$. $1000 \oplus 0111 = 1111$ (el 15), $F = S(15) = 0010$. Nueva $L = 1000$; nueva $R = 0000 \oplus 0010 = 0010$. Queda $(1000, 0010)$.

Ronda con $K_1 = 1010$. $0010 \oplus 1010 = 1000$ (el 8), $F = S(8) = 0011$. Nueva $L = 0010$; nueva $R = 1000 \oplus 0011 = 1011$. Queda $(0010, 1011)$.

Con el intercambio final: $1011\,0010 = M$. Recuperamos el mensaje. Observa que aparecen las mismas $F$ (0100, 0010, 0011) que al cifrar, en orden inverso.

Como cada ronda es una permutación, el conjunto de las tres rondas también lo es: este cifrado de juguete permuta los 256 bloques de 8 bits (comprobado calculando los 256 resultados). Pero por supuesto es de mentira: con 8 bits de bloque y 12 de clave se rompe en un instante. DES usa los mismos ingredientes, a lo grande.

Una sola ronda no sirve

Fíjate en que la mitad izquierda de la salida de una ronda es la mitad derecha de la entrada, sin tocar. Con una ronda, la mitad del criptograma es un trozo del mensaje a la vista. El ejercicio 1 lo desarrolla. Por eso se encadenan varias rondas (DES usa 16): así cada bit acaba influyendo en todos los demás.

Ejercicios

Ejercicio 1

Considera una sola ronda de Feistel, sin el intercambio final, con subclave $K$ y cualquier función $F$. Prueba que la mitad izquierda de la salida es la mitad derecha de la entrada y explica qué debilidad supone para Eva. Compruébalo con $M = 1110\,0101$ y $K = 1010$ usando la $F$ del ejemplo. Después ponte en el lugar de Eva: conoce $M$ y la salida, pero no $K$. ¿Puede averiguar $K$?

Ver la solución

La salida es $(L_1, R_1) = (R_0, L_0 \oplus F(R_0, K))$. Por definición, $L_1 = R_0$: es la mitad derecha de la entrada, tal cual. La debilidad: Eva ve en claro la mitad derecha del mensaje con solo mirar el criptograma. Además, el resto del cifrado es $R_1 = L_0 \oplus F(R_0,K)$, y como Eva conoce $R_0$, solo queda un XOR con algo que depende de la subclave. Por eso se encadenan varias rondas.

Con $M = 1110\,0101$ y $K = 1010$: $R_0 \oplus K = 0101 \oplus 1010 = 1111$ (el 15), $F = S(15) = \texttt{2} = 0010$, $R_1 = 1110 \oplus 0010 = 1100$. La salida es $(L_1, R_1) = (0101, 1100)$, es decir $0101\,1100$. La mitad izquierda $0101$ coincide con $R_0$.

Eva sí puede averiguar $K$. De $R_1 = L_0 \oplus F$ saca $F = L_0 \oplus R_1 = 1110 \oplus 1100 = 0010$. En la lista de $S$, el $\texttt{2}$ está en la posición 15, así que $R_0 \oplus K = 1111$, y como conoce $R_0 = 0101$, obtiene $K = 0101 \oplus 1111 = 1010$. Con una ronda y esta $F$, un solo par (mensaje, salida) delata la subclave.

Ejercicio 2

Cifra con el Feistel de juguete (mismas tres subclaves $K_1 = 1010$, $K_2 = 0111$, $K_3 = 1100$) el mensaje $M = 0110\,1101$ y descífralo después.

Ver la solución

Aquí $L_0 = 0110$ y $R_0 = 1101$.

Ronda 1 ($K_1 = 1010$): $R_0 \oplus K_1 = 1101\oplus 1010 = 0111$ (el 7), $F = S(7) = \texttt{D} = 1101$. $L_1 = 1101$, $R_1 = 0110 \oplus 1101 = 1011$.

Ronda 2 ($K_2 = 0111$): $R_1 \oplus K_2 = 1011 \oplus 0111 = 1100$ (el 12), $F = S(12) = \texttt{4} = 0100$. $L_2 = 1011$, $R_2 = 1101 \oplus 0100 = 1001$.

Ronda 3 ($K_3 = 1100$): $R_2 \oplus K_3 = 1001 \oplus 1100 = 0101$ (el 5), $F = S(5) = \texttt{0} = 0000$. $L_3 = 1001$, $R_3 = 1011 \oplus 0000 = 1011$.

Con el intercambio, $C = R_3 L_3 = 1011\,1001$ (en hexadecimal, $\texttt{B9}$).

Descifrado: entra $(L,R) = (1011, 1001)$ con $K_3, K_2, K_1$.

• $K_3 = 1100$: $1001\oplus 1100 = 0101$, $F = 0000$. Queda $(1001,\ 1011\oplus 0000) = (1001, 1011)$.
• $K_2 = 0111$: $1011\oplus 0111 = 1100$, $F = 0100$. Queda $(1011,\ 1001\oplus 0100) = (1011, 1101)$.
• $K_1 = 1010$: $1101\oplus 1010 = 0111$, $F = 1101$. Queda $(1101,\ 1011\oplus 1101) = (1101, 0110)$.

Intercambiando: $0110\,1101 = M$.

Ejercicio 3

Usa ahora la función $F(R, K) = R \wedge K$ (AND bit a bit), con $K = 1010$. Esta $F$ no es invertible como función de $R$: hay valores de $R$ distintos con la misma $F$. Comprueba, con una ronda de Feistel, que aun así los bloques $0000\,0000$ y $0000\,0101$ se envían a bloques distintos, y que se puede recuperar la entrada de $0111\,1001$ sabiendo que es la salida de una ronda (sin intercambio final).

Ver la solución

Con $K = 1010$, $R \wedge K$ vale $0000$ para $R = 0000, 0001, 0100$ y $0101$: cuatro entradas distintas con la misma salida, luego $F$ no es inyectiva.

Una ronda es $(L, R) \mapsto (R,\ L\oplus F(R,K))$.

• Bloque $0000\,0000$: $L = 0000$, $R = 0000$, $F = 0000$. Salida $(0000, 0000\oplus 0000) = 0000\,0000$.
• Bloque $0000\,0101$: $L = 0000$, $R = 0101$, $F = 0101 \wedge 1010 = 0000$. Salida $(0101, 0000) = 0101\,0000$.

Las salidas son distintas, porque la mitad $R$ de la entrada se conserva en la izquierda.

Para invertir una salida $(L_1, R_1) = (0111, 1001)$: $R_0 = L_1 = 0111$ y $L_0 = R_1 \oplus F(L_1, K) = 1001 \oplus (0111\wedge 1010) = 1001 \oplus 0010 = 1011$. La entrada era $1011\,0111$. Comprobación: con $L_0 = 1011$ y $R_0 = 0111$, $F = 0010$ y $R_1 = 1011 \oplus 0010 = 1001$. Es correcto.

En resumen

• Una ronda de Feistel parte el bloque en $(L, R)$ y hace $L_i = R_{i-1}$, $R_i = L_{i-1} \oplus F(R_{i-1}, K_i)$.
• Siempre se puede invertir, aunque $F$ no sea invertible: $L_{i-1} = R_i \oplus F(L_i, K_i)$.
• Descifrar es cifrar con las subclaves en orden inverso, gracias al intercambio final de las mitades.
• Con una sola ronda, la mitad izquierda de la salida es la derecha de la entrada: hacen falta varias rondas (DES usa 16).
• DES es una red de Feistel; AES, en cambio, es una red de sustitución-permutación.

Siguiente lección: DES visto desde arriba