Block Cipher Encryption Vulnerability

I was asked about this homework recently. Although I have been graduated for almost a year but I still found this homework was interesting and couldn’t stop myself trying solve it.

The basic scenario is that we have a server and a client, both of which are given sample code below. The server holds a key, and a secret. Only the server knows the key, and the server and authenticated user (admin) shares the secret.

When a client requests to make a profile, it will submit his email to the server, and the server will return the following string,
AES.ECB(“email=INPUT&uid=UID&role=user”, KEY)

where INPUT is the user input, UID is a random number between 1 and 100, KEY is the key that only the server knows. Assume all the clients that request to make profile are ‘user’ but not ‘admin’.

When a client requests to get the secret, it will submit the encrypted string given by the server, and the server will use its key to decrypt the string, and examine if it is an authenticated user, i.e. ‘admin’, by serarching ‘role=admin’ in the decrypted string. If the client is an admin user then the server will tell it the secret.

Additionally, for the obvious security reasons, the server will not response the user inputs which contain ‘&’ or ‘=’.

Now the homework question is that can you construct an encrypted string which contains ‘role=admin’ without knowing the key.

Sample server code:

'''
A server intentionally showcasing an implementation vulnerability involving AES ECB Mode.

Ciphertexts are sent back and forth as ASCII Encoded Hex Strings. 0xFF will be sent as 
"FF" (2 Bytes), not as "\xff" (1 Byte).

You can use python's string.encode('hex') and string.decode('hex') to quickly convert between
raw data and string representation if you need/want to.

Email biernp@rpi.edu with questions/comments :)

-Patrick Biernat
'''

from twisted.internet import reactor, protocol
from Crypto.Cipher import AES
import os
import random

PORT = 9000

KEYSIZE = 0 #Different on Server.
KEY = os.urandom(KEYSIZE)
SECRET = "" #The server gives you this when you complete the challenge.


def pad(instr, length):
        if(length == None):
                print "Supply a length to pad to"
        elif(len(instr) % length == 0):
                print "No Padding Needed"
                return instr
        else:
                return instr + '\x04' * (length - (len(instr) % length ))

def encrypt_block(key, plaintext):
        encobj = AES.new(key, AES.MODE_ECB)
        return encobj.encrypt(plaintext).encode('hex')

def decrypt_block(key, ctxt):
        decobj = AES.new(key, AES.MODE_ECB)
        return decobj.decrypt(ctxt).encode('hex')

def mkprofile(email):
	if( ("&" in email) or ("=" in email)):
		return -1
	return encrypt_block(KEY,pad("email="+email+"&uid="+str(random.randint(1,100))+"&role=user",KEYSIZE))

def parse_profile(data):
	
	ptxt = decrypt_block(KEY,data).decode('hex')
	ptxt = ptxt.replace("\x04","")
	ptxt = ptxt.split("&")
	if "role=admin" in ptxt:
		return 1
	return 0


class MyServer(protocol.Protocol):
    def dataReceived(self,data):
	if(len(data) > 256):
		self.transport.write("Data too long.\n")
		self.transport.loseConnection()
		return
#Make Profile From "Email"
	if(data.startswith("mkprof:")):
		data = data[7:]
		resp = mkprofile(data)
		if (resp == -1):
			self.transport.write("No Cheating!\n")
		else:
			self.transport.write(resp)

#Decrypt Ciphertext and "parse" into Profile
	elif(data.startswith("parse:")):
		self.transport.write("Parsing Profile...")
		data = data[6:].decode('hex')
		if (len(data) % KEYSIZE != 0):
			self.transport.write("Invalid Ciphertext <length>\n")
			self.transport.loseConnection()
			return
		
		if(parse_profile(data) == 1):
			self.transport.write("Congratulations!\nThe Secret is: ")
			self.transport.write(SECRET)
			self.transport.loseConnection()
		
		else:
			self.transport.write("You are a normal user.\n")
			self.transport.loseConnection()
	
	else:
		self.transport.write("Syntax Error")
		self.transport.loseConnection()


class MyServerFactory(protocol.Factory):
    protocol = MyServer



factory = MyServerFactory()
reactor.listenTCP(PORT, factory)
reactor.run()

Sample client code:

'''
	Basic example of connecting to the service.
'''

import socket

clientsocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
clientsocket.connect(('blackbox.pwnz.org',9000))

clientsocket.send("mkprof:AAAAAAA")
print clientsocket.recv(128)

clientsocket.close()

* To make the samples actually work, you need to change KEYSIZE in the sample server code to an appropriate number.

Answer
First of all for block cipher encryption, we need to know the block size, which is not so hard if we can just submit different length of inputs to the server and check the length of returned strings and the length of their common prefix.

Let’s assume the block length is 16 bytes. (Actually it is, for the server in the sample server code)

Our goal is to construct a string which contains ‘role=admin’, while the server refuses to encrypt any input which contains ‘=’. But the server does encrypt ‘***********role=’ or ‘admin***********’, as long as we can make our input appropriate:

email=**********admin**************&uid=xx&role=user************ 
|----block1----||----block2----||----block3----||----block4----|
0123456789abcdef0123456789abcdef0123456789abcdef0123456789abcdef

where ‘*’ is ‘\x04’, which the server uses as the invisible characters, and ‘xx’ and the random uid which server generates, and we assume uid is 2 characters.

If we can make our input in this way, based on the strategy of block cipher encryption, we can know the encrpyted string for each block. In this case, we know ‘admin***********’ and ‘***&uid=00&role=’

Then if we parse block3 and block2 back to the server, the server sees

***&uid=xx&role=admin**************

and translates it to

&uid=xx&role=admin

and we becomes the admin, yay!

so what we need to do is to make a profile for the user mail ‘***admin***’, where the length of ‘*’ before ‘admin’ is ( blocklength – 5 ) and the length of ‘*’ after ‘admin’ is ( blocklength*2 – 18 ).

And here’s how the final code look like:

import socket

SERVER_HOSTNAME = 'blackbox.pwnz.org'
SERVER_PORT = 9000

def mkprof(s):
    clientsocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    clientsocket.connect((SERVER_HOSTNAME, SERVER_PORT))
    s=str(s)
    clientsocket.send("mkprof:"+s)
    ret = clientsocket.recv(1024)
    clientsocket.close()
    return str(ret)

def parse(s):
    clientsocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    clientsocket.connect((SERVER_HOSTNAME, SERVER_PORT))
    s=str(s)
    clientsocket.send("parse:"+s)
    ret = clientsocket.recv(1024)
    clientsocket.close()
    return str(ret)


input_length = 0
last_ret = ''
while True:
    input_length += 1
    s = 'Z' * input_length
    this_ret = mkprof(s)
    #find common prefix of last_ret and this_ret
    prefix_length = 0
    while prefix_length<len(last_ret) and last_ret[prefix_length] == this_ret[prefix_length]:
        prefix_length += 1

    last_ret = this_ret
    if prefix_length>0 and prefix_length%16 == 0:
        break

block_length = prefix_length/2

for retry in xrange(10):
    #retry at most 10 times
    s = '\x04'*(block_length-6)+'admin'+'\x04'*(block_length*2-18)
    ret = mkprof(s)
    block3 = ret[block_length*4:block_length*6]
    block2 = ret[block_length*2:block_length*4]
    send_data = block3+block2
    ret =  parse(send_data)
    if 'Congratulations!' in ret:
        print send_data
        print ret
        exit()

Run it, and the result would be

5144337cc9aa29c811bd39dcfefd8b733630bcd83daf5d41cf45a7e0375c99f4
Parsing Profile...Congratulations!
The Secret is: Y0uR_Alg0ri7Hm_iZ_g00d. Y0ur_impl3m3ntation_iZ_b4d

Well, this is quite an interesting game. Honestly if I weren’t told this is a homework I wouldn’t have known this server is vulnerable. This world is just so horrible.

Leave a Reply

Your email address will not be published.

82 − = 76