New Vignere picoCTF 2021 Solution

Description

1. Step 1Understand the New Vigenere encoding

   Observation

   The name says 'New' and the ciphertext alphabet is only 16 letters, a through p. So this is not a standard Vigenere, and the extra base-16 nibble-encoding layer has to be understood before any cryptanalysis.

   The 'New' Vigenere differs from classical Vigenere by first encoding the plaintext into a restricted alphabet using a custom base16-like scheme before applying the Vigenere cipher. Understand both layers before attempting decryption.

   Learn more

   Classical Vigenere refresher. Plaintext letter at position i is shifted by key letter at position i mod L, all modulo 26. Encryption: c_i = (p_i + k_(i mod L)) mod 26. Decryption: p_i = (c_i - k_(i mod L)) mod 26. Strength comes from the polyalphabetic shift; weakness comes from the repeating key.

   The "new" twist. Plaintext is first nibble-encoded into the 16-letter alphabet abcdefghijklmnop (a=0, b=1, ..., p=15), then Vigenere-shifted modulo 16:

   Encrypt:
     for byte b in plaintext:
         hi, lo = b >> 4, b & 0xF
         out += alpha[(hi + key[i % L]) % 16]
         out += alpha[(lo + key[(i+1) % L]) % 16]
   
   Decrypt:
     reverse: subtract key, repack nibbles into bytes

   Worked tiny example. Plaintext 'A' = 0x41; key k = "ba" = [1, 0]:

   hi = 4, lo = 1
   ct[0] = alpha[(4 + 1) % 16] = alpha[5] = 'f'
   ct[1] = alpha[(1 + 0) % 16] = alpha[1] = 'b'
   ciphertext = "fb"
   
   Decrypt "fb" with key [1, 0]:
   hi = (5 - 1) mod 16 = 4
   lo = (1 - 0) mod 16 = 1
   byte = (4 << 4) | 1 = 0x41 = 'A'   ✓

   Why the alphabet shrinks the keyspace. Modulo 16 instead of modulo 26, with key length L, total keyspace is 16^L. L = 6 gives 2^24 ≈ 16M keys - brute-forceable in seconds. The nibble-doubling also means the key advances twice per plaintext byte, so an odd key length makes each key position alternate between "hi" and "lo" roles on successive bytes - worth remembering when interpreting Kasiski distances, which are measured in encoded characters, not plaintext bytes.

2. Step 2Perform the Kasiski examination or frequency analysis

   Observation

   The ciphertext is long enough to carry repeated substrings, and the polyalphabetic key repeats. Kasiski examination extracts the key length, then per-column index-of-coincidence isolates each Caesar shift on its own.

   Find the key length using the Kasiski test (look for repeated ciphertext substrings; their spacings are multiples of the key length). Then use index of coincidence or frequency analysis to recover the key. Split the ciphertext into L columns with cols = [ct[i::L] for i in range(L)] so each column is a single-shift Caesar.

   python

   python3 - <<'EOF'
   ciphertext = "PASTE_CIPHERTEXT_HERE"
   alpha = "abcdefghijklmnop"  # the b16 alphabet
   
   # Kasiski: find repeated trigrams and their spacings
   from collections import Counter, defaultdict
   import math
   
   def gcd_list(lst):
       result = lst[0]
       for v in lst[1:]:
           result = math.gcd(result, v)
       return result
   
   positions = defaultdict(list)
   for i in range(len(ciphertext) - 2):
       tri = ciphertext[i:i+3]
       positions[tri].append(i)
   
   spacings = []
   for tri, pos in positions.items():
       if len(pos) > 1:
           spacings.extend([pos[j+1]-pos[j] for j in range(len(pos)-1)])
   
   if spacings:
       key_len = gcd_list(spacings)
       print(f"Likely key length: {key_len}")
   
   # Index of coincidence: discriminator for the right key length
   def ic(s):
       n = len(s)
       counts = Counter(s)
       return sum(c*(c-1) for c in counts.values()) / (n*(n-1))
   
   # Average IoC across columns; structured plaintext sits well above 1/16 = 0.0625
   for L in range(2, 12):
       cols = [ciphertext[i::L] for i in range(L)]
       avg = sum(ic(c) for c in cols) / L
       print(f"L={L}: avg IoC = {avg:.4f}")
   EOF

   Copied!

   What didn't work first

   Tried: Treat the ciphertext as a standard Vigenere over the 26-letter alphabet and run a classical Kasiski tool against it.

   The ciphertext uses only the 16-letter alphabet a to p, so any tool expecting 26 letters miscounts the frequencies and reports a nonsensical index of coincidence, near 1/26 rather than 1/16. The threshold for structured plaintext here is 0.0625, not 0.0385. The script sets the alphabet and modulus to 16 explicitly to get the right baseline.

   Tried: Take the GCD of ALL repeated trigram gaps and accept the result immediately as the key length without verifying with IoC.

   Coincidental repeated trigrams, unrelated to the key, create spurious gaps that drag the GCD down to 1 or 2 and hide the real key length. The index-of-coincidence check on each candidate column slice confirms it: the correct length gives high per-column values around 0.07 to 0.10, while a wrong one sits near the uniform floor of 0.0625.

   Learn more

   Kasiski intuition. If two identical plaintext substrings happen to align with the same key offset, they produce identical ciphertext substrings. The distance between those occurrences must therefore be a multiple of the key length L. Find every repeated trigram in the ciphertext, list the gaps between occurrences, and take the GCD of those gaps. The result is almost always L (occasionally a small multiple of L).

   Worked toy example. Ciphertext ...HJBCFHJBCFHJBC... has trigram HJB at positions 0, 5, 10. Gaps: 5, 5. GCD = 5, so the key length is 5 (or a divisor of 5, i.e., 1 - which would be a Caesar cipher and is ruled out by the IoC test).

   Index of Coincidence as a sanity check. For a 16-letter alphabet, English (or any structured plaintext) has IoC well above the uniform value 1/16 = 0.0625. Compute IoC of each candidate column slice; when key length is correct, every slice IoC should be ~0.07-0.10 (since each slice is now a simple shift cipher and preserves frequency). Wrong key lengths give IoC around 0.0625 (uniform).

   IoC(column) = sum_c [n_c * (n_c - 1)] / [N * (N - 1)]
   where n_c is the count of letter c in the column, N is column length

   Recovering each key byte. Once L is locked, split into L columns. Each column is a Caesar cipher mod 16. The most common letter in an encoded flag is the high-nibble letter 'd' = 3, because every hex digit 0-9 has high nibble 0x3, followed by 'g' = 6 for the lowercase letters ('i', 'c', 'o', 'a'-'f' all sit in 0x60-0x6f); low nibbles are spread. For each column, find the most frequent ciphertext letter x, set k_i = (x - expected) mod 16. Verify the candidate key by decrypting and checking that the result starts with picoCTF.

3. Step 3Brute-force the key or use CyberChef

   Observation

   A 16-letter alphabet reduces the keyspace to 16 raised to the key length. Once Kasiski gives that length, testing all 16 shifts column by column takes seconds, so a targeted brute force checking for the picoCTF prefix is the fastest route.

   If the key is short, brute-force all possible keys. Use Python to apply the inverse b16 decode and Vigenere decryption, checking if the result contains 'picoCTF'.

   python

   python3 - <<'EOF'
   ciphertext = "PASTE_CIPHERTEXT_HERE"
   alpha = "abcdefghijklmnop"
   
   def b16_decode(s):
       result = []
       for i in range(0, len(s), 2):
           hi = alpha.index(s[i])
           lo = alpha.index(s[i+1])
           result.append(hi << 4 | lo)
       return bytes(result)
   
   def vigenere_decrypt(ct, key):
       N = len(alpha)
       result = []
       for i, c in enumerate(ct):
           k = alpha.index(key[i % len(key)])
           result.append(alpha[(alpha.index(c) - k) % N])
       return ''.join(result)
   
   # Brute force short keys
   key_len = 9  # from Kasiski
   assert len(alpha) == 16, "alphabet must be 16 chars for the base-16 conversion"
   # Note: 16^9 is too large for exhaustive brute force; use column-by-column analysis instead (see context)
   for key_int in range(len(alpha) ** key_len):
       key = ''
       n = key_int
       for _ in range(key_len):
           key = alpha[n % len(alpha)] + key
           n //= len(alpha)
       assert len(key) == key_len  # avoid off-by-one base-16 conversion bugs
       decrypted_b16 = vigenere_decrypt(ciphertext, key)
       try:
           decoded = b16_decode(decrypted_b16)
           if b'picoCTF' in decoded:
               print(f"Key: {key}")
               print(f"Flag: {decoded.decode()}")
               break
       except Exception:
           pass
   EOF

   Copied!

   What didn't work first

   Tried: Use CyberChef's built-in Vigenere Decode operation directly on the ciphertext without first reversing the b16 nibble-encoding layer.

   CyberChef's Vigenere Decode works on the 26-letter English alphabet, while this ciphertext uses 16 letters and mod-16 arithmetic, so CyberChef returns garbage even with the right key. The base-16 decode, repacking nibbles into bytes, comes after the Vigenere reversal, not before it and not instead of it.

   Tried: Run exhaustive brute force over all 16^9 keys in a Python loop, iterating key_int from 0 to 16^9.

   16^9 is about 68 billion candidates. A pure Python loop processes roughly 1-5 million keys per second, meaning full exhaustion would take days. The correct approach is column-by-column analysis: test all 16 Caesar shifts independently on each of the 9 columns and discard shifts that produce non-ASCII output, reducing the combined search space from billions to at most a few thousand survivors.

   Learn more

   The b16 encoding into the abcdefghijklmnop alphabet means the Vigenere cipher operates over a 16-character alphabet (not 26). With the correct key length of 9, the full keyspace 16^9 ≈ 68B is too large for pure Python brute force. In practice, cryptanalysts use column-by-column analysis: for each of the 9 columns, test all 16 Caesar shifts independently and keep only the shifts where b16_decode produces valid ASCII output. This reduces the search to at most 16 x 9 = 144 individual tests, then itertools.permutations on the surviving candidates to find the key that fully validates. Total attempts are in the thousands, not billions.

   Defensive assertion. The base conversion in the loop above can silently truncate when n hits zero before the inner loop completes (leading-letter a = 0 would make key shorter than expected). The assert len(key) == key_len catches that off-by-one before it reaches the cipher.

Flag

Static flag: the ciphertext is baked into the challenge files rather than generated per instance, so the same plaintext comes back every time.