7
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – JZeolla
    Commented May 10, 2013 at 16:47
  • $\begingroup$ Some background. $\endgroup$
    – Paŭlo Ebermann
    Commented May 10, 2013 at 17:51
  • $\begingroup$ 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 :-) $\endgroup$
    – Paŭlo Ebermann
    Commented May 10, 2013 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – mikeazo
    Commented May 10, 2013 at 18:30

2 Answers 2

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Commented May 10, 2013 at 18:59
  • 2
    $\begingroup$ I don't get how you go from $2^{52}$ to $2^{26}$, considering this is a near pre-image, not a near collision. $\endgroup$
    – CodesInChaos
    Commented May 10, 2013 at 19:02
  • $\begingroup$ @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. $\endgroup$
    – mikeazo
    Commented May 10, 2013 at 19:25
  • $\begingroup$ Cool! I didn't realize hardware could make all the difference. $\endgroup$
    – 0xFE
    Commented May 10, 2013 at 19:44
  • $\begingroup$ @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). $\endgroup$
    – mikeazo
    Commented May 10, 2013 at 19:45
4
$\begingroup$

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.
  • They had some luck.

The task of finding a low-hamming-distance match to a given hash is embarrassingly parallel. Individual threads/processes/... don't have to communicate, just try random (or serial) values and calculate the hash, and occasionally report their minimum-distance results back to a central instance, which reports the overall minimum values back to the user.

So if you have a GPU with some 100 cores, you can let all of them work in parallel to find matches. If you have a whole computer pool full with computers with GPUs which do not much else the whole day, it gets proportionally faster. Add some big iron super computers (what universities often have) to the mix, and you are done.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.