Rating:
# OTS (crypto, 104+1p, 51 solved)
Once we connect to the server we get [code](https://raw.githubusercontent.com/TFNS/writeups/master/2020-05-09-SpamAndFlags/code.py), public key, message and signature, and we're asked to provide new message containing word `flag` and valid signature.
## Overview
The algorithm is pretty easy to follow:
1. There are 128 chunks of 16 bytes randomly generated to server as key.
2. Message is padded with lots of zeros and md5 checksum of the message is appended at the end, so that the total message length is exactly 128 bytes.
3. For `i from 0 to 128` take byte `message[i]` and key chunk `key[i]`, now turn the message byte into an integer `xi` according to ascii table, and perform `255-xi` times `md5` hash recursively on the key chunk, as in `md5(md5(md5(...(md5(key[i])))))`.
4. Such generated md5 checksum is appended to the signature.
The `public key` in this case is just secret key chunks hashed in this way 255 times for each block, the same as if you hashed a message containing only zero bytes.
The signature verification takes the message and the signature, and performs similar hashing, but this time of the signature blocks instead of secret key, and hashes `xi` times instead of `255-xi`.
The point is that by doing this, each secret key block gets hashes exactly `255` times, since it was `255-xi` when generating the signature, and `xi` when doing verification, so in total just `255`.
And this should be equal to the public key.
## Vulnerability
Just by looking at the verification logic it should instantly be obvious what the problem is.
If we change `k-th` byte in the message from `b` to `a` then the verification procedure will perform one `md5` operation less than it should on the signature block, but we can apply `md5` on the `k-th` signature block ourselves!
This will cause this signature block to be valid for the new message.
Notice that we can only flip downwards, we can change `b` to `a` but not `a` to `b`, because we can hash only forward.
There is also one small problem: the whole message checksum is added at the end of the message.
If we flip `k-th` byte from `b` to `a` then the entire checksum will change!
So not only we need to flip the `k-th` signature block by applying one more `md5`, but we also need to somehow fix the last 16 signature blocks corresponding to the checksum.
It's easy to notice that in fact this is exactly the same issue - we know the checksum of original message and we want to change it to something else and then `flip` the signature blocks by applying proper number of `md5`, so the signature is valid.
The trick is, as mentioned above, that we can only flip downwards.
This means that our new checksum for the message needs to have each corresponding byte smaller than the checksum of original message:
```python
def is_ok(original_hash, new_hash):
valid_ones = 0
for a, b in zip(original_hash, new_hash):
if a >= b:
valid_ones += 1
return valid_ones == 16
```
Fortunately the original message is long and we can randomly flip all bytes (except for the `flag` word we need) and check if the new checksum is nice or not.
## Solution
We proceed as follows:
- Original message is something like `My favorite number is 688915709066267095."`, we can flip `vori` to `flag` because each target byte is smaller than original one.
- Now we want to flip all other character to some random smaller bytes, and calculate the checksum.
- We can then verify if the new md5 checksum we got has each byte smaller than the original md5 of the message did.
- If not, then we repeat steps 2 and 3. Once we finally found valid checksum we proceed further.
- Now we have a new message, we can append new md5 checksum at the end.
- Finally we can go over the message, calculate the difference between `k-th` byte of the original message and `k-th` byte of new message, and apply `md5` that many times on the `k-th` signature block.
```python
def solve(msg, signature):
original_msg = msg[:]
original_hash = calculate_hash(msg)
msg = list(msg)
for idx, char in zip([5, 6, 7, 8], 'flag'):
msg[idx] = char
new_msg = flip_hash(msg, original_hash)
new_sig = fix_signature(wrap(original_msg), signature, wrap(new_msg))
return new_msg, new_sig.hex()
def flip_hash(msg, original_hash):
while True:
nice_msg = msg[:]
for idx in range(len(nice_msg)):
if idx in [5, 6, 7, 8]:
continue
to = random.randrange(ord(' '), ord(nice_msg[idx]) + 1)
nice_msg[idx] = chr(to)
current_msg = "".join(nice_msg)
current = calculate_hash(current_msg)
if is_ok(original_hash, current):
print(current_msg)
break
return current_msg
def fix_signature(original_msg, signature, new_msg):
signature = binascii.unhexlify(signature)
c = chunk(signature, 16)
for i in range(len(original_msg)):
c[i] = flip_block(c[i], original_msg[i], new_msg[i])
return b''.join(c)
def calculate_hash(msg):
raw = msg.encode('utf-8')
raw = raw + b'\x00' * (128 - 16 - len(raw))
return hashlib.md5(raw).digest()
def wrap(msg):
raw = msg.encode('utf-8')
raw = raw + b'\x00' * (128 - 16 - len(raw))
raw = raw + hashlib.md5(raw).digest()
return raw
```
We connect to the server, provide new message and signature and get flag:`SaF{better_stick_with_WOTS+}`
Complete solver [here](https://raw.githubusercontent.com/TFNS/writeups/master/2020-05-09-SpamAndFlags/ots.py)
