pCTF 2013 – prove it (misc 150)

We’ve been reading about bitcoins.

We were given a service that asked us to provide an input that would result in an md5 with a given prefix of 52-bits. At first we were looking at modifying an existing GPU cracker to find input resulting in the given prefix. Luckily one of our team members tried a few hashes against a wordlist and noticed he could find some of the in the wordlist.

The answer was using a huge wordlist. We decided to go for the Wikipedia wordlist created by sraveau (http://www.hack3r.com/forum-topic/wikipedia-wordlist). This wordlist contains a huge (750MB) list of words from the English wikipedia. We decided to create a lookup table for these words in python (uses a lot of RAM but after reading the word-list the lookups are almost instant).

import hashlib
h = {}
nr = 0
print "Hashing..."
f = open('wp.txt')
for line in f:
    line = line.strip()
    x = hashlib.md5(line).hexdigest()
    w = x[:13]
    h[w] = line
    nr += 1
    if (nr % 10000) == 0:
        print nr
print "Done"
while True:
    f = raw_input()
    print h.get(f,'Not found')

We ran this on an Amazon GPU cluster instance (which we had already spawned for running the planned GPU cracking anyway). Using this lookup tool solving the challenge was straight forward:

nc 9001
Free Key Distribution Service
Welcome! I am more than happy to give you a key, but you must first prove you did some work!

MD5 Prefix: 1e09bbe921abd
Enter string: ergotropic
Correct! -- Only 19 to go!
MD5 Prefix: 996112bd14241
Enter string: Monegasque
Correct! -- Only 18 to go!
MD5 Prefix: 3d39845fb8996
Enter string: Cyanamid
Correct! -- Only 17 to go!
MD5 Prefix: a8d6d1db92b3b
Enter string: painters
Correct! -- Only 16 to go!
MD5 Prefix: af7e551d04400
Enter string: preemergence
Correct! -- Only 15 to go!
MD5 Prefix: 3f78f74680b9e
Enter string: merriness
Correct! -- Only 14 to go!
MD5 Prefix: c575f20aa68fd
Enter string: signories
Correct! -- Only 13 to go!
MD5 Prefix: 5332c788a7805
Enter string: til
Correct! -- Only 12 to go!
MD5 Prefix: cb9f81491427f
Enter string: seeker
Correct! -- Only 11 to go!
MD5 Prefix: d2b3259467cfd
Enter string: giller
Correct! -- Only 10 to go!
MD5 Prefix: 145c3daa71cfa
Enter string: waistcoated
Correct! -- Only 9 to go!
MD5 Prefix: dbc6d7be820f9
Enter string: predicator
Correct! -- Only 8 to go!
MD5 Prefix: 7efa47b135ea5
Enter string: maimers
Correct! -- Only 7 to go!
MD5 Prefix: 792e5dce80b40
Enter string: sox
Correct! -- Only 6 to go!
MD5 Prefix: b5653da3f6a7d
Enter string: understrapper
Correct! -- Only 5 to go!
MD5 Prefix: 104750e26c896
Enter string: neurectomy
Correct! -- Only 4 to go!
MD5 Prefix: 6a72fa3a4d6b7
Enter string: squabbler
Correct! -- Only 3 to go!
MD5 Prefix: d792fe1c30c6b
Enter string: uncharge
Correct! -- Only 2 to go!
MD5 Prefix: 8c67036439e1a
Enter string: alula
Correct! -- Only 1 to go!
MD5 Prefix: 27fac5a0b93a0
Enter string: invulnerability
Correct! -- Only 0 to go!
FLAG: ricky_mad3_m3_chang3_th3_k3y

Comments are closed.