py4h4sher_solution.py

#!/usr/bin/python
# coding: utf-8

'''
Here is only explanation how I find stage1 data (stage2 and stage3 are same
as others).

stage1 wants us to find the data that mysql323 hash of it is 'AAAAAAAA'.
For each byte, the hash is computed as below. 'nr' is first 4 bytes.
'nr2' is last 4 bytes.

    unsigned int tmp = pass[i];
    nr ^= (((nr & 63)+add)*tmp)+ (nr << 8);
    nr2 += ((nr2 << 8) ^ nr);
    add += tmp;

The differences between this challenge and mysql323 hash are
- '\x00' is not end of string in this challenge. we can use it.
- the data size of this challenge is limited by post data size (~20M should be fine)

If we use '\x00' ('tmp' is 0), the 'nr' value is simply computed as below

    nr ^= (nr << 8);

The computation is only shift and xor. If 'nr' is computed like this 4 times,
it goes back to first value. This is useful because we can maintain 'nr' value
while 'nr2' value is changed.

So my idea is
- find the data that make 'nr' value to 'AAAA' (0x41414141)
- then append '\x00\x00\x00\x00' until 'nr2' is 'AAAA'

The problem left is
- while 'nr' is 'AAAA', nr2 value cannot be 'AAAA' no matter how many
  '\x00\x00\x00\x00' is appended
- the trail zeros might be too long for post data

I solved above problems by using lookup table. Before bruteforcing, I
pre-computed the possible 'nr2' that can be changed to 'AAAA'. I also
limits the trailing zeros to 16M.

Done!!.

First time I ran the program, I found 'eed70d1019' with 4016703 (~4M) zero
within a minute. I got flag with this data. Then, I tried change start
'pass_len' and run program with a few minutes with each value. I found
not too long zero ('4c5ac816000000007e' with 62131 zero)

Below is python code for post data.
'''

import httplib

headers = {
    'User-Agent': 'plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd'
}

conn = httplib.HTTPConnection("203.66.14.43", 80)

params = 'checksum=af247ce6e8c70768eae27ec6feae34f6&mode=a&stage1='
#params += 'eed70d1019'.decode('hex')+'\x00'*4016703
#params += 'e2b52d160021'.decode('hex')+'\x00'*1422017
params += '4c5ac816000000007e'.decode('hex')+'\x00'*62131
params += '&stage2=eBkXQTfuBqp%27cTcar%26g*&stage3=e&stage3=n&stage3=0&stage3=i&stage3=0&stage3=gma'

conn.request("POST", "/cgi-bin/py4h4sher?filename=py4h4sher&mode=download", params, headers)
resp = conn.getresponse()
print resp.status
data = resp.read()
print data

"""
Congrat! The flag is HITCON{th1s_1s_bas1c_cha11enge_f0r_p3nt3st3r!}
"""