(nice solutions will get extra score, as usual)

This zip file contains a RSA test key pair and two simple bash scripts to sign and verify messages. The scripts are supposed to sign contracts of the form “I owe Bob xxxx Euros. Alice.”

Apparently, for compatibility with legacy systems, the security of the adopted algorithm is pretty poor and Bob has found a way to fool Alice into signing a contract with an amount different from what she expects … can you find out how?

Hi all!

I found a fake signature that Bob can use to fool Alice.

The security system uses an hash function but, if we check the signature, we can notice that it uses only the first 12 hexadecimal characters of the hash (that is the first 4 * 12 = 48 bits of the 64 * 4 = 256 bits of the complete hash).

So I created a huge number of strings in order to find a collision between two of them.

I introduced the comma in the price of the message, in this way I represented a same number in different manners (ie 0.5, 0.50, 0.500), and obviously each message had a completely different hash. I used a dictionary structure in python, that is an hash table, and I put the hash of the messages as the keys, that allowed to find a possible collision faster than using other structures.

My idea was to change some other parts of the sentence (the coin currency etc…) and maybe I’ill improve the script with this feature. For the time being, I found a collision with these two sentences:

“I owe Bob 14304.55 Euros. Alice.”

and

“I owe Bob 3632210 Euros. Alice.”

So Bob gains 3.617.905,45 Euros!

Nice! I like the idea of exploiting the floating point to variate messages 🙂

What you have implemented is in fact a birthday attack. We know that it takes on average a number of steps that is about the square root of the digest space. Now, the hash is cut to 12 hex characters which is 6 bytes, i.e., 48 bits. So we have 2

^{48}different digests. The square root is 2^{24}= 16777216.I’ve run Davide’s script a printed the length of the dictionary (which is the number of computed hashes to find the collision) and it takes 11259851 which is very close to 16777216. This requires about 1 minute on my computer! Iterating for 2

^{48}would not be feasible unless you have parallel computers and a lot of time to spend 🙂