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.
A 1-bit oracle leaks the AES key one bit at a time - but only if you can tell the
oracle's two answer types apart. The server lets the client pick the generator
G of the group it uses, and never checks that G generates
anything larger than a two-element subgroup.
$ file a254c951-36b6-427d-89e9-6a567dccdeb0-1784850384.zip
a254c951-36b6-427d-89e9-6a567dccdeb0-1784850384.zip: Zip archive data, at least v1.0
to extract, compression method=store
$ unzip -l a254c951-36b6-427d-89e9-6a567dccdeb0-1784850384.zip
Length Date Time Name
--------- ---------- ----- ----
0 07-23-2026 15:40 crypto_false_witness/
1816 07-23-2026 17:47 crypto_false_witness/server.py
--------- -------
1816 2 filesOne file, and it is the server source - so the whole task is a code review:
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
KEY = secrets.token_bytes(32)
KEY_BITS = list(map(int, f"{int.from_bytes(KEY):0256b}"))
def H(msg):
return pow(G, msg, 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
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
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()
while True:
print("1. Oracle")
print("2. Exit")
ch = input("> ")
if ch == "1":
offset_input = input("Enter offset: ")
offset_input = offset_input.strip()
if not offset_input:
continue
try:
offset = int(offset_input)
except ValueError:
print("ERROR: Invalid offset input!")
continue
if 0 <= offset < len(KEY_BITS):
print("Oracle result:", oracle.oracle(offset))
else:
print("ERROR: Invalid offset. Must be in range [0-{}]".format(len(KEY_BITS)-1))
elif ch == "2":
print("bye")
break
else:
print("ERROR: Unknown command.")
A plain TCP service. It can also be run locally, which is how the attack was developed -
drop a placeholder into flag.txt first, since the server reads it at startup:
$ echo hubertf-was-here > flag.txt
$ python3 server.py
Here is something for you:
e56ba5426aea905ae481d9433fc812ca66f208693caca9ffd6844ff1ac175486
Before we start, give me the hashing generator: 123
1. Oracle
2. Exit
> 1
Enter offset: 0
Oracle result: 9535645453501309095255367619999718798774002916558537655539142098174857511139
1. Oracle
2. Exit
> 2
bye
So we get the encrypted flag up front, we get to choose G, and then we may
ask the oracle about key bit i as often as we like.
1816 bytes of server - small enough to understand completely. The interesting part is the
branch inside Oracle.oracle().
ret = secrets.randbelow(2**N) if KEY_BITS[i] == 0 else PK[i % len(PK)][secrets.randbelow(2)]with
def H(msg):
return pow(G, msg, P) # PK entries are H(s) = G^s mod P
Conclusion: Key bit 0 gives a uniformly random value in [0, 2^256);
key bit 1 gives G^s mod P for some secret s. The entire challenge
is therefore: tell "random" apart from "power of G". And since answers are cached
in self.appeared, each bit can only be sampled once - no averaging over
repeated queries.
Normally G would be a fixed domain parameter. Here it is not.
while True:
G = int(input("Before we start, give me the hashing generator: "))
if 1 < G < P:
break
SK, PK = keygen() # <- keys are generated AFTER G is chosen
Conclusion: We choose G, and we choose it before the key pair
exists - so G shapes every value the oracle will ever return. The only
validation is the range check 1 < G < P.
The obvious first thought: pick some normal-looking G and find a statistical
property that separates G^s from random.
That does not work. The order d of G - the smallest d > 0
with G^d = 1 mod P - bounds how many distinct values G^s can take.
For a random G modulo a 256-bit prime, d is on the order of
P itself. So G^s ranges over essentially the whole field and is
indistinguishable from a random draw, especially with only one sample per bit.
Conclusion: Do not look for a property of the output. Choose a
G whose output set is tiny - i.e. minimise d.
Which small orders are reachable given only 1 < G < P?
G = 1, which the range check rejects.G^2 = 1 mod P, so
(G-1)(G+1) = 0 mod P. P is prime and G != 1,
hence G + 1 = P, i.e. G = P - 1 = -1 mod P. That
satisfies 1 < G < P.
With G = P - 1, the value G^s mod P can only ever be
1 (for even s) or P - 1 (for odd s).
A random 256-bit value hits one of those two by chance with probability about
2^-255.
Conclusion: This is a textbook small-subgroup attack: the server validates
the range of G but never that it generates a large subgroup. The
distinguisher is now exact rather than statistical - bit = 1 iff the answer is in
{1, P-1}.
256 bits recovered, but they still have to be assembled into the AES key the same way the server took it apart.
KEY_BITS = list(map(int, f"{int.from_bytes(KEY):0256b}"))
Conclusion: Python's b format is most-significant-bit first, so
offset 0 is the top bit. Assemble MSB-first, convert to 32 bytes big-endian, then
AES-ECB-decrypt the ciphertext printed at connect time and strip the padding.
2hf-remote.py - 256 oracle queries, one per key bit. The local variant
1hf.py is identical except that connect() spawns
server.py as a subprocess instead of dialling out.
#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
from pwn import context, process, remote
P = 0xCD4A96D3B7FA7251A1BB765933FB676FCAE8C9026682E34F779122DFD66915BB
KEY_BITS = 256
context.log_level = "info"
def connect():
#return process(["python3", "server.py"])
return remote("154.57.164.70", 32030)
def read_ciphertext(io):
"""The first thing the server prints is the AES-ECB encrypted flag."""
io.recvuntil(b"Here is something for you:\n")
return bytes.fromhex(io.recvline().strip().decode())
def send_generator(io, g):
io.recvuntil(b"give me the hashing generator: ")
io.sendline(str(g).encode())
def query_oracle(io, offset):
"""Ask about one key bit; returns the raw value the oracle hands back."""
io.recvuntil(b"> ")
io.sendline(b"1")
io.recvuntil(b"Enter offset: ")
io.sendline(str(offset).encode())
io.recvuntil(b"Oracle result: ")
return int(io.recvline().strip())
def main():
io = connect()
ciphertext = read_ciphertext(io)
print("[*] ciphertext: %s" % ciphertext.hex())
g = P-1
send_generator(io, g)
bits = []
for offset in range(KEY_BITS):
value = query_oracle(io, offset)
bit = bit = 1 if value in (1, P - 1) else 0
bits.append(bit)
key = int("".join(map(str, bits)), 2).to_bytes(32, "big")
print("[*] key: %s" % key.hex())
flag = unpad(AES.new(key, AES.MODE_ECB).decrypt(ciphertext), 16)
print("\n%s" % flag.decode())
io.close()
if __name__ == "__main__":
main()
Against the live service:
$ python3 2hf-remote.py
[+] Opening connection to 154.57.164.70 on port 32030: Done
[*] ciphertext: 9b066b42305551fc8e6c7eee3977ec7008a6d65ceef42914585b7f7851da3551
b5b464b971ca00a6be10a681e82d5496
[*] key: 27c713082491e5f9a9bac27b926e20e9f7027843933547d967a4b3828485ed18
HTB{___l34k1ng_b1ts_0n3_by_0n3___}
[*] Closed connection to 154.57.164.70 port 32030
The attack reproduces against the shipped
server.py - with a placeholder flag, since the real one was never in the
handout:
$ echo hubertf-was-here > flag.txt
$ python3 1hf.py
[+] Starting local process '/.../venv-htb/bin/python3': pid 81168
[*] ciphertext: 7f29afb8412d353f7f2e895b7b516c5c29f43c6f1fe3d8712f9231214af210fb
[*] key: 3f6ed55f1d3783284f6e9d2efe85e5f2d95193c56efaed5f56d45f24e017100c
hubertf-was-here
[*] Stopped process '/.../venv-htb/bin/python3' (pid 81168)All 256 bits recovered on the first pass, in both cases - the distinguisher has no error rate to work around.
HTB{___l34k1ng_b1ts_0n3_by_0n3___}
| # | Stage | Mechanism |
|---|---|---|
| 1 | The leak | The oracle answers per key bit: bit 0 returns a uniformly random 256-bit value,
bit 1 returns G^s mod P. Distinguishing the two recovers the AES key
bit by bit. |
| 2 | The flaw | The client picks G, and the only check is 1 < G < P.
Nothing verifies that G generates a large subgroup. |
| 3 | The choice | G = P - 1 = -1 mod P has order 2, so G^s is either
1 or P - 1 - two values instead of ~2^256. |
| 4 | The distinguisher | Query offsets 0..255; bit = 1 iff the answer is in {1, P-1}. A random
value collides with that set with probability ~2^-255, so the read is exact. |
| 5 | The key | Assemble MSB-first (the server used f"{...:0256b}"), take 32 bytes
big-endian, AES-ECB-decrypt the ciphertext printed at connect, unpad. |
The instructive part is stage 3. The server's range check looks like input
validation - it rejects the degenerate G = 1 and everything outside the
field. But order-2 elements are not out of range, they are just useless as generators,
and nothing in the code says so. Validating a group parameter means checking the subgroup
it generates, not the interval it falls into.