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