PicoCTF Substitution0 Writeup — Break a Substitution Cipher with Frequency Analysis

PicoCTF Substitution0 Writeup — Break a Substitution Cipher with Frequency Analysis

In this challenge, an encrypted message is provided that has been encoded using a substitution cipher. Unlike a Caesar cipher, each letter in the plaintext is replaced by a different letter according to a fixed but unknown mapping. To decrypt the message, the key step is frequency analysis.

The text contains a few hundred characters, which provides enough ciphertext to perform a reliable frequency analysis. The first step is to count the occurrence of each letter in the ciphertext. By comparing these frequencies to the expected letter frequencies in the English language (E is the most common at 12.7%, followed by T at 9.1%), we can make educated guesses about the mapping.

For example, the most frequent letter in the ciphertext, 'x', is likely to correspond to 'E'. Similarly, 'q' might map to 'T', 'z' to 'A', and 'j' to 'O'. These initial letter substitutions give us a starting point.

However, frequency analysis alone is not enough to solve the cipher in one go. We need to refine our mappings using structural clues in the English language. For instance, single-letter words can only be 'A' or 'I', and the most common three-letter words are often 'THE' or 'AND'. The presence of doubled letters like 'SS', 'LL', or 'EE' can also give us hints.

By progressively substituting the most likely letters and re-reading the partially decrypted text, we can confirm or correct our hypotheses. As recognizable words and phrases emerge, the text becomes more readable. With enough ciphertext, the frequency distribution of letters in the ciphertext aligns closely with the statistical properties of English, making frequency analysis an effective method to break the cipher.

Once the text is fully decrypted, we arrive at the expected pattern 'picoCTF{...}', revealing the flag hidden within. This writeup demonstrates the power of combining frequency analysis with an understanding of language structure to break simple substitution ciphers. The longer the ciphertext, the more reliable the frequency analysis, and the easier the decryption becomes.