PlaidCTF 2013 – Crypto 250 Compression Writeup
On the recently concluded PlaidCTF (which was an awesome competition) by PPP there was a problem. Here it goes:
Question: We managed to get the source code for an encryption service running at 54.234.224.216:4433.
I have listed the python source provided below:
#!/usr/bin/python
import os
import struct
import SocketServer
import zlib
from Crypto.Cipher import AES
from Crypto.Util import Counter
# Not the real keys!
ENCRYPT_KEY = '0000000000000000000000000000000000000000000000000000000000000000'.decode('hex')
# Determine this key.
# Character set: lowercase letters and underscore
PROBLEM_KEY = 'XXXXXXXXXXXXXXXXXXXX'
def encrypt(data, ctr):
aes = AES.new(ENCRYPT_KEY, AES.MODE_CTR, counter=ctr)
return aes.encrypt(zlib.compress(data))
class ProblemHandler(SocketServer.StreamRequestHandler):
def handle(self):
nonce = os.urandom(8)
self.wfile.write(nonce)
ctr = Counter.new(64, prefix=nonce)
while True:
data = self.rfile.read(4)
if not data:
break
try:
length = struct.unpack('I', data)[0]
if length > (1<<20):
break
data = self.rfile.read(length)
data += PROBLEM_KEY
ciphertext = encrypt(data, ctr)
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()
The key on this challenge is to see that the stream encryption is being done on the compressed input. In the source provided, if the user input is similar to the secret value in the PROBLEM_DATA variable then the zlib.compress() function would show a reduced length ciphertext. This is somewhat (and I use the term loosely) similar to the CRIME vulnerability. The AES Counter mode RFC has the implementation details of the cipher. So I wrote the following script.
import socket
import sys
from itertools import *
import struct
def display(msg,numbytes):
#print >>sys.stderr, 'received "%s"' % msg
#print >>sys.stderr, 'bytes "%d"' % numbytes
print >>sys.stderr, 'bytes %d ' % numbytes + msg.encode('hex')
# Create a TCP/IP socket
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
# Connect the socket to the port where the server is listening
server_address = ('54.234.224.216', 4433)
print >>sys.stderr, 'connecting to %s port %s' % server_address
sock.connect(server_address)
#mesage len = 20 lowercase and underscore letters
try:
amount_received = 0
nonce = sock.recv(8)
amount_received += len(nonce)
# Send data
#strng = 'crime_some'
#minciphlen = 1000
#strng = 'crimes_pays'
#strng = 'so_'
#strng = 'crime_some_times_pays'
#strng = 'somet_'
strng = 'cr'
minchar = ''
ciphlen = 1000
sampleset = 'hijklmnopqrstuvwxyz_abdefgc'
#while True:
strng = strng + minchar
minciphlen = ciphlen
minchar = ''
for s in map("".join,permutations(sampleset,1)):
#message = nonce + (strng + s)*10 #'\x00'*11 + s
message = strng + s
datalen = struct.pack('I',len(message)) # datalen = '\xe4\x00\x00\x00'
sock.sendall(datalen)
#print >>sys.stderr, 'sending '+ message
sock.sendall(message)
#print >>sys.stderr, 'message sent'
amount_received = 0
# Look for the response
data = sock.recv(4)
amount_received += len(data)
ciphlen = struct.unpack('I', data)[0]
#print >>sys.stderr, message + ' '
amount_received = 0
if ciphlen <= minciphlen:
minciphlen = ciphlen
minchar = s
print str(ciphlen) + ' It is ' + strng + minchar
data = sock.recv(ciphlen)
#display(data,ciphlen)
finally:
print >>sys.stderr, 'closing socket'
sock.close()
When you connect to the service it provides you the nonce, so I prepended the nonce to the plaintext. The above script shows the plaintext and the length of the cipher text. To start off with this, you start with a string of length 1, and see which is the smallest length response, that gives your first character. Then in the
strng
variable above, you add that character and run again, and the lowest length ciphertext tells you the next character and so on. I noticed that sometimes the output had a few characters with the lowest length. So I tried each of them and ended up with the following flag:
crime_sometimes_pays