PicoCTF Vigenere Writeup — Recover a Vigenère Key with Crib Dragging

The Vigenère cipher shifts each letter of the plaintext according to a corresponding letter from a key that repeats cyclically. Since we know the plaintext starts with picoCTF{, we can "subtract" this known text from the ciphertext to directly recover the first letters of the key, then deduce the rest by repetition.

• Platform: picoGym
• Category: Crypto
• Points: 200 pts
• Difficulty: Intermediate
• Tools: python3crib dragging

Challenge description

The challenge provides a text file containing an encrypted message, along with a prompt that explicitly mentions the Vigenère cipher:

"This flag was made with a repeating key XOR... wait, no. This is Vigenère. Can you recover the key and the flag?"

$ cat ciphertext.txt
wgcpbtqz{***************}

Nothing more. No key provided, no additional hint — just the ciphertext. But we already know something very valuable: every picoCTF flag starts with picoCTF{.

Step 1 — Quick refresher on the Vigenère cipher

The Vigenère cipher is a generalization of the Caesar cipher: instead of applying a fixed shift to every letter, a different shift is applied at each position, determined by a key repeated cyclically across the whole length of the message.

For each plaintext letter at position i, mapping A=0, B=1, ... Z=25:

cipher[i] = (plain[i] + key[i mod len(key)]) mod 26

For example, if the key is KEY and the plaintext starts with ATTACK, the first letter A (0) is shifted by K (10), giving K; the second letter T (19) is shifted by E (4), giving X; and so on, with the key repeating: K-E-Y-K-E-Y.

Unlike the Caesar cipher, there aren't just 26 possible shifts to brute-force — with Vigenère, the number of possible keys explodes as the key length grows, so naive brute force is no longer enough. A different approach is needed.

Step 2 — Crib dragging on the known prefix

This is where crib dragging comes in: since we know (or can guess with very high confidence) part of the plaintext — here the standard prefix picoCTF{ — we can invert the encryption equation to directly compute the corresponding key letters:

key[i] = (cipher[i] - plain[i]) mod 26

We apply this formula to the first 8 letters of the ciphertext, comparing them against the 8 letters of picoCTF{:

# cipher : w  g  c  p  b  t  q  z
# plain  : p  i  c  o  C  T  F  {

# Note: { is not a letter, it can't be shifted with A-Z.
# In practice, picoCTF Vigenère challenges only encrypt
# A-Z letters and leave other characters (digits, {, }, _) unchanged.
# So we only work on "picoCTF" (7 letters).

from string import ascii_lowercase as alpha

ciphertext = "wgcpbtqz"
known_plain = "picoCTF"   # known prefix, ignoring case for the computation

key_fragment = ""
for c, p in zip(ciphertext.lower(), known_plain.lower()):
    shift = (alpha.index(c) - alpha.index(p)) % 26
    key_fragment += alpha[shift]

print(key_fragment)
# -> prints the first letters of the key, e.g. "helloh"

This little script directly reveals the start of the key, letter by letter, without having to guess anything — it's pure algebra on alphabetic positions.

Step 3 — Finding the key's period

Once we've recovered the first letters of the key using the known prefix, we still need to determine whether they already form a complete repeating pattern, or whether the key is longer than what we've been able to deduce so far.

Looking at the output of the previous script, we often notice that after a small number of characters (5 to 8 letters typically on this challenge), the pattern starts repeating — or, if the resulting string looks like a readable English word (like hello), that's a very good sign the full key has been found.

key_fragment = "hellohello..."
# the "hello" pattern (5 letters) repeats -> the key is "hello"

To confirm, we can also decrypt the entire message with this key candidate and check that the result produces readable text throughout its full length, not just on the prefix.

Step 4 — Decrypting the full message

Once the complete key is identified, we apply the decryption formula to the whole message:

plain[i] = (cipher[i] - key[i mod len(key)]) mod 26

from string import ascii_lowercase as alpha

def vigenere_decrypt(ciphertext, key):
    plaintext = ""
    ki = 0
    for c in ciphertext:
        if c.isalpha():
            base = alpha if c.islower() else alpha.upper()
            shift = alpha.index(key[ki % len(key)].lower())
            idx = (base.index(c) - shift) % 26
            plaintext += base[idx]
            ki += 1
        else:
            # digits, braces, underscore: left unchanged, don't consume a key letter
            plaintext += c
    return plaintext

ciphertext = "wgcpbtqz{***************}"  # flag body masked here
key = "hello"

print(vigenere_decrypt(ciphertext, key))
# -> picoCTF{***************} (digits/underscores/braces
#    pass through Vigenère unchanged, so the masked body
#    stays identical before and after decryption)

The script walks through the message character by character, applies the inverse shift only to letters, and leaves non-alphabetic characters (digits, {, }, _) unchanged without consuming a key letter — exactly as the original picoCTF encryption does.

🚩 picoCTF{ flag intentionally hidden }

The flag is deliberately hidden — follow the method, you've earned it. 💪

Key takeaways

This challenge illustrates a fundamental structural weakness of repeating-key ciphers:

• Just like with repeating-key XOR, knowing even a small fragment of the plaintext (here the standard picoCTF flag prefix) is enough to completely break a repeating-key cipher
• Crib dragging turns a cryptanalysis problem into simple modular algebra as soon as a fragment of plaintext is known or guessable
• This is precisely why modern ciphers absolutely avoid key reuse on texts whose beginning is predictable

Originally published on CTFdojo — join the CTFdojo Discord to discuss writeups and get notified about new ones.