We were given a Haskell source for a cryptographic cipher. The task was to find a collision with a given key, which was "Le1sRI6I". First we wanted to identify the cipher to see if it's an already existing one. By googling the hex version of the integer constants (2654435769, 3337565984) we found that this is most probably the xTea cipher.
First we were trying to bruteforce the collision, but we were looking at it the wrong way. However, we found something important when playing with the haskell code -- the cipher only uses the first 4 characters from the key.
After inspecting the source in detail we found that the "hash" function of the code is not used anywhere, and this gave us a clue. We translated the haskell version to python:
def hash(passwd): acc = (1, 0) for x in passwd: (a, b) = acc acc = (a + ord(x), a + b + ord(x)) (a, b) = acc return a | (b << 16)
All this function does is collecting the sum of ASCII values into one part of the tuple, and collecting another aggregate value into the other. It is quite easy to find a collision for this. This is the bruteforce approach:
def brute(): arr = string.ascii_letters + string.digits for x in arr: for y in arr: for z in arr: for w in arr: s = "%c%c%c%c" % (x,y,z,w) if hash(s) == hash("Le1s"): print s
This gave us a list of around 1000 possible keys. Then we wrote a function that evaluates the resulting key by executing the Haskell binary (that we compiled from the source) and checking the number of ASCII characters in the deciphered result:
for pwd in passwords: process = Popen(['./pwd_check', pwd], stdout=PIPE) stdout, stderr = process.communicate() dat = stdout hex_str = "%x" % (int(dat)) if len(hex_str) % 2 != 0: hex_str = "0" + hex_str res = unhexlify(hex_str) score = 0 for ch in string.ascii_letters + string.digits + " _": if ch in res: score += 1 if score > 5: print res
And after running this, we got the key straight away:
Thanks again to the FluxFingers team for the nice challenges.