woman in front of its computer with the Insomniak Logo

FCSC 2022 T-Rex

Top News05/17/2022

By Florian Picca

In this challenge, an AES IV is derived from the secret key in reversible manner. The goal is to undo the derivation process and recover the key.

Details
 

  • Category : Crypto
  • Points : 344
  • Solves : 67

Description
 

You have to decrypt the flag :-)

Source code :

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

Understanding the problem

The flag is encrypted using AES128-CBC. The IV is derived from the encryption key by applying the transformation R 31337 times, modulo 2^128.

The goal is clearly to recover the encryption key from the IV and decrypt the flag.

Solving the problem

After playing a bit with the transformation R, I realized that applying it M/2 times to a value x produces x again. This makes sense as M is a power of 2, so the order of the group generated by R is at most M/2.

But because M = 2^128, naivly applying the transformation R to the IV 2^127-31337 times would be infeasible in a reasonable amount of time.

It’s possible apply the transformation in a smart way, by first defining 128 intermediary transformation for each power of 2 :

R2 = R(R(x))
R4 = R2(R2(x))
...

Then, for each bit of the number of times we need to apply R, we can apply the corresponding intermediary transformation. For example, applying R 10 times is done like this : R8(R2(x))

Implementing the solution

The full attack is given in the script below:

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}

Our News