Engineyard Challenge Python Code

Re:Engineyard Challenge Python Code by ErrantX on Wednesday July 15, 2009 @04:58AM (#705398)

I dont wish to be, umm, mean. But I know of at least 3 companies (ours included) that could run this in a few minutes.

this is my code (using mighty, our python based cluster service):

  import mighty

  word_generator = mighty.word_generator("wordlist",(mighty.APPEND_NUMERALS,5))
  phrase_generator = mighty.word_concentate(word_generator,' ')

  job = mighty.match_to_hash('PROVIDEDHASH',mighty.SHA1,phrase_generator.iterate_all)
  job.priority = mighty.CRITICAL
  mighty.submit_job(job)

Done. Takes about 5 minutes (I wont enter - it's not fair).

EDIT: added CRITICAL as the priority or it takes longer :)

EDIT: ok so the code is a bit the wrong side of the tracks. It wouldnt take long to refactor it :)

[ Parent | on HN ]

Re:Engineyard Challenge Python Code by decode on Wednesday July 15, 2009 @02:43PM (#706295)

This isn't actually correct, is it? Assuming an average 6-letter word length, there are about 10^67 valid combinations that your iterate_all() can go through: (((2^6) * 1000) ^ 12) * (94 ^ 5) = 3.5 * 10^67

Since this is much larger than the total hash space (2^160 = 10^48), you can hope you'll get a collision after the number of tries equal to half of the hashspace (10^48 / 2). That means you'll have to generate 10^47 hashes. At 5 minutes of runtime, you'll have to generate 10^45 hashes per second.

Bottom line: if you can run this on 200,000 cores, you'll have to generate 10^40 hashes per second per core, and that seems impossible to me.

[ Parent | on HN ]

Re:Engineyard Challenge Python Code by ErrantX on Wednesday July 15, 2009 @05:45PM (#706662)

Weeell we have 20,023 computers (that fluctuates a tad). That's probably about 30,000 cores in the end.

I cant iterate the whole lot - but I can cover a substantial portion more of the keyspace in 5 mins than most could in the 30hrs. I bet 5 minutes will easily get me damn close :)

[ Parent | on HN ]

Re:Engineyard Challenge Python Code by decode on Thursday July 16, 2009 @03:38PM (#708604)

I'm seeing about 1 million hashes per second on a single core. So, you can do about 10^11 hashes per second on 30,000 cores. At that rate, it will only take you 10^48 years to cover the keyspace.

You won't even cover a fraction of a percent of the keyspace before the sun burns out.

[ Parent | on HN ]

Re:Engineyard Challenge Python Code by jamie_ca on Wednesday July 15, 2009 @02:52PM (#706312)

I think it unlikely you have a compute cluster that can generate 3.3 million, billion, billion, billion SHA1 hashes per second (edit: and that assumes not adding the random 5 characters to the end). The actual contest will have a word list of a thousand words.

Also, (a) you're allowed to permute case of letters, exploding the search space even more, which is handy because (b) I presume the target sha1 will come from words not on the word list, making an exact match unlikely (hence score based on hamming distance).

[ Parent | on HN ]