(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!
# -*- coding: latin-1 -*- from Crypto.PublicKey import RSA from Crypto.Hash import SHA256 # used to hash the strings # return the first lenght letters of the hexadecimal hash def cut_sha256(string, length): h = SHA256.new() h.update(string) return h.hexdigest()[:length] # start to build a dictionary, use each hash as a key # if there is a collision stop and print the signature that collide def build_dict(dictionary, min_value, max_value, factor): for value in range(min_value, max_value): string = [] # use different representation of the same number, with 0, 1, 2 and 3 digits after the comma string.append(str(value)) for f in range(1, 4): float_string = ("{0:."+str(f)+"f}").format(value / factor) if float(float_string) == value / factor: string.append ( float_string ) # save the hash of all the strings for st in string: text = prefixes[0] + st + suffixes[0] key = cut_sha256(text, cut_length) found_value = dictionary.get(key) # add the strings that are not in the dictionary if found_value == None: dictionary[key] = text else: # if a string is already in the dictionary, there is a collision print('collision:' + found_value + ' - ' + text) return {} # (only the first prefix, suffix and separator are used in the script) prefixes = ['I owe Bob ', 'I owe Mr. Bob '] suffixes = [' Euros. Alice.', ' €. Alice.', ' $. Alice.'] separators = ['.', ',', ' '] cut_length = 12 # this lenght is used by the signature system of Alice # Uncomment it to start the script, it takes some time!!! #build_dict({}, 0, 10000000, 100.0) # Test the result of the script print( cut_sha256('I owe Bob 14304.55 Euros. Alice.', cut_length) ) print( cut_sha256('I owe Bob 3632210 Euros. Alice.', cut_length) )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 248 different digests. The square root is 224 = 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 248 would not be feasible unless you have parallel computers and a lot of time to spend 🙂