Xorxes the Hash (Crypto 200)

Task:

Xorxes is a hash collision challenge. The goal is to find a second preimage for the input string "Klaatubaradanikto". Submit it as the flag. UPDATE: It has been pointed out that there are multiple solutions. The flag is the one with md5sum '7179926e4253a0b405090df67f62c543'. (Use `echo -n FLAG | md5sum'.) UPDATE THE SECOND: The solution is short.

http://bostonkeyparty.net/challenges/xorxes-ad7b52380d3ec704b28954c80119789a.py

Solution:

First, take a look on xorxes-hash sript. Inside we can find a comment about xorxes algorithm:

# Xorxes Hash uses message blocks of 8-bits, with a 224-bit chaining variable.
#
#   (m_0)       (m_1)         ... (m_n)  = input message blocks
#     |           |                 |
#   SHA224      SHA224        ... SHA224    
#     |           |                 |
#  V-(+)-[>>>56]-(+)-[>>>56]- ... --+--- = chaining variable 
#
#  chaining variable + (message length mod 24) = hash output
#

You can see, that hash function is very simple. It's just xors SHA224 hash for every byte of message together and shift buffer to the right, after each xoring. We can rewrite function a bit:

Xorxes(m) =R(...R( R(IV + H(m[0]) ) + H(m[1]) )...) + H(m[len(m)-1]) + len%24,

where R is a right shifting, H is a SHA224 hash and + is a xor, m[i] is a i-byte of message. But xoring is a commutative operation and  right shifting is distributive over xor. So we can open bracers and get:

Xorxes(m) = R^len(m)-1(IV) + R^len(m)-1(H(m[0])) + Rlen(m)-2(H(m[1])) + Rlen(m)-3(H(m[2])) + ... + R(H(m[len(m)-2])) + H(m[len(m)-1])

We can also notice, thath R⁴ = R⁰ (cos shifting buffer of length 224  four times to the right equal to not shifting at all), so all addends will be splited in four groups:

Xorxes(m) = {H(m[len(m)-1]) + H(m[len(m)-5]) + ...  } + R({ H(m[len(m)-2]) + H(m[len(m)-6]) + ...  }) + R²({ H(m[len(m)-3) + H(m[len(m)-7]) + ...  }) + R³({ H(m[len(m)-4) + H(m[len(m)-8]) + ...  }) + Rlen(m)-1(IV)

Now it's obvious, that hash doesn't depent on order of bytes of each group in message due to commutativity of xor operation. And message "11112222" will have same hash as "22221111" and "12122121". So we can split bytes of given message and generate new messages as all possible permutation of this bytes inside their own groups. Thoose new messags will ahve same hash like original messages. And then we must find one message with md5 hash '7179926e4253a0b405090df67f62c543'.

So let's do some python here:

#!/usr/bin/python
import itertools
import hashlib
import sys

MD5 = '7179926e4253a0b405090df67f62c543'

group1 = "Ktrno"
group2 = "luai"
group3 = "abdk"
group4 = "aaat"

all_variants = 24*24*24*120
count = 0

for g1 in itertools.permutations(group1):
	for g2 in itertools.permutations(group2):
		for g3 in itertools.permutations(group3):
			for g4 in itertools.permutations(group4):
				result = ''
				for i in xrange(0,17,1):
					if i%4 ==0:
						result+=(g1[i/4])
					if i%4 ==1:
						result+=(g2[i/4])
					if i%4 ==2:
						result+=(g3[i/4])
					if i%4 ==3:
						result+=(g4[i/4])
				md5 = hashlib.new('md5')
				md5.update(result)
				hashed = md5.hexdigest()
				if hashed == MD5:
					print "Flag: " + result
					exit(0)
	count+=13824
	sys.stdout.write( "Progress: " + str(100*count/all_variants) + "%\r" )
	sys.stdout.flush()

It takes some time to generate all possible 4!*4!*4!*5! = 1658880 variants, but after several seconds we get a flag: radaniktKlaatubao

Flag: radaniktKlaatubao