In this challenge we are told to retrieve a flag from a vulnerable server. We are given the files contract.pcapng with network traffic and server.py with a simple python TCP server implementation. We are also given the command nc contract.vuln.icec.tf 6002 which tells us the address and port we can use to communicate with the server.

The pcapng file consists mostly of packets used for DNS resolution and TCP handshaking. Only packet 6, 18 and 20 contain an actual payload. Packets 6 and 18 were sent from the client to the server and contain a payload of the format: “command:<192 bytes of hexadecimal characters>.”. with the commands help and time sent in packet 6 and 18 respectively. Packet 20 seems to be sent as a response to packet 18 since it contains only a string with the date and time. Let’s look at the server code and see what the server does with the data it receives:

    def handle(self):
        signal.alarm(5)
        d = self.rfile.readline().strip()
        try:
            msg, sig = d.split(b":")
        except ValueError as e:
            self.wfile.write(b"bad command\n")
            return
        if not self.verify(msg, sig):
            self.wfile.write(b"bad signature\n")
            return

        self.run_command(msg)

We see that server tries to split the data at the colon character and upon succes seemingly performs a verification on it. The help or time strings we saw earlier would be assigned to the msg variable. The hexadecimal string we saw gets assigned to the sig variable indicating it is likely going to be used as a signature. If the verification succeeds it passes msg as an argument to the run_command function seen below:

 
    def run_command(self, msg):
        cmd, *args = msg.split()
        if cmd == b"read":
            try:
                with open(args[0], "rb") as f:
                    self.wfile.write(f.read())
            except:
                self.wfile.write("\n")
        elif cmd == b"time":
            self.wfile.write(datetime.datetime.strftime(datetime.datetime.now(), "%Y-%m-%d %H:%M:%S").encode("utf8"))
        elif cmd == b"help":
            self.wfile.write(help_string)
        else:
            self.wfile.write(b"bad command\n")

After reading this function it becomes clear that the challenge reduces to finding the correct signature to send along with the read command and hopefully use it to read a file with our flag from the server. We can get more insight into the type of verification used by looking at the verification function:

 
    def verify(self, msg, sig):
        try:
            return vk.verify(unhexlify(sig), msg, hashfunc=hashlib.sha256)
        except:
            return False

We see that the object vk is used for verification which is created at the beginning of the file using the following code:

 
PUBLIC_KEY = """
-----BEGIN PUBLIC KEY-----
MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEgTxPtDMGS8oOT3h6fLvYyUGq/BWeKiCB
sQPyD0+2vybIT/Xdl6hOqQd74zr4U2dkj+2q6+vwQ4DCB1X7HsFZ5JczfkO7HCdY
I7sGDvd9eUias/xPdSIL3gMbs26b0Ww0
-----END PUBLIC KEY-----
"""
vk = VerifyingKey.from_pem(PUBLIC_KEY.strip())

The class VerifyingKey is imported from the ecdsa library which is a python implementation of the ECDSA digital signature algorithm. When reading through the library and the wikipedia page it becomes clear that a signature actually consists of an r,s pair. The VeryfyingKey class and its counterpart SigningKey are defined in the keys.py. We see that the sign function calls another function called sign_digest which takes an r,s pair and encodes it in a string. Considering the format of the data sent to the server and the api presented by this library through the key classes defined in this file, the client must have hexlified and appended this pair to the command and a colon. The server then unhexlifies the signature after which it uses the command and signature for verification. After peeling away some layers of abstraction we can find that the actual ECDSA signing algorithm that returns this pair is implemented as the sign function in the ecdsa.py file:

 
  def sign(self, hash, random_k):
    """Return a signature for the provided hash, using the provided
    random nonce.  It is absolutely vital that random_k be an unpredictable
    number in the range [1, self.public_key.point.order()-1].  If
    an attacker can guess random_k, he can compute our private key from a
    single signature.  Also, if an attacker knows a few high-order
    bits (or a few low-order bits) of random_k, he can compute our private
    key from many signatures.  The generation of nonces with adequate
    cryptographic strength is very difficult and far beyond the scope
    of this comment.
    May raise RuntimeError, in which case retrying with a new
    random value k is in order.
    """

    G = self.public_key.generator
    n = G.order()
    k = random_k % n
    p1 = k * G
    r = p1.x()
    if r == 0:
      raise RuntimeError("amazingly unlucky random number r")
    s = (numbertheory.inverse_mod(k, n) *
         (hash + (self.secret_multiplier * r) % n)) % n
    if s == 0:
      raise RuntimeError("amazingly unlucky random number s")
    return Signature(r, s)

We see that in order to compute a signature the functions needs four values: hash,k,G and self.secret_multiplier. Here hash is just the hash of the data we wanna sign and G is the so called elliptic curve base point which is part of the public key. What is unknown to us is k and self.secret_multiplier which is the actual private key. If we could find these we could sign our message and be able to use the servers read command. The first thing to ask is if ECDSA has any known vulnerabilities that we could exploit. After doing some research on ECDSA I found this pdf: 1780_27c3_console_hacking_2010.pdf. On slide 124 and 125 it talks about the possibility to compute m and k incase the same m is used to compute each signature. After comparing we see that the m and k in the slides correspond to the variable k and the private key self.secret_multiplier in the code. Another thing to note is that existence of this vulnerability would imply that the r in the r,s pair would be the same each time. After inspecting the signatures in the pcapng file we see that this is indeed the case! Both signatures start with the string: “c0e1fc4e3858ac6334cc8798fdec40790d7ad361ffc691c26f2902c41f2b7c2fd1ca916de687858953a6405423fe156c” : ).

The difficult part was to implement the code to retrieve the variables k and the private key and sign a new message. Please see the ecdsa_ps3.py which is the python script I wrote for this. During writing it I realised that the verification algorithm used by the ecdsa library must have some functions that extract the G we need from the public key. I used these functions to implement my own function get_G. To retrieve k and and the private key i wrote the functions get_k and get_privkey. These functions implement the ideas conveyed in the slides. For clarity I wrote an improved version of the mathematical derivations in latex.



Here the last implications in both derivations are true because in the ECDSA algorithm pk and k are chosen to be between 1 and n - 1. Let’s turn to the main code:

 
PUBLIC_KEY = """
-----BEGIN PUBLIC KEY-----
MHYwEAYHKoZIzj0CAQYFK4EEACIDYgAEgTxPtDMGS8oOT3h6fLvYyUGq/BWeKiCB
sQPyD0+2vybIT/Xdl6hOqQd74zr4U2dkj+2q6+vwQ4DCB1X7HsFZ5JczfkO7HCdY
I7sGDvd9eUias/xPdSIL3gMbs26b0Ww0
-----END PUBLIC KEY-----
"""
G = get_G(PUBLIC_KEY)

hash1 = int(hashlib.sha256('time').hexdigest(),16)
hash2 = int(hashlib.sha256('help').hexdigest(),16)
hash3 = int(hashlib.sha256('read flag.txt').hexdigest(),16)
sig1 ="c0e1fc4e3858ac6334cc8798fdec40790d7ad361ffc691c26f2902c41f2b7c2fd1ca916de687858953a6405423fe156c0cbebcec222f83dc9dd5b0d4d8e698a08ddecb79e6c3b35fc2caaa4543d58a45603639647364983301565728b504015d"
sig2 ="c0e1fc4e3858ac6334cc8798fdec40790d7ad361ffc691c26f2902c41f2b7c2fd1ca916de687858953a6405423fe156cfd7287caf75247c9a32e52ab8260e7ff1e46e55594aea88731bee163035f9ee31f2c2965ac7b2cdfca6100d10ba23826"
r1,s1 =  sigdecode_string(unhexlify(sig1), G.order())
r2,s2 =  sigdecode_string(unhexlify(sig2), G.order())

k = get_k(s1, s2, hash1, hash2, G)
private_key = get_privkey(k, s1, hash1, r1, G)
r3, s3 =  sign(hash3, k, private_key, G)

print 'read flag.txt:' + hexlify(sigencode_string(r3, s3, G.order()))

First we extract G from the public key. Then we create the three hashes, extract the r,s pairs from the signatures of the two sent messages and use these to retrieve the k and private_k variables. Along with the message we want to send and G these are then passed as arguments to the sign function. This function is simply a modified version of the sign function in ecdsa.py that allows G and k be passed as arguments. The r, s pair then gets encoded into a byte string, hexlified and appended to our message to conform to the format the server expects. Finally we open up a terminal and type nc contract.vuln.icec.tf 6002 after which we paste the generated and signed message and hit enter. The server responds with: IceCTF{a_f0rged_signatur3_is_as_g00d_as_a_real_1} as expected.