Probably Unbreakable

Platform: Broncoctf2026 | Category: Cryptography | Type: Challenge | Difficulty: Easy | OS: NA | Author: D3v0o0Nu11 | Date: 2026-07-11 | Status: Solved Techniques: candidate_intersection, known_alphabet_attack, restricted_alphabet_xor

Summary

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 plaintext bytes (those where ciphertext XOR p lands in the alphabet) across all ciphertexts until exactly one survives — a restricted-alphabet XOR candidate-intersection attack, no PRNG state recovery needed.

Recon

Port scan

 bash read-only • copy allowed Copy
nmap -p- -sV -sC <TARGET> --min-rate 1000 -Pn

Enumeration highlights

• Event: broncoctf2026 | ID: 20260711_broncoctf2026_probably_unbreakable
• Tags: xor, stream_cipher, prng, restricted_alphabet, candidate_intersection
• 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
• Source: 20260711_broncoctf2026_probably_unbreakable.md

Foothold

Vulnerability / Misconfiguration

1. candidate_intersection
2. known_alphabet_attack
3. restricted_alphabet_xor

 bash read-only • copy allowed Copy
<command>

Exploitation

• See original writeup content for detailed exploitation.

Privilege Escalation

Enumeration

 bash read-only • copy allowed Copy
sudo -l
find / -perm -4000 2>/dev/null
getcap -r / 2>/dev/null
cat /etc/crontab
ps aux

Exploitation

1. N/A for challenge-type writeup; see exploitation above.
2. Flag obtained via challenge solve.

 bash read-only • copy allowed Copy
<command>

Flags

Key Takeaways / Lessons

• candidate_intersection
• known_alphabet_attack
• restricted_alphabet_xor
• Tags: xor, stream_cipher, prng, restricted_alphabet, candidate_intersection

Original Writeup

<details><summary>Click to expand original content</summary>

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.

</details>

---

signed by XESXOR