La función f de DES y sus cajas S

En la lección anterior vimos el esqueleto de DES: la permutación inicial, 16 rondas de Feistel y la final. Dejamos una caja negra, la función $f(R, K_i)$, que toma 32 bits y una subclave de 48 y devuelve 32 bits. Hoy la abrimos. Es ahí donde DES tiene su confusión: la no linealidad de todo el cifrado sale de unas pocas tablas, las cajas S.

Seguimos con el ejemplo del hilo, con la ronda 1 hecha a mano de principio a fin. Las subclaves, por ahora, nos las dan hechas: en la lección 7 veremos cómo salen.

La idea

Una red de Feistel puede usar como $f$ cualquier función, sin que tenga que ser invertible. DES elige una que mezcla bien en cuatro etapas:

1. Expansión $E$. Los 32 bits de $R$ se convierten en 48, repitiendo algunos.
2. Mezcla con la clave. Se hace XOR con la subclave $K_i$ de 48 bits.
3. Cajas S. Los 48 bits se parten en ocho trozos de 6 bits, y cada trozo pasa por una tabla que lo cambia por 4 bits. Salen $8\times 4 = 32$ bits.
4. Permutación $P$. Los 32 bits se reordenan.

Solo la etapa 3 es no lineal. Las otras tres (expandir, hacer XOR con la subclave y permutar) son lineales o afines sobre $\mathbb{F}_2$. Lineal quiere decir que respeta el XOR, $T(x\oplus y) = T(x)\oplus T(y)$; afín, que es lineal más una constante, como cuando se suma la subclave fija. Por eso las cajas S son lo más importante de DES.

Las cuatro etapas

Expansión $E$

$E$ es una lista de 48 posiciones: el bit $j$ de la salida es el bit $E[j]$ de la entrada. Por filas de 6, que luego serán las entradas de las ocho cajas:

32	1	2	3	4	5
4	5	6	7	8	9
8	9	10	11	12	13
12	13	14	15	16	17
16	17	18	19	20	21
20	21	22	23	24	25
24	25	26	27	28	29
28	29	30	31	32	1

La regla es sencilla. Se parte $R$ en ocho bloques de 4 bits. A cada bloque se le añade, por la izquierda, el último bit del bloque anterior, y por la derecha el primer bit del bloque siguiente (el primer bloque toma el bit 32 y el último, el bit 1: se da la vuelta). Así, 16 bits de $R$ aparecen dos veces.

XOR con la subclave

Es la única etapa donde entra la clave: $E(R)\oplus K_i$, con 48 bits cada uno.

Las ocho cajas S

Cada caja S (de substitution box) $S_1,\dots,S_8$ es una tabla de 4 filas por 16 columnas, con números del 0 al 15. Recibe 6 bits $b_1b_2b_3b_4b_5b_6$ y devuelve un número de 4 bits. Cómo se lee:

• La fila la forman los bits extremos $b_1b_6$, leídos en binario (de 0 a 3).
• La columna la forman los cuatro bits centrales $b_2b_3b_4b_5$, leídos en binario (de 0 a 15).
• El número que está en esa casilla, escrito en 4 bits, es la salida.

Esta es la caja $S_1$ completa. Para que se vea en el móvil la hemos transpuesto: cada fila de la tabla es una columna de la caja.

columna	fila 0	fila 1	fila 2	fila 3
0	14	0	4	15
1	4	15	1	12
2	13	7	14	8
3	1	4	8	2
4	2	14	13	4
5	15	2	6	9
6	11	13	2	1
7	8	1	11	7
8	3	10	15	5
9	10	6	12	11
10	6	12	9	3
11	12	11	7	14
12	5	9	3	10
13	9	5	10	0
14	0	3	5	6
15	7	8	0	13

Las otras siete cajas, $S_2,\dots,S_8$, tienen la misma forma y están en el apéndice 1 de FIPS 46-3 (enlace en las fuentes). Cada fila de cada caja contiene los números del 0 al 15 una sola vez. Eso significa que, fijados los dos bits extremos, la caja es una permutación de los 16 valores de los cuatro bits centrales.

Permutación $P$

Es la lista de 32 posiciones siguiente, por filas de 4:

16	7	20	21
29	12	28	17
1	15	23	26
5	18	31	10
2	8	24	14
32	27	3	9
19	13	30	6
22	11	4	25

Su misión es repartir los 4 bits de salida de cada caja entre varias cajas de la ronda siguiente. Por ejemplo, los cuatro bits que salen de $S_1$ van a las posiciones 9, 17, 23 y 31 de $f$, muy separadas entre sí.

Ejemplo resuelto

Calculamos la ronda 1 del ejemplo de la lección 5: $K = \texttt{133457799BBCDFF1}$, $M = \texttt{0123456789ABCDEF}$. Allí obtuvimos $R_0 = \texttt{F0AAF0AA}$. La primera subclave (se calcula en la lección 7) es $K_1 = \texttt{1B02EFFC7072}$.

Paso 1: $R_0$ en bits. $R_0 = 1111\,0000\,1010\,1010\,1111\,0000\,1010\,1010$.

Paso 2: expansión. Bloque a bloque, añadimos el vecino de cada lado:

bloque de $R_0$	vecino izq.	vecino der.	resultado
$1111$	$0$ (bit 32)	$0$	$011110$
$0000$	$1$	$1$	$100001$
$1010$	$0$	$1$	$010101$
$1010$	$0$	$1$	$010101$
$1111$	$0$	$0$	$011110$
$0000$	$1$	$1$	$100001$
$1010$	$0$	$1$	$010101$
$1010$	$0$	$1$	$010101$

Así,

$$\begin{gathered} E(R_0) = 011110\ 100001\ 010101\ 010101 \\ 011110\ 100001\ 010101\ 010101. \end{gathered}$$

Paso 3: XOR con $K_1$. $K_1$ en grupos de 6 bits es

$$\begin{gathered} 000110\ 110000\ 001011\ 101111 \\ 111111\ 000111\ 000001\ 110010. \end{gathered}$$

Hacemos XOR bloque a bloque:

bloque	$E(R_0)$	$K_1$	XOR
1	$011110$	$000110$	$011000$
2	$100001$	$110000$	$010001$
3	$010101$	$001011$	$011110$
4	$010101$	$101111$	$111010$
5	$011110$	$111111$	$100001$
6	$100001$	$000111$	$100110$
7	$010101$	$000001$	$010100$
8	$010101$	$110010$	$100111$

Paso 4: las cajas S. Cada bloque de 6 bits $b_1\dots b_6$ da la fila $b_1b_6$ y la columna $b_2b_3b_4b_5$:

caja	entrada	fila	columna	valor	salida
$S_1$	$011000$	0	12	5	$0101$
$S_2$	$010001$	1	8	12	$1100$
$S_3$	$011110$	0	15	8	$1000$
$S_4$	$111010$	2	13	2	$0010$
$S_5$	$100001$	3	0	11	$1011$
$S_6$	$100110$	2	3	5	$0101$
$S_7$	$010100$	0	10	9	$1001$
$S_8$	$100111$	3	3	7	$0111$

Para comprobar las otras siete necesitas sus tablas, del apéndice 1 de FIPS 46-3. Como muestra, la fila 1 de $S_2$ es

$$3,\ 13,\ 4,\ 7,\ 15,\ 2,\ 8,\ 14,\\ 12,\ 0,\ 1,\ 10,\ 6,\ 9,\ 11,\ 5$$

y en su columna 8 está el 12 de la tabla.

Comprobemos la primera con la tabla de arriba. La entrada es $011000$: los bits extremos son $0$ y $0$, así que la fila es 0. Los cuatro centrales son $1100$, que es la columna 12. En la tabla de $S_1$, columna 12, fila 0: el valor es 5, que es $0101$. Para $S_4$, la entrada $111010$ tiene bits extremos $1$ y $0$ (fila $10_2 = 2$) y centrales $1101$ (columna 13).

Juntamos las ocho salidas:

$$0101\ 1100\ 1000\ 0010\ \ 1011\ 0101\ 1001\ 0111.$$

Paso 5: permutación $P$. Reordenamos esos 32 bits con la tabla $P$ y sale

$$\begin{gathered} f(R_0,K_1) = 0010\ 0011\ 0100\ 1010 \\ 1010\ 1001\ 1011\ 1011 = \texttt{234AA9BB}. \end{gathered}$$

Paso 6: cerrar la ronda. $R_1 = L_0\oplus f = \texttt{CC00CCFF}\oplus\texttt{234AA9BB} = \texttt{EF4A6544}$ y $L_1 = R_0 = \texttt{F0AAF0AA}$, como en la lección anterior.

Por qué las cajas S no son lineales

Imagina que las cajas S fueran lineales, es decir, que cumplieran $S(x\oplus y) = S(x)\oplus S(y)$. Entonces $E$, el XOR con la clave, las cajas y $P$ serían todas lineales sobre $\mathbb{F}_2$ (vistas como funciones del mensaje y de la clave a la vez). Todo DES sería una función lineal de la clave y del mensaje, y la clave sería la solución de un sistema de ecuaciones lineales. Eva lo resolvería con unos cuantos pares (mensaje, criptograma) conocidos, con eliminación gaussiana (el método de bachillerato para resolver sistemas de ecuaciones, pero sumando módulo 2), y no habría seguridad alguna.

Las cajas S rompen eso. Es el único sitio de DES donde $S(x\oplus y)\neq S(x)\oplus S(y)$ (el ejercicio 2 lo comprueba con $S_1$). Y están diseñadas con cuidado: las filas son permutaciones, y cambiar un solo bit de la entrada de una caja cambia al menos dos bits de su salida (lo comprobamos para las ocho cajas con un programa).

Criptoanálisis diferencial y lineal

Cuando DES era ya un estándar, aparecieron dos técnicas generales para atacar este tipo de cifrados:

• Criptoanálisis diferencial (Biham y Shamir, 1990-1991): estudia cómo una diferencia $\Delta = x\oplus x'$ entre dos entradas se propaga a la diferencia de las salidas, y qué diferencias de salida son más probables que otras. Las cajas S son lo que decide cuánto se puede aprovechar eso. Don Coppersmith contó en 1994 que IBM ya conocía esta técnica en 1974 y que los criterios de diseño de las cajas S se habían elegido para resistirla.
• Criptoanálisis lineal (Matsui, 1993): busca aproximaciones lineales de las cajas S, relaciones entre bits de entrada y de salida que se cumplen con probabilidad algo distinta de $1/2$, y las encadena a lo largo de las rondas.

Los detalles técnicos de estos ataques quedan fuera del curso. Lo que importa aquí es la idea: todo lo que un cifrado de bloque tenga de aproximadamente lineal o de demasiado regular en sus cajas S es una puerta para Eva. Con todo, DES no cayó por estos ataques, sino por su clave corta, como veremos en la lección 8.

Ejercicios

Ejercicio 1

Con la tabla de $S_1$, calcula $S_1(011011)$, $S_1(101110)$ y $S_1(111111)$ (da la fila, la columna y la salida en 4 bits).

Ver la solución

• $011011$: bits extremos $0$ y $1$, fila $01_2 = 1$. Centrales $1101$, columna 13. En la fila 1, columna 13 está el 5: salida $0101$.
• $101110$: extremos $1$ y $0$, fila $10_2 = 2$. Centrales $0111$, columna 7. Fila 2, columna 7: el 11, salida $1011$.
• $111111$: extremos $1$ y $1$, fila 3. Centrales $1111$, columna 15. Fila 3, columna 15: el 13, salida $1101$.

Ejercicio 2

Comprueba que $S_1$ no es lineal: toma $x = 000001$ e $y = 000010$ y compara $S_1(x\oplus y)$ con $S_1(x)\oplus S_1(y)$.

Ver la solución

Para $x = 000001$: fila $01_2=1$, columna 0, valor 0. Para $y = 000010$: fila 0, columna $0001 = 1$, valor 4. Para $x\oplus y = 000011$: fila 1, columna 1, valor 15.

Por otra parte, $S_1(x)\oplus S_1(y) = 0\oplus 4 = 4$ (en binario, $0000\oplus 0100 = 0100$). Como $15\neq 4$, $S_1(x\oplus y)\neq S_1(x)\oplus S_1(y)$: la caja no es lineal. Basta una sola pareja para saberlo.

Ejercicio 3

¿Qué bits de $R$ aparecen dos veces en $E(R)$? ¿En qué cajas S entra el bit 4 de $R$? ¿Y el bit 32?

Ver la solución

Dieciséis bits aparecen dos veces: son el primero y el último de cada bloque de 4, es decir, los bits 1, 4, 5, 8, 9, 12, 13, 16, 17, 20, 21, 24, 25, 28, 29 y 32. Los otros 16 (los dos centrales de cada bloque) aparecen una sola vez. En total, $16\cdot 2 + 16 = 48$.

El bit 4 de $R$ está en las posiciones 5 y 7 de $E(R)$. La posición 5 es el penúltimo bit de la entrada de $S_1$ (el bloque 1 son las posiciones 1 a 6), y es uno de los centrales. La posición 7 es el primer bit de la entrada de $S_2$, un bit extremo, que elige fila. El bit 32 está en las posiciones 1 y 47: el primer bit de $S_1$ (extremo) y el penúltimo de $S_8$ (central).

Es lo que hace la expansión: un bit de $R$ influye en dos cajas S vecinas, lo que acelera la difusión.

En resumen

• $f(R,K_i)$ = expansión $E$ (32 a 48 bits), XOR con la subclave, ocho cajas S (6 a 4 bits) y permutación $P$.
• Una caja S se lee con los bits extremos como fila y los cuatro centrales como columna.
• Las cajas S son lo único no lineal de DES. Si no, todo el cifrado sería un sistema lineal sobre $\mathbb{F}_2$.
• La ronda 1 del ejemplo da $f = \texttt{234AA9BB}$ y $R_1 = \texttt{EF4A6544}$.
• Los criptoanálisis diferencial (Biham y Shamir) y lineal (Matsui) estudian cómo se comportan las cajas S.

Siguiente lección: Las subclaves de DES