Probably Unbreakable

Platform: CUSTOM | Category: Crypto | Type: Challenge | Difficulty: Easy | OS: N/A | **Author: XESXOR Techniques: candidate_intersection, known_alphabet_attack, restricted_alphabet_xor

Summary

Walkthrough of the CUSTOM Crypto Probably Unbreakable. Task: a service XORs the flag with random key bytes drawn from a fixed 64-character alphabet and lets you request up to 20000 encryptions. Solution: for each flag position, intersect the candidate pla

---

title: "Probably Unbreakable" id: 20260711_broncoctf2026_probably_unbreakable category: crypto difficulty: easy event: broncoctf2026 tags: ["xor", "stream_cipher", "prng", "restricted_alphabet", "candidate_intersection"] techniques: ["candidate_intersection", "known_alphabet_attack", "restricted_alphabet_xor"] tools: ["python3", "socket"] indicators: ["XOR with random.choices from a fixed 64-char alphabet", "large query budget (20000 encryptions)", "keystring alphabet does not span full byte range", "one-time-pad-style XOR that is not actually a full OTP"]

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:

 python read-only • copy allowed Copy
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.

 python read-only • copy allowed Copy
#!/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.

Key Takeaways / Lessons

• Mastering candidate_intersection, known_alphabet_attack, restricted_alphabet_xor was key to this challenge.
• Always check for common misconfigurations and verify assumptions.

---

Crafted by XESXOR Research • 2026-07-11 • CUSTOM • Probably Unbreakable • Difficulty: Easy