WOTS Up 2

I fixed the problem with my last scheme, now I can confidently sign my WOTScoin transactions.

Challenge contributed by CryptoHack

Challenge files:

• data.json
• chal.py

This is another challenge that implements WOTS (more information at www.codingninjas.com).

Source code analysis

The Winternitz class is a bit different from the first part of the challenge, in the keys generation:

class Winternitz:
    def __init__(self):
        self.priv_key = []
        for _ in range(KEY_LEN):
            priv_seed = urandom(KEY_LEN)
            self.priv_key.append(priv_seed)
        self.gen_pubkey()

    def gen_pubkey(self):
        self.pub_key = []
        for i in range(KEY_LEN):
            pub_item = self.hash(self.priv_key[i])  
            for _ in range(BYTE_MAX):
                pub_item = self.hash(pub_item)
            self.pub_key.append(pub_item)

    def hash(self, data):
        return hashlib.sha256(data).digest()

Now, each element of the private keys list is a 32-byte random value. Then, each element of the public key is the $\mathrm{SHA256}^{(256)}$ hash of each element of the private key list. Again, it is not easy to find the private keys from the public keys.

This time, we are given a total of $20$ messages and signatures, and we are required to sign another message to build an AES key to decrypt the flag:

if __name__ == "__main__":
    w = Winternitz()

    output = {
        "signatures": []
    }

    for i in range(20):
        message = f"{w.pub_key[0].hex()} sent {int.from_bytes(urandom(1))} WOTScoins to {urandom(32).hex()}".encode()  
        signature = w.sign(message)
        assert w.verify(signature, message)
        output["signatures"].append({
            "message": message.decode(),
            "signature": [s.hex() for s in signature],
        })

    message2 = f"{w.pub_key[0].hex()} sent 999999 WOTScoins to me".encode()
    signature2 = w.sign(message2)
    assert w.verify(signature2, message2)

    with open("flag.txt") as f:
        flag = f.read().strip().encode()

    aes_key = bytes([s[0] for s in signature2])
    aes_iv = urandom(16)
    cipher = AES.new(aes_key, AES.MODE_CBC, aes_iv)
    encrypted = cipher.encrypt(flag)

    with open("data.json", "w") as f:
        output["public_key"] = [s.hex() for s in w.pub_key]
        output["iv"] = aes_iv.hex()
        output["enc"] = encrypted.hex()

        f.write(json.dumps(output))

In this challenge, we will need to exploit the signature algorithm, which is exactly the same as before:

    def sign(self, data):
        data_hash = self.hash(data)
        data_hash_bytes = bytearray(data_hash)  
        sig = []
        for i in range(KEY_LEN):
            sig_item = self.priv_key[i]
            int_val = data_hash_bytes[i]
            hash_iters = BYTE_MAX - int_val
            for _ in range(hash_iters):
                sig_item = self.hash(sig_item)
            sig.append(sig_item)
        return sig

Breaking WOTS algorithm

Given the fact that WOTS stands for Winternitz One-Time Signature, and we have $20$ signatures with the same private key, it should be feasible to break the algorithm.

The signature works as follows. Let’s take the first message as example:

$ echo -n "6df32bef41a3a6242af1702da255d01baf84ebcf9a6a310d8ca90760c0579f28 sent 53 WOTScoins to 25c6c68522eec18d2f68ba962170745ff009c63f49746cefd5ff020bb1b062dc" | sha256sum  
db72f2691dd68b04db5f5bb23632294d9a0c3d741ac3366ac7a11b0df5fa1847  -

The algorithm takes each byte of the hash and does the following:

$$ \begin{cases} h_1 = \mathrm{0xdb} &\Rightarrow 255 - \mathrm{0xdb} = 36 &\Rightarrow s_1 = \mathrm{SHA256}^{(36)}(k_1) \\ h_2 = \mathrm{0x72} &\Rightarrow 255 - \mathrm{0x72} = 141 &\Rightarrow s_2 = \mathrm{SHA256}^{(141)}(k_2) \\ h_3 = \mathrm{0xf2} &\Rightarrow 255 - \mathrm{0xf2} = 13 &\Rightarrow s_3 = \mathrm{SHA256}^{(13)}(k_3) \\ h_4 = \mathrm{0x69} &\Rightarrow 255 - \mathrm{0x69} = 150 &\Rightarrow s_4 = \mathrm{SHA256}^{(150)}(k_4) \\ \dots \\ h_{32} = \mathrm{0x47} &\Rightarrow 255 - \mathrm{0x47} = 184 &\Rightarrow s_{32} = \mathrm{SHA256}^{(184)}(k_{32}) \end{cases} $$

Recall that the objective is to find the signature of a given message.

The signature algorithm is not so secure when used several times. Imagine that we want to sign a message and the first byte of the SHA256 hash starts with 0xda. Since we already know the above value $s_1 = \mathrm{SHA256}^{(36)}(k_1)$, that corresponds to $h_1 = \mathrm{0xdb}$, if we were to sign 0xda, we only need to hash once more. Inductively, we could be able to sign message hashes that start with a byte less than or equal to 0xdb, by iterating SHA256 hashes.

As a result, we will take the hash of the message we are required to sign and then find large values for each hash byte among the $20$ messages we are given. Once we have one, we can find the expected signature for each byte.

Flag

Eventually, we will have the expected signature and we will be able to build the AES key to decrypt the flag.

$ python3 solve.py
ECSC{0ne_m0r3_t1m3_s1gn4tur3_ff}  

The full script can be found in here: solve.py.