• Category: Crypto
  • Points: 130
  • Solves: 54
  • Description:

My friend set up a small signing scheme, however she won’t let me sign stuff. Can you get it signed?

Find it at dub-key-t8xd5pn6.9447.plumbing port 9447

dub-key.tar.gz MD5 checksum: ab9f970aa1ae119fc486e88e15c859a6


Thanks to

  • jrandom
  • verr
  • febo
  • kree
  • wolfg

for the collaboration on this challenge :)


This crypto challenge is about proof of work and signatures.

At first we need to solve a proof of work challenge. The server sends 9 random bytes, base64 encoded. The challenge is to find an input which has a length of 20 bytes and starts with the 12 base64 encoded random bytes from the server for the SHA-1 hash algorithm that results in an output value with 3 \x00 in the end. This was a straight forward task: appending characters to the challenge in a loop until we find a hash which fulfills our criteria.

Now the tricky part begins. The server generates 2 times 128 random bytes, SECRET and TO_SIGN. The signature is then calculated as follows: sig = sign(SECRET + TO_SIGN). The server sends us TO_SIGN and we need to find a collision. This means that we need to find another input, which gets concatenated with SECRET, that results in the same signature. Before we provide our input, we can send the server values which are different to TO_SIGN, lets call them TO_SIGN’, and the server responds with the signature (sig = sign(SECRET + TO_SIGN’)). For each connection we can ask the server for at most 255 signatures.

To solve also this challenge, we needed to take a closer look at the signature algorithm. It’s the product of each cycle length of the input (SECRET + value). The cycle length can also be thought as the amount of edges in a graph. For instance you start at index 0, which is your first node, and jump to the index which is the value at index 0. Now you would have a cycle length of 1. This process continues until you get an index which is already in the graph.

We came up with 2 solutions.

One is that we searched for a circle inside TO_SIGN and changed the orientation (each node points then to the incoming node). For example if you have the circle 7–>10–>8–>7, you can change its orientation to 7–>8–>10–>7. This is a different input for the signature algorithm, but leads to the same signature as we are challenged on :) One remark here is that we came up with this solution when the CTF was already over.

One is that we changed exactly 1 byte in TO_SIGN (to the value of the current index), let the server sign the modified value, and store the signature in a map. The key of this map is the signature, and the value is the occurrence of this signature. After 128 iterations (length of TO_SIGN) we take the signature which occurred most often, and this was in almost every case the same signature as we are challenged on :) This is the solution we used during the CTF.

Solution in python

The second solution, what we used during the CTF, can be found in the outcommented part in the main function.

import hashlib
import itertools
from base64 import b64encode, b64decode
from pwn import remote

__host__ = 'dub-key-t8xd5pn6.9447.plumbing' #'localhost'
__port__ = 9447

def get_SHA(data):
    ha = hashlib.sha1()
    return ha.digest()

def find_SHA(challenge):
    charset = "".join(chr(i) for i in range(0x00, 0x100))
    for p in itertools.chain.from_iterable((''.join(l) for l in itertools.product(charset, repeat=i)) for i in range(8, 8 + 1)):
        candidate = challenge + p
        print "p        : " + p
        print "candidate: " + candidate
        proof = get_SHA(candidate)
        if (ord(proof[-3]) == 0) and (ord(proof[-2]) == 0) and (ord(proof[-1]) == 0):
            return candidate
    return None

def get_cycle_circle(data, start_index):
    # print "in get_cycle, got data: " + ''.join([str(x) for x in data])
    cycle_circle = []

    for i in range(start_index, len(data)-1):
        # calculate cycle
        index = i
        indices = []
        values = []
        count = 0
        while not index in indices:
            count += 1
            index = data[index]

        # check if it's a circle with length >= 3
        if count >= 3:
            circle = True
            for j in indices:
                if not(j in values):
                    circle = False
            if circle:
                # print "We found a circle! :)"
                # print "Indices: " + ','.join([str(x) for x in indices])
                # print "Values: " + ','.join([str(x) for x in values])
                cycle_circle = indices

    return cycle_circle

def change_circle_orientation(data, cycle_circle):
    change pointing of circle nodes to the incoming ones
    (reverse cycle orientation)
    data_mod = list(data)

    for i in cycle_circle:
        index = data[i]
        value = i
        # print "index: " + str(index)
        # print "value: " + str(value)
        data_mod[index] = value

    return ''.join([chr(x) for x in data_mod])

if __name__ == "__main__":
    # loop until we found a collision (different input, same output)
    while True:
        # ----------------------------------------------------------------------
        # initialization

        # connect to the server
        except NameError:
        _s = remote(__host__, __port__)
        # ----------------------------------------------------------------------

        # ----------------------------------------------------------------------
        # proof of work
        _pow_challenge = _s.recv(12)
        # print _pow_challenge

        _pow = find_SHA(_pow_challenge)

        _r = _s.recvline()
        if _r.__contains__("Bad proof of work"):
            print "[!] We got a bad proof of work!"
        # ----------------------------------------------------------------------

        # ----------------------------------------------------------------------
        # get the base64 encoded value TO_SIGN, on which we are challenged on
        _challenge_b64 = _s.recvline()
        _challenge = b64decode(_challenge_b64)
        # print "we are challenged on (base 64 encoded): " + _challenge_b64
        # ----------------------------------------------------------------------

        # ----------------------------------------------------------------------
        # request up to 128 signatures which are very similar to the original
        # one

        # map for our test signatures:
        #   key     --> signature
        #   value   --> occurrences of the signature
        observed_signatures = {}

        for i in range(128):
            test_string = challenge[:i] + chr(i) + challenge[i+1:]
            # test_string = challenge[:i] + chr(127-i) + challenge[i+1:]
            # test_string = chr(i) + challenge[1:]
            if test_string == challenge:

            # Ask oracle for signature of the test string
            s.recvuntil("Give me signiture of data\n")
            test_sig = s.recvline()
            test_sig = test_sig[:-1]
            # print "received signature: " + test_sig

            # store signatures in our map
            if test_sig in observed_signatures:
                observed_signatures[test_sig] += 1
                observed_signatures[test_sig] = 1
        # ----------------------------------------------------------------------

        _chl_test = '0' * 128 + _challenge
        _cycle_circle_ = get_cycle_circle(map(ord, _chl_test), 128)
        if _cycle_circle_ == []:
            print "[>] No circle found! --> next iteration"
        print "[>] Found a circle :D"
        _challenge_mod = change_circle_orientation(map(ord, _chl_test), _cycle_circle_)
        _challenge_mod = _challenge_mod[128:]

        _s.recvuntil("Give me signiture of data\n")
        _sig = _s.recvline()
        _sig = _sig[:-1]

        # ----------------------------------------------------------------------
        # send signature to verification

        _sig = "0" * (620 - len(_sig)) + str(_sig)

        # send it and see if it's the same signature as we are challenged on :)
        _r = _s.recvuntil("Give me signiture of data\n")

        _flag = _s.recvline().replace('\n', '')

        if _flag.startswith("9447{") and _flag.endswith("}"):
            print "[>] Looks like as we found a flag :D\n[>] " + _flag

        print "[!] Found a circle but no collision or the flag format is " \
              "different?!\n[>] Got:  " + _flag
        # ----------------------------------------------------------------------