Détails
- Catégorie : Crypto
- Points : 344
- Résolutions : 67
Description
Vous devez déchiffrer le flag :-)
Code source :
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
class TRex:
def __init__(self, key):
= len(key)
N = 2 ** (8 * N)
M self.key = key
self.iv = int.from_bytes(key, "big")
= lambda x: ((2 * x + 1) * x)
R for _ in range(31337):
self.iv = R(self.iv) % M
self.iv = int.to_bytes(self.iv, N, "big")
def encrypt(self, data):
= AES.new(self.key, AES.MODE_CBC, iv = self.iv)
E return self.iv + E.encrypt(pad(data, 16))
if __name__ == "__main__":
= TRex(os.urandom(16))
E = open("flag.txt", "rb").read().strip()
flag = E.encrypt(flag)
c print(c.hex())
# 070a4a5811dd013c301f30070924528796cb8fe8ddd6d8851f90ab1a8977e9c71accbed0a5936414445739ce76763002fd29337834c8976fef36decdc522a6b93c967c90d0e69e46674d634ba5a9badbd834bad8042515029b6fa833c98da0a7
Comprendre le problème
Le flag est chiffré en utilisant AES128-CBC. L’IV est dérivé de la clé de chiffrement en appliquant la transformation R
31337 fois, modulo 2^128.
Le but est clairement de récupérer la clé de chiffrement à partir de l’IV et de déchiffrer le flag.
Résoudre le problème
Après avoir joué un peu avec la transformation R
, j’ai réalisé que l’appliquer M/2 fois à une valeur x
produit à nouveau x
. Cela a du sens puisque M
est une puissance de 2, donc l’ordre du groupe généré par R
est au plus M/2.
Mais parce que M = 2^128, appliquer naïvement la transformation R
à l’IV 2^127-31337 fois serait infaisable dans un temps raisonnable.
Il est possible d’appliquer la transformation de manière intelligente, en définissant d’abord 128 transformations intermédiaires pour chaque puissance de 2 :
R2 = R(R(x))
R4 = R2(R2(x))
...
Ensuite, pour chaque bit du nombre de fois que nous devons appliquer R
, nous pouvons appliquer la transformation intermédiaire correspondante. Par exemple, appliquer 10 fois R
se fait comme ceci : R8(R2(x))
Implémentation de la solution
L’attaque complète est donnée dans le script ci-dessous :
from Crypto.Cipher import AES
from sage.all import *
def solve():
# Build the intermediary transformations
= PolynomialRing(Zmod(2**128), "x")
p = p.gen()
x = [2*x**2 + x]
rs for i in range(1, 128):
= rs[i-1]
r0 = r0(r0(x))
ri
rs.append(ri)
# recover the key
= 0x070a4a5811dd013c301f300709245287
m = bin(2**127 - 31337)[2:].zfill(128)[::-1]
b for i, e in enumerate(b):
if e == "1":
= rs[i](m)
m = int(m)
key = int.to_bytes(key, 16, "big")
key
= AES.new(key, AES.MODE_CBC, iv=bytes.fromhex("070a4a5811dd013c301f300709245287"))
E print(E.decrypt(bytes.fromhex("96cb8fe8ddd6d8851f90ab1a8977e9c71accbed0a5936414445739ce76763002fd29337834c8976fef36decdc522a6b93c967c90d0e69e46674d634ba5a9badbd834bad8042515029b6fa833c98da0a7")))
solve()
Flag : FCSC{54a680c151c2bff32fd2fdc12b4f8558012dc71e429f075bab6bfc0322354bf4}