substitution0 picoCTF 2022 Solution

Description

1. Step 1

   Derive the mapping

   Observation

   I noticed the top of message.txt contained a 26-character permutation of the alphabet printed before the ciphertext, which identified the cipher as a keyed monoalphabetic substitution and indicated that reversing the key lookup would directly yield the plaintext.

   Because the key lists ciphertext letters in order of plaintext A-Z, you simply look up each encrypted character's index in the key and pull the corresponding letter from the alphabet.

   What didn't work first

   Tried: Treating the key as a direct substitution table - mapping plaintext letter A to the first key character, B to the second, etc. - and applying it forward to decrypt.

   This is the encryption direction, not the decryption direction. Applying the key forward re-encrypts the ciphertext rather than decoding it. To decrypt, you need the reverse: find where each ciphertext letter appears in the key and read off the corresponding A-Z position.

   Tried: Running frequency analysis on the ciphertext to reconstruct the key, ignoring the key that is already printed at the top of the file.

   Frequency analysis is the fallback when no key is provided. Here the key is explicitly included in message.txt, so all the guesswork is eliminated. Reading the file fully before starting any analysis saves significant time.

   Learn more

   A monoalphabetic substitution cipher replaces each letter with a fixed substitute throughout the entire message. The key is a permutation of the alphabet - a mapping from each plaintext letter to a unique ciphertext letter. With 26 letters, there are 26! (about 4 × 10^26) possible keys, making brute force impractical.

   However, monoalphabetic ciphers are completely broken by frequency analysis: in English, "E" appears roughly 12.7% of the time, "T" at 9.1%, "A" at 8.2%, etc. By counting letter frequencies in the ciphertext and matching them to known English frequencies, an attacker can recover the key without knowing it. This attack was described by Al-Kindi in the 9th century - making monoalphabetic ciphers over 1000 years old and broken. Our Frequency Analysis tool automates this: paste the ciphertext and it builds an interactive decryption mapping ranked by frequency.

   In this specific challenge, the key is provided in the file, so no analysis is needed - it's purely an exercise in applying the mapping. The Python one-liner uses key.index(c) to find where ciphertext letter c appears in the key (which corresponds to its plaintext position), then maps it back to the correct alphabet letter.

2. Step 2

   Assemble the flag

   Observation

   I noticed the decoded output contained alphabetic characters alongside underscores, digits, and curly braces, which indicated that only the letters needed the reverse substitution applied and that non-alpha characters should pass through unchanged to form the picoCTF{...} flag.

   Handle underscores/digits literally, wrap the decoded string with picoCTF{...}, and you have the final flag.

   What didn't work first

   Tried: Applying the reverse substitution to every character in the output, including underscores, digits, and curly braces.

   Monoalphabetic substitution only affects the 26 alphabetic characters. Non-alpha characters like underscores, digits, and punctuation pass through unchanged. Running them through the lookup crashes or produces garbage because they have no position in the A-Z key.

   Tried: Submitting the decoded text as-is without adding the picoCTF{} wrapper.

   The flag format always requires picoCTF{...} around the inner text. The decoded message contains the content of the flag but the submission is only accepted with the correct format. Check whether the braces are already part of the ciphertext before adding them manually.

   Learn more

   The substitution cipher only affects alphabetic characters - digits, underscores, spaces, and punctuation pass through unchanged. This is a deliberate design choice in classical ciphers (and in the picoCTF flag format, where _ and digits are common).

   The Python approach (alphabet[key.index(c)] if c.isalpha() else c) cleanly handles this: for alphabetic characters, perform the reverse substitution; for everything else, output the character as-is. This is the standard pattern for implementing classical cipher decoders.

   Historical context: the Caesar cipher is a special case of monoalphabetic substitution where the key is a rotation of the alphabet (ROT-13 is Caesar with a shift of 13). The Vigenère cipher extends this to use different substitutions at different positions, making frequency analysis harder but not impossible via Kasiski examination and index of coincidence analysis.

Flag

This challenge is intentionally straightforward, so no frequency analysis is required once the key is provided.