crypto/dream

104 solves / 448 points

Writeup by Aryan

NOTE: This writeup is a valid solution to both dream and dream-revenge. There was a cheese in dream which I did not notice, leading me to take the long road and find the intended solution.

We are given a script which encrypts a flag with AES. Before encrypting the flag, the program takes in a list of 8 indexes as inputs. It then randomly generates 624 numbers and gives us the numbers at the indexes we requested, as shown below:

# taken from challenge source
from ast import literal_eval
idxs = literal_eval(input(">>> "))
if len(idxs) > 8:
    print("Ha thats funny")
    exit()
for idx in range(624):
    rand_out = random.getrandbits(32)
    if idx in idxs:
        print(rand_out)

The idea is to somehow crack the random seed with access to only 8 generated numbers. This task is trivial if we had access to all 624 generated numbers, thanks to randcrack. However, having 8 numbers makes it a lot harder.

Here's where the cheese comes in. The server code reads the seed from a text file; see below:

from os import urandom
# check if seed.txt exists
try:
    seed = open("seed.txt", "rb").read()
except:
    seed = urandom(8)
    open("seed.txt", "wb").write(seed)

If the seed is the same every time, we can just enter indices 0, 1, ... 7 on our first run, then 8, 9, ... 15 on our second run, and so on, where we enter indices 8n, 8n+1, ... 8n+7 on the nth run. We do this until we get all 624 numbers, at which point we use randcrack.

However, I didn't see this, and found the actual solution.

Doing a bit of searching leads us to an interesting blog on breaking Python's PRNG. The bottom of this blog contains a link to a GitHub repository with example seed recovery code.

Using the seed recovery code provided and then decrypting the AES, we are able to get our flag.

# dream (and the revenge)
# messy code sorry

# credits:
# https://stackered.com/blog/python-random-prediction/
# https://github.com/StackeredSAS/python-random-playground/blob/main/recover_64bitSeed.py
from functions import * # https://github.com/StackeredSAS/python-random-playground/blob/main/functions.py
import random
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import binascii

indexes = [0, 1, 2, 3, 227, 228, 229, 230] # enter this to server
# replace below with received values
values = [475736381, 2599178730, 639420308, 1400092731, 661837392, 3139312426, 2862425384, 2640369286]

S = [0] * 624

for i in range(len(indexes)):
    S[indexes[i]] = values[i]

S = [untemper(item) for item in S]
I_227_, I_228 = invertStep(S[0], S[227])
I_228_, I_229 = invertStep(S[1], S[228])
I_229_, I_230 = invertStep(S[2], S[229])
I_230_, I_231 = invertStep(S[3], S[230])
I_228 += I_228_
I_229 += I_229_
I_230 += I_230_

seed_h = recover_Kj_from_Ii(I_230, I_229, I_228, 230) - 1
seed_l1 = recover_Kj_from_Ii(I_231, I_230, I_229, 231)
seed_l2 = recover_Kj_from_Ii(I_231+0x80000000, I_230, I_229, 231)
seed1 = (seed_h << 32) + seed_l1
seed2 = (seed_h << 32) + seed_l2
random.seed(seed1)
# ^ if this doesnt work try random.seed(seed2)

for idx in range(624):
    rand_out = random.getrandbits(32)

key = random.getrandbits(256)
nonce = random.getrandbits(256)

aes_key = sha256(str(key).encode()).digest()[:16]
aes_nonce = sha256(str(nonce).encode()).digest()[:16]

# replace below with received ciphertext 
ciphertext_hex = "cb3cc14d2f5eeac6b5645bb66fa268d88399d1654df20668110e1d04bf135db71930985b5eba307c0197b035f2e9203f"
ciphertext = binascii.unhexlify(ciphertext_hex)
cipher = AES.new(aes_key, AES.MODE_GCM, nonce=aes_nonce)
flag = unpad(cipher.decrypt(ciphertext), 16)
print(flag.decode())

Flag: vsctf{dream_luck???_5e3ec2f2d338fc9f}