PicoCTF Substitution0 Writeup — Break a Substitution Cipher with Frequency Analysis

Unlike Caesar, each letter is replaced by a different letter according to an arbitrary mapping (not a simple shift). We solve it by comparing the letter frequency of the ciphertext to the known letter frequency in English, and guessing short words (the, and, a...).

• Platform: picoGym
• Category: Cryptography
• Points: 150 pts
• Difficulty: Beginner
• Technique: Monoalphabetic substitution, frequency analysis

Challenge description

The challenge provides a fairly long, fully encrypted text, with no hint other than the challenge's name:

"Not all ciphers are too complicated. Sometimes, all you need to do is find the correct letters."

The text contains several hundred characters — that's no accident, as we'll see, the more ciphertext there is, the more reliable frequency analysis becomes.

Step 1 — The difference from Caesar: monoalphabetic substitution

Here, there's no simple shift: each letter of the alphabet is mapped to another letter according to an arbitrary correspondence (for example A→Q, B→W, C→E...), fixed once and for all for the entire message. This gives 26! (26 factorial) possible combinations — an astronomical number, far too large for naive brute force like on Caesar.

But substitution remains vulnerable to a structural weakness: it preserves the relative frequency of letters. If "E" is the most used letter in English, then in the ciphertext, the most frequent letter very likely corresponds to "E".

Step 2 — Frequency analysis

We start by counting the occurrence of each letter in the ciphertext with collections.Counter:

from collections import Counter

with open("ciphertext.txt") as f:
    text = f.read().lower()

letters = [c for c in text if c.isalpha()]
freq = Counter(letters)

for letter, count in freq.most_common():
    pct = 100 * count / len(letters)
    print(f"{letter} : {count:4d} occurrences  ({pct:.1f}%)")

x :  187 occurrences  (12.4%)
q :  143 occurrences  ( 9.5%)
z :  121 occurrences  ( 8.0%)
j :   98 occurrences  ( 6.5%)
...

We compare this ranking to the known letter frequency in English: E (12.7%), T (9.1%), A (8.2%), O (7.5%), I (7.0%), N (6.7%)... First hypothesis: x → E, q → T, z → A, j → O.

Step 3 — Deduce mappings and iterate

Overall frequency gives a starting point, but it's never enough to solve the text in one shot — you have to refine it with structural clues:

• Single-letter words in English can only be A or I
• The most common three-letter words are often THE or AND
• Consecutive doubled letters (like SS, LL, EE) point toward certain common pairs
• Punctuation and word structure (apostrophes, short words at the end of a sentence) provide further clues

We progressively substitute the safest letters, re-read the partially decrypted text, and correct wrong hypotheses as recognizable words emerge:

Before: xqz zex ol jax os qjx pxrq ...
After (E,T,A,O known): ..e ..a .. .a. .. e..a...

By iterating several times, the text becomes more and more readable until it reveals complete words, then whole sentences, and finally the expected pattern picoCTF{...}.

Step 4 — Verify with an automatic solver

To save time or check your work, there are online substitution solvers like quipqiup.com, which use an English dictionary and a search algorithm to automatically suggest the most likely mapping. It's an excellent way to confirm a solution found manually, or to unblock a text too short for reliable frequency analysis.

🚩 picoCTF{ flag intentionally hidden }

The flag is deliberately hidden — follow the method, you've earned it. 💪

Key takeaways

Monoalphabetic substitution has a huge key space (26!), but it doesn't hide the underlying statistical structure of the language — and that's exactly what frequency analysis exploits.

• Frequency analysis is THE basic technique against any simple substitution cipher — it's what has made these ciphers obsolete for centuries against an adversary with enough ciphertext
• The longer the ciphertext, the closer the frequency distribution gets to the language's theoretical distribution, and the easier it is to solve
• Combining letter frequency with recognizing short words (A, I, THE, AND) dramatically speeds up solving compared to a purely statistical approach

Originally published on CTFdojo — join the CTFdojo Discord to discuss writeups and get notified about new ones.