## Initial investigation

We are given the following source code.

challenge.py

```
import os
from numpy import random
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad
from secret import flag

def rand_32():
return int.from_bytes(os.urandom(4),'big')

flag = pad(flag,16)

for _ in range(2):
# hate to do it twice, but i dont want people bruteforcing it
random.seed(rand_32())
iv,key = random.bytes(16), random.bytes(16)
cipher = AES.new(key,iv=iv,mode=AES.MODE_CBC)
flag = iv+cipher.encrypt(flag)

print(flag.hex())
```

The encrypted flag is configured as follows.

`IV2 + ENC2(Key2, IV2, IV1 + ENC1(Key1, IV1, flag))`

This value is the value returned when connecting with the `nc` command.

```
$ nc crypto.zh3r0.cf 3333
44e0c3cf5f09c03add34bf3a14f5b282e5197fd9cab2e69ece4275d872700901336bf2fb8036322fe64b2c03bc85ae7f16be8faba04312c2260e884d0947d270d56ee34ceb93965b76b7da9090fe3f34faa0c0c8e0ed3fd28383fac3b0713416255c67c766beece3c387269b90acb2d4357528a7188691ee9ed7330ef119df24
```

ENC1 and ENC2 are encrypted in AES CBC mode.

Key and IV are generated as follows.

```
from numpy import random
random.seed(rand_32())
iv,key = random.bytes(16), random.bytes(16)
```

We wouldn't be able to guess `rand_32()` because `os.urandom(4)` is used.

## Guessing Key2, IV1, Key1

Of the following, the `IV2` is known.

`IV2 + ENC2(Key2, IV2, IV1 + ENC1(Key1, IV1, flag))`

I tried to guess `Key2`,` IV1`, and `Key1` using a vulnerability in the` random` module.
However, I didn't know what algorithm NumPy's `random` module works with, so I couldn't solve it this way.

## Use of rainbow table

I considered how to generate a rainbow table and apply a large amount of ciphertext.
While incrementing `seed_x` of `random.seed(seed_x)` from 0, generate the following rainbow table.

```
randic = {
iv_0: seed_0
iv_1: seed_1
iv_2: seed_2
...
}
```

Since this method requires a lot of memory, I had to decide the number of rainbow tables in a trade-off with the execution environment while considering the amount of memory.
The possible range of `seed_x` is 0 to `0xffffffff`, but in my environment I was able to generate a rainbow table of 0 to `0x03ffffff`.
In other words, it became a 1/64 rainbow table of the whole.
The following is the source code that creates a rainbow table, converts it to pickle, and saves it in a file.

```
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from numpy import random
import time
import pickle

randnum = 0x4000000
# randnum = 0x1000000
# randnum = 0x10000

def main():
randic = {}
for s in range(randnum):
if s & 0xfffff == 0:
print('s: %d/%d' % (s, randnum))
random.seed(s)
iv = random.bytes(8)
if iv in randic:
print('Conflict : %s, %d, %d' % (iv, s, randic[iv]))
randic[iv] = s

with open('randic.pickle', 'wb') as f:
pickle.dump(randic, f)

if __name__ == '__main__':
main()
```

Since there are two IVs in the ciphertext, the probability of hitting is `(1/64) * (1/64) = 1/4096`.
I solved with the following source code.

```
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from socket import create_connection
import socket
import binascii
import pickle
from Crypto.Cipher import AES
from numpy import random

SERVER = ('crypto.zh3r0.cf', 3333)
RECV_SIZE = 8192

response = b''

def read_line(conn):
global response
while True:
r = response.split(b'\n')
if len(r) >= 2:
response = response[len(r[0]) + 1:]
return r[0] + b'\n'
response += conn.recv(RECV_SIZE)

def read_size(conn, size):
global response
while True:
if len(response) >= size:
r = response[:size]
response = response[size:]
return r
response += conn.recv(RECV_SIZE)

def read_until(conn, until):
global response
while True:
r = response.split(until)
if len(r) >= 2:
response = response[len(r[0]) + len(until):]
return r[0] + until
response += conn.recv(RECV_SIZE)

def read_all(conn):
global response
try:
response += conn.recv(RECV_SIZE, socket.MSG_DONTWAIT)
except BlockingIOError:
pass
r = response
response = b''
return r

def get_ct(conn):
r = read_line(conn) # 9edbc671fb24a7b92007d49c46e886b7ce6eb96c65212a87539d08aaaf0473510bea9d781b570fbc47c4c2fec3caca821b0cdee8e3ef953b8c7c55e4dee386b904c068a5ca199a5d69ad794b733b4956314a45a305f03451c2dd0d27a9c42a429e37cfe4f1d590da32f3ab8ba78955e853e97e8c4488c27c0d89f81fa40a135e
print(r.decode(), end='')
ct = binascii.unhexlify(r[:-1])
return ct

def solve(randic):
conn = create_connection(SERVER)
ct = get_ct(conn)
conn.shutdown(socket.SHUT_RDWR)
conn.close()
# conn = None
print('disconnected')

iv = ct[:16]
ct = ct[16:]
if iv[:8] in randic:
print('*************************************** First attack ***************************************')
s = randic[iv[:8]]
random.seed(s)
iv, key = random.bytes(16), random.bytes(16)
cipher = AES.new(key, iv=iv, mode=AES.MODE_CBC)
ct = cipher.decrypt(ct)
else:
return

iv = ct[:16]
ct = ct[16:]
if iv[:8] in randic:
print('*************************************** Second attack ***************************************')
s = randic[iv[:8]]
random.seed(s)
iv, key = random.bytes(16), random.bytes(16)
cipher = AES.new(key, iv=iv, mode=AES.MODE_CBC)
ct = cipher.decrypt(ct)
print(ct)
exit()
else:
print('Unmatch second attack.')
return

def main():
with open('randic.pickle', 'rb') as f:
randic = pickle.load(f)
t = 0
while True:
print('Trial times:', t)
solve(randic)
t += 1

if __name__ == '__main__':
main()
```

The result is as follows.

```
$ ./try4.py
Trial times: 0
cd079a8ba44355ef93db04c1d0d482e1fc03835069e1423aa0cb3fd93a51fb0a49da17a7602b7eb1f87a5de1d17cd517356cf8ad153310de398c87c27a7eacceb76a7ba6bdf4bde1338705044bd50f1a55fd9c45ea8013b25d1757e8ab4de00ee58b4cc0d83ddad4060a50908a9f39566a9aa43fc879972e31279c08c4009e72
disconnected
*************************************** First attack ***************************************
Unmatch second attack.
Trial times: 1
03a23468786703679a2540b82453af8e1f445ab63a8a9c6c58526b744b3c956641998dd9b30df089331ce0042ec98bae7f699c5181657223fcb7ff6ddeb22ef7d6d61c4332674f938d0dd6bfe297124fb26a68148a89f2a4cc257bd078262e2035a62bb727b4ce04c05840ad06f0e66fb9513ba96f86a09a56e57af4c009e7e4
disconnected
Trial times: 2
df0347ab2d0282d1f7f2fe8ef1a8fedd23bfeb235f1682dad4a56dbd7f5e2876f117f7a7754a91d05ad9d1819775308c1ecfc62ea8ef49450bdd9540e2f348b2000870dc525ebcc34cc6cb9eb1ff39fb079e142ba3e3664c07025aa5f4ee2df305f963f51f28cf1a0d82ab917fb9d8e92e0d83c7161a71bedeee9e22415fba16
disconnected
: (snip)
Trial times: 298
bf0b76f47a2618dc5315ea7e975fa020b4c7404a886c97d5e20920e44b6be81776f86878cbac7df38cb9ede0cb30e881f77f51fe2048960724d72598747710460f70383870db023728aa3e1bcef3a8b0d2f48f545ad19a185dae2954d28329ca7a106387335bd4591adbc53dc765a24dc0cae7713041940e1f6dee84b8f565ed
disconnected
Trial times: 299
f8de279aa539817c49903bda624a2deddba6805824afe60269e85fd87252424499f38ba422c384780b8a443a1f0c3f825c87386bfdc9a4c97fe610370c1d948235557b2bdd671dac1c5bb131bbcd5419c3af6e00566102c898a811abd81d3787467dae09c6968e42259d3b15e943296a2224624f9bf964f7e44449b597b0eef0
disconnected
*************************************** First attack ***************************************
*************************************** Second attack ***************************************
b'zh3r0{wh0_th0ugh7_7h3_m3r53nn3_7w1573r_w45_5o_pr3d1c74bl3?c3rt41nly_n0t_m47454n0}\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f\x0f'
```