XOR y la libreta de un solo uso

En la lección anterior vimos que Alicia y Bernardo comparten una clave y que Eva, si el espacio de claves es pequeño, puede probarlas todas. Pues bien: existe un cifrado contra el cual la fuerza bruta no sirve de nada, porque ni siquiera una Eva con tiempo infinito aprende algo. Es la libreta de un solo uso, el punto de partida del curso. Veremos qué la hace perfecta y qué la hace impracticable. Esa tensión es la que empuja, lección tras lección, hasta AES.

La idea

Un mensaje es una sucesión de bits. Imagina que Alicia tiene una sucesión de bits completamente al azar, tan larga como el mensaje, y que Bernardo tiene una copia. Alicia combina cada bit del mensaje con el bit de la clave en la misma posición, de modo que el resultado sea el contrario cuando el bit de clave es 1 y el mismo cuando es 0. Bernardo repite la operación con su copia y recupera el mensaje.

La operación se llama XOR (o exclusivo) y es la suma módulo 2. Lo único que hay que saber de ella es que aplicada dos veces con la misma clave se deshace. Y lo sorprendente: si la clave es al azar y se usa una sola vez, el criptograma es también una sucesión al azar, que no depende del mensaje. No hay nada que Eva pueda aprender.

Binario, hexadecimal y bytes

Repaso Bits, bytes y hexadecimal

Un bit es 0 o 1. Un byte son 8 bits y permite 256 valores, de 0 a 255. Escribir 8 ceros y unos es pesado, así que se agrupan de 4 en 4 y cada grupo se escribe con un dígito hexadecimal: los dígitos $0$ a $9$ y las letras $\texttt{A}$ a $\texttt{F}$ para 10 a 15. Un byte son entonces dos dígitos hexadecimales. Por ejemplo,

$$\texttt{4F} \;=\; 0100\;1111 \;=\; 4\cdot 16 + 15 = 79.$$

En este curso escribimos los bytes y bloques en hexadecimal, en monoespaciado y sin prefijo: $\texttt{4F}$. Los bits van como $0110$.

El código ASCII asigna un byte a cada letra: $\texttt{4F}$ es la letra O. Las otras tres letras de nuestro ejemplo son $\texttt{48}$ (H), $\texttt{4C}$ (L) y $\texttt{41}$ (A).

El XOR

El XOR de dos bits, que escribimos $\oplus$, es 1 si los bits son distintos y 0 si son iguales. Es la suma módulo 2:

$a$	$b$	$a \oplus b$
0	0	0
0	1	1
1	0	1
1	1	0

Para bloques de bits se hace posición a posición. Sus propiedades clave, para cualquier $a$, $b$ y $c$:

• $a \oplus b = b \oplus a$ y $(a\oplus b)\oplus c = a \oplus (b \oplus c)$.
• $a \oplus 0 = a$: sumar ceros no cambia nada.
• $a \oplus a = 0$: cualquier cosa se cancela consigo misma.

De las dos últimas sale el truco central:

$$(a \oplus b) \oplus b = a \oplus (b\oplus b) = a \oplus 0 = a.$$

Hacer XOR con $b$ y volver a hacerlo deshace la operación. Por eso, con el mismo bloque $k$, cifrar y descifrar son la misma operación.

El XOR en hexadecimal. Cada dígito hexadecimal son 4 bits que no se mezclan con los vecinos, así que el XOR se puede hacer dígito a dígito: $\texttt{C}\oplus\texttt{2} = 1100\oplus 0010 = 1110 = \texttt{E}$, y por tanto $\texttt{CC}\oplus\texttt{23} = \texttt{EF}$. Con un poco de práctica no hace falta escribir los bits. A partir de la lección 5 haremos así el XOR de bloques enteros.

La libreta de un solo uso

La libreta de un solo uso (en inglés, one-time pad) funciona así. Alicia y Bernardo comparten una clave $k$ formada por bits al azar, de la misma longitud que el mensaje $m$.

$$c = m \oplus k, \qquad m = c \oplus k.$$

Las dos reglas que no se pueden saltar:

1. $k$ es uniformemente al azar (cada bit es 0 o 1 con la misma probabilidad, independientemente de los demás).
2. $k$ se usa una sola vez. De ahí el nombre.

El cifrado de teletipo de Gilbert Vernam, ingeniero de AT&T, ya usaba este XOR: lo patentó en 1919.

Secreto perfecto

En 1949, Claude Shannon publicó «Communication Theory of Secrecy Systems» y dio la definición precisa. Un cifrado tiene secreto perfecto si el criptograma no da a Eva información alguna sobre el mensaje: lo que Eva sabe sobre $m$ tras ver $c$ es lo mismo que sabía antes. Shannon demostró que la libreta de un solo uso lo cumple y que cualquier cifrado con secreto perfecto necesita al menos tantas claves posibles como mensajes posibles. Con claves y mensajes de bits al azar, eso quiere decir una clave al menos tan larga como el mensaje.

La razón, con un solo bit. Alicia envía $m \in \{0,1\}$ con una clave $k$ al azar, es decir, $k=0$ o $k=1$ con probabilidad $1/2$ cada una. El criptograma es $c = m \oplus k$.

$m$	$k=0$	$k=1$
0	$c=0$	$c=1$
1	$c=1$	$c=0$

Si $m=0$, el criptograma es 0 con probabilidad $1/2$ y 1 con probabilidad $1/2$. Si $m=1$, ocurre exactamente lo mismo. Eva ve, por ejemplo, $c=1$: eso es igual de probable tanto si $m=0$ como si $m=1$. No sabe más que antes. Con un mensaje de $n$ bits el argumento es idéntico, bit a bit: para cada mensaje $m$ posible y cada criptograma $c$ existe exactamente una clave que los une, $k = m \oplus c$, y todas las claves son igual de probables.

Eso significa que la fuerza bruta no sirve de nada, por muy potente que sea el ordenador de Eva. Si prueba todas las claves, obtendrá todos los mensajes posibles de esa longitud, sin forma de distinguir el verdadero.

Ejemplo resuelto

Alicia envía el mensaje «HOLA» con la clave $\texttt{5A 1F 93 C4}$. Los cuatro bytes del mensaje son $\texttt{48 4F 4C 41}$. Se hace XOR byte a byte, en bits:

	byte 1	byte 2	byte 3	byte 4
$m$	$01001000$	$01001111$	$01001100$	$01000001$
$k$	$01011010$	$00011111$	$10010011$	$11000100$
$c = m\oplus k$	$00010010$	$01010000$	$11011111$	$10000101$

En hexadecimal, $c = \texttt{12 50 DF 85}$. Por ejemplo, el primer byte, dígito a dígito: $\texttt{4}\oplus\texttt{5} = \texttt{1}$ y $\texttt{8}\oplus\texttt{A} = \texttt{2}$, así que $\texttt{48}\oplus\texttt{5A} = \texttt{12}$.

Bernardo recibe $c$ y hace XOR con su copia de $k$:

$$\texttt{12 50 DF 85} \oplus \texttt{5A 1F 93 C4} = \texttt{48 4F 4C 41},$$

que es HOLA.

Ahora lo notable. Si Eva intercepta $c = \texttt{12 50 DF 85}$ y prueba una clave cualquiera, obtiene un mensaje de cuatro bytes. Para leer «MUSA» ($\texttt{4D 55 53 41}$) le basta la clave $\texttt{5F 05 8C C4}$. Cada uno de los $2^{32} = 4\,294\,967\,296$ mensajes posibles de cuatro bytes corresponde a una clave y solo una.

Reutilizar la clave lo rompe

La segunda regla, «una sola vez», no es un adorno. Imagina que Alicia, descuidada, cifra un segundo mensaje, «CHAO» ($\texttt{43 48 41 4F}$), con la misma clave:

$$c' = \texttt{43 48 41 4F} \oplus \texttt{5A 1F 93 C4} = \texttt{19 57 D2 8B}.$$

Eva escucha los dos criptogramas. No conoce $k$, pero hace XOR de ambos:

$$c \oplus c' = (m \oplus k) \oplus (m' \oplus k) = m \oplus m' ,$$

porque $k \oplus k = 0$. Numéricamente:

$$\texttt{12 50 DF 85} \oplus \texttt{19 57 D2 8B} = \texttt{0B 07 0D 0E},$$

que es exactamente HOLA $\oplus$ CHAO. La clave ha desaparecido. Lo que queda es el XOR de dos textos en español, y eso se ataca: si Eva adivina una palabra de un mensaje (un saludo, una cabecera), obtiene la parte correspondiente del otro. Si sabe que $m=$ HOLA, hace $\texttt{0B 07 0D 0E} \oplus \texttt{48 4F 4C 41} = \texttt{43 48 41 4F}$ y lee CHAO. Con textos largos y suposiciones sobre el idioma se llega a leer los dos enteros.

Es el mismo fenómeno que hunde a un cifrado de flujo mal usado. Lo retomaremos en la última lección.

El precio

La libreta es perfecta, pero impracticable para casi todo. El motivo:

• La clave es tan larga como el mensaje. Para cifrar un vídeo de un gigabyte, hace falta un gigabyte de clave.
• No se puede reutilizar. Cada mensaje consume clave nueva.
• Hay que repartir esa clave de forma segura, y es el problema de la lección 1: si tuvieran un canal seguro para mandar la clave, lo usarían para mandar el mensaje.
• La clave debe ser realmente aleatoria. Producir tantos bits al azar es difícil.

Shannon demostró que esto es inevitable para el secreto perfecto: hacen falta tantas claves como mensajes. Entonces la pregunta pasa a ser: ¿podemos conformarnos con algo menos que perfecto a cambio de una clave corta, por ejemplo de 128 bits, que cifre mensajes mucho más largos? La respuesta son los cifrados de bloque, que empezamos a estudiar en la lección siguiente.

Ejercicios

Ejercicio 1

Calcula $\texttt{A7} \oplus \texttt{3C}$, primero en bits y luego pasando a hexadecimal. Comprueba que, haciendo XOR con $\texttt{3C}$ otra vez, vuelves a $\texttt{A7}$.

Ver la solución

$\texttt{A7} = 1010\,0111$ y $\texttt{3C} = 0011\,1100$. Posición a posición:

$$1010\,0111 \oplus 0011\,1100 = 1001\,1011 = \texttt{9B}.$$

Dígito a dígito sale lo mismo: $\texttt{A}\oplus\texttt{3} = \texttt{9}$ y $\texttt{7}\oplus\texttt{C} = \texttt{B}$. Haciendo XOR con $\texttt{3C}$ de nuevo: $1001\,1011 \oplus 0011\,1100 = 1010\,0111 = \texttt{A7}$.

Ejercicio 2

Eva intercepta $c = \texttt{12 50 DF 85}$ y sabe que el mensaje era HOLA ($\texttt{48 4F 4C 41}$). ¿Qué clave se usó? ¿Y qué clave habría hecho que el mismo $c$ fuese el cifrado de BESO ($\texttt{42 45 53 4F}$)?

Ver la solución

Como $c = m\oplus k$, entonces $k = m \oplus c$:

$$\texttt{48 4F 4C 41}\oplus\texttt{12 50 DF 85} = \texttt{5A 1F 93 C4}.$$

Para BESO, $k' = \texttt{42 45 53 4F} \oplus \texttt{12 50 DF 85} = \texttt{50 15 8C CA}$. Comprobación: $c \oplus k' = \texttt{42 45 53 4F}$, que es BESO.

Ejercicio 3

Alicia reutiliza la clave $\texttt{5A 1F 93 C4}$ y cifra «ADIO» ($\texttt{41 44 49 4F}$), con lo que $c' = \texttt{1B 5B DA 8B}$. Eva conoce también $c = \texttt{12 50 DF 85}$ (el cifrado de HOLA) y sabe que el primer mensaje es HOLA. ¿Qué obtiene al hacer $c \oplus c'$ y cómo llega a leer el segundo mensaje?

Ver la solución

$c \oplus c' = \texttt{12 50 DF 85} \oplus \texttt{1B 5B DA 8B} = \texttt{09 0B 05 0E}$, que es $m \oplus m'$ = HOLA $\oplus$ ADIO. Como Eva sabe $m = \texttt{48 4F 4C 41}$, hace

$$\texttt{09 0B 05 0E} \oplus \texttt{48 4F 4C 41} = \texttt{41 44 49 4F},$$

que es ADIO. Sin conocer la clave, ha leído el segundo mensaje.

En resumen

• El XOR ($\oplus$) es la suma módulo 2 bit a bit; cumple $a\oplus a = 0$ y $a\oplus 0 = a$, de modo que hacerlo dos veces con la misma clave deshace el cifrado.
• La libreta de un solo uso cifra con $c = m \oplus k$, con $k$ al azar, tan larga como $m$ y usada una sola vez.
• Tiene secreto perfecto (Shannon, 1949): $c$ no dice nada sobre $m$; ni la fuerza bruta ayuda, porque cada mensaje posible corresponde a una clave.
• Reutilizar la clave la destruye: $c\oplus c' = m \oplus m'$, y la clave desaparece de la cuenta.
• Para el secreto perfecto hacen falta tantas claves como mensajes posibles, es decir, una clave tan larga como el mensaje: ese es el precio, y por eso buscamos cifrados con claves cortas.

Siguiente lección: Cifrados de bloque