Hash Game is back!

Written by Benjamin Eriksson

31 May 2020

For more than 3 years "The famous HASH game" has been unavailable but now I'm happy to announce that I have revived it and will host it here! Try it out! I've also included all the old records!

Background

If you are unfamiliar with the hash game the goal is to find an input message which generates a hash with some special properties. The most common properties here are usually the smallest or largest.
Since a hash is simply a string of bits it can be intreprted as a number and compared numerically. Let's do an example.

md5("alice") => "6384e2b2184bcbf58eccf10ca7a6563c"
md5("bob")   => "9f9d51bc70ef21ca5c14f307980a29d8"

The messages "alice" and "bob" will generate the md5 hashes 6384e2b2184bcbf58eccf10ca7a6563c and 9f9d51bc70ef21ca5c14f307980a29d8. Comparing these we see that "alice" generates a smaller number while "bob" generates a larger one. Now comes the challenge, can you find smaller or larger hashes than these? 

Motivation

If you're not already enthusiastically coding a high-performance hash generator then let me motivate the challenge further! This challenge is actually a core building block of Bitcoin and most proof-of-work cryptocurrencies. So if you think this challenge is easy, then you're about to become very wealthy! If you have a method to quickly generate small hashes you can decide which transactions are added to the blockchain.

This is, of course, not the reason why I like the hash game. The real value of this challenge is that it shows the evolution of hash cracking performance. If you are good at solving this challenge, which is technically a preimage attack, you can break a lot of interesting security.

Trying the challenge

The beauty of hashes is that there is no dominant strategy in picking messages. This means that hash(random()) is just as likely to generate small hashes as hash(youname + random()). For this reason, people usually try to sneak in some messages in their hashes. Like an email or website.

I wrote a simple python script to generate md5 hashes of the form hash("beneri" + str(i)). Below is some data from this test:

What this shows is that after about 12 minutes and 1 billion hashes I was able to generate a hash with 7 leading zeros. This was already easily beaten back in 2004. A key-takeway here is that my setup has a hashrate of about 1.3 MH/s (Mega hashes per second). To put this into perspective, the bitcoin network currently has a hashrate of about 100 EH/s (Exa hashes), i.e.10^20 hashes per second.

The current record md5 hash has 14 leading zeros! To reach this you would have to generate approximately 10 PH (Peta hashes) ~ 16^14 (1/16 chance for each zero). Using my setup above this would take 244 years! I'm not sure how long time it took for Jiyong Youn (hletrd) to do this, nevertheless, very impressive! It's also fun to compare this to the Bitcoin network which could beat this record in 0.1 milliseconds! I should say that Bitcoin does not use md5 but rather sha256 so it's not a super fair comparision.

But wait, you might think, doesn't this mean that we can use the Bitcoin blockchain to cheat on this challenge for sha256? Luckily not, because Bitcoin is little endian. Following this example, we see that sha256(hex("b9d751533593ac10cdfb7b8e03cad8babc67d8eaeac0a3699b82857dacac9390")) is 1dbd981fe6985776b644b173a4d0385ddc1aa2a829688d1e0000000000000000, note all the zeroes on the right!

History

The famous hash game was initially created by Dr. Boldizsár Bencsáth from the CrySyS Lab back in 2004. Since then it has been running for over 10 years, with the last record being set in 2016 by Jiyong Youn (hletrd). We  have seen similar challenges in the popular Advent of Code (Day 4 in 2015). There was also another similar website, http://h11e.com/. I was not able to include their records as they only show the hash and not the actual input message, making it impossible to verify it's validity.

Write your comment!

Comments