substitution2 picoCTF 2022 Solution

Description

1. Step 1

   Leverage an automatic solver

   Observation

   I noticed the ciphertext was a long block of English-like prose with consistent letter substitutions and no spaces, which suggested a monoalphabetic substitution cipher long enough for n-gram frequency analysis to succeed with an automated solver like quipqiup.

   Tools like quipqiup produce a readable paragraph about offensive competitions. Copy the output and focus on the last sentence (the one mentioning the flag).

   What didn't work first

   Tried: Trying to solve it manually using frequency analysis from scratch, counting every letter and guessing E, T, A one at a time.

   Manual frequency analysis works in theory but takes many iterations on a long ciphertext with no spaces. The top-frequency letter maps to E most of the time, but the second and third ranks often swap between T and A, and resolving ambiguities requires repeated trial and error. Automated solvers like quipqiup run thousands of candidate alphabets in seconds using n-gram scoring and should always be the first move.

   Tried: Assuming the solver output is completely correct and copying the flag directly from the decoded text without checking.

   Solvers optimize for the prose portion of the text and can mismap rare characters that only appear in the flag, especially underscores and digits. Always cross-check the last line of the decoded output against the ciphertext character by character to catch any lingering substitution errors before submitting.

   Learn more

   Without word boundaries (spaces) or punctuation, substitution solving becomes harder because solvers can't use word-shape patterns. They fall back to pure n-gram statistics- scoring candidate plaintexts based on how common each sequence of 2, 3, or 4 consecutive letters is in English. "th", "he", "in" are very common bigrams; "xz" and "qk" are extremely rare.

   Despite the added difficulty, modern solvers still handle this well for sufficiently long texts. The paragraph about offensive competitions provides enough English text for statistical patterns to emerge, allowing quipqiup to recover the correct (or near-correct) substitution alphabet. The longer the ciphertext, the more reliable the statistical attack.

   A key forensic skill demonstrated here is cross-referencing: using the partially-solved plaintext to bootstrap the full solution. Our Frequency Analysis tool lets you paste the ciphertext and interactively correct the auto-generated mapping. Once most letters are known from the prose section, the remaining mappings for digits and underscores in the flag can be inferred from the established key.

2. Step 2

   Fix the flag characters

   Observation

   I noticed the solver's decoded output looked correct for the prose section but the final line (the flag) contained underscores and digits that automated solvers often mismap, which suggested using the known-plaintext prefix picoCTF to pin the remaining substitutions and reconstruct the exact flag characters.

   Seed your solver with the known-plaintext mapping from picoCTF{: pre-fill those 7 letter substitutions, then let the solver close out the rest. Underscores and digits pass through unchanged.

   What didn't work first

   Tried: Trying to match the known prefix picoCTF against the decoded output instead of the ciphertext, leading to circular reasoning.

   The known-plaintext technique only works when you pair the known plaintext with the raw ciphertext characters. If you compare picoCTF against the solver's (possibly wrong) decoded output, you are not adding any new information. Open the original message.txt, find the last line, and read off the seven ciphertext characters that precede the opening brace to get the real mappings.

   Tried: Assuming digits and underscores inside the flag braces are also encrypted and spending time trying to decode them.

   Classic substitution ciphers in CTF problems typically only substitute alphabetic characters. Digits and punctuation like underscores are passed through the cipher unchanged. If you see a digit in the ciphertext at the flag position, it is the same digit in the plaintext - only look up the letter characters in your recovered substitution table.

   Learn more

   The flag wrapper picoCTF{...} is a known-plaintext element. You know the plaintext and can read the corresponding ciphertext. This is called a known-plaintext attack (KPA): given pairs of plaintext and ciphertext, recover the key. The prefix picoCTF maps directly to the seven cipher characters before the opening brace, revealing seven letter substitutions immediately.

   Seeding the solver in practice. Suppose the ciphertext ends with qcuhUIE{N6R4M_4N41Y515}. Pair the letters position by position:

   plain:   p i c o C T F
   cipher:  q c u h U I E
   
   Pre-fill the substitution table before solving:
     q -> p
     c -> i
     u -> c
     h -> o
     U -> C
     I -> T
     E -> F
   
   Most solvers (quipqiup, dCode, our Frequency Analysis tool) accept
   "locked" mappings as input. Lock these seven and the search space
   collapses from 26! to 19! before the solver even starts.

   Known-plaintext attacks are powerful in classical cryptography. For monoalphabetic ciphers, knowing even a few plaintext-ciphertext pairs directly reveals portions of the key. The Enigma machine was partly broken this way: German operators began messages with predictable weather reports and protocol headers that gave Allied cryptanalysts at Bletchley Park known plaintext to work with.

   Digits and underscores pass through unchanged. Confirm with the body of the flag: ciphertext N6R4M_4N41Y515 decodes to N6R4M_4N41Y515 for the non-letters (the digits 6, 4, 1, 5 and the underscore _ are identical on both sides). Only the letters N, R, M, Y need to be looked up in the recovered key, which the prose section already pinned down.

Flag

Classic substitution can be solved in seconds with automated tools, but always verify the final characters.