# dub-key

[9447ctf, 2015]

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

## Credits

Thanks to

- jrandom
- verr
- febo
- kree
- wolfg

for the collaboration on this challenge :)

## Write-up

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

*. The signature is then calculated as follows:*

**TO_SIGN***. The server sends us*

**sig = sign(SECRET + TO_SIGN)***and we need to find a collision. This means that we need to find another input, which gets concatenated with*

**TO_SIGN***, that results in the same signature. Before we provide our input, we can send the server values which are different to*

**SECRET***, lets call them*

**TO_SIGN***, and the server responds with the signature (*

**TO_SIGN'***). For each connection we can ask the server for at most 255 signatures.*

**sig = sign(SECRET + TO_SIGN')**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

*, you can change its orientation to*

**7-->10-->8-->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.*

**7-->8-->10-->7**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

*) 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.*

**TO_SIGN**## Solution in python

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

{% highlight python %} #!/usr/bin/python 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() ha.update(data) 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:
indices.append(index)
values.append(data[index])
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
break
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
break
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
try:
_s.close()
except NameError:
pass
_s = remote(__host__, __port__)
# ----------------------------------------------------------------------
# ----------------------------------------------------------------------
# proof of work
_pow_challenge = _s.recv(12)
# print _pow_challenge
_pow = find_SHA(_pow_challenge)
_s.send(_pow)
_r = _s.recvline()
if _r.__contains__("Bad proof of work"):
print "[!] We got a bad proof of work!"
exit(1)
# ----------------------------------------------------------------------
# ----------------------------------------------------------------------
# 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:
continue
# Ask oracle for signature of the test string
s.recvuntil("Give me signiture of data\n")
s.send("1")
s.send(b64encode(test_string))
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
else:
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"
continue
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")
_s.send("1")
_s.send(b64encode(_challenge_mod))
_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")
_s.send("2")
_s.send(_sig)
_flag = _s.recvline().replace('\n', '')
if _flag.startswith("9447{") and _flag.endswith("}"):
print "[>] Looks like as we found a flag :D\n[>] " + _flag
break
print "[!] Found a circle but no collision or the flag format is " \
"different?!\n[>] Got: " + _flag
# ----------------------------------------------------------------------
```

{% endhighlight %}