## 9447ctf: dub-key

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