I blogged a while back about a contest where you were asked to find input for an MD5 hash that would produce a result that matched at least some number of bits to a hash value the contest provided.
I found the contest by watching the promotion video on the Novena crowd funding campaign web site. Towards the end of the video you’ll see some text appear for a fraction of a second on the screen behind Andrew Huang. It’s a base64 encoded URL for the contest web site. The contest awarded a Novena laptop to the person who found the most strings whose hashes matched a given number of bits. The contest web site stated the number of bits you had to match might change depending on how difficult the challenge proved to be.
When I found the contest, the number of bits you had to match was up to 107. There was one person at the top who already had several hundred matches under their belt. Either they are and expert at MD5 and its vulnerabilities, or (my guess) they found the contest much sooner when the difficulty was much lower.
The target hash for the contest was “29c986a49abf80e9edf2ffe8efb7e040” which is the MD5 hash of the string “novena”.
The most number of bits I was able to match was 105 after running my HashAway program for 48 hours on a 4-core Intel i5 processor. That I didn’t even find one was a bummer, but it was a great exercise in the search to pull out the best performance from my program. For example I had initially written the program to generate a random string and hash that to search for matches. What I eventually did was hash the result of the previous hash. This had a great boost in performance as the overhead of generating random strings, and converting them to byte values to hash, was gone. A simple trick with big results. It was also a great exercise in becoming familiar with multi-threading in Java.
The last version of the code I had posted was version 1.3. Here is HashAway version 1.4 which is what I used to find my best 105-bit match.
I did do a quick search and found one other person’s source code for this problem. In the source you can see they found the contest when the difficulty was at 105 bits. If only I’d found the contest sooner. The comments in the source also state the contest started out at 90 bits! I can get 90-bit matches at a rate of 4/5 a second even on an old dual-core processor.
Ah well. So it goes.