XKCD Hash Breaking

The PiCloud team has been nerd-sniped by the April Fools XKCD comic Externalities which pits visitors against each other in a contest of raw computing power (and a little luck). Here at PiCloud we’ve got lots of computing power, but about how much is needed (on expectation) to win their hash breaking competition?
The probability of matching a certain number of bits in the hashed output follows a binomial distribution. The current leaders of the contest are 389 bits off out of 1024 bits. We can calculate our chance of generating a better hash value like so:
This is the fraction of the distribution that is less than 389 bits off, and it’s one in 228 trillion!
Not to be discouraged, we wrote a program to generate random hashes and test how close they are to the goal given by XKCD. Running it on a single f2 core, we were able to generate and check over 160,000 hashes per second. Multiplying the prior probability by this rate results in a 1 in 1.43 billion chance of finding a better hash in 1 second, but we can do much better than that.
How many f2 cores running in parallel would it take, on expectation, to generate a better hash within the next 6 hours? It turns out that it would take over 66,200 f2 cores running in parallel over 6 hours before we can expect to find a better hash. Unfortunately, we can’t get you 60 thousand f2 cores and the cost would be nearly $87,500 on PiCloud.

Feeling Lucky?

There are still over 6 hours left in the competition as of the time of this blog post and we’ve made it easy for you to get hashing using our environment set up with a skein-1024 hashing program. We’ve shared the environment publicly, so you can use it directly with no setup.
Here’s how you can give it a shot (You need our client library installed):
1$ picloud exec -e /picloud/xkcd_skein -t f2 skein
This will run indefinitely and print to standard output the best result it has yet to come accross. You can monitor the standard output of the job from the Jobs Dashboard to see if you’ve found a better hash.
 
1$ picloud exec -e /picloud/xkcd_skein -t f2 skein 389
This form of invocation will not print any output until it has come across a hash that is closer than 389 bits away from the goal.
 
1picloud exec -e /picloud/xkcd_skein -t f2 skein 400 1000000000
This form of invocation will not print any output until it has come across a hash that is closer than 400 bits away from the goal, but will stop hashing after 1 billion attempts.
From the Environments Dashboard, you can also clone our public environment, and modify the program for yourself.
You can run “picloud exec” as many times as you want to maximize your parallel computing power.

By Josh Hawn
Source:
http://blog.picloud.com/2013/04/02/xkcd-hash-breaking/

0 yorum: