This is the solution of the challenge “Counting On You” given during the GreHack 2022 CTF. It consisted in a nonce reuse attack on AES CTR using a weak PRNG for nonce.
Description
To speak securely with the administrator, a toolbox has been made available for you to encrypt a message securely.
To prove to you that they don’t fear any breach, they have made available an encrypted administrator message that you won’t be able to read.
Author: Feelzor#4242
app.py
Details
Points: 100
Category: Cryptography
Solution
The server encrypts messages of the flag with AES in CTR mode. The key is randomly generated at each connection. The PRNG used by the function gen_random to generate the nonce is a Xorshift PRNG. To have a long period the parameters of the PRNG have to be chosen carefully if not we may have a short period. I coded a small test to find the period:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
import time
def gen_random():
state = int(time.time())
while True:
x = state
x ^= (x << 42) & 0xffffffffffffffff
x ^= x >> 31
x ^= (x << 19) & 0xffffffffffffffff
state = x
yield state
random = gen_random()
def get_period():
x0 = next(random)
i = 1
while True:
x = next(random)
i += 1
if x0 == x:
return i
p = get_period()
print(p)
|
And instantly the script outputs a period of 4065. It is very small and it allows to have a nonce reuse attack against AES in CTR mode. The idea is first to get the encrypted flag from the server then send 4064 messages until we loop back to the same nonce value. Then the output xored together with the plaintext and the encrypted flag gives the flag in clear. Here is the full script:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
from pwn import *
from Crypto.Util.strxor import strxor
from binascii import unhexlify
ciphertext_len = 380
r = remote('10.0.202.2', 5100)
# Get encrypted flag
print(b"> " + r.recvuntil(b"Enter your choice. "))
time.sleep(0.1)
r.send(b"2\n")
rsp = r.recvuntil(b"Enter your choice. ")[:388]
nonce_flag = rsp[0:16]
flag_enc = rsp[16:]
print(f"Flag {flag_enc}")
# Encrypt "0"
plaintext = b"0" * 186 + b"\n"
i = 0
while True:
print(i)
r.send(b"1\n")
r.recvuntil(b"you like to encrypt?\r\n> ")
r.send(plaintext)
rsp = r.recvuntil(b"Enter your choice. ")[:388]
nonce = rsp[0:16]
enc = rsp[16:]
if nonce == nonce_flag:
break
i += 1
enc = unhexlify(enc)
flag_enc = unhexlify(flag_enc)
print(strxor(strxor(enc, flag_enc), plaintext))
|
It ouptus the flag after 20 minutes:
1
2
|
4064
b"Congratulations, you've found me!\nYou are now the wonderful AES Toolbox master and you may validate the challenge.\nThis may be what you are looking for, GH22{1nsecur3_AES_CTR_w1th_PRNGs}"
|