Tags: hashing crypto

Rating: 4.5

# Easy Hash (easy)

## Given file and prompt


Source Code: easy_hash.7z
Web Server: https://crypto01.chal.ctf.westerns.tokyo

For beginners: you can use curl to interact with the web server.

(Example)
\$ curl https://crypto01.chal.ctf.westerns.tokyo -d 'twctf: hello 2020'


python
import struct
import os

MSG = b'twctf: please give me the flag of 2020'

assert os.environ['FLAG']

def easy_hash(x):
m = 0
for i in range(len(x) - 3):
m += struct.unpack('<I', x[i:i + 4])[0]
m = m & 0xffffffff

return m

def index(request):
message = request.get_data()
if message[0:7] != b'twctf: ' or message[-4:] != b'2020':
return b'invalid message format: ' + message

if message == MSG:
return b'dont cheet'

msg_hash = easy_hash(message)
expected_hash = easy_hash(MSG)
if msg_hash == expected_hash:
return 'Congrats! The flag is ' + "HERE IS THE FLAG"
return 'Failed: easy_hash({}) is {}. but expected value is {}.'.format(message, msg_hash, expected_hash)


## Approach

I had two approach to this:

- Like MD5, possibly trying to find a collision of the hash (the desired value was 1788732187)
- Finding a character that wouldn't change the hash

### Finding a colision

I tried first to brute force this using the same method as MD5 collision but this took too long and I abandoned.
While I do believe that there is a string that will collide and equal the one that we want in value, there was a faster approach.

### A character that wont affect the hash

The function to calculate the hash is the following:

python
def easy_hash(x):
m = 0
for i in range(len(x) - 3):
m += struct.unpack('<I', x[i:i + 4])[0]
m = m & 0xffffffff

return m


It takes a window of 4 characters and unpacks their value with little endian and unsigned integer and sums them all to mod 0xffffffff. Our goal is to then add one character that would have value of 0 when its unpacked. We can reverse this by using:

python
import struct
struct.pack('<I', 0) #==> b'\x00\x00\x00\x00'


Thus adding the character \x00 to the string b'twctf: please give me the flag of 2020' would make it different from the message while retaining the hash.

## Solution

Using the python command line:

python
import requests

r = requests.post('https://crypto01.chal.ctf.westerns.tokyo', data=b'twctf: please give me the flag of \x002020')
print(r.text) # 'Congrats! The flag is TWCTF{colorfully_decorated_dream}'


## Flag

'Congrats! The flag is TWCTF{colorfully_decorated_dream}'

Original writeup (https://susanou.github.io/CTFWriteups/posts/easy_hash/).