Category: Cryptography
Flag: apoorvctf{T1m3_trAv3l_w1ll_n0t_h3lp_w1th_st4t3_crypt0}
Challenge Description
Whenever Nathan Summers solves one of the stages with his time jump machine, the next stage changes up on him.
Analysis
I started by reading the provided source to understand the protocol and what exactly the remote service was leaking.
cat challenge.py...
q = (self.a * self.s + self.b) % self.p
...
if ci % self.p != q:
return {"error":"FATAL: Algebraic violation. State desync.", "expected_state": q}, True
self.s = q
ok = self._dc(self.k, cb)
return {"status":"math_ok", "oracle": "padding_ok" if ok else "padding_error"}, False
...That snippet is the whole challenge in one place: it is a CBC padding oracle, but each decrypt query is gated by a congruence check int(ct) % p == q where q evolves as an LCG state. So it is not enough to do a standard oracle attack; every ciphertext I submit must be shaped to satisfy the current state check first.
My first implementation tried to recover p from tiny finite differences using a few math_test calls, and that was a trap because those samples often did not wrap modulo p, so the derived value collapsed to zero and the exploit crashed before reaching the oracle.
The pivot that worked was using many math_test probes with large d values. Since math_test returns y(d) = (a*d + b) mod p and a is already revealed in the banner, each value a*d - y(d) differs by multiples of p; taking GCDs over those differences recovers the modulus. With p known, b is y(0), and then I can predict every future state from S_0.
I then fixed the oracle plumbing itself. The service overwrites the first ciphertext block in effect (because we must solve it to satisfy % p == q), so using only two blocks destroys control over the block used for padding manipulation. The reliable setup is a three-block query dummy || crafted_prev || target_block: the first block is sacrificial for the congruence gate, the second stays attacker-controlled for byte-by-byte PKCS#7 oracle work, and the third is the block being decrypted.
After patching both issues, the same script completed against the netcat service and printed the flag.
Solution
#!/usr/bin/env python3
import json
import os
import re
import socket
import math
import random
HOST = "chals2.apoorvctf.xyz"
PORT = 13424
class ExploitClient:
def __init__(self, host, port):
self.s = socket.create_connection((host, port))
self.f = self.s.makefile("rwb", buffering=0)
banner = self._recv_json()
self.a = int(banner["lcg_params"]["A"])
self.s0 = int(banner["lcg_params"]["S_0"])
self.flag_ct = bytes.fromhex(banner["flag_ct"])
self.p = None
self.b = None
self.state = self.s0
def _recv_json(self):
line = self.f.readline()
if not line:
raise RuntimeError("connection closed")
return json.loads(line.decode().strip())
def send(self, obj):
self.f.write(json.dumps(obj).encode() + b"\n")
return self._recv_json()
def recover_mod_and_b(self):
samples = []
ds = [0, 1, 2, 3]
ds.extend(random.getrandbits(56) for _ in range(40))
for d in ds:
y = self.send({"option": "math_test", "data": d})["result"]
samples.append((d, y))
t0 = self.a * samples[0][0] - samples[0][1]
g = 0
for d, y in samples[1:]:
td = self.a * d - y
diff = abs(td - t0)
if diff:
g = diff if g == 0 else math.gcd(g, diff)
if g == 0:
raise RuntimeError("failed to recover gcd for modulus")
def valid_mod(pv):
if pv <= 0:
return False
b = samples[0][1] % pv
for d, y in samples:
if (self.a * d + b) % pv != y:
return False
return True
p = g
for f in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]:
while p % f == 0 and valid_mod(p // f):
p //= f
ymax = max(y for _, y in samples)
if p <= ymax or not valid_mod(p):
raise RuntimeError("could not validate recovered modulus")
self.p = p
self.b = samples[0][1] % p
def lcg_next(self):
self.state = (self.a * self.state + self.b) % self.p
return self.state
def decrypt_query(self, crafted_ct: bytes):
q = self.lcg_next()
n = len(crafted_ct)
assert n >= 32 and (n - 16) % 16 == 0
tail = int.from_bytes(crafted_ct[16:], "big")
shift = 8 * (n - 16)
modpow = pow(2, shift, self.p)
inv = pow(modpow, -1, self.p)
x = ((q - (tail % self.p)) * inv) % self.p
c0 = x.to_bytes(16, "big")
forged = c0 + crafted_ct[16:]
rsp = self.send({"option": "decrypt", "ct": forged.hex()})
if rsp.get("status") != "math_ok":
return False
return rsp.get("oracle") == "padding_ok"
def split_blocks(b, bs=16):
return [b[i:i + bs] for i in range(0, len(b), bs)]
def decrypt_block(client, c_prev, c_cur):
bs = 16
I = [0] * bs
P = [0] * bs
dummy = os.urandom(bs)
for idx in range(bs - 1, -1, -1):
pad = bs - idx
base = bytearray(os.urandom(bs))
for j in range(bs - 1, idx, -1):
base[j] = I[j] ^ pad
found = False
for g in range(256):
base[idx] = g
if not client.decrypt_query(dummy + bytes(base) + c_cur):
continue
if idx > 0:
chk = bytearray(base)
chk[idx - 1] ^= 1
if not client.decrypt_query(dummy + bytes(chk) + c_cur):
continue
I[idx] = g ^ pad
P[idx] = I[idx] ^ c_prev[idx]
found = True
break
if not found:
raise RuntimeError(f"byte recovery failed at idx={idx}")
return bytes(P)
def pkcs7_unpad(m):
if not m:
return m
p = m[-1]
if p < 1 or p > 16 or m[-p:] != bytes([p]) * p:
return m
return m[:-p]
def main():
c = ExploitClient(HOST, PORT)
c.recover_mod_and_b()
blocks = split_blocks(c.flag_ct)
iv = blocks[0]
cts = blocks[1:]
pt = b""
prev = iv
for cur in cts:
pt += decrypt_block(c, prev, cur)
prev = cur
pt = pkcs7_unpad(pt)
print(pt)
m = re.search(rb"apoorvctf\{[^}]+\}", pt)
if m:
print(m.group(0).decode())
if __name__ == "__main__":
main()python cable_temporal_solver.pyb'apoorvctf{T1m3_trAv3l_w1ll_n0t_h3lp_w1th_st4t3_crypt0}'
apoorvctf{T1m3_trAv3l_w1ll_n0t_h3lp_w1th_st4t3_crypt0}