Friday, November 2, 2012

NEOISF Puzzle Solution

A few people emailed me with the solution to the puzzle I posted, but I figured I'd post the solution for those that wanted it.

In the puzzle, Van Helsing is attempting to break the crypto that Dracula is using to try and find him. Fortunately for Van Helsing, the program is free and he can download it to see if he can crack it. He ran the program and typed in "vampire_vampire_vampire" and got back "R1lUR1hKXGhHWVRHWEpcaEdZVEdYSlw=". 

Anyone who has done any type of network analysis, or looked at a raw SMTP message, should recognize the output as base64 encoded. Base64 is an algorithm that converts binary data to ASCII so it can be transferred over protocols that do not natively allow binary (e.g. SMTP). It does this by converting every 3 bytes of data to 4 bytes of ASCII. The "=" character is used as padding in case more characters are needed and is often a give-away.

Base64 can be converted using many methods, but since Van Helsing is awesome he is using Linux and uses the base64 command to do so.

$ echo -n R1lUR1hKXGhHWVRHWEpcaEdZVEdYSlw= | base64 -d -
GYTGXJ\hGYTGXJ\hGYTGXJ\

NOTE: Van Helsing really should have redirected the output to a file since the characters could have been binary.

The base64 decoding produced a string that has 2 interesting qualities.

First, the base64 decoded string is the same length as the string he entered. This means that whatever algorithm the encryption program is using may be doing a 1-for-1 character encryption. In other words, the characters in his plaintext is being encrypted one at a time.

Second, there is a pattern of "GYTGXJ\h". The pattern is 8 characters long, which just happens to be the length of "vampire_". Coincidence? Probably not. 

The type of encryption that immediately popped into Van Helsing's head that can have these properties is XOR encryption. XOR is a boolean logic function that can be applied in encryption. This is done by taking a key and XOR'ing each of its bytes against the characters in the plaintext. 

One property of XOR encryption is that if you take the plaintext and XOR it with the ciphertext, it will reveal the key! Van Helsing knew this and XOR'd his plaintext against the ciphertext he got. (He wrote a quick Python script to do so):

$ python xordecode.py GYTGXJ\hGYTGXJ\hGYTGXJ\ vampire_vampire_vampire

18971897189718971897189

Voila! XOR'ing each byte of his plaintext with the ciphertext he received returned a pattern of "1897", which must be the key!

Taking that as the key, he then base64 decoded Dracula's message and applied the key of 1897 to get:

I will be at the Ohio Information Security Summit.

Now Van Helsing knew where he would be and could destroy the fiend!

For those in the know, the key does have some significance. :)



5 comments:

Chris J said...

I know the significance of the date. My question was how did van helsing know to use vampire_vampire_vampire to start with.

I also don't quite understand the way the script took that string and then gave the 1897 string back.

Tyler said...

Chris,

Van Helsing didn't have to use vampire_vampire_vampire - he could have used any string. The point was that when he did so, the base64 decoded output from the encryption program was a pattern of the same length and repeating as well. This gave a clue that the protocol used was XOR.

As for the script, it probably would have helped if I included the source code for it, huh? :) My bad. Here it is. Excuse the coding please. (If you are going to use it, make sure you escape any backslashes or put in single quotes on linux.)

The script loops through each letter of the two strings and XORs them against each other, displaying the result. So, you get:

"v" XOR "G" = "1"
"a" XOR "Y" = "8"
"m" XOR "T" = "9"
"p" XOR "G" = "7"

and so on.

Hope this helps!

Doug Hiwiller said...

As Tyler pointed out, Van Helsing could have used any known plaintext to feed into the encryption program he knew was being used.

For example, if he started with "ABCDEFGHIJKLMNOPQRSTUVWXYZ", he would have gotten the following ciphertext: cHp6c3R+fn94cnJ7fHZ2Z2BqamNkbm5vaGI=

When you base64 decode that, you get: pzzst~~xrr{|vvg`jjcdnnohb

Not as fortuitous an output as what 'vampire_vampire_vampire' produced because we don't get as much information about the length or nature of the key with this output. But, we can see some interesting artifacts. We see repeating characters spaced out at 4 positions which, with some analysis, is indeed a clue to the fact that this is a repeating key and likely XOR. Knowing that reversing the operators in an XOR cipher, we can obtain the missing operator (XOR_cipher), we XOR our ciphertext against the plaintext to obtain the key.

Using the same approach with this example, we would obtain the same key '1897'

"A" XOR "p" = "1"
"B" XOR "z" = "8"
"C" XOR "z" = "9"
"D" XOR "s" = "7"

Tyler said...

Thanks Doug! Great response!

Eric Vanderburg said...

Fun puzzle. Thanks.