SECCON 2016 Online CTF – Vigenere (100 points)

Description

Vigenere
k: ????????????
p: SECCON{???????????????????????????????????}
c: LMIG}RPEDOEEWKJIQIWKJWMNDTSR}TFVUFWYOCBAJBQ

k=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 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:

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):

Let’s execute the cracker!

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.

 

Leave a Comment

Your email address will not be published.