Brute force http://xkcd.com/1193/

1193.py

#!/usr/bin/env python3

# REQUIRES:
# pyskein http://pythonhosted.org/pyskein/
# python > 3.0 (due to pyskein)
#
# INSTALLATION:
# (install virtualenv)
# (install python3)
# virtualenv -p /path/to/python3 skein
# source skein/bin/activate
# pip install pyskein

import sys
import random
import struct
import string
from skein import skein1024

def hash2bytes(thehash):
    return struct.unpack('128B', bytearray.fromhex(thehash))

THRESHOLD=421                   # from http://almamater.xkcd.com/best.csv (search for usu.edu)
target = '5b4da95f5fa08280fc9879df44f418c8f9f12ba424b7757de02bbdfbae0d4c4fdf9317c80cc5fe04c6429073466cf29706b8c25999ddd2f6540d4475cc977b87f4757be023f19b8f4035d7722886b78869826de916a79cf9c94cc79cd4347d24b567aa3e2390a573a373a48a5e676640c79cc70197e1c5e7f902fb53ca1858b6'
target_bytes = hash2bytes(target)

def sendit(what, offby):
    print ()
    print ('New best hash found!')
    print ('---BEGIN STRING:---')
    print ('%s' % what)
    print ('---END STRING---')
    print ('(should be off by %d)' % offby)
    print ()


def hashdiff(hash_Y_bytes,hash_Z_bytes):
    nbits = 0
    # see how many bits are different
    for Y, Z in zip(hash_Y_bytes, hash_Z_bytes):
        X = Y ^ Z
        while(X):
            X &= X - 1
            nbits += 1
    return nbits

def newstring(strlen,candidate_chars):
    theString = ''.join(random.choice(candidate_chars) for x in range(strlen))
    return theString


print()

best_hash = 1024
min_hash = ''
nattempts = 0
n = 0
candidate_chars = string.printable[:-6]
strlen = 2
attempt = newstring(strlen,candidate_chars)

while True:
    attempt_hash = skein1024(bytes(attempt, 'ascii'), digest_bits=1024).hexdigest()
    attempt_bytes = hash2bytes(attempt_hash)
    d = hashdiff(attempt_bytes,target_bytes)
    if d < best_hash:
        best_hash = d
        min_hash = attempt
        if d < THRESHOLD:
            sendit(attempt,d)
            THRESHOLD = d
    nattempts += 1
    n += 1
    if (n >> 10):
        sys.stdout.write('\r%d hashes compared. Best so far is %d' % (nattempts, best_hash))
        attempt = newstring(strlen-1,candidate_chars)
        n = 0
    attempt = attempt + random.choice(candidate_chars)

1193.sh

while :; do
    rand=$(echo $RANDOM | sha1sum | cut -f1 -d' ')
    len=$(shuf -i 3-31 -n 1)
    try=${rand:$len}
    output=$(curl -s -X POST --data "hashable=$try" http://almamater.xkcd.com/?edu=usu.edu | grep -o 'It is off by .* bits.')
    echo "$try $output"
done | tee -a tries.txt

Yeah, I thought about getting rid of the printable ascii requirement... I just need to see if I can enter non-ascii data on the submit form (if not through the web interface maybe I can make it work with wget)...

UPDATE: All future development will happen here: https://github.com/mgalgs/xkcd-1193

Native C implementation added (at the above URL)