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 : https://github.com/HoLyVieR/CS-Games-2014-CryptoChallenge.

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.

CTF Olympic - Emdee - An alternate approach

The "Emdee" challenge featured at the Olympic CTF required you to find a secret and salt that was hashed together. To be able to achieve it, you had access to a web API that was hashing for you a message of your choice with the salt and a timestamp. The normal approach to do it was to find the salt by using backspace characters for the message. This would reduce the length of the salt, allowed you to bruteforce smaller part of the salt and progressively get it. However, what I will present is how to get the secret without knowing the salt. One of the reason I find it interesting to talk about it is because it's a good introduction to hash extensions and most people seemed surprise that it was even possible.

First, let's look at how the message are hashed and how MD5 works at a high-level.

MD5

MD5 uses a Merkle-Damgard construction which can be described with the following image that's taken directly from Wikipedia.

In the case of MD5, the IV is static, the function "f" can found in any implementation of MD5 and the padding is constructed by adding 0x80 + (0x00)*(N) + (length of what is hashed). Here N is adjusted so that the length of the last block is exactly 64 bytes long.

The message

The message you have to find is given by MD5(salt+ secret).
The output of the API is given by MD5(salt+ input + timestamp) and the timestamp used is returned to you.

Doing the hash extension

So with that in mind, we now know that the message was evaluated this way:
hashed message = f(PADDING(salt + secret), IV)

And we also know that the output of the API is the following:
output = f(PADDING(salt + input + timestamp), IV)

For the message, it is likely that the length is below 64 bytes, so we will assume it always fit on a single block. For the output however, if the content gets bigger than 64 bytes it will then be hashed the following way:

txt = PADDING(salt + input + timestamp)
output = f(substring(txt, 64, 128), f(substring(txt, 0, 64), IV))

Where it starts to get interesting is that we can make the first 64 bytes equals to PADDING(salt + secret) and this will happen:

txt = PADDING(salt + input + timestamp)
output = f(substring(txt, 64, 128), f(PADDING(SALT + secret), IV))
output = f(timestamp + padding, hashed message)

And this means that we can verify if the secret we have sent to the server is correct if the following holds:

f(timestamp given by the API + padding, hashed message) = output of the API

To have the hash extension work properly, you need to know the length of the salt otherwise the padding will be incorrect. Since it's unknown for the problem we will have to test for both the secret and the length of salt.

Conclusion

When all wrapped up together it gives the following :
https://gist.github.com/HoLyVieR/8920691

This allowed you to find the length of the salt and the secret message. In the case of the challenge the length was 40 and the secret was "cow".