Usama Arshad. Résumé

Challenge 3 of 15 Crypto Full writeup

BlackHat MEA 2026 · Qualifiers

Reduce, Reuse, Recycle.

Reduce what you waste. Reuse what you can. Recycle what remains.

Crypto· 4 November 2026

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.

Captured

01Recon

python
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:

snippet
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 50

Four 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:

snippet
nonce = (J0 XOR L*H) * H^-2

Submit 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.