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}'
