EngineYard SHA1 Contest Approaches

Question

EngineYard is holding a constest here, where given a phrase and a dictionary of words, come up with a 12 word phrase whose SHA1 hash has the smallest hamming distance from the SHA1 hash of the given phrase.

A couple of sites are using cloud/crowd-sourcing to try to bruteforce it, while others are using CUDA and GPUs. Some reports have the GPUs scoring mid-30 hamming distances, while the crowd-sourcing javascript have hamming distances in the 40s.

What would your approach to this contest be? One approach per answer.

Contest Has Closed

Answer 1

I was pondering whether or not a local search or genetic algorithm would work. I don't think it would, where a small permutation (changing the capitalization of a letter) would create a completely new hash.

Is brute force really the best way?

Answer 2

Options are pretty much (1) brute force, (2) exploit weaknesses in SHA-1. If you could solve this with a genetic algorithm in less than brute-force time, then I think that would constitute a weakness in SHA-1 by definition. Certainly if the genetic algorithm could produce an exact match in less than brute-force time, it would be.

Mind you, I don't know whether difficulty of finding a near-match is actually a required property of a cryptographic hash. Is a hash secure for all standard crypto applications if it's easy to find near matches, but still properly hard to find exact matches? If so, then there may be a middle ground where you use some property of SHA-1 which is not a weakness.

However, I suspect the reason the winning phrase must consist of exactly twelve words from a given dictionary is to be extra-confident that there cannot be a less-than-brute approach. Even if a technique were known for finding near-pre-images in SHA-1, adapting it to produce legal results would most likely be quite hard.

Answer 3

Maybe somebody can implement the ideas of Xiayoun Wang and her collegues?

See their book chapter on: Finding Collisions in the Full SHA-1

and also this powerpoint presentation entitled Cryptanalysis on SHA-1

here's an excerpt of what Wikipedia has to say about her:

"In February 2005 it was reported that Wang and co-authors had found a method to find collisions in the SHA-1 hash function, which is used in many of today's mainstream security products. Their attack is estimated to require less than 2^69 operations, far fewer than the 280 operations previously thought needed to find a collision in SHA-1. Their work was published at the CRYPTO '05 conference. In August 2005, an improved attack on SHA-1, discovered by Xiaoyun Wang, Andrew Yao and Frances Yao, was announced at the CRYPTO conference rump session. The time complexity of the new attack is claimed to be 2^63."

A hash collision attack has further lowered the bar from 2^69 to 2^52 by McDonald, Hawkes and Piepryzk in 2009