So the April 1, 2013 xkcd Externalities web comic features a Skein 1024 1024 hash breaking contest. I'm assuming that this must be nothing more than a brute force effort where random strings are hashed in an effort to match Randall's posted hash? Is this correct?

Also, my knowledge of Skein hashing theory is virtually non-existent but being a halfway decent programmer I was able to download and run both SkeinFish (C#) and Maarten Bodewes Skein implementation (Java) locally in 1024 1024 mode with some input strings. The hashes that they gave, however, were different than the hash that xkcd returned for the same input. This may be an extremely naive question but do different Skein implementations give different hashes? And what Skein implementation is xkcd using?

Thanks for pardoning my ignorance!

  • I have the same questions. I found this script which someone wrote for this contest. It generates random input and hashes it. I am walking through the code right now trying to understand it. Hopefully someone answers your question! github.com/dghubble/xkcd-hashing/blob/master/main.py – Jefferson Hudson Apr 2 '13 at 16:37
  • 4
    @JeffersonHudson OMG brute force. I was wondering what was this burning CPU smell this morning. While 36,000$ were donated to Wikipedia, electric companies got a 200,000$ income increase. – gawi Apr 2 '13 at 16:58
  • The perl and Haskell versions yield different results too. Maybe that's part of the April's fool joke. – gawi Apr 2 '13 at 16:59
  • 2
    @JeffersonHudson pythonhosted.org/pyskein is working for me. POSTing guesses is most definitely not the way to do it, unless you are counting on getting VERY lucky. – adotout Apr 2 '13 at 19:22
  • 1
    The one from Maarten Bodewes is hopelessly out of date as he was too busy answering questions on Stackoverflow. Sorry about that :) – Maarten Bodewes Apr 8 '13 at 22:44
up vote 11 down vote accepted

There are several different iterations of the skein algorithm. XKCD is using version 1.3, which is also the most recent. Sources can be found here (look for "V1.3")

Interestingly enough, this brute-force method is the same one employed by Bitcoin to "mine" bitcoins. The big differences are the hash algorithm (SHA-256 in that case) and the target hash (which is dynamically determined to be any hash starting with a certain number of zeros.) It takes a lot of work to discover the hash, but once it has been found it is trivial to verify the source bits and that the resulting hash meets the criteria.

  • SkeinFish is version 1.3 but still gives a different result. – Tom Apr 2 '13 at 23:19
  • 3
    @Tom I used SkeinFish for some of the cracking, and it worked fine as long as you initialize it with the right magic value:var skein = new Skein1024(); skein.Initialize(SkeinInitializationType.Normal); – cobbal Apr 6 '13 at 0:22

Here's the source code the Stanford team used. We ran this on about a hundred 8-core EC2 servers for a while, but not the whole competition.

https://github.com/jhiesey/skeincrack

If you were hashing non-alphanumeric characters (spaces, punctuation, etc.), you may have been getting different results due to HTML form encoding. The "enctype" attribute on the form XKCD was hosting was "application/octet-stream", which according to https://developer.mozilla.org/en-US/docs/HTML/Element/form is not a browser-supported standard. I assume the browser falls back on the URL-encoding type when it sees one it doesn't recognize.

I observed the string "=" being submitted URL-encoded in Chrome, and returning a different hash than what I got locally with the latest pyskein. But when I submitted it with this curl command line (no longer works), I got the expected hash:

curl -X POST --data-binary "hashable==" "http://almamater.xkcd.com/?edu=school.edu"

The Stanford code in another answer does the same thing, and they apparently had some success. I never got any random data to locally hash to a better score than even my own school, so I never got a chance to test thoroughly how to pass arbitrary data in properly. I don't know what the exact behavior was (e.g., perhaps if you omitted hashable= the server would detect that and just hash the whole POST body), but it may have intentionally been a little tricky as part of April Fool's.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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