FCSC 2022 T-Rex

A la Une17/05/2022

Par Florian Picca

Dans ce challenge, un IV pour AES est dérivé de la clé secrète de manière réversible. L’objectif est d’inverser le processus de dérivation et de récupérer la clé.

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):
        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())
# 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
    p = PolynomialRing(Zmod(2**128), "x")
    x = p.gen()
    rs = [2*x**2 + x]
    for i in range(1, 128):
        r0 = rs[i-1]
        ri = r0(r0(x))
        rs.append(ri)

    # recover the key
    m = 0x070a4a5811dd013c301f300709245287
    b = bin(2**127 - 31337)[2:].zfill(128)[::-1]
    for i, e in enumerate(b):
        if e == "1":
            m = rs[i](m)
    key = int(m)
    key = int.to_bytes(key, 16, "big")
    
    E = AES.new(key, AES.MODE_CBC, iv=bytes.fromhex("070a4a5811dd013c301f300709245287"))
    print(E.decrypt(bytes.fromhex("96cb8fe8ddd6d8851f90ab1a8977e9c71accbed0a5936414445739ce76763002fd29337834c8976fef36decdc522a6b93c967c90d0e69e46674d634ba5a9badbd834bad8042515029b6fa833c98da0a7")))

solve()

Flag : FCSC{54a680c151c2bff32fd2fdc12b4f8558012dc71e429f075bab6bfc0322354bf4}