Wednesday, March 17, 2010

CodeGate 2010 CTF - Challenge 8: Bit-flipping attack on CBC mode

This is a web-based cryptography challenge. In this challenge, we were provided a URL and a hint "the first part is just an IV".
The URL is: http://ctf1.codegate.org/99b5f49189e5a688492f13b418474e7e/web4.php.

Analysis
Go to the challenge URL. It will ask you the username for the first time. After we enter a value, for example 'namnx', it will return only a single message "Hello, namnx!". Examine the HTTP payload, we will see the cookie returned:
web4_auth=1vf2EJ15hKzkIxqB27w0AA==|5X5A0e3r48gXhUXZHEKBa5dpC+XfdVv4oamlriyi5yM=
The cookie includes 2 parts delimited by character '|'. After base64 decode the first part of the cookie, we have a 16-byte value. According to the hint, this is the IV of the cipher. And because it has 16-byte length, I guess that this challenge used AES cipher, and the block size is 16 bytes. Moreover, the cipher has an IV, so it can't be in ECB mode. I guessed it in CBC mode. The last part is the base64 of a 32-byte value. This is a cipher text. We will exploit this value later.

Browse the URL again, we will receive another message: "Welcome back, namnx! Your role is: user. You need admin role." Take a look into this message, we can guess the operation of this app: it will receive the cookie from the client, decrypt it to get the user and role information and return the message to the client based on the user and role information. So, in order to get further information, we must have the admin role. This is our goal in this challenge.

Exploit
I wrote some Python to work on this challenge easier:
import urllib, urllib2
import base64, re

url = 'http://ctf1.codegate.org/99b5f49189e5a688492f13b418474e7e/web4.php'
user_agent = 'Mozilla/4.0 (compatible; MSIE 5.5; Windows NT)'

def get_cookie(user):
    headers = { 'User-Agent' : user_agent}
    values = {'username' : user, 'submit' : "Submit"}
    data = urllib.urlencode(values)
    request = urllib2.Request(url, data, headers)
    response = urllib2.urlopen(request)
    cookie = response.info().get('Set-Cookie')
    groups = re.match("web4_auth=(.+)\|(.+);.+", cookie).groups()
    iv = base64.b64decode(groups[0])
    cipher = base64.b64decode(groups[1])
    return iv, cipher

def get_message(iv, cipher):
    cookie = base64.b64encode(iv) + '|' + base64.b64encode(cipher)
    cookie = urllib.quote(cookie)
    cookie = 'web4_auth=' + cookie
    headers = { 'User-Agent' : user_agent, 'Cookie': cookie}
    request = urllib2.Request(url, None, headers)
    response = urllib2.urlopen(request)
    data = response.read()
    print repr(data)
    groups = re.match(".+, (.*)! .+: (.*)\. You.+", data).groups()
    return groups[0], groups[1]
The first function, get_cookie will submit a value as a username in the first visit to the page, get the returned cookie, and then parse it to get the IV and cipher. The second function, get_message, do the task like when you visit the page in later times, it parses the response message to get the returned username and role.

Let do some test cases:
>>> iv, cipher = get_cookie('123456789012')
>>> len(cipher)
32
>>> iv, cipher = get_cookie('1234567890123')
>>> len(cipher)
48
When you input the user with a 12-byte value, the returned cipher will have 32 bytes (2 blocks). And when you enter a 13-byte value, the cipher will have 48 bytes (3 blocks). This means that beside the username value, the plain text of the cipher will be added more 20 bytes.

Try altering the cipher text to see how it is decrypted:
>>> iv, cipher = get_cookie('1234567890')
>>> cipher1 = cipher[:-1] + '\00'
>>> username, role = get_message(iv, cipher1)
'Welcome back, 1234567\xa2\xc2\xca\xfei\xdb\xee_c\xa7\xd7\x0c\xa9j\xe0\xbb! Your role is: . You need admin role.'


When we altered the last block of the cipher, just first 7 characters of the username is decrypted correctly. So the format of the plain text maybe like this: [9 bytes] + username + [11 bytes].

Now we'll try to determine the first 9 bytes of the plain text:
>>> iv, cipher = get_cookie('1234567890123456')
>>> cipher1 = cipher[:32] + iv + cipher[:16]
>>> username, role = get_message(iv, cipher1)
'Welcome back, 1234567890123456! Your role is: E\x9bpY?\xfbW6\x84{\x8fn\x1e\x80\x10\x1busername=1234567. You need admin role.'
As you can see, the last block of the decrypted role is the first block of the plain text. So, the format of the plain text may be: 'username=' + username + [11 bytes].

To here, we can guess that the format of the plain text can be something like:
'username=' + username + [delimiter] + [param] + '=' + [value]
The last 11 bytes of the plain text can be determined by the code below:
>>> iv, cipher = get_cookie('\x00')
>>> username, role = get_message(iv, cipher)
'Welcome back, \x00##role=user\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00\x00! Your role is: . You need admin role.'
You can see the last 11 bytes of the plain text in the returned message. So, at this time, we can conclude format of the plain text is:
'username=' + username + '##role=' + role
Now, the last thing we have to do is altering the role value to 'admin'. Because we've already known the format of the plain text, we can choose to input the username close to the target plain text and try to alter the cipher text in the way that the decrypted value is what we want.

Let remind the operation of CBC mode in cryptographic ciphers. In encryption process:
y[1] = C(IV xor x[1])
y[n] = C(y[n-1] xor x[n])
and in the decryption:
x[1] = D(y[1]) xor IV
x[n] = D(y[n]) xor y[n-1]
Notice that if we flip one bit in the (n-1)th block of cipher text, the respective bit in the n-th block of plain text will be also flipped. So, we will you this fact to exploit the challenge:
>>> iv, cipher = get_cookie('012345678901234567890123#role=admin')
>>> s = cipher[:16] + chr(ord(cipher[16]) ^ 0x10) + cipher[17:]
>>> username, role = get_message(iv, s)
'Welcome back, 0123456L\xaa\x17m\xe9\x91\xdc\xe2`#z)\xd8m\xd8\x18! Your role is: admin. You need admin role. Congratulations! Here is your flag: the_magic_words_are_squeamish_ossifrage_^-^!!!!!'
Successful! Such an interesting challenge, isn't it?


References
- Block cipher modes of operation: http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation
- Bit-flipping attack: http://en.wikipedia.org/wiki/Bit-flipping_attack

Tuesday, March 16, 2010

CodeGate 2010 CTF - Challenge 7: Weak SSL Cracking

Last weekend, I had a great hacking time with team CLGT in the CodeGate 2010 CTF Preliminary Round. It lasted 36 consecutive hours from 7:00AM March 13 to 7:00PM March 14. There were a lot of teams around the world participating in this hacking contest. And excellently, CLGT proved it as one of the best teams when got the 2nd place in this round. See final ranking.

This entry is my writeup for challenge 7. I think this is an interesting challenge from which you can learn more deeply about SSL protocol and public key cryptography. In this challenge, we were provided a tcpdump file of a SSL traffic and a hint "does the modulus look familiar?". So our goal is to analyze and decrypt this captured traffic to get the flag.

Analysis
Firstly, I used Wireshark to load this file and start to analyze it:


There are 26 packets captured. Packet #4 is a SSL Client Hello packet, but after it, packet #8 and packet #9 have FIN flag. This mean that the session was termininated. So we just ignore them.

Packet #14 is another SSL Client Hello packet. This is where the real session began. Take a look into it:

There is nothing special. It is just a normal SSL Client Hello packet. It happens when a client want to connect to a SSL service. We continue look into the packet #16, the SSL Server Hello packet:


This is the response for SSL Client Hello packet. We can see some useful information here:
- The cipher suite will be used: RSA_WITH_AES_256_CBC_SHA
- The X509 certificate of the server

In the SSL protocol, the server send its certificate to the client in the handshaking process. This certificate will be used for supporting the key exchange afterward. The certificate contains the server's public key and other data. By extracting the public key and recovering the private key from it, we can decrypt the SSL traffic.

Exploit
I wrote some Python code to exploit this challange:
from scapy.all import *
from M2Crypto import X509

def decode_serverhello(packet):
    payload = packet.load
    cert = payload[94:1141]
    cert = X509.load_cert_string(cert, 0)
    return cert

def get_pubkey(cert):
    pubkey = cert.get_pubkey().get_rsa()
    n = long(pubkey.n.encode('hex')[8:], 16)
    e = long(pubkey.e.encode('hex')[9:], 16)
    return n, e

packets = rdpcap('ssl.pcap')
cert = decode_serverhello(packets[15])
n,e = get_pubkey(cert)
Because this traffic used RSA as public key algorithm, the public key contains 2 components: n and e. We get their values from the above code:
n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
e = 65537
In RSA, n is the product of 2 big prime numbers p and q. So, in order to recover the RSA private key from the public key, we must factorize n into p and q. This is the key point of the challenge. In this situation, n is a very big number (232 decimal digits). How can we do that? In the beginning, I didn't know how to solve it. But I remembered the hint "does the modulus look familiar?". So I tried googling it :-D (actually just its last digits). And... oh my god, I was lucky! It is RSA-768. It's factorized just few months ago.
RSA-768 = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
        × 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917
So now, we have all components of the RSA keys.
n = 1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413

e = 65537

p = 33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489

q = 36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

d = 703813872109751212728960868893055483396831478279095442779477323396386489876250832944220079595968592852532432488202250497425262918616760886811596907743384527001944888359578241816763079495533278518938372814827410628647251148091159553
The last thing we have to do is generating the RSA private key in PEM format from these components. But how can we do that? As far as I know, popular cryptographic libraries like OpenSSL do not support this. So in this case, I wrote my own tool to do this task. It is based on ASN1. It is a little long to post here. But if you want to write your own one, I recommend pyasn1.

After having the private key, just import it to Wireshark to decrypt the SSL traffic:



References
- SSL/TLS: http://en.wikipedia.org/wiki/Transport_Layer_Security
- RSA: http://en.wikipedia.org/wiki/RSA