# crypto/dream

### 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:

```python
# 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](https://github.com/tna0y/Python-random-module-cracker). 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:

```python
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](https://stackered.com/blog/python-random-prediction/) on breaking Python's PRNG. The bottom of this blog contains a link to a [GitHub repository](https://github.com/StackeredSAS/python-random-playground) with example seed recovery code.

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

```python
# 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}`


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://centinels.gitbook.io/home/writeups/vsctf/crypto-dream.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.