[ECW] - BMPaaS

Enoncé #

Utilisation #

Si on accède directement à l’instance, on voit que le script BMPaaS.py nous propose d’obtenir un flag chiffré autant de fois qu’on le souhaite :

Code source #

import base64
import os

FLAG = base64.b85encode(open("flag.bmp", "rb").read()).decode()

CHARSET = base64._b85alphabet.decode()
N = len(CHARSET)

def generate_key(length):
    random_stream = os.urandom(length)
    return "".join(CHARSET[x % N] for x in random_stream)

def encrypt(plaintext, key):
    ciphertext = ""
    for i in range(len(plaintext)):
        ciphertext += CHARSET[(CHARSET.find(plaintext[i]) + CHARSET.find(key[i])) % N]
    return ciphertext

print("[+] Welcome to BMPaaS!")
print("[+] We offer a military-grade BMP encryption algorithm, powered by one of the safest OTP mechanisms in the world.")
print("[+] For now, uploading new BMP files is disabled. However, you can challenge our security by requesting an encrypted flag ;)\n")

print("[1] Request a new encrypted flag")
print("[2] Exit\n")

while True:

    choice = input("[?] Enter your choice: ")

    if choice == "1":
        key = generate_key(len(FLAG))
        print(encrypt(FLAG, key))

    elif choice == "2":
        exit()

    else:
        print("[x] Invalid choice.")

Analyse du code #

L’algorithme de chiffrement dans le script précédent est un algorithme cryptographique de type OTP  (One Time Pad)

Voici un résumé de ce que fais cet algorithme :

1. Le script lit les bits du fichier flag.bmp et les encode en base85 dans la variable FLAG
2. Le script créer la variable CHARSET et N :
   1. CHARSET correspond à l’alphabet base85 (0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~)
   2. N à la longueur de cet alphabet (85)
3. Le script génère une clé OTP aléatoire :
   1. La clé est de la même longueur que la variable N
   2. La clé est constituée de caractères aléatoire compris dans la variable CHARSET
   3. Exemple de clé : “kZds>~?4BJHkg{Z(Z@g9B;3zbo&1VM<k}jK>w+^W>&Yzx>3wXJnW&q=A`P1qh5MI+FNg8Zr|zlh2T@>mo<0hK”
4. Le script chiffre la variable FLAG avec la clé précédemment créée :
   1. Pour chaque caractère de la variable FLAG il cherche l’index dans la variable CHARSET et dans la clé précédemment créée
   2. Il additionne ces 2 index
   3. Il modulo ce résultat par la variable N

On peut en déduire plusieurs choses :

• Le flag est une image bmp
• La fonction os.urandom est une fonction sécurisée dont le caractère aléatoire ne peut être remis en cause ici (voir énoncé)
• L’algorithme (addition suivit du modulo) est de même plutôt sécurisé car le modulo est une opération à sens unique.

Explication de la faille #

Faisons un peu de maths (désolé mais ça va nous être utile !)

On peut transcrire l’algorithme de chiffrement sous l’équation suivante :

$$ c_i=p_i+k_i[mod N] $$

• p est le plaintext chiffré en base85 décrit dans le point 1 de l’analyse de code
• k est la clé de chiffrement OTP décrit dans le point 3 de l’analyse de code.
• c est le résultat chiffré

La fonction os.urandom renvoie aléatoirement un octet, cet octet a pour valeur de 0 à 255 soit 256 possibilités.

Or lorsqu’on génère la clé, on va modulo chaque octet par la longueur de l’alphabet base85 soit 85 :

def generate_key(length):
    random_stream = os.urandom(length)
    return "".join(CHARSET[x % N] for x in random_stream) // x est un octet qui peut prendre 256 possibilités et N est égale à 85

Mais 85*3=255, ce qui veut dire qu’il y a 4 nombres entre 0 et 255 qui modulo 85 donne 0 —> [0, 85, 170 et 255]

Les autres nombres compris entre 0 et 255 modulo 85 donneront 3 fois un résultat différent de 0.

Dit autrement :

• Tous les nombres entre 0 et 255 modulo 85 donneront 3 fois le même résultat (compris entre 1 et 84)
• Sauf les nombres [0, 85, 170 et 255] qui donneront 4 fois le résultat 0

On peut le voir avec cette commande :

>>> [i%85 for i in range(256)] :
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 0]

Et c’est là qu’est la vulnérabilité car il y a statistiquement plus de chances d’obtenir une clé qui modulo 85 donnera 0.

On reprend l’équation cryptographique :

$$ c_i=p_i+k_i[modN] $$

Si on chiffre un message avec une clé qui modulo 85 donne 0, on obtient alors k = 0 :

$$ c_i=p_i[modN] $$

Or comme p < N car p est issue d’un encodage en base85 donc contient des caractères appartenant à l’alphabet base85, l’équation devient:

$$ c_i=p_i $$

Le texte chiffré est alors égale au plaintext.

Exploitation de la faille #

Pour exploiter cette faille il nous suffit :

1. De récupérer suffisamment d’échantillons de flags chiffrés qu’on va stocker dans une liste (ça tombe bien on peut en récupérer autant qu’on veut !)
2. De redemander un nouveau flag chiffré qu’on va essayer de casser
3. De récupérer pour chaque caractère de ce flag chiffré sa valeur la plus fréquente dans nos échantillons

Puisque pour un grand nombre d’échantillons, statistiquement cette valeur censée être chiffré sera égale à la valeur du plaintext.

Si on récupère le plaintext, il ne nous restera plus qu’à le décoder en base85 (ce qui nous donnera les données binaires de l’image BMP en clair). Enfin on a plus qu’à re-créer le fichier BMP utilisé pour chiffrer le flag.

C’est ce que fait le script suivant en récupérant 50 000 échantillons :

from pwn import *

HOST = "instances.challenge-ecw.fr"
PORT = 42581

CHARSET = base64._b85alphabet.decode()
N = len(CHARSET)

NOMBRE_FLAGS_CHIFFRES = 50000

# Fonction pour récupérer les 50 000 flags chiffrés
def get_flags_chiffres(nb):
    # On se connecte à l'instance
    con = remote(HOST,PORT)
    
    # On initialise le tableau qui contiendra les 50 000 flags chiffrés
    flags_chiffres = []
    
    for i in range(nb):
        con.sendlineafter(b"[?] Enter your choice:",b"1") # On demande à l'instance de nous envoyer un flag chiffré
        data = con.recvuntil("\n")[1:-1] # On récupère les données formatées
        flags_chiffres.append(data) # On les ajoute au tableau
        print(f"\r-> {i}/{nb}",end='')
    return flags_chiffres

# Fonction pour rechercher le caractère le plus fréquent dans les flags chiffrés
def find_cara(flags_chiffres):
    # Liste pour stocker les caractères majoritaires
    resultats = []
   
    # Parcours des caractères de chaque position dans les flags chiffrés
    for i in range(len(flags_chiffres[0])):
        # Dictionnaire pour compter les occurrences de chaque caractère à cette position
        dictionnaire = dict()
        
        # Parcours des flags chiffrés pour compter les occurrences de chaque caractère
        for j in range(len(flags_chiffres)):
            caractere = flags_chiffres[j][i]  # Caractère à la position i dans le flag chiffré j
            if caractere in dictionnaire:
                dictionnaire[caractere] += 1
            else:
                dictionnaire[caractere] = 1
        
        # Recherche du caractère avec le plus grand nombre d'occurrences
        max_occurrence = 0
        caractere_majoritaire = None
        for z in dictionnaire:
            if dictionnaire[z] > max_occurrence:
                max_occurrence = dictionnaire[z]
                caractere_majoritaire = z
        
        # Ajout du caractère majoritaire à la liste des résultats
        resultats.append(caractere_majoritaire)
    
    # Retourne la liste des caractères majoritaires
    return resultats

# Fonction pour convertir une liste de caractères en une chaîne de texte
def to_string(resultats):
    s = ""
    for i in resultats:
        s += chr(i)  # Convertit l'entier en caractère et l'ajoute à la chaîne
    return s

# Fonction pour écrire une chaîne de texte encodé en base85 dans un fichier BMP
def write_flag(e: str):
    # Décode la chaîne base85 en données binaires
    b = base64.b85decode(e.encode())
    
    # Écrit les données binaires dans un fichier BMP
    with open("flag.bmp", "wb") as f:
        f.write(b)          
    
def main():
    flags_chiffres = get_flags_chiffres(NOMBRE_FLAGS_CHIFFRES)
    cara = find_cara(flags_chiffres)
    string = to_string(cara)
    write_flag(string)
    
if __name__ == "__main__":
    main()

Flag #

On obtient alors l’image suivant :

🚩 Flag : ECW{b85_modulo_bias_!!}