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