## SuperAES - GCCCTF 2024

import random
from Crypto.Cipher import AES
import time
import os

flag = b"GCC{pretend_its_a_good_flag_2515}"

m = 288493873028852398739253829029106548736

a = int(time.time())

a = 1709434579

b = a%16

s = random.randint(1,m-1)

class LCG:
    def __init__(self, a, b, m, seed):
        self.a = a
        self.b = b
        self.m = m
        self.state = seed
        self.counter = 0

    def next_state(self):
        ret = self.state
        self.state = (self.a * self.state + self.b) % self.m
        return ret

class SuperAES:
    def __init__(self,key,lcg):
        self.aes = AES.new(key,AES.MODE_ECB)
        self.lcg = lcg

    def encrypt(self,plaintext):
        ciphertext = b""
        for i in range(0,len(plaintext),16):
            ciphertext += self.encrypt_block(plaintext[i:i+16])

        return ciphertext

    def encrypt_block(self,block):
        keystream = self.aes.encrypt(int(self.lcg.next_state()).to_bytes(16,"big"))
        return bytes([k^b for k,b in zip(keystream,block)])

assert len(flag) == 33
assert flag.startswith(b"GCC{")

key = os.urandom(32)

cipher = SuperAES(key,LCG(a,b,m,s))

times = int(input("how many times do you want the flag ?"))

assert times < 50

print(cipher.encrypt(flag*times).hex())

Ta thấy rằng, đây là dạng LCG có dạng như sau $$X_n = (a.X_{n-1} + b ) \pmod{m}$$

Ta có: Với $$m = x^k$, $a \pmod{x} = 0$$ và $$b = 0$$ thì tới lần thứ $$k$$ trở đi, tất cả các giá trị $$X_n$$ sẽ bằng 0 hết.

Ví dụ: Ta có LCG như sau: $$X_n = (15.X_{n-1}) \pmod{5^6}$$ với $seed = 1234$. Ta có rằng:

$$X_0 = (15*1234) \text{ mod }{5^6} = 2885$$

$$X_1 = (15*2885) \text{ mod }{5^6} = 12025$$

$$X_2 = (15*12025) \text{ mod }{5^6} = 8500$$

$$X_3 = (15*8500) \text{ mod }{5^6} = 2500$$

$$X_4 = (15*2500) \text{ mod }{5^6} = 6250$$

$$X_5 = (15*6250) \text{ mod }{5^6} = 0$$

Ta factor số $m$ thì có dạng là $$m = 56^{22}$$. Và $$b = a \pmod{16}$$. Thế nên, ta sẽ phải chọn $$a = lcm(56,16) = 112$$. Thì lúc đó, $$b=0$$, $$a \pmod{56} = 0$$ thỏa mãn chứng minh trên.

import random
from Crypto.Cipher import AES
import time
import os

m = 288493873028852398739253829029106548736

# Lấy giá trị time sao cho % 112 = 0
a = 1709748320

b = a%16

s = random.randint(1,m-1)

class LCG:
    def __init__(self, a, b, m, seed):
        self.a = a
        self.b = b
        self.m = m
        self.state = seed
        self.counter = 0

    def next_state(self):
        ret = self.state
        self.state = (self.a * self.state + self.b) % self.m
        return ret, self.state
    
lcg_instance = LCG(a, b, m, s)

lst = []

for i in range(25):
    x, y = lcg_instance.next_state()
    print(x,y,i)

Ta được output như sau

274307500331584051073578502175940157317 104754307875076833751031273141586313696 0
104754307875076833751031273141586313696 277520889646677069025428199197852742656 1
277520889646677069025428199197852742656 249481270928262185811348656037153701888 2
249481270928262185811348656037153701888 166094904809131223331828456148488421376 3
166094904809131223331828456148488421376 273233070009197129947077531338922786816 4
273233070009197129947077531338922786816 174166286815414199366690356161431994368 5
174166286815414199366690356161431994368 94180593477662401567319558063749332992 6
94180593477662401567319558063749332992 221895196624817315665099047193983057920 7
221895196624817315665099047193983057920 164020426616595714380811837341077340160 8
164020426616595714380811837341077340160 84737181605014689305827498846526111744 9
84737181605014689305827498846526111744 255798279933858104915930464667301838848 10
255798279933858104915930464667301838848 270948402813344686191178148637436805120 11
270948402813344686191178148637436805120 161133629499390641591826424006604488704 12
161133629499390641591826424006604488704 124647467485842492268889925285750767616 13
124647467485842492268889925285750767616 55893776530177019698109733122093350912 14
55893776530177019698109733122093350912 98378105143643629652781786218486562816 15
98378105143643629652781786218486562816 46465931712328401462911888807151271936 16
46465931712328401462911888807151271936 10333391537060102578748783547065040896 17
10333391537060102578748783547065040896 174946721836738480868118940052636041216 18
174946721836738480868118940052636041216 217842312287092627619436564777080455168 19
217842312287092627619436564777080455168 206067052163465999099467020735076106240 20
206067052163465999099467020735076106240 0 21
0 0 22
0 0 23
0 0 24

Thế nên, giờ ta sẽ lấy tổng cộng cộng 32 flag rồi thử trên local như sau

import random
from Crypto.Cipher import AES
import time
import os


flag = b"GCC{pretend_its_a_good_flag_2515}"

m = 288493873028852398739253829029106548736

a = 1709752464

b = a%16

s = random.randint(1,m-1)

count = 0
class LCG:
    def __init__(self, a, b, m, seed):
        self.a = a
        self.b = b
        self.m = m
        self.state = seed
        self.counter = 0

    def next_state(self):
        ret = self.state
        self.state = (self.a * self.state + self.b) % self.m
        return ret

class SuperAES:
    def __init__(self,key,lcg):
        self.aes = AES.new(key,AES.MODE_ECB)
        self.lcg = lcg

    def encrypt(self,plaintext):
        ciphertext = b""
        global count
        for i in range(0,len(plaintext),16):
            x = self.encrypt_block(plaintext[i:i+16])
            print(x,count-1)
            ciphertext += x

        return ciphertext

    def encrypt_block(self,block):
        global count
        x = int(self.lcg.next_state()).to_bytes(16,"big")
        keystream = self.aes.encrypt(x)
        print(keystream,block, count)
        count +=1
        return bytes([k^b for k,b in zip(keystream,block)])

assert len(flag) == 33
assert flag.startswith(b"GCC{")

key = os.urandom(32)

cipher = SuperAES(key,LCG(a,b,m,s))

encrypted_flag = (cipher.encrypt(flag*32))

Vì từ block thứ 22 trở đi, keystream sẽ giống nhau, thế nên ta có thể lấy form flag để có thể tìm lại được keystream. Chạy code trên, ta thấy được 16 byte của keystream lần lượt xor với ``33: GCC{; 41:GCC{; 49:GCC{; 59:}GCC``. Thế nên, giờ ta sẽ lấy các block có thứ tự như trên rồi xor lại sẽ có được flag.

import time
from pwn import*
from itertools import cycle

while int(time.time())%112 !=0:
	time.sleep(0.2)
    
io = remote("localhost", 1337)
print("time : ",int(time.time())%112)

io.recvuntil(b"?")

io.sendline(b"32")

data = bytes.fromhex(io.recvline().decode())

key1 = b""
key2 = b""
key3 = b""
key4 = b""
for i in range(0,len(data),16):
    x = (data[i:i+16])
    y = ((i+16)//16 - 1)
    if y == 33:
        key1 = xor(b"GCC{",x[:4])
    if y == 41:
        key2 = xor(b"GCC{",x[4:8])
    if y == 49:
        key3 = xor(b"GCC{",x[8:12])
    if y == 59:
        key4 = xor(b"}GCC",x[12:16])
key = key1 + key2 + key3+ key4
for i in range(0,len(data),16):
    x = (data[i:i+16])
    print(xor(x,key))

**Flag: GCC{pretend_its_a_good_flag_2515}**