Hacker News Reader

Comment by brown9-2 | Hacker News Reader

Just to be clear, there is probably no realistic way of winning this without having lots and lots and lots of computing resources available to you once the dictionary is released, is there?

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?

  1000! / 982! permutations of dictionary words * 36^5 permutations of random chars

View on HN

Agreed... The average developer has no hope of winning this. It will almost certainly be won by someone with a roomful of PS3s or graphics cards who already cranks through hashes for a living. (like these guys: http://www.win.tue.nl/hashclash/Nostradamus/)

What about..

"You may permute capitalization for the dictionary words (i.e. you may use Ruby, rUby, RUBY, and RUBy)"

Forgot to consider that; along with the fact that the 5 random characters can be any printable ASCII characters, not just alphanumeric.

So this is somewhere upwards of 10^50 phrases to hash (in a naive implementation), right?

Well, are you also including the fact that there is nothing forbidding repeated words?

While this has a marginal effect on the total number of possible hashes, repeated words are still an important consideration: If you can guess even one word that is likely to appear in their 1000-word dictionary, you can precompute the hashes for all possible variants of the corresponding phrase (that word repeated twelve times) prior to the contest, giving you a jump on other contestants.

I'd guess that we'll either see the rules revised to prevent this or see a dictionary filled with non-dictionary words.

According to the rules you can append up to 5 random chars. But you don't have to.

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.

My thoughts exactly. Also, there are enough additional permutation rules to balloon the result space way beyond the reach of even a modest super computer.

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.

You can permute the capitalization of the words in the dictionary, and the random characters as well ..

If you can guess 5 words in the dictionary, you can pre-compute over 7 billion guesses...

Reply on news.ycombinator.com