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.