New Caesar picoCTF 2021 Solution

Description

1. Step 1Understand the encoding

   Observation

   The ciphertext uses only a through p, 16 distinct letters. That is not a standard 26-letter Caesar but a nibble scheme: each byte splits into two 4-bit halves mapped onto a 16-letter alphabet, and the key shift comes after.

   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 2Brute-force the key

   Observation

   An a-to-p alphabet caps the key space at 16 possible shifts. Brute-forcing all 16 is trivial, and a printable-ASCII filter on the decoded output picks out the right one cleanly.

   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 is computed modulo 16, not 26, because the alphabet runs only a to p. Use modulo 26 and many unshifted characters land outside that range, so ALPHABET.index() raises a ValueError and all 26 keys appear to fail. Restrict both the key loop and the modulo to the alphabet's length of 16.

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

   The nibble encoding turns one input byte into two output characters, so the ciphertext is twice the plaintext length. Feed single characters to the decode step and you get a high nibble with no low nibble, producing bytes from 0x00 to 0xF0 that almost never survive the printable-ASCII filter. Step the decode loop two characters at a time.

   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.