waves over lambda picoCTF 2019 Solution

Description

1. Step 1

   Get the ciphertext

   Observation

   I noticed the challenge description explicitly says 'substitution cipher' and instructs connecting to a server, which meant the ciphertext had to be retrieved live via nc before any analysis could begin.

   Connect with nc. The server prints a paragraph of ciphertext encrypted with a simple substitution cipher (each letter is replaced by a different letter consistently throughout the text). Copy the entire ciphertext.

   Learn more

   Why the keyspace size is misleading. A monoalphabetic substitution cipher maps each plaintext letter to a unique cipher letter. The total keyspace is 26! ≈ 4 * 10^26 - far too large to brute force. But the cipher leaks two structural properties: (1) letter equality is preserved - identical plaintext letters always map to the same ciphertext letter, and (2) letter frequency is preserved- if 'e' is 12.7% of plaintext, then whatever letter 'e' maps to is 12.7% of ciphertext.

   English letter frequencies (long text).

   E  12.7%   T  9.1%   A  8.2%   O  7.5%   I  7.0%
   N  6.7%    S  6.3%   H  6.1%   R  6.0%   D  4.3%
   L  4.0%    C  2.8%   U  2.8%   M  2.4%   W  2.4%
   F  2.2%    G  2.0%   Y  2.0%   P  1.9%   B  1.5%
   V  1.0%    K  0.8%   J  0.15%  X  0.15%  Q  0.10%   Z  0.07%

   Index of Coincidence (IoC). A statistical measure: probability that two randomly chosen letters from the text are equal. For English, IoC ~= 0.0667; for uniform random text (26 equally likely letters), IoC = 1/26 ~= 0.0385. A monoalphabetic substitution preserves IoC at the English value (since frequencies are merely relabeled). A polyalphabetic cipher (Vigenere) drops IoC toward 0.0385 because it flattens the distribution. Computing IoC of the ciphertext is the first sanity check that this is a simple substitution.

   Bigram and trigram analysis sharpen the attack. The most common English bigrams: TH HE IN ER AN RE. Trigrams: THE AND ING HER. The single most common word: THE (~3% of all words). Once you guess e -> X and t -> Y from frequency, look at three-letter words starting with Y and ending with X: those are likely THE, fixing the third letter as h -> ? in one shot.

2. Step 2

   Perform frequency analysis

   Observation

   I noticed the cipher preserves word spacing and each letter maps consistently to the same ciphertext letter, which are the defining traits of a monoalphabetic substitution and indicated that aligning letter-frequency histograms against the known English distribution would reveal the substitution key.

   Count letter frequencies in the ciphertext. The most frequent cipher letter is probably E, the second most frequent is probably T, and so on. Build a substitution key based on these correspondences.

   python

   python3 << 'EOF'
   from collections import Counter
   
   ciphertext = """PASTE CIPHERTEXT HERE"""
   ct_letters = [c.lower() for c in ciphertext if c.isalpha()]
   freq = Counter(ct_letters).most_common()
   print("Cipher letter frequencies:")
   for letter, count in freq:
       print(f"  {letter}: {count}")
   print("\nExpected English order: e t a o i n s h r l d c u m f p g w y b v k x j q z")
   EOF

   Copied!

   What didn't work first

   Tried: Directly mapping the most frequent cipher letter to E, the second to T, and so on for all 26 letters at once, then reading the result as plaintext.

   Frequency order is only a statistical guide, not a guaranteed 1-to-1 ranking. In a short paragraph the 3rd and 4th most frequent letters may be swapped relative to the expected English order, producing garbled output for most of the alphabet. The correct approach is to use frequency rank as a starting hypothesis, then refine by looking at high-frequency bigrams and short words to confirm or swap individual letters.

   Tried: Running a Vigenere decryption tool on the ciphertext, treating it as a polyalphabetic cipher and trying common key lengths.

   Vigenere decryption tools look for repeating key patterns using Kasiski or Index of Coincidence tests; a monoalphabetic substitution has an IoC near 0.0667 (the English value), not the flattened ~0.0385 a Vigenere cipher produces. The tool will either report an inconsistent key length or produce incoherent output because the underlying cipher model is wrong.

   Learn more

   Crib bootstrapping. A crib is a piece of plaintext you know lives in the ciphertext. The flag format picoCTF{...} guarantees the seven letters p, i, c, o, C, T, F appear inside the braces. Find any {...} pattern in the ciphertext - the seven letters inside are exactly that mapping (case is sometimes preserved, sometimes flattened). Lock those substitutions, propagate them throughout the text, and the partial decryption guides the rest.

   Hill-climbing solver (quipqiup style). Start with a random key. Compute a fitness score: log-likelihood of the partial decryption under English n-gram probabilities (typically quadgram statistics from a corpus). Repeatedly swap two letters in the key, accept the swap if fitness improves, occasionally accept a worse swap (simulated annealing) to escape local optima. After ~5000-10000 iterations the key converges to the real one. quipqiup.com runs this in your browser; expect a clean answer in under 10 seconds for a paragraph of text.

   fitness(text) = sum over each 4-letter window:
                     log P(quadgram | English)
   
   P(THER | English) ~ 10^-2
   P(QXJZ | English) ~ 10^-9   <- garbage

3. Step 3

   Decode the flag

   Observation

   I noticed the frequency analysis and crib-based substitutions had reconstructed enough of the key to make the plaintext readable, which meant applying the complete mapping to the full ciphertext would reveal the picoCTF{...} flag embedded in the decrypted paragraph.

   Apply your discovered substitution key to the entire ciphertext. The flag text will appear. Look for the picoCTF{...} pattern.

   Learn more

   Frequency analysis was first described by Arab mathematician Al-Kindi in the 9th century. It remained the primary cryptanalytic technique for nearly 1000 years, until the invention of polyalphabetic ciphers (Vigenere) made it less effective.

Flag

Per-instance flag: prefix 'frequency_is_c_over_lambda_' is fixed but the trailing suffix varies per team instance