Rune Decryptor — UIUCTF 2026

Description

No separate organizer description was preserved in the task artifacts. The interactive service supplied the rules summarized below.

The TLS service ran 20 rounds. In each round it encrypted a multilingual literary excerpt using a fresh monoalphabetic mapping from plaintext letters to Unicode runes while retaining spaces and punctuation. It allowed five full-plaintext guesses, and an incorrect guess disclosed only the number of correctly decrypted symbols. Solving more than 70% of the rounds was required.

The server was reached at rune-decryptor.chal.uiuc.tf:1337 and required a kCTF proof of work before the first round.

Analysis

Why the oracle was not enough

The word “decryptor” initially suggested an RSA or padding oracle, but the live protocol immediately disproved that interpretation: this was a direct monoalphabetic-substitution problem. The score returned after a failed guess was a single weighted Hamming total over the whole paragraph. Five such scalar observations cannot recover an arbitrary fresh key containing roughly two dozen independent mappings. At best, that feedback could distinguish a few nearly complete candidates.

Direct substitution cryptanalysis was also unattractive because every round used another language and a new key:

• An exact search in the NLTK UDHR corpus found no matching excerpt.
• Generic multilingual quadgram hillclimbing converged to plausible-looking pseudo-language rather than valid prose.
• An exhaustive beam search across ten language dictionaries was slow, and mapped-symbol coverage did not rank languages reliably.

The decisive observation was outside the ciphertext. Under every paragraph, the service printed a redacted attribution derived from Title -- Authors. Alphanumeric characters became block glyphs, but spaces, punctuation, character counts, and the truncation point remained visible. This was a strong structural fingerprint.

Project Gutenberg publishes the same title and author metadata in pg_catalog.csv.gz. Reproducing the redaction over every catalog row usually reduced a round to one source book:

def redact(text):
    return "".join("█" if ch.isalnum() else ch for ch in text)

def mask_matches(observed, display):
    prefix, truncated = clean_mask(observed)
    candidate = redact(display)
    return candidate.startswith(prefix) if truncated else candidate == prefix

This changed the problem from blind multilingual substitution cryptanalysis into corpus identification followed by a known-plaintext attack.

Locating the excerpt inside a book

For a word such as letter, define a canonical repetition pattern by assigning consecutive IDs on first appearance:

letter -> (0, 1, 2, 2, 1, 3)

Substitution preserves this pattern. The solver extracted all rune words from the ciphertext and normalized all words from the candidate Gutenberg book. It indexed the book by (word length, repeated-letter pattern), selected the ciphertext word shape with the fewest positions as an anchor, and aligned the complete ciphertext word sequence at each possible occurrence.

Every alignment was checked using one global bijection in both directions:

def extend_mapping(cipher_word, plain_word, c2p, p2c):
    if len(cipher_word) != len(plain_word):
        return False
    for c, p in zip(cipher_word, plain_word):
        if c in c2p and c2p[c] != p:
            return False
        if p in p2c and p2c[p] != c:
            return False
        c2p[c], p2c[p] = p, c
    return True

# Select the rarest shape as an anchor, slide the paragraph, and reject an
# alignment as soon as any word contradicts the shared c2p/p2c bijection.

A valid full-paragraph alignment identified the exact excerpt and supplied every rune-to-letter assignment needed to decrypt it. Cached Gutenberg matches completed in seconds; the historical benchmark solved all 25 applicable captured rounds.

Solution

1. Prepare the Gutenberg corpus

gutenberg_attack.py downloads and validates the compressed catalog, then caches books beneath the task directory:

python3 gutenberg_attack.py --bootstrap

The catalog parser constructs the same Title -- Authors display string as the challenge. It omits qualified contributors such as translators or editors where necessary, folds whitespace, reproduces the block mask, and supports prefix matching when the service truncates an attribution.

2. Solve a captured modern-language round

For a saved service response containing both the runes and attribution mask:

python3 gutenberg_attack.py --cipher-file capture.bin

The implementation performs this pipeline:

1. Strip ANSI escapes and extract the longest rune line and block-redacted line.
2. Match the attribution mask against pg_catalog.csv.gz.
3. Fetch or reuse each candidate Gutenberg text.
4. Normalize its words, including accent removal and language-specific German expansions.
5. Anchor on the rarest matching word pattern.
6. Test the complete contiguous word sequence under one bijective substitution map.
7. Decrypt the original paragraph while preserving its punctuation and submit it.

3. Use a narrow fallback for catalog misses

The Gutenberg attack handled all 14 modern-language rounds in the successful live session. Non-Gutenberg rounds came from Latin, Ancient Greek, or Russian material.

Instead of repeating the expensive and unreliable ten-language search, live_solver_gutenberg.py invoked pattern_beam.py only with the Latin dictionary and beam width 1000. The CSP processed constrained repeated or long words first, extended one global letter bijection, and retained only complete plaintexts. It solved one live Latin round.

Ancient Greek, Russian, and an incomplete Latin result were intentionally skipped by consuming the five permitted attempts. This was safe because 15 correct rounds already exceeded the threshold.

4. Run the complete live solver

PYTHONPATH=vendor python3 -u live_solver_gutenberg.py

The script establishes TLS, solves the kCTF proof of work, processes all 20 rounds, submits exact Gutenberg matches or complete Latin candidates, and deliberately advances unsupported rounds. The server's final result was exactly:

Solved 15/20 (75%).

It then returned the accepted flag.

Artifacts

• gutenberg_attack.py — catalog masking, Gutenberg caching, exact excerpt matching, and benchmarks.
• live_solver_gutenberg.py — TLS, proof-of-work, round orchestration, and bounded fallback logic.
• live_gutenberg_transcript.bin — transcript of the accepted 15/20 session.
• pattern_beam.py — dictionary-pattern CSP used only for Latin fallback candidates.
• probe.py — protocol capture and kCTF proof-of-work implementation.
• recover_capture.py and recovered_plaintext.txt — earlier Ancient Greek recovery that helped validate normalization and global bijection assumptions.