Flagvent 2025: Day 14
FV25.14 - the-prng
Difficulty
hard
Categories
crypto
Description
warmup chal
Author
xtea418Solution
The files we were provided indicate the remote server is running a dockerised app that runs the Python script below:
import os
import hmac
def h(b: bytes) -> bytes:
s0 = 0x9F12A3C64D78B2E1
s1 = 0x4C85E79A132FDB07
s2 = 0xB7D40E9C58A3F621
s3 = 0x21E6C8D4FA9037BB
M = 0xFFFFFFFFFFFFFFFF
msg = bytearray(b)
msg.append(0x80)
while (len(msg) % 32) != 24:
msg.append(0)
msg += (len(b) * 8).to_bytes(8, "little")
for i in range(0, len(msg), 32):
w0 = int.from_bytes(msg[i + 0 : i + 8], "little")
w1 = int.from_bytes(msg[i + 8 : i + 16], "little")
w2 = int.from_bytes(msg[i + 16 : i + 24], "little")
w3 = int.from_bytes(msg[i + 24 : i + 32], "little")
s0 ^= w0
s1 ^= w1
s2 ^= w2
s3 ^= w3
for i in range(5):
s0 ^= ((s1 << 13) & M) ^ (s2 >> 7)
s1 ^= ((s2 << 17) & M) ^ (s3 >> 9)
s2 ^= ((s3 << 29) & M) ^ (s0 >> 11)
s3 ^= ((s0 << 5) & M) ^ (s1 >> 3)
s0, s1, s2, s3 = s2 & M, s0 & M, s3 & M, s1 & M
for j in range(6):
s0 ^= ((s1 << 9) & M) ^ (s2 >> 7)
s1 ^= ((s2 << 7) & M) ^ (s3 >> 5)
s2 ^= ((s3 << 11) & M) ^ (s0 >> 13)
s3 ^= ((s0 << 3) & M) ^ (s1 >> 17)
s0, s1, s2, s3 = s3 & M, s2 & M, s1 & M, s0 & M
return (
(s0 & M).to_bytes(8, "little")
+ (s1 & M).to_bytes(8, "little")
+ (s2 & M).to_bytes(8, "little")
+ (s3 & M).to_bytes(8, "little")
)
class H:
block_size = 64
digest_size = 32
def __init__(self, data=b""):
self._buf = bytearray()
if data:
self.update(data)
def update(self, data):
if not data:
return
self._buf.extend(data)
def copy(self):
c = H()
c._buf = bytearray(self._buf)
return c
def digest(self):
return h(self._buf)
def hexdigest(self):
return h(self._buf).hex()
def hash256_new(data=b""):
return H(data)
class RNG:
def __init__(self, seed: bytes):
if not seed:
raise ValueError("no")
self._key = h(seed)
self._counter = 0
def _next_block(self):
ctr = self._counter.to_bytes(16, "big")
block = hmac.new(self._key, ctr, digestmod=hash256_new).digest()
self._counter += 1
return block
def _generate(self, nbytes):
out = bytearray()
while len(out) < nbytes:
out.extend(self._next_block())
return bytes(out[:nbytes])
def getrandbits(self, n):
nbytes = (n + 7) // 8
v = int.from_bytes(self._generate(nbytes), "big")
return v & ((1 << n) - 1)
def randrange(self, n):
k = (n - 1).bit_length()
while True:
r = self.getrandbits(k)
if r < n:
return r
def randint(self, a, b):
return a + self.randrange(b - a + 1)
if __name__ == "__main__":
import signal
signal.alarm(30)
for i in range(0x100):
scheed = os.urandom(30)
chal = RNG(scheed)
leek = chal.getrandbits(0x100)
print(f"{leek = :#x}")
try:
lmao = bytes.fromhex(input("gib scheed: "))
assert lmao == scheed
except:
exit("no")
print(os.environ.get("FLAG", "FV25{local_flag}"))
The first thing we do is add a FLAG environment variable to our compose.yml, so we can spin up a local container and try to solve the challenge locally first:
services:
chal:
build: .
ports:
- 1337:1337
environment:
- FLAG=FV25{motest}The Python script shows a main function with a loop that iterates 256 times. Random numbers are generated using os.urandom(), so we explored the special Docker image used for this challenge to check whether the PRNG was patched to always return the same results. We ran the following command several times:
docker run --rm ghcr.io/flagvent/challenges/alpine-stable:1.0 \
sh -c "apk add --no-cache python3 && python3 -c 'import os; print(os.urandom(16).hex())'"The output is always different, so this is a dead end and the random number generator in the image is normal.
Each round, the challenge does the same thing:
- It picks a random 30-byte seed.
- It computes a key from that seed:
key = h(seed)(whereh()is the custom 256-bit hash). - It computes and prints a leak:
leek = HMAC_h(key, ctr0)wherectr0is 16 zero bytes (the counter value 0). - It then asks you to send back the exact seed. If you’re right, you move to the next round. After 256 rounds, it prints the flag.
Therefore, we have the following function:
F(seed) = HMAC_h(h(seed), ctr0)Our goal is to invert this function given only leek, then automate solving all 256 loops until we exit the loop and print the flag from the environment.
Inverting the function is possible because the h() function only uses XOR, shifts, swapping state words, and fixed padding. This means h() is a linear hash function. In other words, h() behaves like h(m) = A·m ⊕ c, which is an affine function. HMAC is built from XOR and hashing, so when the hash is affine and the message is fixed (ctr0 is always the same), the whole mapping from the 30-byte seed to the printed leak is also affine.
F(seed) = B ⋅ seedBits ⊕ dWe know that:
seedBitsis the 240 bits of the seedleekis 256 bitsBis a 256×240 binary matrix (“how each seed bit affects the leak”)dis a constant 256-bit offset
So recovering the seed is just solving: B·seedBits = leek ⊕ d.
That’s a normal linear system, just using XOR instead of plus.
We used an LLM to help write a solver that models the leak as a linear (XOR) system, precomputes an inverse mapping once, then connects to the service and recovers and sends each 30-byte seed automatically for all 256 rounds to print the flag.
import socket
import hmac
import re
import ssl
import sys
# Start - Copied from provided chal.py
def h(b: bytes) -> bytes:
s0 = 0x9F12A3C64D78B2E1
s1 = 0x4C85E79A132FDB07
s2 = 0xB7D40E9C58A3F621
s3 = 0x21E6C8D4FA9037BB
M = 0xFFFFFFFFFFFFFFFF
msg = bytearray(b)
msg.append(0x80)
while (len(msg) % 32) != 24:
msg.append(0)
msg += (len(b) * 8).to_bytes(8, "little")
for i in range(0, len(msg), 32):
w0 = int.from_bytes(msg[i + 0 : i + 8], "little")
w1 = int.from_bytes(msg[i + 8 : i + 16], "little")
w2 = int.from_bytes(msg[i + 16 : i + 24], "little")
w3 = int.from_bytes(msg[i + 24 : i + 32], "little")
s0 ^= w0
s1 ^= w1
s2 ^= w2
s3 ^= w3
for i in range(5):
s0 ^= ((s1 << 13) & M) ^ (s2 >> 7)
s1 ^= ((s2 << 17) & M) ^ (s3 >> 9)
s2 ^= ((s3 << 29) & M) ^ (s0 >> 11)
s3 ^= ((s0 << 5) & M) ^ (s1 >> 3)
s0, s1, s2, s3 = s2 & M, s0 & M, s3 & M, s1 & M
for j in range(6):
s0 ^= ((s1 << 9) & M) ^ (s2 >> 7)
s1 ^= ((s2 << 7) & M) ^ (s3 >> 5)
s2 ^= ((s3 << 11) & M) ^ (s0 >> 13)
s3 ^= ((s0 << 3) & M) ^ (s1 >> 17)
s0, s1, s2, s3 = s3 & M, s2 & M, s1 & M, s0 & M
return (
(s0 & M).to_bytes(8, "little")
+ (s1 & M).to_bytes(8, "little")
+ (s2 & M).to_bytes(8, "little")
+ (s3 & M).to_bytes(8, "little")
)
class H:
block_size = 64
digest_size = 32
def __init__(self, data=b""):
self._buf = bytearray()
if data:
self.update(data)
def update(self, data):
if not data:
return
self._buf.extend(data)
def copy(self):
c = H()
c._buf = bytearray(self._buf)
return c
def digest(self):
return h(self._buf)
def hexdigest(self):
return h(self._buf).hex()
def hash256_new(data=b""):
return H(data)
# End - Copied from provided chal.py
CTR0 = (0).to_bytes(16, "big")
def F(seed30: bytes) -> int:
key = h(seed30)
out = hmac.new(key, CTR0, digestmod=hash256_new).digest()
return int.from_bytes(out, "big")
def build_basis():
d = F(b"\x00" * 30)
cols = []
for i in range(240):
s = (1 << i).to_bytes(30, "big")
cols.append(F(s) ^ d)
basis_vec = [0] * 256
basis_comb = [0] * 256
for i, v in enumerate(cols):
c = 1 << i
x = v
m = c
for p in range(255, -1, -1):
if (x >> p) & 1:
if basis_vec[p]:
x ^= basis_vec[p]
m ^= basis_comb[p]
else:
basis_vec[p] = x
basis_comb[p] = m
break
return d, basis_vec, basis_comb
def solve_rhs(rhs: int, basis_vec, basis_comb) -> int:
comb = 0
v = rhs
for p in range(255, -1, -1):
if (v >> p) & 1:
if basis_vec[p] == 0:
raise ValueError("No solution (basis missing pivot) — unexpected.")
v ^= basis_vec[p]
comb ^= basis_comb[p]
if v != 0:
raise ValueError("Did not fully reduce rhs — unexpected.")
return comb
HEX_RE = re.compile(rb"0x[0-9a-fA-F]+")
def read_leek(sock, buf: bytearray) -> int:
while True:
m = HEX_RE.search(buf)
if m:
hx = m.group(0)[2:]
del buf[:m.end()]
return int(hx, 16)
chunk = sock.recv(4096)
if not chunk:
raise EOFError("server closed connection before providing next leak")
buf.extend(chunk)
def read_all_remaining(sock, buf: bytearray) -> bytes:
out = bytearray(buf)
buf.clear()
while True:
chunk = sock.recv(4096)
if not chunk:
break
out.extend(chunk)
return bytes(out)
def connect(host: str, port: int, use_tls: bool) -> socket.socket:
s = socket.create_connection((host, port))
s.settimeout(None)
try:
s.setsockopt(socket.IPPROTO_TCP, socket.TCP_NODELAY, 1)
except OSError:
pass
if not use_tls:
return s
ctx = ssl.create_default_context()
# if the CTF uses a self-signed cert, you can disable verification:
ctx.check_hostname = False
ctx.verify_mode = ssl.CERT_NONE
return ctx.wrap_socket(s, server_hostname=host)
# usage:
# python solve.py -> localhost:1337 plain
# python solve.py host port --tls -> remote TLS
# python solve.py host port --plain -> remote plain
def main():
host = "localhost"
port = 1337
use_tls = False
if len(sys.argv) >= 2:
host = sys.argv[1]
if len(sys.argv) >= 3 and sys.argv[2].isdigit():
port = int(sys.argv[2])
if "--tls" in sys.argv:
use_tls = True
if "--plain" in sys.argv:
use_tls = False
d, basis_vec, basis_comb = build_basis()
with connect(host, port, use_tls) as s:
buf = bytearray()
for i in range(0x100):
leak = read_leek(s, buf)
rhs = leak ^ d
seed_mask = solve_rhs(rhs, basis_vec, basis_comb)
seed = seed_mask.to_bytes(30, "big")
s.sendall(seed.hex().encode() + b"\n")
tail = bytes(buf) + s.recv(4096)
print(tail.decode(errors="replace").strip())
if __name__ == "__main__":
main()
Running this script against the remote server gets us the daily flag:
python solve.py e6acd751-a118-4a71-9d1f-4a7b9a6d4227.challs.flagvent.org 31337 --tlsFlag:
FV25{w4sn't_th4t_h4rd_n0w_w4s_it?}Hidden 3
This challenge also contained the solution to: FV25.H3 - Sneaky Elves