cryptofreehard

manytags

b01lersc

Task: a service encrypts random one-block AES-GCM messages and corrupts the low 64 bits of each tag with MT19937 output seeded from the AES key. Solution: cancel the affine GHASH term with nullspace relations, solve a large GF(2) system for the MT state, invert CPython seeding, recover the master key, and decrypt the flag.

$ ls tags/ techniques/
linear_algebraghashmt19937aes_gcmfaulty_tagaffine_mapcpython_rng
gf2_gaussian_eliminationghash_cancellationnullspace_relation_attacksymbolic_mt19937_recoveryinit_by_array_inversion

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

manytags — b01lers CTF 2026

Description

too many tags

We are given many_tags.py and a service that reveals the encrypted flag once, then lets us request up to 704 random one-block AES-GCM encryptions. Each query returns (nonce, ciphertext, tag), but the tag is faulty: its lower 64 bits are not the real GCM value.

Goal: recover the AES master key and decrypt the flag.

Analysis

The core bug is in construct_tag:

def construct_tag(real_tag, ghash_value, fault_words):
    real_tag_int = int.from_bytes(real_tag, "big")
    fault_value = (fault_words[0] << 32) | fault_words[1]
    tag_low = (ghash_value ^ fault_value) & MASK64
    tag_int = (real_tag_int & (~MASK64)) | tag_low
    return tag_int.to_bytes(BLOCK_SIZE, "big")

For query messages, the service computes a valid AES-GCM ciphertext, then replaces the low 64 bits of the tag with:

low64(tag) = low64(GHASH_H(C)) XOR fault_value

where fault_value is two consecutive outputs of Python's random.Random.getrandbits(32).

Two details make this exploitable:

  1. All query plaintexts are exactly one block, so GHASH_H(C) has a very simple structure.
  2. The fault RNG is seeded as random.Random(int.from_bytes(master_key, "big")), so recovering the MT19937 state recovers the AES key source.

1. GHASH becomes an affine map on ciphertext bits

For one-block ciphertexts,

GHASH_H(C) = (C · H ⊕ L) · H

where L is the fixed length block for 16-byte messages. Therefore the low 64 bits of GHASH are an affine linear function of the 128 ciphertext bits:

low64(GHASH_H(C)) = A(C) XOR b

for some unknown affine map A and constant b depending only on H.

So every query gives:

tag_low_i = A(C_i) XOR b XOR mt64_i

with mt64_i the 64-bit mask formed from two MT outputs.

2. Nullspace relations cancel the unknown GHASH map

...