Analyse du challenge

Neo challenge

Dans ce challenge, il nous est demandé de choisir la pilule bleu, ou la pilule rouge. Après une rapide analyse, la pilule bleu sert juste à lancer un alert() Javascript, alors que la pilule rouge permet d'envoyer son matrix-id au serveur.

En tentant de modifier notre matrix-id, on tombe rapidement sur ce message :

Neo challenge

Celà ressemble fortement à une vulnérabilité de type CBC padding oracle...

Rappel sur le fonctionement de CBC

Pour expliquer le fonctionnement de l'attaque, un petit rappel du fonctionnement de CBC est nécessaire.

Lorsque nous souhaitons utiliser un chiffrement par bloc tel que AES sur des messages de longueur supérieur à la taille d'un bloc, nous devons utiliser un mode de chiffrement tel que CBC (il en existe d'autres, tel que CTR, CFB, GCM...).

Pour démarrer l'algorithme, le mode CBC à besoin d'un IV (vecteur d'initialisation). Appellons \(E_k\) la fonction de chiffrement de bloc (ici, l'AES), et \(D_k\) la fonction de déchiffrement.

Lorsque l'on souhaite chiffrer un message, on doit le découper en \(n\) blocs de taille fixe (16 bytes pour AES). Appellons, \(C_i\) le chiffré du bloc \(i\) du message, et \(P_i\) le bloc \(i\) du message en clair.

Pour chiffrer un message de \(n\) blocs en mode CBC, on réalise les opérations suivantes :

$$C_{1} = E_k(IV \oplus P_{1})$$

$$\forall i \in \{2, ..., n\},~C_{i} = E_k(C_{i-1} \oplus P_{i})$$

Le déchiffrement réalise les opérations dans l'ordre inverse :

$$\forall i \in \{2, .., n\},~P_{i} = D_k(C_{i}) \oplus C_{i-1}$$

$$P_{1} = D_k(C_{1}) \oplus IV$$

Rappel sur le padding PKCS#7

Il est rare qu'un message soit d'une longueur multiple de la taille du bloc, ce qui est nécessaire pour appliquer un chiffrement par bloc.

Afin de pallier à ce problème, on rajoute de l'information au message, afin que sa longueur devienne multiple de la taille du bloc. C'est ce qu'on appelle l'opération de remplissage (ou padding en anglais).

Une des norme les plus utilisée est la norme PKCS#7.

Soit \(T_b\) la taille d'un bloc (16 pour l'AES), et \(T_m > 0\) la taille du message à chiffrer.

On a $$T_m = kT_b + r~~~~~~~~k,r \in \mathbb{N},~r < k$$

Si \(r = 0\), on ajoute \(T_b\) octets de valeur \(T_b\) à la fin du message. Sinon, si \(r > 0\), on rajoute \(r\) octets de valeur \(r\) à la fin du message.

Si on a par exemple le message "HelloWorld" à chiffrer, et que \(T_b = 4\), le message auquel on aura ajouté le padding aura cette forme (ici, on a 3 blocs) :

Hell || oWor || ld\x02\x02

CBC padding oracle

Maintenant que j'ai expliqué le fonctionnement du mode CBC et de comment est utilisé la norme PKCS#7 pour rajouter du bourrage à un message, je vais détailler le fonctionnement d'une attaque de type padding oracle sur CBC.

Ce type d'attaque est possible lorsque l'on peut soumettre des chiffrés à un oracle de déchiffrement qui nous indique si oui ou non le message clair obtenu a un padding correct.

Soit \(C_i\) le bloc chiffré que l'on souhaites déchiffrer, et \(C'\) un bloc que nous controlons entièrement et qui nous servira à déchiffrer \(C_i\).

L'attaque consiste à envoyer un message de la forme :

\(C'\) || \(C_i\)

Voyons comment on peut retrouver le dernier octet du bloc \(P_i\), d'indice \(T_b\).

Vu que l'on controle le dernier octet de \(C'\), on peut tester les 256 possibilités, jusqu'à ce que l'oracle nous dise que le padding est correct.

Si le padding est correct, celà signifie que le dernier octet de \(P'\) à toutes les chances d'être égal à 0x01 d'après la norme PKCS#7.

D'après les formules de déchiffrement du mode CBC, on a :

$$P' = D_k(C_i) \oplus C'$$

On rajoute \(C_{i-1}\) des deux côtés de l'équation :

$$\Longleftrightarrow C_{i-1} \oplus P' = C_{i-1} \oplus D_k(C_i) \oplus C'$$

D'après la définition de CBC : \(P_i = C_{i-1} \oplus D_k(C_i)\) :

$$\Longleftrightarrow C_{i-1} \oplus P' = P_i \oplus C'$$

$$\Longleftrightarrow P_i = P' \oplus C_{i-1} \oplus C'$$

On a donc pour le dernier octet :

$$P_i[T_b] = 1 \oplus C_{i-1}[T_b] \oplus C'[T_b]$$

En itérant le procédé sur les octets d'indice \(T_{b}-1, T_{b}-2, ..., 1\), on peut alors procéder au déchiffrement complet du bloc \(C_i\) et donc du message complet.

Il faut par contre bien penser à modifier les derniers octets du bloc \(C'\) (cf. dernière équation).

Soit \(i\) l'indice de l'octet à déchiffrer :

$$\forall j > i,~C'[j] = (T_b-i+1) \oplus P_i[j] \oplus C_{i-1}[j]$$

Exploit

Voici l'exploit Python permettant de déchiffrer l'ensemble des blocs du matrix-id :

import socket
import sys
import re
from binascii import *
import urllib
import base64

BLOCK_SIZE = 16
URL = 'http://crypto.chal.csaw.io:8001/'

def get_matrix_id():
    f = urllib.urlopen(URL)
    url = f.read()

    for l in url.split("\n"):

        m = re.search("value=\"(.+)\">", l)
        if m:
            return m.group(1)

    return None

def check_padding(matrix_id):
    params = urllib.urlencode({'matrix-id': matrix_id})
    f = urllib.urlopen(URL, params)

    return f.read().find("exception") == -1

def assemble_blocks(b1, b2):
    m = "".join(map(chr, b1))
    m += "".join(map(chr, b2))

    return m

def attack_block(block, blocks):
    cur = [0 for i in xrange(BLOCK_SIZE)]
    plain = [0 for i in xrange(BLOCK_SIZE)]

    for i in xrange(BLOCK_SIZE-1, -1, -1):
        found = False

        for j in xrange(i+1, BLOCK_SIZE):
                cur[j] = (BLOCK_SIZE - i) ^ plain[j] ^ blocks[block-1][j]

        for b in xrange(0, 0x100):
            cur[i] = b

            m = assemble_blocks(cur, blocks[block])

            if check_padding(base64.b64encode(m)):
                plain[i] = (BLOCK_SIZE - i) ^ cur[i] ^ blocks[block-1][i]
                print "[+] Plain =", plain
                found = True
                break

        if not found:
            print "Byte", i, "not found !"
            sys.exit(1)

    return plain

def split_blocks(matrix_id):
    blocks = [[] for i in xrange(len(matrix_id)/BLOCK_SIZE)]

    for i in xrange(len(matrix_id)):
        blocks[i/BLOCK_SIZE].append(ord(matrix_id[i]))

    return blocks

def block_to_text(block):
    while block[-1] <= 16:
        del block[-1]

    return "".join(map(chr, block))

matrix_id = get_matrix_id()
blocks = split_blocks(base64.b64decode(matrix_id))

flag = ""

for i in xrange(len(blocks)-1, 0, -1):
    print "[+] Attacking block %d" % (i)

    b = attack_block(i, blocks)
    flag = block_to_text(b) + flag
    print "FLAG = ", flag

On obtient alors le flag :

FLAG =  flag{what_if_i_told_you_you_solved_the_challenge}