Easy Hash (easy)
Given file and prompt
1
2
3
4
5
6
7
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'
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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:
1
2
3
4
5
6
7
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:
1
2
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:
1
2
3
4
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}’