L’épreuve fournit un script Python carotte-radis-tomate.py qui :
- Génère une clé AES-256 aléatoire.
- Interprète cette clé comme un entier et affiche plusieurs restes modulo de celui-ci.
- Chiffre le fichier
flag.txt.
Nous avons également un fichier output.txt qui contient les résultats des différents modulos effectués.
Quelle est la vulnérabilité possible ?
Bien que la valeur exacte de la clé K ne soit jamais révélée, nous connaissons plusieurs restes modulo de cette clé. Autrement dit, il fournit des informations partielles sur K sous la forme : K mod m1, K mod m2, …., K mod mn
Même sans connaître K, il est alors possible de trouver l’ensemble des nombres qui possèdent ces mêmes restes modulo. Plus le nombre de restes est élevé, plus il va être difficile de trouver plusieurs valeurs de K correspondantes. Au bout d’un certain moment, si le produit de ces modulos est supérieur à 2^256 (ce qui est le cas dans cette épreuve), il n’existe qu’une seule clé K valide.
On peut donc reconstituer cette clé unique à partir de ses restes modulo grâce au Théorème chinois des restes (CRT)
Code complet
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from sympy.ntheory.modular import crt
# Données connus
mods = [
17488856370348678479,
16548497022403653709,
17646308379662286151,
14933475126425703583,
17256641469715966189
]
rem = [
392278890668246705,
4588810924820033807,
17164682861166542664,
12928514648456294931,
5973470563196845286
]
enc_hex = "2da1dbe8c3a739d9c4a0dc29a27377fe8abc1c0feacc9475019c5954bbbf74dcedce7ed3dc3ba34fa14a9181d4d7ec0133ca96012b0a9f4aa93c42c61acbeae7640dd101a6d2db9ad4f3b8ccfe285e0d"
# CRT pour récupérer la clé K
K, _ = crt(mods, rem)
# Conversion en clé
key = int(K).to_bytes(32, byteorder="big")
# Déchiffrement
cipher = AES.new(key, AES.MODE_ECB)
plaintext = unpad(cipher.decrypt(bytes.fromhex(enc_hex)), 16)
# Affichage du Flag
print(plaintext)