Padding Oracle Attack

Lo siguiente es un write-up que hice hace 6 meses sobre el ataque de padding oracle. Creo que merece la pena tenerlo aquí también, quien sabe, igual a alguien le resulta útil.

Para ver el código completo, incluidas las instrucciones de uso, ve aquí ENLACE EXTERNO A:

https://github.com/m1urah/padding-oracle-attack .

Si eres nuevo en criptografía, te recomiendo que le eches un vistado al siguiente Glosario sobre Criptografía ENLACE EXTERNO A:

https://developer.mozilla.org/es/docs/Glossary/Cryptography , te vendrá bien ;).

Los algoritmos de cifrado en bloque (como AES) requieren que los datos de entrada tengan una longitud múltiplo del tamaño de bloque. En el caso de AES, que es el foco de este write-up, es 16 bytes. Si el texto plano no cumple este requisito, hay que añadir padding para ajustar su longitud.

Este ataque se basa en disponer de un “padding oracle” que responde si un mensaje está correctamente rellenado (padded) o no. Esta información puede obtenerse directamente, o mediante ataques de canal lateral (side channel attacks) ENLACE EXTERNO A:

https://en.wikipedia.org/wiki/Side-channel_attack .

Con esa información, un texto cifrado se puede descifrar sin necesidad de conocer la clave, excepto para el primer bloque (los primeros 16 bytes), que requiere el Vector de Inicialización (IV) ENLACE EXTERNO A:

https://es.wikipedia.org/wiki/Vector_de_inicializaci%C3%B3n utilizado durante el cifrado.

Mis dieses a flashs101 por inspirar este write-up. Mucho de lo siguiente es gracias a su trabajo ENLACE EXTERNO A:

https://github.com/flast101/padding-oracle-attack-explained

Introducción

Los algoritmos de clave simétrica son algoritmos criptográficos que usan la misma clave secreta para las operaciones de cifrado y descifrado. En cambio, los algoritmos de clave asimétrica (o de clave pública) utilizan dos claves: una clave pública (conocida) para cifrar los mensajes y una clave privada para descifrarlos.

Uno de los principales inconvenientes de este tipo de algoritmos es que ambas partes tienen que tener acceso a la clave secreta. Por eso los algoritmos de clave pública se usan a menudo para intercambiar dicha clave.

El cifrado de clave simétrica puede usar:

Cifrado de flujo. Cifran los datos como un flujo continuo de bits o bytes, uno a uno, utilizando un flujo de claves (keystream) ENLACE EXTERNO A:

https://es.wikipedia.org/wiki/Flujo_de_claves pseudoaleatorio (una secuencia de bytes o bits generada por el algoritmo a partir de una clave secreta).
Cifrado por bloque. Cifran los datos en bloques de tamaño fijo, añadiendo padding al texto plano para que sea múltiplo del tamaño de bloque.

Nos centraremos en estos últimos.

Conceptos básicos

Los siguientes son algunos de los conceptos básicos necesarios para entender este write-up:

Texto plano: Cualquier información legible presentada en un formato accesible y utilizable sin necesidad de descifrado, incluyendo datos binarios.
Texto cifrado: La versión cifrada del texto plano.
Algoritmo de cifra: Un algoritmo criptográfico utilizado para aplicar operaciones de cifrado o descifrado a datos.
Cifrado: Convierte texto plano en texto cifrado usando un algoritmo de cifra y una clave secreta.
Descifrado: Convierte texto cifrado en texto plano.

Cifrado con clave simétrica

Un cifrador por bloque por sí mismo solo puede transformar de forma segura bloques de datos de tamaño fijo. Para cifrar mensajes de longitud arbitraria, necesitamos usar un modo de operación, que define cómo procesar múltiples bloques y gestionar el padding.

La mayoría de los modos de operación usan un Vector de Inicialización (IV) ENLACE EXTERNO A:

https://es.wikipedia.org/wiki/Vector_de_inicializaci%C3%B3n , una secuencia binaria única que se añade al proceso de cifrado. El IV añade aleatoriedad, asegurando que cifrar el mismo texto plano con la misma clave produzca textos cifrados distintos. Esto es importante para evitar que un atacante detecte patrones, lo que facilitaría adivinar el mensaje original o encontrar debilidades en el cifrado.

Modos de Operación de Cifrados por Bloque

Existen muchos modos de operación, pero los más comúnmente usados son estos:

GCM (Galois/Counter Mode)
CCM (Counter with CBC-MAC)
SIV (Synthetic IV)
GCM-SIV
CBC (Cipher Block Chaining)

Modos como ECB (Electronic Codebook) se evitan porque son vulnerables al análisis de patrones y a otros ataques. Aquí ENLACE EXTERNO A:

https://en.wikipedia.org/wiki/Block_cipher_mode_of_operation#Electronic_codebook_%28ECB%29 puedes ver como de inseguro es.

AES-CBC

El ataque de padding oracle se basa principalmente en el modo AES-CBC. Observando cómo responde un sistema a distintos textos cifrados (si el padding es válido o no), el atacante (nosotros) será capaz de recuperar gradualmente el texto plano sin conocer la clave secreta.

Durante el cifrado, cada bloque de texto plano se XORea ENLACE EXTERNO A:

https://en.wikipedia.org/wiki/Exclusive_or con el bloque de texto cifrado anterior (o el IV para el primer bloque), y después se cifra con la clave secreta.

Como cada bloque de texto cifrado depende del anterior, el cifrado no puede paralelizarse.

Para descifrar, simplemente invertimos el proceso: primero se descifra cada bloque de texto cifrado con la clave secreta y después se XORea el resultado con el bloque de texto cifrado anterior (o el IV en el primer bloque), lo que recupera el bloque de texto plano original.

Estas operaciones se pueden representar como operaciones matemáticas. No te preocupes, no estoy loco ENLACE EXTERNO A:

https://www.youtube.com/watch?v=Mec2ZSOr6K8 , son fórmulas bastante simples que solo están aquí porque son necesarias para este ataque. Si no, no me molestaría en incluirlas.

Las veremos en un segundo.

XOR funciona en bits individuales (y por extensión, bytes). Esto significa que si cambias un bit (o byte), solo esa parte específica se ve afectada, nada más.

Cifrado

C_i = E_K(P_i \oplus C_{i-1})

donde:

$C_i$ es el bloque de texto cifrado
$E_K$ es la operación de cifrado AES-CBC
$P_i$ es el bloque de texto plano
$C_{i-1}$ es el bloque de texto cifrado anterior, o el $IV$ en el primer bloque
$\oplus$ significa XOR

Descifrado

P_i = D_K(C_i) \oplus C_{i-1}

Algoritmo de padding (PKCS#7)

Aquí es donde está la magia .

Muchas implementaciones de AES-CBC utilizan el algoritmo PKCS#7 ENLACE EXTERNO A:

https://en.wikipedia.org/wiki/PKCS_7 para el padding, una solución simple pero elegante a este problema.

Este algoritmo funciona de una manera muy simple. Si N es el número de bytes de un bloque y faltan M bytes (M < N) en el último bloque, se añade el carácter 0xM (hexadecimal) M veces al final del bloque.

Digamos que estamos trabajando con bloques de 4 bytes y queremos cifrar el siguiente texto plano:

p = 'PURPLE'

Como el texto tiene 6 bytes y el tamaño de bloque es 4, PKCS#7 necesita añadir 2 bytes extra para completar el último bloque, así:

p_padded = 'PURPLE\0x02\0x02'

Si se necesitaran 3 bytes extra añadiría tres 0x03, para 4, cuatro 0x04, etc.

PKCS#7 siempre añade padding, incluso si la longitud del texto plano ya es múltiplo del tamaño de bloque.

Nuestro texto plano ahora es:

p = 'HOLA'

Tiene 4 bytes, que ya es múltiplo de 4, pero como siempre se añade padding, se agrega un nuevo bloque de caracteres 0x04 al final:

p_padded = 'HOLA\0x04\0x04\0x04\0x04'

Quién en el qué ahora

Esta cita de Los Simpson ENLACE EXTERNO A:

https://www.youtube.com/watch?v=XsiQsFHlRC4 *No he sido capaz de encontrar el clip en español :( ilustra DEMASIADO bien cómo funciona todo el ataque. En un momento verás a que me refiero.

Ahora que ya tenemos la base teórica (espero), veamos cómo podemos explotar el Oráculo for fun and profit ENLACE EXTERNO A:

https://inst.eecs.berkeley.edu/~cs161/fa08/papers/stack_smashing.pdf .

Para hacer las cosas mas simples, vamos a trabajar con un ejemplo pequeño usando solo 4 bloques. Es decir, tendremos 4 bloques de texto plano y 4 de texto cifrado. El tamaño de bloque seguirá siendo 16 (estamos en AES).

Por tanto, para el cifrado tenemos:

Y para el descifrado:

Volvamos a la fórmula de descifrado (AES-CBC):

P_i = D_K(C_i) \oplus C_{i-1}

Ahora introduzcamos $X$, un bloque que controlamos y que podemos cambiar como queramos. Esta es la base de todo el ataque.

Expresándo esto con las fórmulas anteriores, obtenemos:

$C_3 = E_K(P_3 \oplus C_2)$
$P^{\prime}_1 = D_K(C_3) \oplus X$

Si sustituimos $C_3$, tenemos:

P^{\prime}_1 = D_K(E_K(P_3 \oplus C_2)) \oplus X

Como el descifrado ($D_K$) y el cifrado ($E_K$) se anulan mutuamente, y XOR es conmutativo, queda:

P_3 = P^{\prime}_1 \oplus C_2 \oplus X

Y hemos llegado a un punto en el que tenemos 2 conocidos y 2 desconocidos.

Conocidos:

$C_2$: Bloque de texto cifrado anterior.
$X$: Bloque de texto cifrado que controlamos.

Desconocidos:

$P_3$: Último bloque de texto plano.
$P^{\prime}_1$: Último bloque de texto plano al descifrar $X || C_3$ ($||$ significa concatenación).

XOR Aplicado a Bytes

XOR funciona sobre bits individuales (y por extensión, bytes). Esto significa que si cambias un bit (o byte), solo se ve afectada esa parte concreta.

Supongamos que tenemos la siguiente secuencia de números:

Queremos aplicar XOR a esta secuencia de modo que solo se vea afectado el número 27. Si hacemos XOR entre el binario $10$ y la representación binaria de 27 ($00011011$), obtenemos:

Podemos ir un paso más allá y aplicar el XOR binario $10$ a solo un par de bits:

Como XOR se aplica en bytes individuales (o bits), podemos descomponer la fórmula anterior de $P_3$ en su representación byte a byte:

$P_{3[0]} = P^{\prime}_{1[0]} \oplus C_{2[0]} \oplus X{[0]}$
$P_{3[1]} = P^{\prime}_{1[1]} \oplus C_{2[1]} \oplus X{[1]}$
$...$
$P_{3[15]} = P^{\prime}_{1[15]} \oplus C_{2[15]} \oplus X{[15]}$

Llegamos hasta 15 ya que el tamaño de bloque es 16 y empezamos a contar desde 0.

Obteniendo el Último Byte de Texto Plano

Para obtener el último byte de texto plano necesitamos resolver esta fórmula (la que acabamos de ver):

P_{3[15]} = P^{\prime}_{1[15]} \oplus C_{2[15]} \oplus X_{[15]}

Tal y como vimos antes, tenemos dos conocidos y dos desconocidos. Centrándonos en el desconocido que SÍ podemos obtener, queda:

P^{\prime}_{1[15]} = D_K(C_{3[15]}) \oplus X_{[15]}

La idea en la primera iteración es modificar el último byte de $X$ y enviar $X || C_3$ al servidor. Por cómo funciona el modo CBC, el servidor descifrará $C_3$ y aplicará XOR con nuestro bloque $X$ modificado. El resultado de esta operación es el bloque de texto plano $P^{\prime}_1$. El servidor (nuestro fiel oráculo) devuelve entonces si el padding del último bloque descifrado ($P^{\prime}_1$) es correcto o no (un padding PKCS#7 válido).

Esto es muy interesante: si conseguimos forzar que el último bloque de texto plano tenga un padding concreto (0x01 en la primera iteración), podemos obtener esos bytes de texto plano simplemente aplicando la fórmula de $P_3$. :O

Podemos literalmente obligar al servidor a revelar el texto plano SIN SIQUIERA TENER LA CLAVE .

En esta primera iteración queremos forzar que el texto plano tenga padding 0x01 ($P^{\prime}_{1[15]} = 0x01$). ¿Por qué? Porque aún no conocemos ningún byte de texto plano.

Como XOR funciona byte a byte, podemos probar todos los valores posibles (0 a 255) para $X_{[15]}$ hasta que el oráculo nos diga que el padding es válido (o no devuelva error).

Para asegurarnos de que no estamos acertando por casualidad con un padding ya existente, también debemos modificar el byte anterior a $C_{3[15]}$, es decir, $C_{3[14]}$. Así el único padding posible será 0x01.

Una vez sabemos qué valor hace que $P^{\prime}_{1[15]} = 0x01$, podemos usar esta fórmula para obtener el byte de texto plano:

P_{3[15]} = P^{\prime}_{1[15]} \oplus C_{2[15]} \oplus X_{[15]}

donde:

$P^{\prime}_{1[15]}$: $0x01$ (el valor que forzamos cambiando $X_{[15]}$).
$C_{2[15]}$: El byte correspondiente del bloque de texto cifrado anterior.
$X_{[15]}$: El valor (0 a 255) que hizo que $P^{\prime}_{1[15]}$ fuese $0x01$.

Matemáticas nena, MATEMÁTICAS.

Penúltimo byte de texto plano

Ahora hay dos fórmulas involucradas:

$P_{3[15]} = P^{\prime}_{1[15]} \oplus C_{2[15]} \oplus X{[15]}$
$P_{3[14]} = P^{\prime}_{1[14]} \oplus C_{2[14]} \oplus X{[14]}$

Queremos forzar que $P^{\prime}_1$ tenga un padding de dos, es decir:

P^{\prime}_{1[15]} = P^{\prime}_{1[14]} = 0x02

Sin embargo, no podemos usar el $X{[15]}$ que encontramos antes, porque estaba elegido para producir un padding de 0x01, no 0x02. Pero sí tenemos $P_{3[15]}$, y como XOR es conmutativo, obtenemos:

X{[15]} = P^{\prime}_{1[15]} \oplus C_{2[15]} \oplus P_{3[15]}

donde:

$P^{\prime}_{1[15]}$: $0x02$
$C_{2[15]}$: El byte correspondiente del bloque de texto cifrado anterior.
$P_{3[15]}$: El byte de texto plano que calculamos antes.

Con esto en mente, necesitamos:

Calcular y actualizar $X{[15]}$ usando la fórmula anterior.
Alterar $X{[13]}$ (el byte anterior a $X{[14]}$) para asegurarnos de que el único padding posible sea $0x02$.
Probar todos los valores posibles (0 a 255) para $X{[14]}$ hasta que el oráculo diga que el padding es válido.

Generalizando

Para calcular cualquier byte de texto plano ($P_{i[j]}$), recorremos cada byte del bloque de texto cifrado correspondiente ($C_{i[j]}$), empezando por el último byte ($j=15$) y avanzando hasta el primero ($j=0$).

Para cada posición (byte), calculamos el valor correcto de $X_{[j]}$ que produce un padding válido, usando los valores que ya hemos encontrado para los bytes posteriores a $j$.

Como los bytes de texto plano se calculan por bloques, este proceso puede paralelizarse.

El siguiente pseudocódigo ilustra el proceso:

1
2
3
4
5
6
Para cada bloque (excepto el primero):
    Para j desde 15 hasta 0:
        - Establecer el valor de padding como (16 - j): 0x01, 0x02, ...
        - Para todas las posiciones k>j, ajustar X[k] para que P’[k] = padding (usando fórmula1)
        - Probar todos los valores posibles para X[j] (0 a 255) hasta que el oráculo diga que el padding es válido
        - Una vez encontrado, calcular el byte de texto plano usando fórmula2

donde:

Fórmula1: $X{[k]} = padding \oplus C_{i-1[k]} \oplus P_{i[k]}$
Fórmula2: $P_{i[j]} = padding \oplus C_{i-1[j]} \oplus X{[j]}$

Y eso es todo amigos ENLACE EXTERNO A:

https://www.youtube.com/watch?v=Ga_RwPmx-N0 , espero que te haya gustado.

Sed buenos!