Friday, 28 March 2014

CS Games 2014 - Cryptography Challenge Solutions

Crypto #2

This challenge was  about decrypting value which where encoded using a stream cipher and reused the same key. While the encryption method provided is a custom, it was mostly to simplify the problem and require a smaller subset of value to be able to solve it fast. If you where able to find the solution, the same principale can be used for any stream cipher encryption (ex.: RC4).

The main weakness here is that the same key is reused to encrypt all the value provided. For a stream cipher encryption algorithm what this mean is that all the plaintext will be XORed with the same value (for the first block) and we have a situation called a multiple time pad.

What you can do with a 2-time pad is the following :

plaintext1 XOR key = encrypted1
plaintext2 XOR key = encrypted2

encrypted1 XOR encrypted2 = (plaintext1 XOR key) XOR (plaintext2 XOR key) = plaintext1 XOR plaintext2

Now to find the exact value of the plaintext, what we have to do is the following :

 1 - Compute all combinaison of "caracter XOR caracter" for all caracter of the charset.
 2 - Lookup for all the possible caracter that have a result for "encrypted1[0] XOR encrypted2[0]" in the previous step. This will give a subset of possible caracters for plaintext1[0].
 3 - Repeat step 2 with "encrypted1[0] XOR encryptedX[0]" for all other encrypted value.
 4 - Since the value must be in all the subset you have found, intersect them all and you will have found first caracter of encrypted1.

With this, you should be able to decrypt the first block of the password of "thatguy".

For the other block, what you had to do is instead of using all the other block, you need to use all the block for which the previous block has the same value as the previous block of the plaintext of "thatguy".

Crypto #3

This challenge used AES-ECB. ECB mode is almost always a bad idea for very good reason. One of the reason is that if 2 block have the same plaintext, their output will be the same. If you split the encrypted text in 128 bits long block, you will see that the block where the secret is has the exact same value as an other block. So the result is the value of that other block which is known.

Crypto #4

There is a lot of way to do this challenge and you can find lot's of alternative solution to it on the Internet.

For this solution, I will do it in 2 parts. The first one is finding the length of key and the second one is finding the key.

To find the length of the key, you can use the Hamming distance of the binary representation between each block. Statistically speaking, the Hamming distance will be minimal when you compare 2 blocks that have the same length as the key. The reason this usually works well is that if you have the correct length "enc2 XOR enc1 = plain1 XOR plain2" and if plain1 and plain2 have similar ASCII code, the Hamming distance will be small.

The find the key, you can do it caracter by caracter. What you have to do is simply look for the caracter that when used to decrypt the message will yield caracters that are the closer to an English letter distribution.

And with the key, you can now decrypt the message.

Crypto #5

  - 477cbed015420a1a8923c4ebb68cc646 (MD5)
 - Y3NnYW1lcw== (Base64)
 - %63%73%67%61%6d%65%73 (URL Encode)
 - ca48aca99bf3b952a56305050f86eeb422e90d3e (SHA1)
 - a50aaf14c77970a80565f6d1cc51850d (MD4)
 - *2F5FD2319AE0721EE4A400DAB101B241D8E68D6B (MySQL PASSWORD)
 - pftnzrf (ROT13 or CAESAR CIPHER)

Crypto #7

This challenge was about using the Meet-in-the-middle concept. You first had to notice that for the first block, the plaintext is always known "<message><conten" and you also had access to the encrypted value of it "d09e268648cc0684a2b34c4b87b017da" (first block of the encrypted value). To perform the meet-in-the-middle, store in an hash map the encrypted value of "<message><conten" for all the possibility of the first part of the key. After that decrypt "d09e268648cc0684a2b34c4b87b017da" with all the possibility of the second part of the key and lookup in the previous hash map if the result exists in it. If it exists, it means you have found the 2 parts of the key.

Further read

If you want to see the implementation of the solution or see the challenge again, you can find them here :

If you are interested in doing more cryptography, you can take a look at the cryptography course on Coursera or start doing the Matasano crypto challenge.