Engine Yard Programming Contest - Win an iPhone 3GS PLUS $2k in Cloud Credit (engineyard.com)
We’re kicking off a programming contest today that is sure to challenge even the most comp-sci heavy engineers out there, and we’re excited to see what you all come up with. With the difficulty of the challenge in mind, we’ve got some great prizes for the winner: an iPhone 3GS AND $2,000 of Cloud (Flex or Solo) credit.
You must tweet a sequence of twelve words that when hashed is bit-wise closest to a hash of a challenge phrase that we will announce the morning of July 20th. All words must be from a 1,000 word dictionary we will provide at that same time. You are allowed to append up to five random characters to the end of your entry. We’re pretty confident you’ll want to write a program to automate the finding of close matches, so announcing this a week in advance should give you enough time to get your programs up and running.
See the blog post for more details, rules and prizes!
46 comments
[ 3.1 ms ] story [ 95.2 ms ] threadI think I'm going to try to put something together this weekend just for the heck of it. It would be cool if they published the code (with permission) of the top submitters, just to see how they went about solving it.
Now that you have the hash and the word dictionary, you "forget" that you know the real string, and you set your program to try to find it.
At least that would make sure there weren't any major bugs in it (logic bugs not included) before you tried to solve the real problem. Since you only have 24 hours to crack it, every extra second will count ;)
Of course you'd have to write the application before the 20th. My point is that for people with day jobs, Mondays are almost always the busiest day of the week so I'm sure that will preclude a number of people from participating.
Since you need to choose a twelve word permutation from a possible set of one thousand words, plus append a 0-5 character random string, calculate the SHA1 hash for all possible permutations, and calculate the Hamming distance of each to the hash of the challenge phrase... correct?
"You may permute capitalization for the dictionary words (i.e. you may use Ruby, rUby, RUBY, and RUBy)"
So this is somewhere upwards of 10^50 phrases to hash (in a naive implementation), right?
I'd guess that we'll either see the rules revised to prevent this or see a dictionary filled with non-dictionary words.
The potential for case changes in the words really makes the keyspace much larger, since we currently don't know the length of the words.
One approach would be to lease a massive cluster of cloud computers to carry out the calculations. However, this option isn't financially viable for a lone developer.
Maybe there's an alternative way of approaching the problem.
All they have to do is make the dictionary include terms that potential engineyard customers might search for on Twitter.
Check out the Amatch ruby gem ... it can compute the hamming distance ... might be easy to automate with ruby ...
http://amatch.rubyforge.org/doc/index.html
Someone doing this should probably write the fast-spinning cogs in C, but it might be worth using Ruby to manage threads, processes, data segments, etc - indeed, maybe prototype the C code there first too. You'd gain an awful lot of convenience for very little overhead.
Since getting closer words does not get you a closer hash, usual optimization algorithms (like genetic algorithms, simulated annealing, etc.) are not going to be helpful.
Perhaps I'm missing something, but I think brute force and luck are going to win this contest, assuming that SHA1 is not broken between now and July 20th. If you want an iPhone 3G S, you should probably just head over to the Apple store and buy one and spend your valuable time on something else.
Hence my question.
I think the main challenges are deciding how to manage the brute force effort.
You can precompute a lot of hashes, and then search them on the contest day.
Or you can run it only during the 24H of the contest, and only store the result which is nearest.
And the second issue: how much resources to invest. A high CPU on EC2 is $20 for the day. Another doubles the price, and doubles the number of hashes you can check.
EDIT: The restrictions they place on the input makes rainbow tables kind of pointless. Just partition the search space (i.e. the permutations) pick a piece of it at random, and send it to your brute forcers.
EDIT2:
Back of the envelope: you will be able to try about 100million hashes for $20.
If you use a library function to do your SHA-1, you're doing it wrong.
Pad out your test strings to a fixed length of 448 bits (assuming that the words in their dictionary allow this).
Use a custom hashing algorithm that skips the "pre-processing" step by assuming a fixed length string and skips the for loop since it only needs to process one chunk. http://en.wikipedia.org/wiki/SHA_hash_functions#SHA-1_pseudo...
generated in 2^39 perms - http://www.cs.cmu.edu/~dbrumley/srg/spring06/sha-0.pdf
generated in 2^52 perms - http://eprint.iacr.org/2009/259.pdf
Since it would take an average supercomputer 5-6 days to generate the collision, I think I'm going to give the contest a rest (generating something close isn't useful outside the contest).
Another way to go about this is to sort huge rainbow tables by distance, which have been already created by a few reverse hash lookups ( http://md5.rednoize.com/ , http://hashcrack.com, http://sha1-lookup.com ) - You'll probably need to contact them directly or hurry up and make your own.
Here's the SHA1 algorithm itself for anyone interested: (Google Cache) http://74.125.95.132/search?q=cache:QjZpAaNXJr0J:https://www...
The contest describes a preimage attack, where one has a hash value and must guess an input which would have generated that hash. SHA-1 has no known preimage vulnerabilities, so the contest winner will either have to be lucky or break SHA-1.
The best advice would probably be to iterate the keyspace in a novel way and hope you happen upon a good match that someone else doesn't get.
http://www38.wolframalpha.com/input/?i=%281000+choose+12%29+...
The real killer is the allowed capitalization of any letter. If we assume that the average word length will be 6 characters, then we can assume that the average character length of any 12 word string will be 72 (not counting spaces).
With capitalization, the permutations act like a bit string. That is, the capitalization is either on or off. This gives us 2^72.
The resulting hash space is somewhere near (1000 choose 12) * (2^72) * (95 choose 5), or roughly 2^188.
jruby rubinius MRI Cloud postgresSQL record MRI exception record mongrel tokyo Cloud
This task is so unbalanced as a contest. The thought of spending a couple hundred dollars of cloud computing time to just buy more 'lottery tickets' for $3000 worth of prizes (assuming you could use the cloud time) is too much of a stretch for me.