Garbage In, Flag Out

Platform: broncoctf2026 | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-07-11 | Status: Solved Techniques: bit_reversal_key_recovery, constraint_propagation, known_charset_narrowing, two_time_pad

Summary

Task: two ciphertexts (random-lowercase garbage + flag) encrypted with the SAME random key, where the flag's key is the per-byte bit-reversal of the garbage key. Solution: a two-time-pad style attack — recover each key byte from the known-lowercase garbage plaintext, bit-reverse it, XOR with the flag ciphertext, and narrow candidates with a second garbage block whose derived-key high nibble is deterministic.

Garbage In, Flag Out — broncoctf2026

Description

"I've finally fixed the entropy issue with the OTPs! The secret: use them twice, but only slightly. It'll make more sense once you look at the code. Anyways, I'm so confident in my new algorithm that I can send the flag (which I assure you is valid English leetspeak) with it and you will know NOTHING!"

Two files are given: challenge.py (redacted FLAG) and output.txt with two hex ciphertexts labelled "Random garbage" and "The flag". Goal: recover the flag.

Semantic clues

• "use them twice, but only slightly" — the one-time pad is reused across two messages, with a slight (reversible) transform between uses. This is textbook two-time-pad reuse.
• "valid English leetspeak" — the plaintext follows human-language / leetspeak structure, a language crib once the candidate set is narrow.
• Title "Garbage In, Flag Out" — the random garbage message is not noise; its known character set is the exact leverage needed to pull the flag out.

Analysis

challenge.py generates one random key and emits two ciphertexts:

 python read-only • copy allowed Copy
key = random.randbytes(N)               # N = len(FLAG) = 25
real_garb = "".join(random.choices(string.ascii_lowercase, k=2*N))  # guaranteed a..z
garb = block_encrypt(key, real_garb)    # ciphertext #1

key = scramble(key)                     # per-byte bit reversal
flag = block_encrypt(key, FLAG)         # ciphertext #2

Two crucial facts:

1. Same underlying key. The flag is encrypted with scramble(key), and scramble merely reverses the bit order of every key byte:

    python read-only • copy allowed Copy
   for i in range(8):
       num |= ((k & (1 << i)) >> i) << (7 - i)

   This is fully reversible: flag_key[i] = reverse_bits(garb_key[i]). So both messages share the same pad, just bit-reversed per byte — the "use them twice, but only slightly."

2. Garbage plaintext charset is known. The garbage plaintext is 2*N random lowercase ascii letters (a..z). So for each of the first N positions:

   garb_ct[i]  = garb_key[i] XOR garb_plain[i],   garb_plain[i] in [a..z]
   flag_ct[i]  = reverse_bits(garb_key[i]) XOR flag[i]
   

   For every candidate lowercase p, the key byte is garb_key[i] = garb_ct[i] ^ p, and the implied flag byte is flag[i] = flag_ct[i] ^ reverse_bits(garb_key[i]). Keeping only printable results already collapses each position to a handful of characters.

Extra constraint: the second garbage block

block_encrypt extends the key when the plaintext is longer than the key. Because the garbage plaintext has length 2*N, it uses one derived key block for bytes N..2N-1. For each byte of the previous block it computes a new key byte whose high nibble is deterministic (folding each 2-bit pair to one bit and placing it in the top 4 bits) and whose low nibble is random.getrandbits(4):

 python read-only • copy allowed Copy
for i in range(4):
    sub = (element >> (2*i)) & 3
    sub = (sub & 1) ^ (sub >> 1)
    newkey += sub << (7 - i)        # deterministic high nibble
newkey += random.getrandbits(4)     # random low nibble

Requiring the second garbage plaintext byte (garbage[i+N] ^ (high|low)) to also be lowercase for some low nibble eliminates many candidate key bytes, shrinking each flag position further. Combined with the known bronco{...} wrapper and leetspeak structure, the flag is uniquely determined.

Solution

1. For each position, enumerate lowercase garbage plaintext bytes → candidate key byte.
2. Filter by whether the second garbage block admits a lowercase plaintext under the deterministic-high / random-low nibble derived key.
3. XOR the bit-reversed key byte into the flag ciphertext; keep printable results.
4. The candidate lists collapse (with obvious leetspeak/bronco{} structure) to the flag.
5. Verify: recover the original key from the proposed flag, confirm all garbage bytes are lowercase, and confirm re-encryption reproduces flag_ct exactly.

 python read-only • copy allowed Copy
#!/usr/bin/env python3

garbage = bytes.fromhex(
    "96dbcaae807788b5e3abae8e91dc467bd6b5291094a33033c7f47fb66cccf6d"
    "41b2bc01426033a73f444fa44eb412e3ee249"
)
flag_ct = bytes.fromhex("2d4f326d141f0c75e1ff445d23b39880581c09e0585645eab8")


def reverse_bits(x):
    return int(f"{x:08b}"[::-1], 2)


def extension_high_nibble(x):
    out = 0
    for i in range(4):
        pair = (x >> (2 * i)) & 3
        out |= ((pair & 1) ^ (pair >> 1)) << (7 - i)
    return out


# The second garbage block uses an extension of the original key.  Its upper
# nibble is deterministic; only its lower nibble is random.  Requiring both
# garbage plaintext bytes to be lowercase sharply narrows each flag byte.
candidates = []
for i, fc in enumerate(flag_ct):
    chars = set()
    for first_plain in range(ord("a"), ord("z") + 1):
        key_byte = garbage[i] ^ first_plain
        high = extension_high_nibble(key_byte)
        second_is_possible = any(
            ord("a") <= (garbage[i + len(flag_ct)] ^ (high | low)) <= ord("z")
            for low in range(16)
        )
        if second_is_possible:
            candidate = fc ^ reverse_bits(key_byte)
            if 32 <= candidate < 127:
                chars.add(chr(candidate))
    candidates.append("".join(sorted(chars)))

for i, chars in enumerate(candidates):
    print(f"{i:2}: {chars}")

flag = b"bronco{REDACTED}"
# More directly, recover the original key from the proposed flag ciphertext.
key = bytes(reverse_bits(flag_ct[i] ^ flag[i]) for i in range(len(flag)))
first_plain = bytes(garbage[i] ^ key[i] for i in range(len(flag)))
assert all(ord("a") <= x <= ord("z") for x in first_plain)
assert bytes(flag[i] ^ reverse_bits(key[i]) for i in range(len(flag))) == flag_ct

# Verify that every byte in the second garbage block admits the random low
# nibble used by block_encrypt and a lowercase plaintext byte.
for i, key_byte in enumerate(key):
    high = extension_high_nibble(key_byte)
    assert any(
        ord("a") <= (garbage[i + len(flag)] ^ (high | low)) <= ord("z")
        for low in range(16)
    )

print(flag.decode())

The per-position candidate output narrows each byte to 1–2 characters; the leetspeak phrase inside bronco{...} is immediate:

 6: K{      8: 0     12: 4     15: 0     17: _     18: 3     23: h     24: }
...
bronco{REDACTED}

All three verification assertions pass — the recovered key reproduces the flag ciphertext exactly and yields lowercase garbage plaintext for both blocks.