Scenario

Caldrin Vowmark knows that not every seal deserves belief. Some marks still carry the weight of a living vow; others only imitate one well enough to pass a glance. She can question the realm's witnesses as many times as she likes, but certainty, it turns out, is much harder to earn than a convincing lie.

Code Analysis (server.py)

from hashlib import sha256
from Crypto.Util.Padding import pad
from Crypto.Cipher import AES
import secrets

P = 0xCD4A96D3B7FA7251A1BB765933FB676FCAE8C9026682E34F779122DFD66915BB
FLAG = open("flag.txt", "rb").read().strip()
N = sha256().digest_size * 8   # N = 256

KEY = secrets.token_bytes(32)
KEY_BITS = list(map(int, f"{int.from_bytes(KEY):0256b}"))

def H(msg):
    return pow(G, msg, P)

Key observations:

• KEY is a random 256-bit AES key, and KEY_BITS is its bit decomposition (MSB-first, per the format string 0256b).
• H(msg) is not a cryptographic hash function — it's modular exponentiation G^msg mod P. This is the classic Diffie-Hellman-style "hash" used in some Lamport signature variants, where the security relies on the discrete log problem being hard and on G being a generator of a large-order (ideally prime-order) subgroup.
• Critically, G is read from user input before key generation happens, and the only validation is 1 < G < P. There is no check that G actually generates a large subgroup, or even that it isn't 1 or -1 mod P.

class Oracle:
    def __init__(self):
        self.appeared = {}
    def oracle(self, i):
        if i in self.appeared:
            return self.appeared[i]
        else:
            ret = secrets.randbelow(2**N) if KEY_BITS[i] == 0 else PK[i % len(PK)][secrets.randbelow(2)]
            self.appeared[i] = ret
        return ret

This is the core oracle logic:

• For a queried index i (0–255, corresponding to one bit of the AES key):
  • If KEY_BITS[i] == 0, the oracle returns a fresh random 256-bit integer, completely unrelated to any secret or public key material.
  • If KEY_BITS[i] == 1, the oracle returns one of the two public-key hash values PK[i][0] or PK[i][1] (chosen at random), where PK[i] = (H(sk[i][0]), H(sk[i][1])).
• Results are cached per index (self.appeared), so repeated queries to the same i always return the same value — this doesn't matter for our attack since one query per index is already sufficient information.

def keygen():
    sk = [(secrets.randbelow(2**N), secrets.randbelow(2**N)) for _ in range(N)]
    pk = [(H(s[0]), H(s[1])) for s in sk]
    return sk, pk

Standard Lamport-style keygen: for each of the 256 bit positions, generate two random 256-bit secrets and publish their images under H.

print("Here is something for you:")
print(AES.new(KEY, AES.MODE_ECB).encrypt(pad(FLAG, 16)).hex())
while True:
    G = int(input("Before we start, give me the hashing generator: "))
    if 1 < G < P:
        break

SK, PK = keygen()
oracle = Oracle()

The server:

1. Immediately hands us the AES-ECB encryption of the flag under KEY (the same key whose bits we're trying to leak).
2. Lets us choose G before keygen() runs, meaning G is fixed for the entire session and directly controls the behavior of H.
3. Then exposes the oracle for as many queries as we like across all 256 bit indices.

This is the entire vulnerability: the "random oracle" generator is attacker-controlled, so we can make H degenerate into something with a tiny, predictable image.

The Attack: Malicious Generator / Small Subgroup Confinement

The scheme's security implicitly assumes G generates a subgroup of (Z/PZ)* large enough that:

• H(msg) = G^msg mod P looks indistinguishable from a random 256-bit value for a uniformly random msg (this is what lets KEY_BITS[i]==1 outputs blend in with the KEY_BITS[i]==0 random outputs).

But nothing stops us from choosing a G of very small multiplicative order. The simplest possible choice is:

G = P - 1   (i.e. G ≡ -1 mod P)

Since (-1)^2 = 1 mod P, G has order exactly 2. Therefore, for any secret exponent msg:

G^msg mod P = 1        if msg is even
G^msg mod P = P - 1    if msg is odd

No matter what the random 256-bit secret sk[i][0] or sk[i][1] actually is, H(sk) can only ever be one of two fixed values: 1 or P-1.

Consequences for the oracle:

• If KEY_BITS[i] == 1: the oracle returns H(sk[i][b]) for some secret sk, which — thanks to our choice of G — is deterministically 1 or P-1.
• If KEY_BITS[i] == 0: the oracle returns secrets.randbelow(2**256), a uniformly random integer in [0, 2^256).

The probability that a uniformly random 256-bit integer happens to equal 1 or P-1 is astronomically small (~2^-255), so this is a perfect (for practical purposes) distinguisher:

bit = 1   if oracle_result in {1, P-1}
bit = 0   otherwise

Querying every index 0..255 exactly once and applying this rule recovers the entire 256-bit AES key in a single pass over the oracle — no brute force, no partial information, no ambiguity.

Once the key is recovered, decrypting the AES-ECB ciphertext printed at the start of the session (AES.new(KEY, AES.MODE_ECB).encrypt(pad(FLAG, 16))) directly yields the flag.

Why this works in general

This is a well-known pitfall in discrete-log-based constructions: never let the party being proven-to choose the generator/base of the exponentiation unless its order is verified. A generator of small order d collapses G^msg mod P into only d possible outputs regardless of the size of msg's domain, destroying any pseudorandomness or hiding property the construction relied on. Here d = 2 was the most convenient degenerate choice, but any small-order element (order 3, 4, small primes dividing P-1, etc.) would have worked similarly, just with slightly more possible output values to check against.

Exploit

First (naive) version — one query per bit, synchronous

from pwn import *
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad

P = 0xCD4A96D3B7FA7251A1BB765933FB676FCAE8C9026682E34F779122DFD66915BB
N = sha256().digest_size * 8  # 256

io = remote("154.57.164.76", 31342)

io.recvuntil(b"Here is something for you:\n")
ct = bytes.fromhex(io.recvline().strip().decode())

G = P - 1
io.recvuntil(b"generator: ")
io.sendline(str(G).encode())

bits = []
for i in range(N):
    io.recvuntil(b"> ")
    io.sendline(b"1")
    io.recvuntil(b"Enter offset: ")
    io.sendline(str(i).encode())
    val = int(io.recvline().decode().split(":")[1].strip())
    bits.append("1" if val in (1, P - 1) else "0")

io.recvuntil(b"> ")
io.sendline(b"2")

KEY = int("".join(bits), 2).to_bytes(32, "big")
flag = unpad(AES.new(KEY, AES.MODE_ECB).decrypt(ct), 16)
print(flag)

This works correctly but performs 256 full request/response round trips, each incurring network latency — noticeably slow (tens of seconds to minutes depending on RTT).

Optimized version — pipelined single round trip

Since the server just reads lines from stdin in a loop and doesn't need to see our next command before printing the previous result, we can send all 256 queries (and the exit command) at once, then read the entire output in one shot and parse it:

from pwn import *
from hashlib import sha256
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
import re

P = 0xCD4A96D3B7FA7251A1BB765933FB676FCAE8C9026682E34F779122DFD66915BB
N = sha256().digest_size * 8  # 256

io = remote("154.57.164.76", 31342)

io.recvuntil(b"Here is something for you:\n")
ct = bytes.fromhex(io.recvline().strip().decode())

G = P - 1
io.recvuntil(b"generator: ")
io.sendline(str(G).encode())

# Build one pipelined payload: query every bit index, then exit
payload = b""
for i in range(N):
    payload += b"1\n" + str(i).encode() + b"\n"
payload += b"2\n"
io.send(payload)

data = io.recvall(timeout=10).decode(errors="ignore")
results = [int(x) for x in re.findall(r"Oracle result:\s*(-?\d+)", data)]
assert len(results) == N

bits = ["1" if v in (1, P - 1) else "0" for v in results]
KEY = int("".join(bits), 2).to_bytes(32, "big")

flag = unpad(AES.new(KEY, AES.MODE_ECB).decrypt(ct), 16)
print(flag)

This reduces the exploit from ~256 network round trips down to essentially one send + one recv, since the server's input loop doesn't require synchronous back-and-forth — it just consumes whatever is in its stdin buffer line by line and writes results out as it goes.

Result: the recovered KEY correctly decrypts the ECB ciphertext (after PKCS#7 unpadding) to recover the flag.

Root Cause & Take Aways

Fix recommendations:

• Never allow a client-supplied generator for a DH-style hash/commitment function; fix G server-side as a verified generator of a large prime-order subgroup (or use an actual cryptographic hash function instead of modular exponentiation).
• If a generator must be configurable, validate its multiplicative order (e.g., require ord(G) to be a large prime factor of P-1) before proceeding.
• Avoid designs where an oracle's two branches (decoy vs. real) have visibly different output distributions/ranges.