"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 a 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 the 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)

Table of Contents