substitution2 picoCTF 2022 Solution

Description

1. Step 1Leverage an automatic solver

   Observation

   The ciphertext is a long block of English-shaped prose with consistent letter substitutions and no spaces. That is a monoalphabetic substitution, and long enough for n-gram frequency analysis in an automated solver to succeed.

   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 principle and takes many passes on a long ciphertext with no spaces. The top letter is usually E, but second and third place trade between T and A, and resolving that takes trial and error. An automated solver runs thousands of candidate alphabets in seconds with n-gram scoring, so start there.

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

   Solvers optimize for the prose and can mismap rare characters that appear only in the flag, underscores and digits especially. Check the last line of the decoded output against the ciphertext character by character 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 2Fix the flag characters

   Observation

   The decoded prose looks right while the final line, the flag, carries underscores and digits that solvers routinely mismap. Use the known picoCTF prefix to pin the remaining substitutions and rebuild the exact 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 helps when you pair the known text with the raw ciphertext. Compare picoCTF against the solver's own, possibly wrong, output and you learn nothing new. Open the original message.txt, find the last line, and read the seven ciphertext characters before the opening brace.

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

   Classic substitution ciphers in CTFs usually touch only the letters, passing digits and punctuation through unchanged. A digit in the ciphertext at the flag position is the same digit in the plaintext, so look up only the letters in your recovered 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. The ciphertext in this challenge ends with qcuhUIE{K6F4G_4K41R515_15_73A10B5_...}. Pair the letters of the prefix 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 K6F4G_4K41R515 carries the digits 6, 4, 1, 5 and the underscore _ straight through, so they are identical on both sides. Only the letters K, F, G, R need to be looked up in the recovered key, which the prose section already pinned down; they resolve to N, R, M, Y, giving N6R4M_4N41Y515(leetspeak for "ngram_analysis").

Flag

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