CSAW CTF 2012 write-up: CryptoMat (web400)

Here is the description of the challenge:

http://128.238.66.214/
CryptoMat is a site where you can send encrypted messages to other users. Dog is a user on the site and has the key. Figure out how to get into his account and obtain it.

The first thing we had to do was finding out how the encryption algorithm works. After a few attempts, we discovered that the title wasn’t used for the encryption and that, given a plaintext $P$ and a key $k$, we have $f(f(P, k), k)[i] = P[i] \text{ for all } i=0..\min(8, \mathtt{len(P)}) - 1$

where $f$ is the function that encrypts the text $P$ using the key $k$. Furthermore, using a simple script, we found out that the length of each ciphered message is a multiple of 8.

For these reasons we thought that the algorithm works on blocks of 8 bytes and performs some XOR operations using the plaintext, the key and a third parameter: since we were able to decrypt the first block encrypting again the ciphertext with the same key, we thought that the first step uses a fixed constant for the encryption.

All these considerations led us to a CBC cipher, with the difference that the key isn’t as long as the block. Let’s assume that len(plaintext) is a multiple of 8 (if not it’s enough to add some \x00 bytes at the end); the encryption algorithm implemented by the service is the following:

The parameter $iv$ passed to the function is a list of 8 values used to crypt the first block of the plaintext: we can compute it using a sample text and the corresponding message ciphered with a known key.

Okay, at this point we knew how the algorithm works, but… what could we do? Easy, an XSS attack! We thought that the encrypted message was printed without performing any check, so our target was to find a message $M$ such that, fixed a key $k$, $f(M, k)$ was something like

To compute it was enough applying the decryption function $f^{-1}$ to $f(M, k)$ with key $k$, since $f^{-1}(f(M, k), k) = M$. Here is the Python script that we’ve used to do what we have just said: