Probably Unbreakable — broncoctf2026

Description

"I set up a place to for everyone to enjoy their favorite thing: random numbers! Random numbers are great because they let you do really great, really easy encryption. I even left the flag in there, in case that's what you're here for. There's definitely a way to find it. Just kidding! Probably."

Remote service: nc 0.cloud.chals.io 16474 Source file provided: chall.py

A network service encrypts the flag with a "one-time pad"-style XOR using randomly chosen key bytes, and lets the user request up to 20,000 encryptions per connection. The goal is to recover the flag.

Analysis

The provided chall.py performs the encryption as follows:

keystring = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_-"

def encrypt_flag(n):
    for _ in range(n):
        key = random.choices(keystring, k=len(flag))
        enc = bytes([ord(f) ^ ord(k) for f, k in zip(flag, key)])
        print(enc.hex())

Two facts make this breakable:

1. Restricted key alphabet. Each key byte is drawn from a fixed 64-character alphabet (a-z A-Z 0-9 _ -), not from the full 0–255 byte range. This is not a true one-time pad. For a given ciphertext byte c, the plaintext byte p must satisfy c ^ p ∈ KEY_ALPHABET. Only ~64 values of p are ever possible for a single ciphertext.

2. Huge query budget. The service enforces only a + b + c <= 20_000, where c is the number of flag encryptions. Setting a=0, b=0, c=20000 yields 20,000 independent ciphertexts of the same flag.

For each flag position i, the true plaintext byte must satisfy the alphabet constraint against every observed ciphertext at that position. Each fresh ciphertext randomly re-samples the key byte, so the set of surviving candidate plaintext bytes shrinks quickly. With ~20,000 samples the intersection collapses to exactly one byte per position.

This is why the challenge is named "Probably Unbreakable": it is probabilistically breakable, and 20k samples make recovery essentially certain. No Mersenne Twister / MT19937 state recovery is required — the alphabet restriction alone leaks enough structure.

Solution

1. Connect and answer the three prompts with 0, 0, 20000 (all budget on flag encryptions).
2. Read every hex line and decode it into ciphertext bytes.
3. For each byte position i, compute the candidate set: { p : (c[i] ^ p) ∈ KEY_ALPHABET for all ciphertexts c }.
4. Once each position has exactly one surviving candidate, assemble the flag.

#!/usr/bin/env python3
import socket

HOST = "0.cloud.chals.io"
PORT = 16474
KEY = set(b"abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789_-")

with socket.create_connection((HOST, PORT), timeout=20) as s:
    f = s.makefile("rwb", buffering=0)
    for answer in (b"0\n", b"0\n", b"20000\n"):
        f.write(answer)

    ciphertexts = []
    for raw in f:
        line = raw.strip()
        try:
            blob = bytes.fromhex(line.decode())
        except (ValueError, UnicodeDecodeError):
            continue
        if blob:
            ciphertexts.append(blob)

length = len(ciphertexts[0])
flag = bytearray()
for i in range(length):
    candidates = [p for p in range(256) if all((c[i] ^ p) in KEY for c in ciphertexts)]
    if len(candidates) != 1:
        raise SystemExit(f"ambiguous byte {i}: {candidates}")
    flag.append(candidates[0])

print("FLAG:", flag.decode())

Running the script recovered all 34 bytes uniquely.