miércoles, 2 de mayo de 2012

Encryption Service del PlaidCTF

El tema de los CTF es algo en lo que no suelo meterme. En ocasiones me apunto a alguno, pero no puedo dedicar todo el tiempo que requieren, así que suelo intentar sacar algún rato para hacer una prueba o dos y poco más.

El pasado fin de semana tuvo lugar el PlaidCTF, organizado por los PPP, un conocido equipo que compite habitualmente en los CTF. Los int3pids, para variar, no podían faltar a uno de estos eventos, así que aproveché que conozco a varios de ellos para que me dejaran conectarme algún ratejo e intentar alguno de los retos.

Solo me dio tiempo a hacer un par de retos en el rato que le pude dedicar durante el fin de semana, pero de ellos me gustó uno llamado "Encryption Service", que decía algo así:

We found the source code (http://ctf.plaidctf.com/media/files/encryption_service-00280bdc6eb758556bec5d38939aeaf8/encryption_service.py ) for this robot encryption service, except the key was redacted from it. The service is currently running at 23.21.15.166:4433

Como no sé si dejarán el código fuente indefinidamente publicado, os lo dejo subido AQUÍ por si acaso.

Si leéis un poco que hace el servicio, vereis que sigue un proceso tal que así:
  1. El cliente conecta al servidor
  2. El servidor genera aleatoriamente un IV (vector de inicialización) de 16 bytes que posteriormente usará para el cifrado, y se lo pasa al cliente.
  3. El cliente elige una cadena de texto que le debe pasar al servidor en formato: longitud (en 4 bytes) + cadena
  4. El servidor lee la cadena y la concatena con PROBLEM_KEY (que presumiblemente es la clave que se necesaria para superar la prueba) y lo rellena de caracteres hasta que la longitud de la cadena sea múltiplo de 16 (necesario para el cifrado).
  5. La cadena resultante es cifrada mediante AES en Modo CBC con el IV que se nos ha proporcionado y una clave que desconocemos (no son todo 'x', por supuesto).
  6. El resultado del cifrado vuelve al cliente en el mismo formato que antes: longitud (en 4 bytes) + cadena
La verdad es que cuando vi "padding" (relleno) lo primero que pensé fue en un ataque de Padding Oracle, pero en realidad no era nada de eso.

Lo primero que hice fue buscar un diagrama del Modo CBC (Cipher-block Chaining), porque al no ser una persona que se dedica a temas de criptografía (ni tampoco un apasionado del tema), la verdad es que no lo tenía en la cabeza en absoluto. En la Wikipedia sin ir más lejos podemos encontrar este:


Vamos a repasar las variables que tiene este diagrama, a ver que situación tenemos:
  • PlainText: Aunque lo que enviemos al servicio será concatenado con más texto, podemos utilizar cadenas de 16 bytes y así controlaríamos completamente el PlainText del primer bloque. Con 32 bytes controlaríamos el segundo, y así sucesivamente. Podríamos decir que tenemos un control total del PlainText de algunos bloques, pero no del PlainText completo.
  • IV: NO lo controlamos. Es generado aleatoriamente por el servidor. Eso sí, el servidor nos lo da a conocer antes de que le digamos que cadena debe cifrar.
  • Key: NO lo controlamos NI somos capaces de saber cual es. Es algo que permanece interno al servidor y no tenemos ni idea de cual será.
  • CipherText: El servicio nos devuelve el texto cifrado. NO lo controlamos de una forma directa, pero se produce a partir de algunas de los parámetros que sí controlamos, y algunos otros que no. 
Así de primeras, parece que podemos "anular" un poco el factor de aleatorización que introduce el IV, ya que aunque no lo controlamos directamente, este únicamente se utiliza para hacer un XOR con la cadena que introduzcamos. Por poner un ejemplo, imaginad que quisiéramos que la cadena 'ABCDEFGHIJKLMNOP' (16 bytes) llegara tal cual a cifrarse con la clave que desconocemos. Solo tendríamos que seguir el siguiente proceso:
  1. Conectamos y obtenemos el IV
  2. Calculamos PlainText = 'ABCDEFGHIJKLMNOP' XOR IV y lo enviamos como cadena a cifrar
  3. Al llegar al servidor y hacerse otra vez XOR con el IV, ambos se anulan, y la cadena que llega para cifrarse con la clave es 'ABCDEFGHIJKLMNOP'.
En esta situación podemos realizar los llamados Chosen Plaintext Attacks, porque son ataques que pretenden obtener información sobre la clave de cifrado a partir del conocimiento de los plaintext y de los ciphertext, pudiendo ser el plaintext elegido por el criptoanalista.

Buscando un poco a ver que opciones tenemos, podemos ver como se pueden realizar algunos ataques contra este diseño, muy similares a los publicados por Juliano Rizzo y Thai Duong el pasado año (BEAST). De entre la documentación que he podido leer por ahí, me ha gustado mucho (por su simplicidad) la que publicó el equipo de Tor Project AQUÍ, que dice algo así:


The ability to decide where block boundaries fall turns out to be a big deal. Let's suppose that instead of filling up a full plaintext block with 16 bytes of Evil, the attacker only fills up 15 bytes... so the block will have 15 bytes the attacker controls, and one byte of the secret. Whoops! There are only 256 possible values for a single byte, so the attacker can guess each one in turn, and use the older guess-checking attack to see if he guessed right.


En este caso, viendo el código del servidor, no necesitamos probar 256 valores para obtener el valor de un byte, sino que con comprobar los valores [a-z_] tendremos más que suficiente. Imaginad que queremos saber si el primer caracter es una 'x', podríamos hacer algo así:
  1. Tenemos la cadena 'AAAAAAAAAAAAAAA' (15 bytes) que sera concatenada con el primer caracter del PROBLEM_KEY y será cifrada con la clave que desconocemos, y nos proporcionará un ciphertext.
  2. Probamos lo mismo pero esta vez con la cadena 'AAAAAAAAAAAAAAAx' (16 bytes). En esta ocasión el PROBLEM_KEY no va a entrar en este bloque, sino en el siguiente, pero si su primer caracter era una 'x' el plaintext va a ser identico al de antes, y como la clave es la misma... el ciphertext debería ser igual.
  3. Si vamos probando los posibles valores ([a-z_]) y comparando los ciphertext descubriremos cual es el valor de la X.
  4. Este proceso se puede repetir reduciendo el número de bytes (14 bytes) para descubrir el segundo caracter, y así sucesivamente hasta descubrir toda la cadena.


Bueno, parece que lo tenemos ya casi todo hecho, pero... ¿y el IV? ¿No nos va a fastidiar un poco al "mezclarse" con PROBLEM_KEY? Pues... SI, así de primeras nos va a fastidiar un poco el asunto,  porque podemos anular el IV con el PlainText que nosotros elegimo, pero cuando se concatena con el PROBLEM_KEY... perdemos esa capacidad. Veamos como lo haremos:

Si recordamos el diagrama y el control que tenemos sobre los elementos de él, sabemos que tenemos un control parcial del PlainText y una ausencia total de control del IV que se aplica al primer bloque, pero si conseguimos anular el IV inicial con los primeros 16 bytes del PlainText que elijamos entonces convertimos el ciphertext del primer bloque en estático (siempre será el mismo), con lo que el algoritmo pierde la aleatorización que le hubiera aportado el IV para este y los siguientes bloques. Para hacer esto simplemente elegimos los primeros 16 bytes que queramos (16 'A's, por poner el mismo ejemplo) y le hacemos XOR con el IV de cada conexión que hagamos, el cual se anulará al hacerse XOR con el mismo valor en el servidor. Hecho esto, podemos aplicar la técnica que comentaban en el blog del Tor Proyect a partir del segundo bloque.

Por lo tanto, vamos a utilizar el primer bloque para cargarnos la influencia del IV, y los dos siguientes para obtener el PROBLEM_KEY, que según el código al que hemos tenido acceso son 29 bytes, empleando la técnica que hemos descrito antes:
  1. Conectamos y obtenemos el IV.
  2. Cogemos los 16 bytes estáticos y hacemos XOR con el IV. Con eso obtenemos los primeros 16 bytes de nuestra cadena de entrada.
  3. Creamos una cadena de 15 'A's y la concatenamos con la anterior. La enviamos para cifrar y nos guardamos el ciphertext del segundo bloque.
  4. Repetimos la operación, pero vez vamos añadiendo a las 15 'A's los posibles valores [a-z_] y comprobamos si el ciphertext es el mismo que antes. Si lo es este es el caracter que buscamos.
  5. Repetimos el proceso con 14 'A' (+ 1 caracter obtenido previamente + uno que probamos todas las opciones), luego con 13 (+ 2 obtenidos + 1 probando), y así sucesivamente hasta que hayamos llenado todo el primer bloque con los primeros 16 bytes del PROBLEM_KEY.
  6. Nos vamos ahora al tercer bloque, y seguimos repitiendo idéntico proceso hasta que hayamos obtenido los 29 bytes del PROBLEM_KEY.

La implementación de todo esto la podeis descargar de AQUÍ si quereis ver todos los detalles. El script funcionaría algo así:

$ time ./encryption_f___er.py
p
r
e
d
i
c
t
a
b
l
e
_
i
v
s
_
a
r
e
_
d
a
n
g
e
r
o
u
s

PASSWORD = predictable_ivs_are_dangerous

real 3m28.070s
user 0m0.115s
sys 0m0.107s

Como podeis ver, hemos sacado el PROBLEM_KEY en unos pocos minutos sin conocer la clave de cifrado, solo por la posibilidad de hacer un Chosen-Plaintext-Attack.

5 comentarios :

dreyercito dijo...

La forma en que finalmente lo resolvimos: en lugar de enviar una cadena estatica XOReada con el IV, basta enviar como primer bloque el propio IV para anular/fijar su efecto en el segundo bloque.

Jose Selvi dijo...

@dreyercito: Pues sí, lo mismo es :) Es como si la cadena estática, en lugar de 'AAA' fuera '\x00\x00\x00'

Darizotas dijo...

Para añadir más material de lectura. En formato vídeo, en el curso online de criptografía: https://class.coursera.org/crypto/auth/welcome

también hablan de este tipo de ataques.

HTH.

Anónimo dijo...

Mi solución: https://pad.nopcode.org/p/foovar

Jose Selvi dijo...

@Anónimo: Me gusta más la tuya, más cortita y elegante :)

La mia es un poco chapuza, pero bueno, funciona xD