Las subclaves de DES: de 56 bits a 16 claves de ronda

Ya conocemos el esquema de DES (lección 5) y el interior de cada ronda (lección 6). Solo nos falta una pieza: en la ronda 1 usamos $K_1 = \texttt{1B02EFFC7072}$ sin decir de dónde sale. Hoy lo explicamos. Con ello, DES queda completo en nuestro relato: Alicia y Bernardo comparten una clave $K$, y cada uno fabrica con ella las 16 claves de ronda. Además veremos dos rarezas de DES que se heredan de este calendario de claves: las claves débiles y la complementación.

La idea

La clave $K$ tiene 64 bits, pero solo se usan 56. Esos 56 bits se parten en dos mitades de 28, $C$ y $D$. En cada ronda las dos mitades rotan hacia la izquierda una o dos posiciones, y de las 56 posiciones se escogen 48 para formar la subclave de esa ronda. No hay ninguna operación complicada: son permutaciones, selecciones y rotaciones. Toda la no linealidad de DES está en las cajas S, no aquí.

Los pasos

Recuerda que DES numera los bits de 1 a 64 desde la izquierda.

Bits de paridad

Los bits 8, 16, 24, 32, 40, 48, 56 y 64 de $K$ (el último de cada byte) son bits de paridad: se escogen para que cada byte tenga un número impar de unos, de modo que un error al copiar la clave pueda detectarse. No participan en el cifrado. Quedan $64 - 8 = 56$ bits efectivos, y por eso el espacio de claves de DES es de $2^{56}$ claves.

PC-1: de 64 a 56 bits

La primera permutación, PC-1 (permuted choice 1), descarta los ocho bits de paridad y reordena los otros 56. La tabla, por filas de 7, es:

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

Las cuatro primeras filas dan $C_0$ (28 bits) y las cuatro últimas, $D_0$ (28 bits). Ningún número de la tabla es múltiplo de 8.

Rotaciones

Para $i = 1,\dots,16$, se rotan $C_{i-1}$ y $D_{i-1}$ hacia la izquierda $r_i$ posiciones, con

$$(r_1,\dots,r_{16}) = (1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1).$$

Se obtienen $C_i$ y $D_i$. La suma de las rotaciones es $28$: hay cuatro rotaciones de una posición (rondas 1, 2, 9 y 16) y doce de dos, y $4 + 24 = 28$. Como cada mitad tiene 28 bits, tras las 16 rondas ha dado exactamente una vuelta completa: $C_{16} = C_0$ y $D_{16} = D_0$.

PC-2: de 56 a 48 bits

Se unen $C_i D_i$ (56 bits) y la permutación PC-2 (permuted choice 2) escoge 48 de ellos, ordenados así, y forma $K_i$:

14	17	11	24	1	5
3	28	15	6	21	10
23	19	12	4	26	8
16	7	27	20	13	2
41	52	31	37	47	55
30	40	51	45	33	48
44	49	39	56	34	53
46	42	50	36	29	32

Las cuatro primeras filas (24 bits) toman posiciones de $C_i$ (números del 1 al 28), y las cuatro últimas (24 bits) de $D_i$ (números del 29 al 56). Se descartan ocho posiciones de las 56. Cada subclave $K_i$ es, pues, una selección de 48 de los 56 bits de la clave efectiva, distinta en cada ronda.

Ejemplo resuelto

Seguimos con $K = \texttt{133457799BBCDFF1}$.

Paso 1: $K$ en bits y paridad. Por bytes:

byte	hex	bits	unos
1	$\texttt{13}$	$00010011$	3
2	$\texttt{34}$	$00110100$	3
3	$\texttt{57}$	$01010111$	5
4	$\texttt{79}$	$01111001$	5
5	$\texttt{9B}$	$10011011$	5
6	$\texttt{BC}$	$10111100$	5
7	$\texttt{DF}$	$11011111$	7
8	$\texttt{F1}$	$11110001$	5

Cada byte tiene un número impar de unos, así que la paridad es correcta.

Paso 2: PC-1. Aplicamos la tabla. El resultado, en 8 grupos de 7 bits, es

$$1111000\ 0110011\ 0010101\ 0101111\ 0101010\ 1011001\ 1001111\ 0001111.$$

Las dos mitades son:

$$C_0 = 1111000\ 0110011\ 0010101\ 0101111,$$ $$D_0 = 0101010\ 1011001\ 1001111\ 0001111.$$

Paso 3: la primera rotación. Como $r_1 = 1$, pasamos el primer bit de cada mitad al final:

$$C_1 = 1110000\ 1100110\ 0101010\ 1011111,$$ $$D_1 = 1010101\ 0110011\ 0011110\ 0011110.$$

Paso 4: PC-2. Juntamos $C_1D_1$ y leemos las posiciones de la tabla de PC-2. Por ejemplo, el primer grupo de $K_1$ toma las posiciones 14, 17, 11, 24, 1 y 5 de $C_1D_1$, cuyos valores son $0, 0, 0, 1, 1, 0$. Siguiendo así con las 48 posiciones sale

$$\begin{gathered} K_1 = 000110\ 110000\ 001011\ 101111 \\ 111111\ 000111\ 000001\ 110010 = \texttt{1B02EFFC7072}, \end{gathered}$$

que es exactamente la subclave que usamos en la ronda 1 de la lección 6.

Paso 5: las demás. La tabla siguiente da las 16 subclaves del ejemplo, todas calculadas del mismo modo:

$i$	$r_i$	$K_i$	$i$	$r_i$	$K_i$
1	1	$\texttt{1B02EFFC7072}$	9	1	$\texttt{E0DBEBEDE781}$
2	1	$\texttt{79AED9DBC9E5}$	10	2	$\texttt{B1F347BA464F}$
3	2	$\texttt{55FC8A42CF99}$	11	2	$\texttt{215FD3DED386}$
4	2	$\texttt{72ADD6DB351D}$	12	2	$\texttt{7571F59467E9}$
5	2	$\texttt{7CEC07EB53A8}$	13	2	$\texttt{97C5D1FABA41}$
6	2	$\texttt{63A53E507B2F}$	14	2	$\texttt{5F43B7F2E73A}$
7	2	$\texttt{EC84B7F618BC}$	15	2	$\texttt{BF918D3D3F0A}$
8	2	$\texttt{F78A3AC13BFB}$	16	1	$\texttt{CB3D8B0E17F5}$

Fíjate en que $K_{16}$ sale de rotar una sola posición, la del final del calendario, y que $C_{16} = C_0$: tras las 16 rotaciones volvemos al punto de partida.

Descifrar y las subclaves

Como vimos en la lección 5, descifrar es cifrar con $K_{16}, K_{15},\dots,K_1$. Para eso hay que tener las subclaves en orden inverso, y se puede hacer de dos maneras: calcular las 16 y leerlas al revés, o ir rotando hacia la derecha. Esto último es posible precisamente porque $C_{16} = C_0$ y $D_{16} = D_0$: en la ronda de descifrado 1, $K_{16}$ sale de $C_{16}D_{16}$, que es $C_0D_0$, sin rotar. Luego, en cada ronda de descifrado, se rota hacia la derecha: 0 posiciones en la primera y después $r_{16}, r_{15}, \dots, r_2$, es decir, $(0,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1)$.

Dos curiosidades

Claves débiles

Si $C_0$ y $D_0$ son cada una de ceros o de unos, rotarlas no las cambia, y las 16 subclaves son iguales. Hay cuatro claves así, las claves débiles de DES, que se ven aquí con su forma en hexadecimal:

clave	$C_0$	$D_0$	subclaves
$\texttt{0101010101010101}$	todo $0$	todo $0$	todas $\texttt{000000000000}$
$\texttt{FEFEFEFEFEFEFEFE}$	todo $1$	todo $1$	todas $\texttt{FFFFFFFFFFFF}$
$\texttt{E0E0E0E0F1F1F1F1}$	todo $1$	todo $0$	todas $\texttt{FFFFFF000000}$
$\texttt{1F1F1F1F0E0E0E0E}$	todo $0$	todo $1$	todas $\texttt{000000FFFFFF}$

Con una clave así, cifrar y descifrar usan las mismas subclaves (las 16 son iguales, y al invertir el orden queda lo mismo). Es decir, $E_K = D_K$ y cifrar dos veces devuelve el mensaje: $E_K(E_K(M)) = M$. Lo hemos comprobado con las cuatro claves y con el mensaje del ejemplo. Aunque son solo 4 entre $2^{56}$ claves, no deben usarse. Hay además seis parejas de claves semidébiles: cifrar con una de la pareja equivale a descifrar con la otra (lo cuenta el Handbook of Applied Cryptography, capítulo 7).

Complementación

Si $\bar x$ es $x$ con todos los bits cambiados, DES cumple

$$E_{\bar K}(\bar M) = \overline{E_K(M)}.$$

La razón: las subclaves de $\bar K$ son las complementarias de las de $K$, y en $f$ se hace $E(\bar R)\oplus \bar K_i = E(R)\oplus K_i$ (el complementario aparece dos veces y se cancela), así que $f$ no cambia. En la ronda 1, $L_0$ y $R_0$ se complementan, $f$ da lo mismo, y $R_1 = \bar L_0\oplus f$ también está complementado. Y así hasta el final.

Con el ejemplo: $\bar K = \texttt{ECCBA8866443200E}$, $\bar M = \texttt{FEDCBA9876543210}$, y

$$E_{\bar K}(\bar M) = \texttt{7A17ECABF0F54BFA} = \overline{\texttt{85E813540F0AB405}}.$$

Qué ahorra en fuerza bruta. Eva tiene un mensaje $M$ y su criptograma $c_1$, y además $\bar M$ con su criptograma $c_2$ (texto elegido). Recorre solo una clave de cada pareja $\{K', \bar K'\}$, y para cada una calcula una sola vez $E_{K'}(M)$. Si da $c_1$, $K'$ es candidata. Si da $\bar c_2$, la candidata es $\bar K'$, porque $E_{\bar K'}(\bar M) = \overline{E_{K'}(M)} = c_2$. (Una candidata se confirma con otro par, porque alguna clave falsa puede acertar por azar.) Con un cálculo se prueban dos claves, así que basta recorrer la mitad: $2^{55}$ claves en vez de $2^{56}$. Es un ahorro de un factor 2, nada decisivo, pero muestra que una propiedad matemática de la estructura se traduce en trabajo de menos.

Ejercicios

Ejercicio 1

Cambia el último bit de la clave del ejemplo: $K' = \texttt{133457799BBCDFF0}$. ¿Cambia el criptograma de $M = \texttt{0123456789ABCDEF}$? ¿Cuántas claves de 64 bits cifran exactamente igual que $K$, sea cual sea el mensaje?

Ver la solución

El último bit de $K$ es el bit 64, un bit de paridad: PC-1 no lo usa. Las subclaves son idénticas, y el criptograma también: $\texttt{85E813540F0AB405}$ (lo hemos comprobado). Cada uno de los 8 bits de paridad se puede cambiar libremente sin tocar las subclaves, así que hay $2^8 = 256$ claves de 64 bits que dan las mismas subclaves y, por tanto, cifran igual cualquier mensaje. De esas 256, solo una cumple la paridad impar en los 8 bytes. Por eso se habla de $2^{56}$ claves y no de $2^{64}$.

Ejercicio 2

Con $C_1 = 1110000\,1100110\,0101010\,1011111$ y $D_1 = 1010101\,0110011\,0011110\,0011110$, calcula $C_2$ y $D_2$ (recuerda $r_2 = 1$).

Ver la solución

Rotamos una posición a la izquierda: el primer bit pasa al final.

$C_1$ empieza por $1$; al quitarlo queda $110000\,1100110\,0101010\,1011111$ y se añade $1$ al final:

$$C_2 = 1100001\,1001100\,1010101\,0111111.$$

$D_1$ empieza por $1$; al quitarlo y ponerlo al final:

$$D_2 = 0101010\,1100110\,0111100\,0111101.$$

Ejercicio 3

Para la clave débil $K = \texttt{E0E0E0E0F1F1F1F1}$, PC-1 da $C_0$ todo de unos y $D_0$ todo de ceros. Demuestra que las 16 subclaves valen $\texttt{FFFFFF000000}$ y que cifrar dos veces devuelve el mensaje.

Ver la solución

Rotar una cadena de 28 unos, o de 28 ceros, la deja igual. Así que $C_i$ son todo unos y $D_i$ todo ceros, para todo $i$. La permutación PC-2 toma sus primeras 24 posiciones de $C_i$ (números del 1 al 28) y las otras 24 de $D_i$ (del 29 al 56), así que $K_i$ son 24 unos seguidos de 24 ceros, es decir, $\texttt{FFFFFF000000}$, en las 16 rondas.

Como las 16 subclaves son iguales, usarlas en orden inverso es lo mismo que usarlas en orden directo: $D_K = E_K$. Entonces $E_K(E_K(M)) = D_K(E_K(M)) = M$. Con el mensaje del ejemplo, la comprobación numérica lo confirma.

En resumen

• La clave de 64 bits tiene 8 bits de paridad que no se usan: la clave efectiva es de 56 bits, $2^{56}$ claves.
• Las subclaves salen de PC-1 (64 a 56), dos mitades $C$ y $D$ de 28 bits que rotan $1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1$ posiciones (suman 28) y PC-2 (56 a 48).
• Como la suma de rotaciones es 28, $C_{16} = C_0$ y $D_{16} = D_0$: al descifrar, las subclaves en orden inverso se generan rotando a la derecha.
• Hay cuatro claves débiles, con las 16 subclaves iguales: cifrar dos veces devuelve el mensaje.
• DES cumple $E_{\bar K}(\bar M) = \overline{E_K(M)}$, y con ella la búsqueda exhaustiva de la clave se reduce a la mitad.

Siguiente lección: La caída de DES y el Triple DES