16. Attaque de CBC par renversement d'octet

CBC bitflipping attacks

Generate a random AES key.
Combine your padding code and CBC code to write two functions.
The first function should take an arbitrary input string, prepend the string:
"comment1=cooking%20MCs;userdata="
.. and append the string:
";comment2=%20like%20a%20pound%20of%20bacon"
The function should quote out the ";" and "=" characters.

The function should then pad out the input to the 16-byte AES block length and encrypt it under the random AES key.

The second function should decrypt the string and look for the characters ";admin=true;" (or, equivalently, decrypt, split the string on ";", convert each resulting string into 2-tuples, and look for the "admin" tuple).

Return true or false based on whether the string exists.
If you've written the first function properly, it should not be possible to provide user input to it that will generate the string the second function is looking for. We'll have to break the crypto to do that.
Instead, modify the ciphertext (without knowledge of the AES key) to accomplish this.
You're relying on the fact that in CBC mode, a 1-bit error in a ciphertext block:

• Completely scrambles the block the error occurs in
• Produces the identical 1-bit error(/edit) in the next ciphertext block.

Stop and think for a second.
Before you implement this attack, answer this question: why does CBC mode have this property?

Fonctions de chiffrement et de validation

La première étape est de coder les différentes fonctions requises pour l'exercice ; celle qui ajoute préfixe et suffixe puis chiffre, celle qui déchiffre le texte et valide le statut de l'utilisateur:

import os
from cryptopals import cbc_encrypt, cbc_decrypt, padding, padding_unset

prepend = b"comment1=cooking%20MCs;userdata="
append = b";comment2=%20like%20a%20pound%20of%20bacon"

key = os.urandom(16)
iv = os.urandom(16)

def is_admin(text):
    return b";admin=true;" in cbc_decrypt(text, key, iv)

def submit_string(string):
    text = prepend + string.decode().replace("=", "_").replace(";", "_").encode() + append
    print(len(text))
    return cbc_encrypt(text, key, iv)

On peut les invoquer comme suit:

cipher_text = submit_string(b"abc")
print(is_admin(cipher_text))

Pour rappel, le fichier cryptopals.py qui nous sert à conserver les fonctions utiles pour plusieurs exercices à la contenu suivant :

from Crypto.Cipher import AES
from base64 import b64decode

import logging

def xor_hex(string_one, string_two):
    return hex(int(string_one, 16) ^ int(string_two, 16))[2:]

def xor_single_char_breaker(hex_string):
    length = len(hex_string) // 2

    xor_list = []

    for i in range(32, 127):
        try:
            xored_hex = xor_hex(hex_string, hex(i)[2:]*length)
            xor_list.append({
                "char": chr(i),
                "string": bytearray.fromhex(xored_hex).decode(),
                "score": char_frequency_score(bytearray.fromhex(xored_hex).decode())
            })
        except:
            pass

    return sorted(xor_list, key=lambda d: -d['score'])


FREQUENCY_SCORES = {
    "A": 8.2,
    "B": 4.4,
    "C": 5.2,
    "D": 4.3,
    "E": 13,
    "F": 4,
    "G": 1.6,
    "H": 6.1,
    "I": 7,
    "J": 0.51,
    "K": 0.86,
    "L": 2.4,
    "M": 3.8,
    "N": 6.7,
    "O": 7.5,
    "P": 4.3,
    "Q": 0.22,
    "R": 6,
    "S": 6.3,
    "T": 9.1,
    "U": 2.8,
    "V": 0.82,
    "W": 5.5,
    "X": 0.045,
    "Y": 0.76,
    "Z": 0.045,
    "'": 1,
    " ": 15,
}
def char_frequency_score(string):
    string = string.upper()
    score = 0
    for char in string:
        if(char in FREQUENCY_SCORES):
            score += FREQUENCY_SCORES[char]
        else:
            score -= 1
    return score

def xor_string(string, key):
    key_length = len(key)
    result = []
    for i in range(len(string)):
        result.append(chr(ord(string[i]) ^ ord(key[i%key_length])))
    return "".join(result)

def xor(var, key):
    return bytes(a ^ b for a, b in zip(var, key))

def padding(bytes_string, block_length=16):
    if len(bytes_string) == block_length:
        return bytes_string
    else:
        padding_length = block_length - (len(bytes_string) % block_length)
        return bytes_string+(bytes([padding_length])*padding_length)

def padding_unset(bytes_string, block_length=16):
    try:
        if(len(bytes_string) != block_length):
            raise ValueError("Block does not match expected block length")
        last_byte_value = bytes_string[-1]
        
        if(last_byte_value >= block_length):
            return bytes_string
        elif(
            len(set(bytes_string[-last_byte_value:])) == 1 
            and all(bytes_string[i] >= block_length for i in range(0,block_length-last_byte_value))
        ):
            return bytes_string[:block_length-last_byte_value]
        else:
            raise ValueError("Invalid padding value")
    except Exception as e :
        logging.error(e)

def ecb_encrypt(text, key):
    aes_object = AES.new(key, AES.MODE_ECB)
    return aes_object.encrypt(padding(text, 16))

def ecb_decrypt(cipher_text, key):
    aes_object = AES.new(key, AES.MODE_ECB)
    return aes_object.decrypt(cipher_text)

def cbc_encrypt(text, key, mask):
    block_size = len(mask)
    blocks = [padding(text[i:i+block_size], block_size) for i in range(0, len(text), block_size)]
    result = b""
    for block in blocks:
        mask = ecb_encrypt(xor(block, mask), key)
        result += mask
    return result

def cbc_decrypt(cipher_text, key, mask):
    block_size = len(mask)
    blocks = [cipher_text[i:i+block_size] for i in range(0, len(cipher_text), block_size)]
    result = b""
    for block in blocks:
        result += padding_unset(xor(ecb_decrypt(block, key), mask), block_size)
        mask = block
    return result

Théorie de l'attaque par renversement d'octet

Pour rappel, voici à quoi ressemble les étapes de déchiffrement de CBC :

D'après un schéma de wikimedia

Chaque bloc subi une opération XOR (avec l'IV pour le premier bloc, puis avec le bloc chiffré précédent pour les autres), puis est déchiffé.

Imaginons maintenant que l'on modifie un octet dans le second bloc chiffré (représenté par le octet rouge sur le schéma). Cela aura pour effet de rendre tout le contenu déchiffré du second bloc illisible, mais modifiera aussi par XOR le résultat du dernier bloc une fois déchiffré:

De manière très simple, cela signifie que si l'on chiffre une première fois une chaine de donnée, alors en modifiant de manière précise celle-ci et en la renvoyant à une fonction qui va la décoder, on peut insérer de la donnée arbitraire.

Ainsi, si l'on sait que ce texte est généré par la fonction de chiffrement:

comment1=cooking%20MCs;userdata=abc;comment2=%20like%20a%20pound%20of%20bacon

Et que l'on veut également voir apparaitre la suite de caractères suivant:

;admin=true;

Alors si l'on prend les 12 derniers caractères du texte qui sera généré et qu'on le XOR avec le texte qu'on veut insérer, on a :

from cryptopals import xor

xor_result = xor(b"20of%20bacon", b";admin=true;")
print(xor_result)

Qui nous donne la valeur:

\tQ\x0b\x0bL\\\r\x16\x13\x16\nU

Il faut de nouveau appliquer une transformation XOR avec les octets chiffrés originiaux du bloc précédent celui qu'on veut modifier

Ainsi, si on remplace les 8 derniers caractères de l'avant dernier bloc du texte chiffré retourné par la fonction submit_string et que l'on utilise ces blocs modifiés en argument de la fonction is_admin, on obtient bien le texte ;admin=true;

Code

L'implémentation en code Python est triviale :

cipher_text = submit_string(b"11111111111111111111111111111111")
custom_mask = xor(xor(cipher_text[32:48], b"1111111111111111"), b";admin=true;1111")
cipher_text = custom_mask.join([cipher_text[:32], cipher_text[32+len(custom_mask):]])

result = cbc_decrypt(cipher_text, key, iv)
print(is_admin(cipher_text))

La première ligne crée un texte qui, avant d'être chiffré, aura la forme suivante (les retours à la ligne représentes les séparations de blocs) :

comment1=cooking
%20MCs;userdata=
1111111111111111
1111111111111111
;comment2=%20lik
e%20a%20pound%20
of%20bacon

Une fois chiffré il ressemblera à cela :

\xc3#u\xdeW>N\xe8\xe7-#$\xd3\x19\r\xae
\xcd\xcc\xce'\xb3\xdd\xa2\xd2\xe4Da\x84\xf0\xe5\xac\xd4
W)\xbe\xb8h\x05$\xf1<\xb1\xc8\xeb\xee:j>
\x97qN\x8a\xe3\xc4\xcfY\x82\xfd\x84\xa8\xcdGR4
\xbe\xd3\xb0\x17\x15\x85g\x9d*\xbd\x1eCt\x9en\xd1
\x85b\xd6ey\x8e\xa0HLz\x14\x983\xa6\x08\xcd
6:\xb6\x15?\xf9\x0c\xf4\x18\xc48\x15\xc3\xfa\xd8\x8f

La ligne de code créant la variable custom_mask a pour effet d'appliquer deux opérations XOR sur le bloc 4:

1111111111111111 ^ \x97qN\x8a\xe3\xc4\xcfY\x82\xfd\x84\xa8\xcdGR4 ^ ;admin=true;1111

De cette manière là, on trouve la valeur qui en remplaçant le bloc 3, sera appliqué comme masque XOR lors du déchiffrement du bloc 4.

Le résultat de cette valeur vient ensuite logiquement remplacer le bloc 3 dans notre donnée chiffrée.

Lorsque l'on exécute ce script, la fonction is_admin nous reconnait bien comme administrateur car elle déchiffre la chaine de caractère ;admin=true;1111 depuis la donnée qu'on lui envoie :

comment1=cooking%20MCs;userdata=\xf0\x17\n3\x98\xc3\xfbn6\xbc\x05f\xbc\x96>\xed;admin=true;1111;comment2=%20like%20a%20pound%20of%20bacon