Le Challenge
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
class TRex:
def __init__(self, key):
N = len(key)
M = 2 ** (8 * N)
self.key = key
self.iv = int.from_bytes(key, "big")
R = lambda x: ((2 * x + 1) * x)
for _ in range(31337):
self.iv = R(self.iv) % M
self.iv = int.to_bytes(self.iv, N, "big")
def encrypt(self, data):
E = AES.new(self.key, AES.MODE_CBC, iv = self.iv)
return self.iv + E.encrypt(pad(data, 16))
if __name__ == "__main__":
E = TRex(os.urandom(16))
flag = open("flag.txt", "rb").read().strip()
c = E.encrypt(flag)
print(c.hex())
À première vue, un code assez court qui plus ou moins réalise les opérations suivantes :
- Génère une clé AES en mode CBC et nous donne le flag chiffré (sous-entendu, il faut retrouver la clé)
- Dérive l’IV de la clé
Marche à suivre
Il faut donc inverser la dérivation de l’IV (qui est donné) pour récupérer la clé. La fonction de dérivation n’est autre que l’application d’un nombre conséquent de tours de l’évaluation d’un polynôme constant et connu en l’IV (sous forme d’entier modulo une puissance de 2).
L’attaque
Mathématiquement, tout se modélise assez bien, la fonction de tours se réalise dans $\mathbb{Z}/2^{8N} \mathbb{Z}$.
Posons alors le polynome de la fonction de tour $P = X(2X + 1)$ à noter que $P \in (\mathbb Z/2^{8N}\mathbb Z)[X]$.
on a alors (la puissance $n$ dénote la $n$-ième composition par soi-même) :
On a alors $n = 31337$ et :
$P^{(n)}(\text{KEY}) = \text{IV}$
On remarque que si on considère le polynôme $Q = P - \text{IV}$, celui-ci a pour racine $P^{(n - 1)}(\text{KEY})$
Car : $P(P^{(n - 1)}(\text{KEY})) - \text{IV} = P^{(n)}(\text{KEY}) - \text{IV} = 0$
On vient de “reculer” d’un round. Ainsi, si on note $y$ une racine trouvée, on peut répéter l’opération en considérant les racines de $Q’ = P - y$
Premier problème, a priori, il peut y avoir plusieurs racines et on ne sait pas vraiment laquelle est “la bonne”. Il va donc falloir faire une méthode “back-track” et revenir en arrière si on avait choisi une racine qui ne marche pas.
Optimisation
Tel quel, on pourrait résoudre le problème avec cette méthode, mais ce serait un peu long, car le back-track correspondrait à l’exploration d’un arbre de profondeur 31337. Une question vient alors : plutôt que de s’embêter avec notre algorithme bizarre, pourquoi ne pas calculer $P^{(n)}$ et prendre une racine une bonne fois pour toutes ?
Et bien, c’est possible au détail près que $\deg(P^{(n)}) = 2^n = 2^{31337}$. Ayy… c’est un peu beaucoup
Pour autant, il y a là un joli compromis à faire !!!!
Plutôt que de prendre des racines de $P - \alpha_i$ on peut “faire des paquets” et prendre des racines de $P^{(k)} - \alpha_i$ avec $k \ll n$.
En pratique, j’ai choisi expérimentalement $k = 5$ ce qui donne $P_n$ de degré $2^5 = 32$, c’est raisonnable. Ainsi, on fait en fait la division euclidienne de $n$ par $k$ car :
On pose $n = a \times k + b$
Et on a alors $P^{(n)} = P^{(b)}((P^{(k)})^{(a)})$ Dans notre cas, $31337 = 3133 \times 2 \times 5 + 7$.
Script
from trex import TRex
import sys; sys.setrecursionlimit(50000)
from sage.all import *
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
out = bytes.fromhex("070a4a5811dd013c301f30070924528796cb8fe8ddd6d8851f90ab1a8977e9c71accbed0a5936414445739ce76763002fd29337834c8976fef36decdc522a6b93c967c90d0e69e46674d634ba5a9badbd834bad8042515029b6fa833c98da0a7")
iv = out[:16]
enc = out[16:]
N = 16
M = 2 ** (8 * N)
K = Zp(2, 8 * N)
Q = PolynomialRing(K, "x")
x = Q.gen()
P = (2 * x + 1) * x
Pn = x
for _ in range(5):
Pn = P(x=Pn)
print(Pn.degree())
print("Done computing Qn")
reached_it = []
def solve_iter(pol, it, s):
if it not in reached_it:
print("hit iter :", it)
reached_it.append(it)
if it == 0: return s
R = pol - s
rts = R.roots()
for k, _ in rts:
s = solve_iter(pol, it - 1, k)
if s is not None:
return ZZ(s)
return None
ivint = int.from_bytes(iv, "big")
s1 = solve_iter(Pn, 3133 * 2, ivint)
print("Done solving the big part")
s = solve_iter(P, 7, s1)
key = int.to_bytes(int(s), N, "big")
TT = TRex(key)
print(iv.hex(), "|", TT.iv.hex())
E = AES.new(key, AES.MODE_CBC, iv = iv)
print(E.decrypt(enc))
"""
real 2m44,146s
user 2m42,159s
sys 0m2,671s
"""
Petite considération mathématico-technique…
Un avantage de cette méthode est qu’elle fonctionne théoriquement pour n’importe quel polynôme $P$.
En pratique, pour trouver des racines de polynômes dans $\mathbb (Z/2^{8N}\mathbb Z)[X]$ il faut trouver une racine dans $P \in (\mathbb Z/2\mathbb Z)[X]$
Puis “lifter” la racine vers $(\mathbb Z/2^{8N}\mathbb Z)[X]$ c’est un peu fastidieux, dans sage, il faut mieux utiliser les p-adic.
En théorie, c’est un objet pas facile à manipuler, mais dans notre utilisation, ça se substitue sans encombre.
Voir Lemme de Hansel pour plus d’explications.