la cifra de picoCTF 2019 Solution

Description

1. Step 1

   Identify the cipher

   Observation

   I noticed the ciphertext preserved word spacing and contained only letters, and the challenge title 'la cifra de' is an incomplete historical phrase referencing Blaise de Vigenere, which strongly suggested this was a Vigenere polyalphabetic substitution cipher.

   The ciphertext uses only letters and preserves word spacing, which is characteristic of a Vigenere cipher. The challenge title 'la cifra de' refers to Blaise de Vigenere, who popularized this polyalphabetic substitution cipher.

   What didn't work first

   Tried: Trying to solve it as a Caesar cipher by shifting every letter by the same amount.

   Caesar is a monoalphabetic cipher - a single fixed shift across all letters. Vigenere uses a different shift per key position, so no single shift decrypts the whole message. Frequency analysis on the full ciphertext will not cleanly align with English because multiple shifts are mixed together.

   Tried: Treating the title 'la cifra de' as the decryption key directly.

   The title is a historical reference meaning 'the cipher of [Vigenere]', not the key itself. The key must be recovered via cryptanalysis of the ciphertext using Index of Coincidence or Kasiski examination.

   Learn more

   The Vigenere cipher is a polyalphabetic substitution cipher invented in the 16th century and long considered unbreakable - it was called le chiffre indéchiffrable (the indecipherable cipher) for nearly three centuries. It works by applying a series of Caesar ciphers using successive letters of a repeating keyword: the first letter of the key shifts the first letter of the plaintext, the second key letter shifts the second plaintext letter, and so on, cycling through the key.

   Key identifying characteristics of Vigenere ciphertext:

   • Only alphabetic characters are shifted; spaces, punctuation, and numbers are often left unchanged
   • Letter frequency distribution is more uniform than a Caesar cipher but less uniform than random (Index of Coincidence falls between 0.038 and 0.065)
   • Repeated sequences of letters in the ciphertext hint at the key length (Kasiski examination)

   The challenge title is a direct historical reference - Blaise de Vigenere (1523-1596) described the cipher in his 1586 Traicté des Chiffres. It was actually invented earlier by Giovan Battista Bellaso in 1553, but Vigenere's name stuck. Understanding historical cipher names helps quickly identify cipher types in CTF challenges.

2. Step 2

   Determine the key length with Index of Coincidence

   Observation

   I noticed that the ciphertext had a non-uniform letter frequency distribution that fell between natural English and fully random, which indicated a repeating key and suggested using the Index of Coincidence method to find the period before attempting decryption.

   Use the Index of Coincidence (IoC) method: try slicing the ciphertext into every nth letter and compute letter frequency statistics. When n equals the key length, the frequency profile looks like natural English (IoC ~0.065) rather than uniform random (IoC ~0.038). Tools like dCode.fr's Vigenere solver automate this step.

   What didn't work first

   Tried: Guessing a key length of 1 because the ciphertext letters seem to shift consistently in some spots.

   A key length of 1 is just a Caesar cipher. Plugging it into a Caesar solver will produce garbled output because Vigenere applies a different shift at each position. Running the IoC test across multiple candidate lengths and looking for the one that peaks near 0.065 reveals the true period.

   Tried: Running Kasiski examination on just two repeated letters rather than full trigrams.

   Single or double letter repeats occur randomly far too often to be useful. Kasiski works reliably only with repeated sequences of 3 or more letters, where the probability of accidental repetition is low enough that the distance between occurrences is likely a multiple of the key length.

   Learn more

   The Index of Coincidence (IoC) measures how likely two randomly chosen letters from a text are to be the same. For natural English, this is about 0.065 (because common letters like E, T, A appear frequently). For uniformly random text, it is about 0.038 (1/26). For a Caesar cipher (monoalphabetic), IoC equals the English value because the frequency distribution is merely shifted. For Vigenere with a long random key, IoC approaches 0.038.

   Key length determination: For each candidate key length k, split the ciphertext into k groups (letters at positions 0, k, 2k, ... form group 0; positions 1, k+1, 2k+1, ... form group 1; etc.). Compute the IoC of each group. When k equals the true key length, each group consists of letters all shifted by the same Caesar amount, so each group's IoC is close to English (0.065). When k is wrong, the groups mix multiple shifts and the IoC drops toward 0.038.

   An alternative key length technique is Kasiski examination: find repeated trigrams (3-letter sequences) in the ciphertext and compute the distances between them. The GCD of those distances is likely the key length, since repetitions arise when the same plaintext aligns with the same key position.

3. Step 3

   Recover the key and decrypt

   Observation

   I noticed that once the key length was established, each column of ciphertext letters shared a single Caesar shift, which suggested independently applying frequency analysis to each column so that the most common letter per column could be mapped to 'e' to reconstruct the full key.

   Once the key length is known, treat each column of letters (positions 0, k, 2k, ...) as a Caesar cipher and use frequency analysis to recover each key character. The most common letter in each column likely corresponds to 'e'. Paste the ciphertext into dCode.fr Vigenere Solver or use a Python library for automated recovery.

   What didn't work first

   Tried: Assuming the most frequent letter in every column must map to 'e' and accepting the result without sanity-checking.

   Frequency analysis gives the statistically most likely mapping, but for short columns it can be wrong - the most common letter might map to 't' or 'a' instead. If the resulting plaintext is garbled, try the second or third most common letter in the misbehaving column and see if the surrounding words start making sense.

   Tried: Using CyberChef's Vigenere Decode operation before knowing the key, leaving the key field blank.

   CyberChef's Vigenere operation requires a known key - it will not auto-recover one. Use dCode.fr's Vigenere Solver or a Python script to first derive the key through frequency analysis, then use CyberChef (or any tool) to decrypt with the recovered key.

   Learn more

   With the key length established, frequency analysis recovers each key character independently. Each column of letters (all encrypted with the same Caesar shift) has its own frequency distribution. In English, the most common letter is 'e' (frequency ~12.7%). If the most common letter in column i is, say, 'J', then the key character for position i likely shifts 'e' (position 4) to 'J' (position 9), giving a shift of 5 and key letter 'F'.

   Practical tools for automated Vigenere cryptanalysis:

   • dCode.fr - web-based Vigenere solver with automated key recovery
   • CyberChef - "Vigenere Decode" operation (requires known key)
   • Python pycipher - library with Vigenere implementation
   • quipqiup.com - general substitution cipher solver using frequency analysis

   The Vigenere cipher was broken by Charles Babbage in 1854 (unpublished) and Friedrich Kasiski in 1863. Today, any repeating-key cipher is trivially broken by these methods. This is why modern symmetric encryption (AES, ChaCha20) generates a unique keystream for each message and uses keys much longer than the message.

Flag

Vigenere is broken when the key is much shorter than the message - frequency analysis per key position reveals each character of the key.