DES visto desde arriba: 16 rondas de Feistel

En la lección anterior montamos una red de Feistel de juguete con bloques de 8 bits y tres rondas. Ahora pasamos a la de verdad. Es el cifrado que reinó dos décadas como estándar: DES (Data Encryption Standard). En el relato del curso, DES es el primer cifrado de bloque con el que Alicia puede mandar datos a Bernardo sin que Eva los lea, siempre que ella no pruebe todas las claves. Esa última condición será la causa de su caída, pero eso llegará en la lección 8.

Hoy vemos DES desde arriba: qué es, de dónde sale y cómo encajan sus piezas. La función $f$ de cada ronda y las subclaves quedan para las lecciones 6 y 7. Con eso, y con un ejemplo completo calculado de principio a fin, tendrás el mapa entero.

La idea

DES es una red de Feistel de 16 rondas. Toma un bloque de 64 bits y una clave, y devuelve otro bloque de 64 bits. Dentro, hace lo mismo que el juguete de la lección 4: parte el bloque en dos mitades de 32 bits, $L$ y $R$, y en cada ronda mezcla una mitad con una función de la otra.

Hay tres diferencias con el juguete. Los bloques son de 64 bits, así que $2^{64}$ bloques posibles. La función $f$ es mucho más elaborada: expande, mezcla con la clave, pasa por ocho cajas S y permuta. Y la clave no se usa tal cual: de ella salen 16 subclaves $K_1,\dots,K_{16}$, una por ronda.

Además, antes de la primera ronda y después de la última hay una permutación fija de los 64 bits. No añade seguridad criptográfica (cualquiera puede deshacerla, no lleva clave), pero está en el estándar y hay que respetarla para obtener los mismos criptogramas que todo el mundo.

Un poco de historia

A principios de los años setenta, la agencia estadounidense NBS (National Bureau of Standards, hoy NIST) buscaba un cifrado común para proteger los datos no clasificados del Gobierno, durante su transmisión y almacenados. IBM presentó un cifrado de bloque de tipo Feistel, heredero de su sistema Lucifer, y la agencia de seguridad NSA participó en la evaluación. El resultado se adoptó como estándar federal en 1977 con el nombre de FIPS 46. El documento fue revisado varias veces; la última versión, FIPS 46-3 (1999), es la que usamos como referencia en este curso y está retirada desde 2005.

La polémica empezó enseguida. Se criticó que la clave fuera de solo 56 bits efectivos, y que la NSA hubiera intervenido en el diseño sin que los criterios de las cajas S fueran públicos. En 1994 Don Coppersmith, uno de los diseñadores de IBM, publicó los criterios que se habían seguido para esas cajas, y contó que formaban parte del diseño original. Volveremos sobre ello en la lección 6.

Parámetros

• Bloque: 64 bits.
• Clave: 64 bits, de los que 8 son de paridad y no entran en el cifrado. La clave efectiva es de 56 bits, es decir, $2^{56}$ claves posibles. Lo vemos en la lección 7.
• Rondas: 16, con una subclave de 48 bits en cada una.
• Estructura: red de Feistel.

Aviso de notación. DES, como el estándar FIPS 46-3, numera los bits de 1 a 64 empezando por la izquierda: el bit 1 es el más significativo. Todas las tablas del estándar usan esta numeración, y nosotros también.

El esquema completo

Sea $M$ el bloque de entrada y $K$ la clave. Cifrar es:

1. Permutación inicial. Se reordenan los 64 bits de $M$ con la permutación $IP$. Se parte el resultado en $L_0$ (32 bits de la izquierda) y $R_0$ (32 de la derecha).
2. Dieciséis rondas. Para $i = 1,\dots,16$:

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

3. Intercambio. Se juntan las mitades al revés: $R_{16}L_{16}$.
4. Permutación final. Se aplica $IP^{-1}$ (la inversa de $IP$), y sale el criptograma $c$.

Como en el juguete de la lección 4, el intercambio del paso 3 hace que descifrar sea cifrar con las subclaves en orden inverso, $K_{16},\dots,K_1$: no hace falta un circuito distinto para descifrar.

La permutación inicial

$IP$ se da como una lista de 64 posiciones: el bit de salida número $j$ es el bit número $IP[j]$ de la entrada. Escrita por filas de 8, es:

58	50	42	34	26	18	10	2
60	52	44	36	28	20	12	4
62	54	46	38	30	22	14	6
64	56	48	40	32	24	16	8
57	49	41	33	25	17	9	1
59	51	43	35	27	19	11	3
61	53	45	37	29	21	13	5
63	55	47	39	31	23	15	7

La primera fila dice: el bit 1 de la salida es el bit 58 de la entrada, el bit 2 de la salida es el 50 de la entrada, etc. Las cuatro primeras filas llenan la mitad izquierda $L_0$ y las cuatro últimas la derecha $R_0$. Mira un detalle: $L_0$ se forma con los bits de posición par de la entrada y $R_0$ con los de posición impar.

Su inversa $IP^{-1}$ tiene la tabla opuesta, que empieza por $40, 8, 48, 16, 56, 24, 64, 32$ (el bit 1 de la salida es el bit 40 de la entrada).

Ejemplo resuelto

Usamos el ejemplo de J. Orlin Grabbe, «The DES Algorithm Illustrated», muy difundido para seguir DES a mano. Es un ejemplo de ese texto (fechado en 1998), y las cifras de abajo las hemos recalculado nosotros paso a paso. Tomamos, en hexadecimal,

$$K = \texttt{133457799BBCDFF1}, \qquad M = \texttt{0123456789ABCDEF}.$$

Paso 1: $M$ en bits. Escribimos $M$ por bytes:

byte	hex	bits
1	$\texttt{01}$	$00000001$
2	$\texttt{23}$	$00100011$
3	$\texttt{45}$	$01000101$
4	$\texttt{67}$	$01100111$
5	$\texttt{89}$	$10001001$
6	$\texttt{AB}$	$10101011$
7	$\texttt{CD}$	$11001101$
8	$\texttt{EF}$	$11101111$

Paso 2: $IP(M)$. Aplicamos la tabla. El bit 1 de la salida es el bit 58 de la entrada (el bit 58 es el segundo bit del byte 8, y vale 1), y así hasta 64 bits. Resulta:

byte	bits	hex
1	$11001100$	$\texttt{CC}$
2	$00000000$	$\texttt{00}$
3	$11001100$	$\texttt{CC}$
4	$11111111$	$\texttt{FF}$
5	$11110000$	$\texttt{F0}$
6	$10101010$	$\texttt{AA}$
7	$11110000$	$\texttt{F0}$
8	$10101010$	$\texttt{AA}$

Partimos en mitades:

$$L_0 = \texttt{CC00CCFF}, \qquad R_0 = \texttt{F0AAF0AA}.$$

Paso 3: las 16 rondas. En la lección 6 calcularemos con todo detalle la ronda 1. De momento usamos los valores de $f(R_{i-1}, K_i)$ para ver que la recurrencia funciona. No puedes comprobarlos todavía: la lección 6 te dará las herramientas para la ronda 1. Ya con $f_1 = f(R_0, K_1) = \texttt{234AA9BB}$:

$$R_1 = L_0 \oplus f_1 = \texttt{CC00CCFF} \oplus \texttt{234AA9BB} = \texttt{EF4A6544}, \qquad L_1 = R_0 = \texttt{F0AAF0AA}.$$

Compruébalo byte a byte: $\texttt{CC}\oplus\texttt{23} = \texttt{EF}$, $\texttt{00}\oplus\texttt{4A} = \texttt{4A}$, $\texttt{CC}\oplus\texttt{A9} = \texttt{65}$, $\texttt{FF}\oplus\texttt{BB} = \texttt{44}$.

La tabla recoge todas las rondas:

ronda $i$	$f(R_{i-1},K_i)$	$L_i$	$R_i$
0		$\texttt{CC00CCFF}$	$\texttt{F0AAF0AA}$
1	$\texttt{234AA9BB}$	$\texttt{F0AAF0AA}$	$\texttt{EF4A6544}$
2	$\texttt{3CAB87A3}$	$\texttt{EF4A6544}$	$\texttt{CC017709}$
3	$\texttt{4D166EB0}$	$\texttt{CC017709}$	$\texttt{A25C0BF4}$
4	$\texttt{BB23774C}$	$\texttt{A25C0BF4}$	$\texttt{77220045}$
5	$\texttt{2813ADC3}$	$\texttt{77220045}$	$\texttt{8A4FA637}$
6	$\texttt{9E45CD2C}$	$\texttt{8A4FA637}$	$\texttt{E967CD69}$
7	$\texttt{8C051C27}$	$\texttt{E967CD69}$	$\texttt{064ABA10}$
8	$\texttt{3C0E86F9}$	$\texttt{064ABA10}$	$\texttt{D5694B90}$
9	$\texttt{22367C6A}$	$\texttt{D5694B90}$	$\texttt{247CC67A}$
10	$\texttt{62BC9C22}$	$\texttt{247CC67A}$	$\texttt{B7D5D7B2}$
11	$\texttt{E104FA02}$	$\texttt{B7D5D7B2}$	$\texttt{C5783C78}$
12	$\texttt{C268CFEA}$	$\texttt{C5783C78}$	$\texttt{75BD1858}$
13	$\texttt{DDBB2922}$	$\texttt{75BD1858}$	$\texttt{18C3155A}$
14	$\texttt{B7318E55}$	$\texttt{18C3155A}$	$\texttt{C28C960D}$
15	$\texttt{5B81276E}$	$\texttt{C28C960D}$	$\texttt{43423234}$
16	$\texttt{C8C04F98}$	$\texttt{43423234}$	$\texttt{0A4CD995}$

Fíjate en la columna $L_i$: es la columna $R_i$ desplazada una fila hacia abajo. Eso es la Feistel, que se limita a mover $R$ a la izquierda en cada ronda.

Paso 4: intercambio y $IP^{-1}$. Se juntan las mitades al revés:

$$R_{16}L_{16} = \texttt{0A4CD995}\,\texttt{43423234}.$$

Aplicamos $IP^{-1}$ y sale el criptograma

$$c = \texttt{85E813540F0AB405}.$$

Solo nos falta ver cómo se calcula cada $f$ y cada subclave. Eso haremos en las dos lecciones siguientes.

Ejercicios

Ejercicio 1

Aplica $IP$ a los bloques $\texttt{0000000000000001}$ (solo el bit 64 vale 1) y $\texttt{8000000000000000}$ (solo el bit 1 vale 1). Da el resultado en hexadecimal.

Ver la solución

En $\texttt{0000000000000001}$ el único 1 es el bit 64 de la entrada. Buscamos el 64 en la tabla de $IP$: está en la cuarta fila, primera columna, es decir, en la posición 25 de la lista. Así que el bit 64 de la entrada pasa a ser el bit 25 de la salida. Entonces el 1 está en el bit 25, que es el primer bit del cuarto byte ($25 = 3\cdot 8 + 1$): el cuarto byte es $10000000 = \texttt{80}$. Resultado: $\texttt{0000008000000000}$.

Para $\texttt{8000000000000000}$ el único 1 es el bit 1 de la entrada. En la tabla, el 1 está en la quinta fila, última columna: posición $4\cdot 8 + 8 = 40$. El 1 pasa al bit 40 de la salida, que es el último bit del byte 5: $00000001 = \texttt{01}$. Resultado: $\texttt{0000000001000000}$.

Ejercicio 2

Con el criptograma $c = \texttt{85E813540F0AB405}$ del ejemplo, queremos descifrarlo. ¿Cuánto valen $L_0$ y $R_0$ al empezar el descifrado, sin calcular $IP$ a mano? ¿Con qué subclave se hace la primera ronda?

Ver la solución

El último paso de cifrar fue $c = IP^{-1}(R_{16}L_{16})$. Por tanto $IP(c) = R_{16}L_{16}$. Al descifrar, la primera mitad es $R_{16}$ y la segunda $L_{16}$, y de la tabla de arriba:

$$L_0' = R_{16} = \texttt{0A4CD995}, \qquad R_0' = L_{16} = \texttt{43423234}.$$

(Lo hemos comprobado calculando $IP(c)$ por separado.) La primera ronda de descifrado usa $K_{16}$, la última subclave. Como $R_{16} = L_{15}\oplus f(R_{15},K_{16})$ y $L_{16} = R_{15}$, esa ronda calcula $R_1' = R_{16}\oplus f(L_{16},K_{16}) = L_{15}$ y deja $L_1' = L_{16} = R_{15}$: se ha deshecho la ronda 16.

Ejercicio 3

Cambiamos el último bit del mensaje: $M' = \texttt{0123456789ABCDEE}$. Calcula $IP(M')$ y la ronda 1 con el mismo $K_1$. ¿Cuántos bits distintos hay entre $R_1$ y $R_1'$? ¿Qué te dice sobre la difusión?

Ver la solución

El bit 64 de $M$ pasa a la posición 25 de $IP$ (ejercicio 1), que está en $L_0$. El bit 25 es el primer bit del cuarto byte de $L_0$, así que ese byte pasa de $\texttt{FF}$ a $\texttt{7F}$: $L_0' = \texttt{CC00CC7F}$, mientras que $R_0' = R_0 = \texttt{F0AAF0AA}$. Como $R_0$ no ha cambiado, $f(R_0',K_1) = f(R_0,K_1)=\texttt{234AA9BB}$, y

$$R_1' = L_0'\oplus f = \texttt{CC00CC7F}\oplus\texttt{234AA9BB} = \texttt{EF4A65C4}.$$

Frente a $R_1 = \texttt{EF4A6544}$ difiere en un solo bit. Después de la primera ronda, el cambio sigue siendo de un bit, porque ha caído en la mitad que solo se suma con XOR. En la ronda 2 ese bit llegará a $f$ y empezará a propagarse. Al final, como vimos en la lección 3, el criptograma cambia en 37 de 64 bits: la difusión necesita varias rondas.

En resumen

• DES es una red de Feistel de 16 rondas sobre bloques de 64 bits, con una clave de 64 bits de los que 56 son efectivos.
• El esquema es: $IP$, 16 rondas $L_i = R_{i-1}$, $R_i = L_{i-1}\oplus f(R_{i-1},K_i)$, intercambio de mitades e $IP^{-1}$.
• $IP$ y $IP^{-1}$ son permutaciones fijas y sin clave: ordenan los bits, no añaden seguridad.
• Descifrar es cifrar con $K_{16},\dots,K_1$, gracias al intercambio final.
• Falta ver $f$ (lección 6) y de dónde salen las subclaves (lección 7).

Siguiente lección: La función f de DES y sus cajas S