# 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.

• I know some people from CMU who do things like this all the time. I'll try to get ahold of them and see how they approached this. May 10, 2013 at 16:47
• May 10, 2013 at 17:51
• It looks like there was some cheating ... I suppose for the next such competition, one should have salted the input by the submitter's name (or institution domain name, here), so copying other people's result will not help at all :-) May 10, 2013 at 18:00
• One problem I ran into when doing this is that the output of the Skein library I was using Skeinfish wasn't the same as what XKCD reported. They were apparently using PySkein which had a newer tweak to the key schedule constants. It took me a while to figure this out. May 10, 2013 at 18:30

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.

• Your math can't be right, $2^{26}$ is far too low to win such a competition. That's less than a CPU minute on a single core. I'd expect them to easily exceed $2^{40}$. I wouldn't be surprised if they managed $2^{51}$ operations with ATI GPUs. May 10, 2013 at 18:59
• I don't get how you go from $2^{52}$ to $2^{26}$, considering this is a near pre-image, not a near collision. May 10, 2013 at 19:02
• @CodesInChaos, this is good. I need all the checking of my math I can get. You are right, it should be $2^{51}$ for a $.5$ probability. Threw in a little birthday problem math by mistake. May 10, 2013 at 19:25
• Cool! I didn't realize hardware could make all the difference.
– 0xFE
May 10, 2013 at 19:44
• @0xFE, if the problem is massively parallelizable, then hardware can make a huge difference. See cs.rit.edu/~ark/parallelcrypto/sha3test01 for more info (including some code). May 10, 2013 at 19:45

If there was a better known way than brute force, I suppose someone would already have made a paper about this (or lets this be secret to use it for attacks – but then this person wouldn't enter in such a competition).

So it looks like just brute force. Why are these people better than you? Some guesses (and most likely it is a combination of these):

• They use better hardware, maybe optimized to the task.
• They use more hardware in parallel.