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 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.
{% 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 %}