hack.lu CTF 2011 Spy Aboard! (300)

Category: crypto

We have a spy aboard! For around 5 minutes ago we intercepted an encrypted transmission to an enemy outpost. It seems like we interrupted the mole in the act because we found an open transmission program on our terminals. We are 100% sure that he sent the position of our fleet to the outpost to plan an attack against us. Our position due the transmission was:

position: Harcon System , Planet Crematoria , x: 129.23432231423 degrees y: 111.13442353423 degrees , z: 100,13142234423 degrees

We need the spies autorization code to prevent this attack. You as our crypto expert you have to find it! The survival of 10000 brave men, women and children depends on you!!!
GOOD LUCK!

download

Summary: ElGamal Diffie-Hellman, bad protocol usage, known plaintext attack

Here we have an ElGamal Diffie-Hellman key exchange protocol:

• a, p are known to everyone
• Client generates random dc
• Server generates random ds
• Client sends a^dc (mod p) to server
• Client receives a^ds (mod p) from server
• Client calculates skey = (a^ds)^dc (mod p) and it is the shared secret.

Here, the standard Diffie-Hellman ends. The program uses the following encryption way:

ciphertext = message * skey (mod p)

Obviously, if we know a message, we can find skey (via Extended GCD algorithm). skey is generated again each session, but if there are several packets in one session, we can decrypt them all.

So, we’ll search sessions with several packets and try to use known message:

skey = ciphertext * message^-1 (mod p)

And decrypt the rest packets in session with this key.

#!/usr/bin/env python
#-*- coding:utf-8 -*-

from elgamal import Elgamal
from scapy.all import *

p = 0x00eaaf764ab5ee2b69e1ff0a2e0767920c5ed5247aa15f
34796487afe728256456b5a020080a683c5d5012f1a479292476
90e616ef85c138bcb5798bfa13e83f96493de791c3ec31ff7076
3acd118cfb70ddf99827c19b022267de71e3410899bd62fc83d0
a5c1ea275d6434b68aad8bb2cc0c17d7b116b6e9c2858007adb2
e9c3

def main():
    packets = rdpcap("capture.cap")
    pub = 0
    session = []
    for pkt in packets:
        if "Raw" not in pkt:
            continue
        data = pkt["Raw"].load
        if "Requesting" in data:
            print "\n" + data[:20] + "..."
        elif "Public" in data:
            if len(session) > 1:
                process_session(session, pub)

            print "\n" + data[:20] + "..."
            session = []
            pub = int(data[13:], 16)
        else:
            print data[:20] + "..."
            session.append(int(data[2:], 16))

def process_session(packets, pub):
    c = Elgamal(1)
    m = "position: Harcon System , Planet Crematoria" +\
        " , x: 129.23432231423 degrees y: 111.134423" +\
        "53423 degrees , z: 100,13142234423 degrees"
    msg = int(text2hex(m), 16)
    im = c.invers(msg, p)

    for i in xrange(len(packets)):
        g = (packets[i] * im) % p
        ig = c.invers(g, p)
        print "---\nTRYING INDEX", i
        for data in packets:
            m = (data * ig) % p
            
            print repr(hex2text(hex(m).rstrip("L")))
        print "---\n"

def text2hex(text):
    return "0x" + text.encode("hex")

def hex2text(hextext):
    hextext = hextext[2:]
    if len(hextext) % 2:
        hextext = "0" + hextext
    return hextext.decode("hex")

main()

Run the script and you’ll find that 5-th session’s 1st packet matched!

TRYING INDEX 0
‘position: Harcon System , Planet Crematoria , x: 129.23432231423 degrees y: 111.13442353423 degrees , z: 100,13142234423 degrees’
‘target position 1: Harcon System , Planet Crematoria , x: 122.24331423 degrees y: 10.134453423 degrees , z: 43,131424423 degrees’
‘target position 2: Harcon System , Planet Crematoria , x: 102.234121423 degrees y: 110.134453423 degrees , z: 43,131231423 degre’
‘estarget position 3: Harcon System , Planet Crematoria , x: 122.23403423 degrees y: 101.1349923 degrees , z: 69,131424423 degree’
‘starget position 4: Harcon System , Planet Crematoria , x: 133.23431223 degrees y: 86.1993423 degrees , z: 23,131423 degreestarg’
‘et position 5: Harcon System , Planet Crematoria , x: 111.23231423 degrees y: 12.134498323 degrees , z: 91,131413 degreestarget ‘
‘position 6: Harcon System , Planet Crematoria , x: 94.2341423 degrees y: 34.13445993 degrees , z: 43,1000321331 degreesautorizat’
‘ion code: N1c3_Crypt0_Sk1ll5_Dud3’

The flag: N1c3_Crypt0_Sk1ll5_Dud3