DEV Community

CTFDojo
CTFDojo

Posted on Originally published at ctfdojo.com

PicoCTF Substitution0 Writeup — Break a Substitution Cipher with Frequency Analysis

#ctf #security #cryptography

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}%)")
Enter fullscreen mode Exit fullscreen mode 
x :  187 occurrences  (12.4%)
q :  143 occurrences  ( 9.5%)
z :  121 occurrences  ( 8.0%)
j :   98 occurrences  ( 6.5%)
...
Enter fullscreen mode Exit fullscreen mode

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...
Enter fullscreen mode Exit fullscreen mode

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.

Top comments (0)