New Caesar picoCTF 2021 Solution

Description

1. Step 1

   Understand the encoding

   Observation

   I noticed the ciphertext used only characters from a-p (16 distinct letters), which suggested the encoding was not a standard 26-letter Caesar cipher but a nibble-based scheme where each byte is split into two 4-bit halves and mapped onto a 16-letter alphabet before a key shift is applied.

   Read new_caesar.py. Each character is converted to a value 0-15 (its nibbles), and each nibble is encoded as a letter a-p. A key-based Caesar shift is then applied to each encoded character. The full alphabet used is a-p (16 characters).

   Learn more

   The "new Caesar" scheme is a two-stage encoding. In the first stage, each byte of the plaintext is split into two nibbles (4-bit halves) - the high nibble (upper 4 bits, value 0 to 15) and the low nibble (lower 4 bits, value 0 to 15). Each nibble is then mapped to a letter from the alphabet a-p (16 letters), so one input character becomes two output characters.

   The second stage applies a Caesar shift to each encoded character using a single-character key. The shift is the key letter's position in the a-p alphabet. This means the combined cipher is not just a Caesar cipher - it's a Caesar cipher on top of a base-16 encoding, applied at the nibble level rather than the character level.

   Operator primer. byte >> 4 is a logical right shift by 4 bits, dropping the low nibble and leaving the high nibble in the low 4 bits of the result. byte & 0x0F is a bitwise AND that masks off the high nibble, leaving only the low nibble. Recombining: (hi << 4) | lo where << shifts the high nibble back into the upper 4 bits and | (bitwise OR) merges the two halves into one byte.

   Validate the alphabet first. Before brute-forcing, confirm every ciphertext character is in a..p: print(sorted(set(ciphertext))). If a character lies outside that range, your understanding of the cipher is wrong. The 32 <= ord(c) < 127 filter used in the brute-force is just printable-ASCII range; that filter rules out garbage candidates and is also how you spot the flag's picoCTF{...} prefix among results.

   Why this matters: The encoding expands the ciphertext (each byte becomes two characters) and restricts the alphabet to just 16 letters, which shrinks the key space. Instead of 26 possible Caesar shifts, there are only 16. The design demonstrates how layering encoding on top of a cipher does not add significant security if the layers are independently weak.

2. Step 2

   Brute-force the key

   Observation

   I noticed the a-p encoding alphabet limits the key space to only 16 possible Caesar shifts, which meant a brute-force attack over all 16 candidate keys was feasible and a printable-ASCII filter on decoded output would cleanly identify the correct key.

   There are only 16 possible key values (letters a through p). Try each one, reverse the Caesar shift, reverse the nibble encoding, and check whether the result is valid printable ASCII.

   python

   python3 << 'EOF'
   ALPHABET = "abcdefghijklmnop"
   
   def b16_decode(encoded):
       result = []
       for i in range(0, len(encoded), 2):
           hi = ALPHABET.index(encoded[i])
           lo = ALPHABET.index(encoded[i+1])
           result.append(chr((hi << 4) | lo))
       return "".join(result)
   
   def shift_char(c, key, decrypt=True):
       idx = ALPHABET.index(c)
       key_idx = ALPHABET.index(key)
       if decrypt:
           return ALPHABET[(idx - key_idx) % len(ALPHABET)]
       return ALPHABET[(idx + key_idx) % len(ALPHABET)]
   
   ciphertext = "kjlijdliljhdjdhfkfkhhjkkhhkihlhnhghekfhmhjhkhfhekfkkkjkghghjhlhghmhhhfkikfkfhm"
   
   for key in ALPHABET:
       try:
           unshifted = "".join(shift_char(c, key) for c in ciphertext)
           decoded = b16_decode(unshifted)
           if all(32 <= ord(c) < 127 for c in decoded):
               print(f"Key={key}: {decoded}")
       except Exception:
           pass
   EOF

   Copied!

   Expected output

   Key=e: et_tu?_1ac5f3d7920a85610afeb2572831daa8

   What didn't work first

   Tried: Brute-force using the full 26-letter Caesar alphabet instead of the 16-letter a-p alphabet.

   The shift in new_caesar.py is computed modulo 16, not modulo 26, because the encoding alphabet is only a-p. Applying modulo 26 shifts produces candidates where many unshifted characters fall outside a-p, causing ALPHABET.index() to raise a ValueError and all 26 keys to appear to fail. Restricting the key loop and the modulo to len(ALPHABET) = 16 is required.

   Tried: Treating each ciphertext character as one encoded byte instead of each pair of characters as one decoded byte.

   The nibble encoding maps one input byte to two output characters, so the ciphertext is twice as long as the plaintext. Passing single characters to the decode step produces (hi << 4) with no lo nibble, yielding bytes in the range 0x00 to 0xF0 that almost never pass the printable-ASCII filter. The decode loop must step in increments of 2 over the unshifted ciphertext.

   Learn more

   Brute-force is viable here because the key space is tiny - only 16 possibilities. For each candidate key, you reverse the Caesar shift on the ciphertext, then attempt to decode the result as base-16 nibble pairs. If the decoded bytes all fall in the printable ASCII range (32 to 126), the key is almost certainly correct.

   The printable ASCII check acts as a crib - a known property of the plaintext. The flag must consist of printable characters (letters, digits, braces, underscores), so any key that produces garbage bytes is immediately eliminated. This kind of filter is standard practice when brute-forcing substitution ciphers: you check candidate plaintexts against an expected character set rather than manually examining all 16 outputs.

   Bit manipulation: The decode step uses (hi << 4) | lo - shifting the high nibble left by 4 bits and OR-ing with the low nibble to reassemble the original byte. This is the inverse of splitting a byte into two nibbles using byte >> 4 and byte & 0x0F. Bit manipulation at the nibble level is fundamental to understanding how many encoding schemes and simple ciphers operate on binary data.

Flag

The custom encoding is a base-16 representation followed by a per-character shift - only 16 possible keys to try.