Saturday, January 18, 2014

Hack You CTF 2014 - Crypto 400 - CRYPTONET - [Team SegFault]

Challenge description says about use of strange protocol using RSA cryptosystem. We also have access to the client source code and a pcap file. Reading the code we could see that, client receives n and e value from remote system. This value is used to encrypt the message before sending it. The protocol has following format
[2 bytes specifying the size zlib compressed e value][zlib compressed e value] [2 bytes specifying the size zlib compressed n value][zlib compressed e value]
[2 bytes specifying the size zlib compressed m^e mod n] [zlib compressed m^e mod n]
Analyzing the pcap file we could see that client has communicated with some 19 remote machines. First we must extract the values of e and n for all the communication. Initially I checked if those n values are having some common prime, but all the gcd checks ended up as relatively prime. e value was small, 17. Further reading on use of low public exponent took me to Hastad's Broadcast Attack. Code to solve the challenge using Hastad's Broadcast Attack is below:
#!/usr/bin/env python

from scapy.all import *
from sage.all import *
import zlib
import struct

PA = 24L
packets = rdpcap('packets.pcap')
client = ''
size = 2 # size of e and n is packed into 2 bytes
list_n = []
list_m = []

for packet in packets:
    if packet[TCP].flags == PA:
       if packet.dst == client:
           src = packet[IP].src
           raw_data = packet[TCP].load

           size_e = struct.unpack('!H', raw_data[:size])[0] 
           e = int(zlib.decompress(raw_data[size: size + size_e]))

           size_n = struct.unpack('!H', raw_data[size + size_e: 2 * size + size_e])[0]
           n = int(zlib.decompress(raw_data[2 * size + size_e: ]))

        if packet[IP].src == client:
            raw_data = packet[TCP].load
            size_m = struct.unpack('!H', raw_data[:size])[0]
            m = int(zlib.decompress(raw_data[size: size + size_m]))

e_17 = crt(list_m, list_n)
factors = prime_factors(e_17)
enc_message = 1
for num in factors:
    enc_message *= num

print hex(enc_message).decode('hex')
# 'Secret message! CTF{336b2196a2932c399c0340bc41cd362d}\n'
Flag for the challenge is CTF{336b2196a2932c399c0340bc41cd362d}

No comments :

Post a Comment