False Witness

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: N/A | **Author: XESXOR Techniques: small_order_generator_attack, subgroup_confinement, order_2_element, bit_leak_oracle, aes_ecb_decryption

Summary

Walkthrough of the CUSTOM Crypto False Witness. Task: crypto oracle AES-ECB encrypts the flag under a random 256-bit key and leaks each key bit as either a random int (bit 0) or a public-key group element H(sk)=G^sk mod P (bit 1), with the player f

Description

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.

The challenge ships a single file server.py and a remote instance reachable over nc <host> <port>. On connect the server prints the flag encrypted with AES-ECB under a random 256-bit key, then lets the player choose a "hashing generator" G and query an oracle any number of times. The goal is to recover the key and decrypt the flag. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

Key facts from server.py:

• KEY = secrets.token_bytes(32) — a random 256-bit key. Its bits are expanded MSB-first via KEY_BITS = list(map(int, f"{int.from_bytes(KEY):0256b}")).
• The flag is printed as AES.new(KEY, AES.MODE_ECB).encrypt(pad(FLAG, 16)).hex().
• The "hash" is a plain modular exponentiation: H(msg) = pow(G, msg, P), where G is fully player-controlled (any value with 1 < G < P).
• keygen() builds N=256 secret-key pairs and public keys PK[j] = (H(sk0), H(sk1)).
• The oracle for offset i:

   python read-only • copy allowed Copy
  ret = secrets.randbelow(2**N) if KEY_BITS[i] == 0 else PK[i % len(PK)][secrets.randbelow(2)]

  So it returns a fresh random 256-bit integer when KEY_BITS[i] == 0, or a public-key group element PK[...] = G^sk mod P when KEY_BITS[i] == 1. Each offset is cached, so it is answered once. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The oracle is therefore a per-bit leak: bit 0 → random number, bit 1 → an element of <G> (the subgroup generated by G). The distinguisher only works if the two distributions are separable — and that is exactly what the attacker's control over G provides.

Subgroup insight. The image of H(·) = G^(·) mod P is confined to the cyclic subgroup generated by G, whose size is ord(G). Factoring P-1:

P - 1 = 2 * 65539 * q
q = 708402032471041307647356682365045041171277816261829566557440242934907807   (239-bit prime)

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Because 2 | P-1, (Z/P)^* contains a unique element of order 2, namely P-1 ≡ -1 (mod P).

Solution

Choose G = P-1 (the order-2 element). Then for any secret exponent sk:

• pow(P-1, sk, P) = 1 if sk is even,
• pow(P-1, sk, P) = P-1 if sk is odd.

So every public-key element PK[j][k] is forced into the two-element set {1, P-1}. The oracle becomes a perfect bit distinguisher:

• KEY_BITS[i] == 1 → oracle returns a value in {1, P-1}.
• KEY_BITS[i] == 0 → oracle returns a uniform 256-bit integer, which lands in {1, P-1} only with negligible probability (~2^-255). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Procedure:

1. Read and store the AES-ECB ciphertext printed at startup.
2. Send G = P-1 as the generator.
3. Query the oracle for every offset 0..255.
4. Classify each result: value in {1, P-1} → bit 1, otherwise → bit 0.
5. Reassemble the 256 bits MSB-first (matching f"{int:0256b}") into the key.
6. AES-ECB-decrypt the ciphertext to recover the flag.

Any small-order generator works (e.g. an element of order 65539 also confines PK to a distinguishable subgroup), but order 2 is cleanest since only two values are possible. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import sys
from pwn import remote, context
from Crypto.Cipher import AES

context.log_level = "info"

P = 0xCD4A96D3B7FA7251A1BB765933FB676FCAE8C9026682E34F779122DFD66915BB
G = P - 1  # element of order 2 -> H(msg) in {1, P-1}

HOST = sys.argv[1]
PORT = int(sys.argv[2])

io = remote(HOST, PORT)

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

io.recvuntil(b"give me the hashing generator: ")
io.sendline(str(G).encode())
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

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

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

key_int = int("".join(map(str, bits)), 2)
KEY = key_int.to_bytes(32, "big")
pt = AES.new(KEY, AES.MODE_ECB).decrypt(ct)
print(KEY.hex(), pt)

Real run evidence (one instance):

• ciphertext: 316967bd5eda84a99fcbe6260c82da0db97c2027ce9afcc1d820d64c0793bad40b4212c53dc744bf46ca35c132364726
• recovered key: b2bf855f2c3f50daf16a22f2e79bd4178d849efca232c39a3858178470d4931f
• decrypted plaintext: the flag followed by PKCS#7 padding (0x0e * 14). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Key Takeaways / Lessons

• Mastering small_order_generator_attack, subgroup_confinement, order_2_element, bit_leak_oracle, aes_ecb_decryption was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-07-27 • CUSTOM • False Witness • Difficulty: Medium