Finding hash almost-collisions A few months ago, XKCD posted a challenge to find a plaintext which hashed (using Skein 1024 1024) to a specified value. Inputs were scored based on the hamming distance between the hash of the specified input and the desired hash.

The top scorer, from Carnegie Mellon, found a plaintext whose hash matched all but 384 bits of the desired hash.

I also tried competing in the contest. I used brute force and just hash many sequential values and submitted the best one I could find. I didn't come close at all. As I expected, it was easy to drop the first few bits and get it down to the mid 400s, but each improvement was harder than the one before.

Is there a better way than brute force? When I was competing, I figured that the Skein hash function seemed pretty secure and that I wouldn't be able to find any weakness to speed up the process. Now I'm doubting that the winner could score so well with brute force, even with immense amounts of computing power.
Since the output of the configuration of Skein is 1024 bits, we would expect to get 512 bits correct just by random hashing. So the question is, what is the probability of getting 640 bits correct? From that we can figure out how long it would take for that to occur.

There are ${1024 \choose 640}\approx 4.16\cdot 10^{292}\approx 2^{972}$ ways this can happen out of $2^{1024}$ different outputs. If we assume the probability of each output is $1/2^{1024}$, then the probability of getting one of those outputs with 640 correct bits is approximately $2^{972}/2^{1024}=1/2^{52}$. So, perform $2^{51}$ hash function calls and you have a $.5$ probability of getting one of those outputs. That sort of work factor should be do able with lots of hardware (supercomputer, GPUs, etc) in 24 hours. As Paulo said, the problem is embarrassingly parallelizable.