Encryption Service

The python source (minus the actual encryption keys) to this service is given as part of the challenge:

import os
import struct
import SocketServer
from Crypto.Cipher import AES

ENCRYPT_KEY = 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx'.decode('hex')
# Character set: lowercase letters and underscore
PROBLEM_KEY = 'xxxxxxxxxxxxxxxxxxxxxxxxxxxxx'
BLOCK_SIZE = 16

def pad(data, blocksize):
    l = blocksize - (len(data) % blocksize)
    return data + chr(l) * l

def encrypt(data, iv):
    aes = AES.new(ENCRYPT_KEY, AES.MODE_CBC, iv)
    return aes.encrypt(pad(data, BLOCK_SIZE))

class ProblemHandler(SocketServer.StreamRequestHandler):
    def handle(self):
        iv = os.urandom(16)
        self.wfile.write(iv)
        while True:
            data = self.rfile.read(4)
            if not data:
                break

            try:
                length = struct.unpack('I', data)[0]
                if length > 4096:
                    break
                data = self.rfile.read(length)
                data += PROBLEM_KEY
                ciphertext = encrypt(data, iv)
                iv = ciphertext[-16:]
                self.wfile.write(struct.pack('I', len(ciphertext)))
                self.wfile.write(ciphertext)
            except:
                break

class ReusableTCPServer(SocketServer.ForkingMixIn, SocketServer.TCPServer):
    allow_reuse_address = True

if __name__ == '__main__':
    HOST = '0.0.0.0'
    PORT = 4433
    SocketServer.TCPServer.allow_reuse_address = True
    server = ReusableTCPServer((HOST, PORT), ProblemHandler)
    server.serve_forever()

So, the IV for the encryption is given before you send your input. This is true for every piece of data sent, as the IV for items after the first is simply the last 16 bytes of the previous ciphertext. The IV is XORed with your input before sending it to the encryption algorithm, so by XORing your desired input with the IV you can control what gets sent to the underlying encryption algorithm (and making the output constant for a given input).

This was abused by sending the IV itself as the data to be encrypted, which makes the algorithm encrypt a block of zeros and give a known IV as output. So now we have a constant starting state, removing the randomness, so we can start analyzing.

We want to leak the plaintext PROBLEM_KEY, which is appended to the input you provide then encrypted. If you send 15 bytes, only one byte in the first encrypted block will be from this key. So, as our IV will always be the same because of the attack above, we can generate a table of ciphertexts for each possible character in the key, then send our 15 byte string, and match the resulting ciphertext with the table we created. This gets us the first character. Now we can send 14 bytes, with a table creating using the (now known) first character of the key, and we can leak the second character, and so on for the rest of the key.

The attack script:

import os
import struct
import socket
import sys
from Crypto.Cipher import AES

ENCRYPT_KEY = '1111111111111111111111111111111111111111111111111111111111111111'.decode('hex')
# Character set: lowercase letters and underscore
PROBLEM_KEY = "this_is_the_key_we_r_looking_"
BLOCK_SIZE = 16

def pad(data, blocksize):
    l = blocksize - (len(data) % blocksize)
    return data + chr(l) * l

def encrypt(data, iv):
    aes = AES.new(ENCRYPT_KEY, AES.MODE_CBC, iv)
    return aes.encrypt(pad(data, BLOCK_SIZE))

def step(data):
	global iv
	s.send(struct.pack("<I", len(data)))
	s.send(data)
	cipherlen = struct.unpack("<I", s.recv(4))[0]
	ciphertext = s.recv(cipherlen)
	return ciphertext

def xor(a, b):
	result = ""
	for i in xrange(0, len(a)):
		result += chr(ord(a[i]) ^ ord(b[i]))
	return result

s = socket.create_connection((sys.argv[1], 4433))

iv = s.recv(16)

known_iv = step(iv)[-16:]

result = ""
for i in xrange(0, 29):
	chars = ''.join([chr(n) for n in xrange(ord('a'), ord('z') + 1)] + ['_'])

	block_end = (i + 16) & (~15)
	block_start = block_end - 16

	db = {}
	for j in chars:
		cipher = step(('A' * (block_end - (i + 1))) + result + j)
		db[cipher[block_start:block_end]] = j
		print j + ": " + cipher[block_start:block_end].encode("hex")
		step(cipher[-16:])

	ch = None
	cipher = step('A' * (block_end - (i + 1)))
	print j + ": " + cipher.encode("hex")
	step(cipher[-16:])
	if cipher[block_start:block_end] in db:
		ch = db[cipher[block_start:block_end]]

	if ch is None:
		print "Error"
		break

	print "Found next char, '%s'" % ch
	result += ch

print result

The key is:

predictable_ivs_are_dangerous