Description
Vigenere
k: ????????????
p: SECCON{???????????????????????????????????}
c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQk=key, p=plain, c=cipher, md5(p)=f528a6ab914c1ecf856a1d93103948fe
|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
-+—————————-
A|ABCDEFGHIJKLMNOPQRSTUVWXYZ{}
B|BCDEFGHIJKLMNOPQRSTUVWXYZ{}A
C|CDEFGHIJKLMNOPQRSTUVWXYZ{}AB
D|DEFGHIJKLMNOPQRSTUVWXYZ{}ABC
E|EFGHIJKLMNOPQRSTUVWXYZ{}ABCD
F|FGHIJKLMNOPQRSTUVWXYZ{}ABCDE
G|GHIJKLMNOPQRSTUVWXYZ{}ABCDEF
H|HIJKLMNOPQRSTUVWXYZ{}ABCDEFG
I|IJKLMNOPQRSTUVWXYZ{}ABCDEFGH
J|JKLMNOPQRSTUVWXYZ{}ABCDEFGHI
K|KLMNOPQRSTUVWXYZ{}ABCDEFGHIJ
L|LMNOPQRSTUVWXYZ{}ABCDEFGHIJK
M|MNOPQRSTUVWXYZ{}ABCDEFGHIJKL
N|NOPQRSTUVWXYZ{}ABCDEFGHIJKLM
O|OPQRSTUVWXYZ{}ABCDEFGHIJKLMN
P|PQRSTUVWXYZ{}ABCDEFGHIJKLMNO
Q|QRSTUVWXYZ{}ABCDEFGHIJKLMNOP
R|RSTUVWXYZ{}ABCDEFGHIJKLMNOPQ
S|STUVWXYZ{}ABCDEFGHIJKLMNOPQR
T|TUVWXYZ{}ABCDEFGHIJKLMNOPQRS
U|UVWXYZ{}ABCDEFGHIJKLMNOPQRST
V|VWXYZ{}ABCDEFGHIJKLMNOPQRSTU
W|WXYZ{}ABCDEFGHIJKLMNOPQRSTUV
X|XYZ{}ABCDEFGHIJKLMNOPQRSTUVW
Y|YZ{}ABCDEFGHIJKLMNOPQRSTUVWX
Z|Z{}ABCDEFGHIJKLMNOPQRSTUVWXY
{|{}ABCDEFGHIJKLMNOPQRSTUVWXYZ
}|}ABCDEFGHIJKLMNOPQRSTUVWXYZ{Vigenere cipher
https://en.wikipedia.org/wiki/Vigen%C3%A8re_cipher
Solution
As the title of the challenge suggests, we are dealing with a simple Vigenere Cipher here. In Vigenere, each character of the plaintext is shifted using a key. Using a lookup table such as the one given in the description, each letter of the plaintext will be ciphered using the according character of the key. Deciphering goes the same.
To make this more concrete, let’s look at a simple example. To encrypt plaintext ‘ABC‘ with key ‘KEY‘, we look up (row K, column A) in the lookup table. The first character of the according ciphertext is thus ‘K‘. Then, the second character of the ciphertext is located at (row E, column E) (= ‘F‘), and the last one is (row Y, column C) (= ‘{‘). The maths behind this is that each plaintext letter L is shifted N places in the alphabet, where N is the index the according character in the key. The first plaintext letter is encrypted with the first letter of the key, the second plaintext letter is encrypted with the second letter of the key, etc. As the key is mostly shorter then the plaintext, the key is often looped through many times.
Now that we know the basics of the Vigenère Cipher, let’s see what we can do. We have the first 7 characters of the plaintext (‘SECCON{‘). Let’s have a look at the according ciphertext. The first 7 characters of the ciphertext are ‘LMIG}RP‘. In other words, encrypting the first plaintext letter (‘S‘) with another character resulted in the ciphertext letter ‘L‘. The same way, ‘E’ * <some character> = ‘M’, ‘C‘ * <some character> = ‘I’, etc.
This means we can get the first character of the key by looking up row S. Encrypting that one with <some character> results in an L. As we can see in the lookup table, this is the case in (row S, column V). Therefore, the first letter of the key is V. The second letter of the key is on row E and must result in ciphertext letter M. This happens at (row S, column I). We know already have the first two letters of the key, namely ‘VI‘.
After repeating these steps, it turns out the first part of the key is ‘VIGENER‘. I assumed the next character would be an ‘E‘, which only left 4 characters to guess. As the alphabet the key can be composed of is custom and has 28 characters, we can calculate the number of possible last four letters of the key as follows:
|
1 |
Number of possible keys = 28 * 28 * 28 * 28 = 28^4 = 614656 |
So, there are 614,565 possibilities for the last part of the key. That is easy to brute force, but looking through all the outcomes manually afterwards is too much work. What we do know, however, is the MD5 hash of the correct plaintext. I figured the way to go now was to do a random guess for the remaining part of the key, say ‘VIGENEREAAAA‘, get the resulting plaintext, calculate the MD5 hash of that plaintext, and compare it with the one we know is correct. If the values don’t match, the key is wrong. We then go on with the next guess, ‘VIGENEREAAAB‘, and do the same. Using this approach, we know for sure we’ll find the correct key after at most 614,656 tries.
I wrote the following Python script to execute the steps explained above (+ some extra code for simply encrypting and decrypting stuff using Vigenere):
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 |
import itertools import hashlib def encrypt(key,plaintext,alphabet): ciphertext = "" # Encrypt each character of the plaintext with the according character of the key for i in range(0,len(plaintext)): # Find the current plaintext character character = plaintext[i] # Find the according key character keychar = key[i%len(key)] # Find the alphabet indexes of the plaintext and key characters shift = alphabet.index(character) key_index = alphabet.index(keychar) # Apply the shift ciphertext += alphabet[(shift+key_index)%len(alphabet)] return ciphertext def decrypt(ciphertext,key,alphabet): plaintext = "" # Decript each character of the ciphertext with the according character of the key for i in range(0,len(ciphertext)): # Find the current ciphertext character character = ciphertext[i] # Find the according key character keychar = key[i%len(key)] # Find the alphabet indexes of the ciphertext and key characters shift = alphabet.index(character) key_index = alphabet.index(keychar) # Apply the shift plaintext += alphabet[(shift-key_index)%len(alphabet)] return plaintext def brute_force(ciphertext,alphabet): # Start with the known part of the key key = "VIGENERE" plaintext = "" # Generate a list of all possible 4-character combinations from our (custom) alphabet possible_keys = [''.join(i) for i in itertools.product(alphabet, repeat = 4)] print "Trying {} keys".format(len(possible_keys)) possible_solutions = [] # Try each possible 4-character combination for possible_key in possible_keys: # Append the combination to the known part of the key (e.g. 'VIGENERE' + 'AAAA') temp_key = key+possible_key # Obtain the plaintext using the current combination as the key plaintext = decrypt(ciphertext,temp_key,alphabet) # If the plaintext does not end in '}', we are not interested if plaintext[-1] == "}": # Store the result (the (key,plaintext) combination) possible_solutions.append((temp_key,plaintext)) print "Found {} possible solutions...".format(len(possible_solutions)) # For each obtained plaintext: for solution in possible_solutions: # ...calculate the MD5 hash and compare it to the known correct hash if hashlib.md5(solution[1]).hexdigest() == "f528a6ab914c1ecf856a1d93103948fe": # If they match, we found the correct key, resulting in the correct plaintext print "FOUND!!!! --> {}".format(solution) # plaintext = "SECCON{???????????????????????????????????}" # key = "VIGENERE????" ciphertext = "LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ" alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ{}" brute_force(ciphertext,alphabet) |
Let’s execute the cracker!
|
1 2 3 4 |
root@kali:~/Downloads/ctf/seccon-2016/vigenere# python cracker.py Trying 614656 keys Found 614656 possible solutions... FOUND!!!! --> ('VIGENERECODE', 'SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}') |
That worked just great! As you can see in the output, the correct key was VIGENERECODE, resulting in the plaintext SECCON{ABABABCDEDEFGHIJJKLMNOPQRSTTUVWXYYZ}, which indeed turned out to be the correct flag.
