Pour ce deuxième write-up sur le CTF ECW édition 2023, j’aborde la résolution d’un challenge de la catégorie crypto « BMPaaS », dans lequel on va devoir exploiter une implémentation d’un algorithme de type OTP (One-Time Pad).
Analyse du code
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.")
Il s’agit d’un algorithme cryptographique de type OTP (One Time Pad), c’est à dire qu’on a une clé de chiffrement (aussi appelé masque) faisant la taille de la donnée à chiffrer. La donnée est ici une image BMP. L’algorithme a pour équation
c_{i} = p_{i} + k_{i} [mod N]- p est le plaintext chiffré en base85 (donc composé de caractère appartenant au charset de cette base).
- k est la clé (masque) de chiffrement. Elle est composé d’octet aléatoire généré par urandom qui ont été modulé par N=85 (fonction generate_key).
On note plusieurs choses. La fonction urandom est une fonction sécurisée dont le caractère aléatoire ne peut être remis en jeu. L’algorithme (addition suivit du modulo) est de même plutôt sécurisé car le modulo est une opération à sens unique.
La faille en théorie
La faille: urandom génère un octet, donc 256 possibilités. Seulement 85 n’est pas un diviseur de 256 (85*3=255), ce qui veut dire qu’il y a 4 nombres entre 0 et 255 qui modulo 85 donne 0. Et là est la vulnérabilité…
Parlons un peu probabilité. Soit X la variable aléatoire qui donne le nombre en sortie du modulo 85. Soit Y est la variable aléatoire qui donne le nombre généré par urandom. Comme on admet que la fonction urandom est sûre, on admet également que Y suit une loi uniforme de paramètre n=256.
P(X=0) = P(Y=0) + P(Y=85) + P(Y=165) + P(Y=255)
P(X=0)= \frac{1}{256} + \frac{1}{256} + \frac{1}{256} + \frac{1}{256} = \frac{4}{256}Donc P(X=0) = 4/256. Or, pour tout les autres nombres différents de 0, la probabilité que X soit égal à ce nombre est de 3/256. Il est donc plus probable d’obtenir un 0 dans la clé qu’un autre nombre < 85. Sur un certain nombre d’échantillons, on peut alors assumer qu’une majorité d’entre eux auront une clé composé du caractère se trouvant à l’indice 0, c’est à dire le caractère « 0 ».
Si je prends 50 000 échantillons (oui c’est beaucoup !), j’aurai alors environ (4/256)*50000 = 784 clé ayant comme caractère « 0 », contre environ 588 pour tout autres caractères du charset du base85. On a donc bypass l’aléatoire de la fonction generate_key.
Si on reprend l’équation cryptographique:
c_{i} = p_{i} + k_{i} [mod N]On aura alors le plus souvent k = 0, c’est à dire:
c_{i} = p_{i} [mod N]Or comme p < N car p issue d’un encodage en base85 donc contient des caractères appartenant au charset du base85, l’équation devient:
c_{i} = p_{i}ce qui nous arrange bien.
La faille en pratique
On récupère d’abord un grand nombre (50 000 pour être sure) d’échantillons (fonction init). Pour chaque caractère chiffré du flag on récupère sa valeur la plus fréquente dans nos échantillons (fonction get_most_char). Il nous suffit ensuite de décoder les données obtenues en base85.
from pwn import *
import colorama
def sorted_dict(dictionnaire):
dictionnaire_trie = dict(sorted(dictionnaire.items(), key=lambda item: item[1]))
return dictionnaire_trie
def get_max_key(dictionnaire):
if not dictionnaire:
return None
max_valeur = max(dictionnaire.values())
for cle, valeur in dictionnaire.items():
if valeur == max_valeur:
return cle
HOST = "instances.challenge-ecw.fr"
PORT = 39345
p = remote(HOST,PORT)
def init():
ALL_DATA = []
for i in range(50000):
p.sendlineafter(b"[?] Enter your choice:",b"1")
data = p.recvuntil("\n")[1:-1]
ALL_DATA.append(data)
print(f"\r-> {i}/15000",end='')
# f = open("bmp3.dump","w")
# f.write(str(ALL_DATA))
# f.close()
init()
# f = open("bmp3.dump","r")
# ALL_DATA = eval(f.read())
# f.close()
def print_num():
letter_1 = {}
for i in range(len(ALL_DATA)):
n = list(ALL_DATA[i])[0]
if n in letter_1:
letter_1[n] += 1
else:
letter_1[n] = 1
print(sorted_dict(letter_1))
def get_most_char():
x = ""
for chara in range(len(ALL_DATA[0])):
letter = {}
print(f"\r-> getting letter {chara}/{len(ALL_DATA[0])}",end='')
for i in range(len(ALL_DATA)):
n = list(ALL_DATA[i])[chara]
if n in letter:
letter[n] += 1
else:
letter[n] = 1
x += chr(get_max_key(letter))
return x
x = get_most_char()
# x = "LQUQV00000004>r004Xd003CM000F500p3178tkO002}500HvU000vU000000W00000000{{R60009300000050BTqQgZ+R0000000000000000000000000000000000000000000v000000000000006200000000000K000000}000m007000000960|NsC000000000000)R90|NsC0iNj900RR9000030|NsC0|NsC0|Ns90090000(R4000000000000RR90|}sC0|Nj6000000|NsC0~Nj6000x0000030|NsC0{{R3000000000000RR9000030|NsC0{{330|NsC0|Nj600RR90|Ns90000000RR90|NsC0|Nj60D000000030|NsC0{{R300000000960{{R30|NWC0|Nj6000000|NsC0|Nj60000000000000960{{R300a00000960|NsC000030|NsC0{{R300000000960{{n30i000000960|NsC000f000000000000|NsC0|Nj6<0RR9000030|Nj6000000|Ns90000000RR90|NsC0|NsC0{{R30|NsC0|NsC0|NsC0|Ns9000960{{R30|Ns9000960|NsC0|N39000960|NsC000030|NsC0{QR30|Nd9000960|NsC000030|NsC0|NsC0|Ns9000960|NsC0|NsC0|NbC0|NsC000030|NsC0{{R30|NsC0|Nj600RR9200030|NsC0{{R30|Ns9000960iNsC000030|Nj600RR90|Ns9000960{{R3Q|Ns90009?0|NsC000030|NsC0|NBC0|NsC0|NsC0{{R{0|NsC0|Nj<0VRR9000030|Nj600R^90|Ns9000960|NsC0|Ns90000000RR90|NsC0|NuC0|msC0|NsC0|NsC0|NsC!|NsC0|NsC0{{R30|Ns9000000000000i030|NsCj{{R3}|Nsi0|NsC0|NsC000030|asC0{{z30|NsC0|Nj600RR900000000960|NsC000030FNsD0{{R30|NsC0|Nj$000000|NsC0|NjO0000000Z050|NsC0|NsC0ENsC0|NsC0|NsC000030|NsC0{{R30|NsC0|Nj600RR9600030|NsC0{$R30|Ns9000960|NsC00m030|Nj600RR90<Ns9000960{{R30|Ns9000960|NsC0000&0|NsCr|NsC0|Ns`0|NsC0{{R30|NsC0|Nj600RR9000030|Nje00RR90|Ns9000960{{R3000030|NsC0|NsC0|NsC0|NsC0|NsC0|NsC0|Nj600RR9000030|NsC0{{R3000003000000RR90|NsC0PNsC0{{R30|NsC0|NsC0|NsC000030|NsC08NsC0|NVC0|N|600RR90|Ns9000960wNsC000000000000RR90|Ns900n960|NsC0+0032|Nj600RP90|NsC0|NsC0|NsC0|NsC0|NsC0|NsC000000*00007RR900000000960|NsC0|Ns9!000C00RR90|NsN0|N?600000000030|Nj600RR90|N{904096({{R30|NsCR1Nj6000K00UNsC0|8sC8|NsC0|NsC0|NsC0{{R300000000960|NsC0|NsC!|NsC0{{R300y0000096W|LsC000000000000RR90|NsC0|NmCP|NsC0|NsC0|Nj600RR9020030|NRC0{{R30rNs9000000000000000000960|NsC0}0000000000RR9000030|rsC^|NvC0|NsC0|NJ600RR90|Ns90000000RR9000030|NsC0|NsC0|NsC0|Nj6000000|NsC0|Nj6000i000000000960|NsC0|Ns80|NsC0=NsC0|NsA0|NsC0|NsC0|NsCz|NPC0|NsC0^NsC0|NsCm|NsC0|NsC0|NsC0|NsC000030|NsC0|NsC0|NsC0|NsC0{{R3g|NsC0|NsC0|NsC0|8YC0|NsC0|NsC0|NsC0|$sC0{{R30|NsC0|NsC0|NsC000030|NsC0|NsC0|NsC0|NsC0|NsC0|NsC0|NsC0|NcC0|NsC0|NsC0|NsC0|NsC0|Nj600RR9000030|Nj6000000|Ns900n0"
f = open("flag.bmp","wb")
f.write(base64.b85decode(x.encode()))
f.close()