# "OTS" crypto task

The SpamAndFlags CTF 2020 took place last week and I managed to solve some tasks
from the crypto category. One of them was the "OTS" task, which name probably stands
for *One Time Signatures*.

## Task

After establishing TCP connection we could see:

```
class OTS:
def __init__(self):
self.key_len = 128
self.priv_key = secrets.token_bytes(16*self.key_len)
self.pub_key = b''.join([self.hash_iter(self.priv_key[16*i:16*(i+1)], 255) for i in range(self.key_len)]).hex()
def hash_iter(self, msg, n):
assert len(msg) == 16
for i in range(n):
msg = hashlib.md5(msg).digest()
return msg
def wrap(self, msg):
raw = msg.encode('utf-8')
assert len(raw) <= self.key_len - 16
raw = raw + b'\x00'*(self.key_len - 16 - len(raw))
raw = raw + hashlib.md5(raw).digest()
return raw
def sign(self, msg):
raw = self.wrap(msg)
signature = b''.join([self.hash_iter(self.priv_key[16*i:16*(i+1)], 255-raw[i]) for i in range(len(raw))]).hex()
self.verify(msg, signature)
return signature
def verify(self, msg, signature):
raw = self.wrap(msg)
signature = bytes.fromhex(signature)
assert len(signature) == self.key_len * 16
calc_pub_key = b''.join([self.hash_iter(signature[16*i:16*(i+1)], raw[i]) for i in range(len(raw))]).hex()
assert hmac.compare_digest(self.pub_key, calc_pub_key)
pub_key = d371b666137bfc0c...<truncated>
sign("My favorite number is 13316916219201846131.") = 0975b6f540249f2d...<truncated>
Your turn! Sign a message that contains "flag" with the same key!
Enter the message:
```

## Solution

### First thoughts

So the signing class operates on 16-byte chunks of the private key individually.
During signing each byte of the *wrapped* message defines number of `MD5`

iterations applied
on the corresponding chunk of the private key. The cryptographic power of this system clearly
must lie in the hashing function's *one-way property*. Even the broken `MD5`

hashing function
cannot be cracked with a feasible amount of time and resources during a CTF competition,
especially when iterated like here.

### Easier version

Let's first solve this task without `MD5`

hash appended to the wrapped message. Then we can
almost fully control the number of `MD5`

iterations for each chunk simply by changing the
corresponding byte of our message. It means that if we set the $$i$$-th byte of our message
to have smaller or equal value than the $$i$$-th byte of the message "`My favorite number is 13316916219201846131.`

"
(which has known signature), then we can forge the $$i$$-th chunk of our signature simply by
iterating `MD5`

on the $$i$$-th chunk taken from the signature of "`My favorite number is 13316916219201846131.`

".
Our goal is to insert the "`flag`

" sequence to the message and provide its signature.
Luckily enough, the original message contains "`vori`

" subsequence, which has greater byte values
than "`flag`

" at every position.

### The MD5 hash

That would be the end of the easier version, but unfortunately there is the `MD5`

hash appended to the
wrapped message, what means that the 16-byte suffix will randomly change after every modification
of the original message. That random hash doesn't have to have convenient, smaller byte values than
the original message's hash... but there is a chance that it has!

#### Probability!

Let's calculate the probability that the random hash will have smaller (or equal) byte values at
every position than the hash of wrapped "`My favorite number is 13316916219201846131.`

", which
is equal to `18a619792e726474722836508c0d5e6d`

. This probability is equal to
\[
p = \prod_{i=0}^{15} \frac{b_i}{2^8}
\]
where $$ b_i $$ is the value of $$i$$-th byte of the original hash.
In our case it's equal to something around $$ 10^{-9} $$, so the chances
are quite small. Fortunately we can modify bytes other than the `vori`

sequence
(which should be replaced with `flag`

) to have smaller byte values. In this way
we can obtain different messages containing "`flag`

" subsequence with different hashes.
After $$10^9$$ tries probability that we didn't obtain
desired hash value is roughly equal to:
\[
(1 - p)^{10^9} \approx 0.36
\]
As $$10^9$$ tries are feasible with efficient implementation,
it looks like we've got a working solution.

##### Note

It's worth mentioning that after every reconnect we received different signed message (the number at the end differed), what meant that the appended hash could have been different and more convenient, i.e. sometimes it had significantly greater byte values, what makes the probability of winning greater (and number of tries smaller). I managed to hit the desired hash after $$\sim1000$$ tries.

### Code

Working, ad-hoc solution written in Rust (~120 lines)