TL;DR
AES-GCM key <i>and</i> nonce are reused on every encryption while the plaintext contains the key's own hex. Half of each tag recovers the GHASH key H; multi-byte UTF-8 characters slide the key hex across GHASH block boundaries; a hex-alphabet quirk collapses the residual 2^48 ambiguity to 2^16.
01Recon
signal.alarm(300)
keys = [os.urandom(16), os.urandom(16)]
for r in [0, 1]:
for ch in input("> ")[:6]:
cipher = AES.new(keys[0], AES.MODE_GCM, nonce=keys[1])
cipher.encrypt(f"{ch}|encrypted by {keys[0].hex()}".encode())
print(cipher.hexdigest()[r::2])
assert input(f"keys[{r}]> ") == keys[r].hex()
print(flag)Three things stack up:
- Key and nonce are reused for every single encryption, AES.new is called inside the loop with the same keys[0] / keys[1], so H = AES_K(0) and E(J0) are constant.
- The plaintext contains keys[0].
hex(), the secret is literally inside the message being authenticated. - You only ever see half of each tag. Round 0 prints
hexdigest()[0::2] (the even hex digits, the high nibble of each tag byte, 64 bits); round 1 prints the odd ones. And you must hand over keys[0] correctly before round 1 ever runs.
Only 6 characters are accepted per round, and the same 6 are replayed in round 1.
02The bug
Nonce reuse in GCM destroys authentication: with a fixed H and a fixed E(J0), the XOR of two tags from equal-length messages cancels E(J0) entirely and leaves a known polynomial in H over GF(2^128), the classic forbidden attack.
The subtler half is that same-length queries leak nothing about the key. The key hex sits at a fixed offset in every message, so it contributes identically to every GHASH and cancels in every difference. Only a length change slides the key hex across GHASH's 16-byte block boundaries and turns it into new linear equations, and multi-byte UTF-8 is exactly the lever that changes the length, because input() is counted in characters but encoded in bytes.
03Exploitation
Stage 1, forbidden attack recovers H. Same-length queries differ only in the leading character, so Tag_i XOR Tag_j = D_ij * H^4 with D known. Round 0 exposes only the even hex digits (64 bits per tag), but two well-chosen difference pairs give 128 equations over GF(2^128), enough to pin H^4 uniquely. Then H = (H^4)^(2^126), since squaring is a bijection on GF(2^128).
Character choice mattered: the first candidate set left a 2^45 nullspace. U+0080, U+00BF, U+07FF collapse it to zero.
Stage 2, UTF-8 length juggling recovers the key. The six characters chosen cover all four reachable message lengths:
CHARACTER UTF-8 BYTES ROLE
U+0080 , U+00BF , U+07FF 2 three same-length queries, pin H
U+0061 ( a ) 1 length 47
U+0800 3 length 49
U+10000 4 length 50Four lengths yield 128 usable bits against 256 unknowns, leaving an irreducible 2^48 ambiguity (about 2^16 of those points being valid hex).
The way in is a property of the hex alphabet: bit 3 of a lowercase hex character is set only for '8' and '9' (probability 1/8), and when it is set, that byte is fully pinned, contributing 4 linear constraints instead of 1. Branching on those 32 bits in Hamming-weight order makes the linear system self-prune. AES_K(0) == H then selects the unique survivor.
Measured: 0.17 s mean, 100% success, no weight cap needed, the uncapped search ran faster than the capped one because it terminates on the hit.
Stage 3, round 1 recovers the nonce. Replaying the same 6 characters yields the odd nibbles, which recombine with round 0's into full 128-bit tags. With the key known, U4 XOR H*U3 cancels E(J0)'s partner terms; guessing the single keystream byte ks[48] (256 tries) gives E(J0). Since the nonce here is 16 bytes, J0 = GHASH(nonce), which inverts to:
nonce = (J0 XOR L*H) * H^-2Submit both hex strings and the flag prints. The whole exploit needs one connection because every stage is deterministic.
04Dead ends
- The first difference-pair character set left a 2^45 nullspace in the H recovery; the pairs have to be chosen so the resulting GF(2^128) system has full rank.
- The 2^48 residual after length juggling is genuinely irreducible from linear structure alone. Trying to find more length variants is wasted effort, four lengths is the ceiling.
- Instances are short-lived: the first endpoint began refusing connections after a few probes. The final exploit needs only one connection, so this is a nuisance rather than a blocker.
- Recovered end to end in ~1.1 s per instance, against a 300 s alarm.