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!!!


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

def main():
    packets = rdpcap("capture.cap")
    pub = 0
    session = []
    for pkt in packets:
        if "Raw" not in pkt:
        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)
            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")


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

‘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


  1. alibert says:

    Hi, this looks very intressting. I tried rebuilding this (although I have no clue about python). I get this error:

    from elgamal import Elgamal
    ImportError: No module named elgamal

    What did I miss? I am on CentOS

  2. hellman says:

    alibert, elgamal is module in the tasks tarball.
    You should run your script in that directory or copy elgamal.py to your new script.
    It’s not default python’s module, so OS doesn’t matter :)

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>