Hack.lu 2015: Creative Cheating

Write-up of Hack.lu 2015’s Creative Cheating challenge.

The first challenge I solved on Hack.lu 2015, hosted by FluxFingers, was Creative Cheating.

The challenge

Mr. Miller suspects that some of his students are cheating in an automated computer test. He captured some traffic between crypto nerds Alice and Bob. It looks mostly like garbage but maybe you can figure something out. He knows that Alice’s RSA key is (n, e) = (0x53a121a11e36d7a84dde3f5d73cf, 0x10001) (192.168.0.13) and Bob’s is (n, e) = (0x99122e61dc7bede74711185598c7, 0x10001) (192.168.0.37)

The solution

Upon inspection of the packet capture, we notice every packet from Alice (192.168.0.13) to Bob (192.168.0.37) contains a base64-encoded payload. E.g.

U0VRID0gNDsgREFUQSA9IDB4MmMyOTE1MGYxZTMxMWVmMDliYzlmMDY3MzVhY0w7IFNJRyA9IDB4MTY2NWZiMmRhNzYxYzRkZTg5ZjI3YWM4MGNiTDs=

Decoding this gives us the string

SEQ = 4; DATA = 0x2c29150f1e311ef09bc9f06735acL; SIG = 0x1665fb2da761c4de89f27ac80cbL;

So we have a sequence number, some data and a signature. Now let’s see if we can decrypt the data part.

Apparently, crypto nerds Alice and Bob failed to choose a large enough n, allowing us to recover their private RSA keys. By converting the hexadecimal numbers to their full-fledged decimal values, and entering them somewhere like here (and here) we can find the prime factors of which the n consists:

0x53a121a11e36d7a84dde3f5d73cf = 38456719616722997 · 44106885765559411

0x99122e61dc7bede74711185598c7 = 49662237675630289 · 62515288803124247

With RSA, those primes factors (p and q) and the exponent (e = 0x10001 = 65537) are all you need to find the decryption key. To generate Bob’s private key, we can use a few simple python lines:

from Crypto.PublicKey import RSA
import gmpy
n = long(3104649130901425335933838103517383)
e = long(65537)
p = 49662237675630289
q = 62515288803124247
d = long(gmpy.invert(e, (p-1)*(q-1)))
rsa = RSA.construct( (n, e, d) )

Using this rsa key, we’re able to decrypt the data:

decrypted = rsa.decrypt(long('0x2c29150f1e311ef09bc9f06735acL', 16))
print str(hex(decrypted)).strip('0x').rstrip('L').decode('hex')

which results in the newline character (0x0a).

Looking through the rest of the decoded packets, we notice every data contains one encrypted character. It would make sense to put the decrypted character at the position of the sequence number in an output string. All we have to fix now, is the problem of having multiple packets with the same sequence number. In order to seperate the bad from the good packets, we will need to check if the signature matches the packet using Alice’s private key.

The following python script performs all of that for us. Only packets where the signature matches the data are considered as valid. Note that I first saved the pcapng as a pcap file in order to be able to use the python module pcapfile.

from Crypto.PublicKey import RSA
import gmpy

# Alice's public encryption parameters
n1 = long(1696206139052948924304948333474767)
e = long(65537)

# Bob's
n2 = long(3104649130901425335933838103517383)

# Yes! We can factorize the n
p1 = 38456719616722997
q1 = 44106885765559411

p2 = 49662237675630289
q2 = 62515288803124247

# that means we can find the decryption exponent d
phi1 = (p1-1)*(q1-1)
phi2 = (p2-1)*(q2-1)
d1 = long(gmpy.invert(e, phi1))
d2 = long(gmpy.invert(e, phi2))

# now construct the RSA with all the parameters
rsa1 = RSA.construct( (n1, e, d1) )
rsa2 = RSA.construct( (n2, e, d2) )

# and decrypt the messages from a pcap file!
from pcapfile import savefile

cf = savefile.load_savefile(open("bob_alice_encrypted.pcap"))

output = {}

for p in cf.packets:
    pack = str(p.packet)[136:].decode('hex').decode('base64')
    if 'DATA' in pack:
        seq = int(pack.split(';')[0].split(' ')[2])
        data = pack[16:].split(';')[0][:-1]
        sig = long(pack.split(';')[2].split(' = ')[1], 16)
        m = long(data, 16)
        decrypted = rsa2.decrypt(m)
        sigcheck = rsa1.sign(decrypted, '')[0]
        val = str(hex(decrypted)).strip('0x').rstrip('L').zfill(2).decode('hex')
        if sig == sigcheck:
            output[seq] = val
print ''.join(output.values())

We are left with the flag: flag{n0th1ng_t0_533_h3r3_m0v3_0n}