WOTS Up

With the need to find post-quantum schemes, hash-based signatures are cool again.

Challenge contributed by CryptoHack

Challenge files:

• data.json
• chal.py

We are given a class called Winternitz that implements some sort of signing protocol based on SHA256 hashes. Actually, WOTS stands for Winternitz One-Time Signature and it is a post-quantum signature algorithm, which is perfectly explained at www.codingninjas.com.

Source code analysis

First of all, the class creates a list of private keys:

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

    # ...

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

Private keys

As can be seen, the first private key of the list is the SHA256 hash of a 32-byte random value, but the next 31 private keys are the SHA256 hash of the previous one:

$$ k_{i} = \mathrm{SHA256}(k_{i - 1}) = \mathrm{SHA256}^{(i - 1)}(k_1) \quad \forall i = 2, 3, \dots, 32 $$

Public keys

Then, the public key is generated in a similar way:

    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)

Basically, it takes each private key and hashes it a total of $256$ times. So, it is nearly impossible to get the private keys from the public keys, at least with this information.

Encryption

The challenge signs a message and gives us the signature. Then it signs another message and uses the signature to create an AES key to encrypt the flag:

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

    message1 = b"WOTS Up???"
    signature1 = w.sign(message1)
    assert w.verify(signature1, message1)

    message2 = b"Sign for flag"
    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:
        f.write(json.dumps({
            "public_key": [s.hex() for s in w.pub_key],  
            "message": message1.decode(),
            "signature": [s.hex() for s in signature1],
            "iv": aes_iv.hex(),
            "enc": encrypted.hex(),
        }))

We know both messages, but we are only given the signature of the first message.

Signature algorithm

The signature algorithm works as follows:

    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

It takes the hash of the message to sign, and takes the bytes of the hash (data_hash_bytes). Then, with each private key (sig_item), it uses a value hash_iters = BYTE_MAX - int_val to hash sig_item a total of hash_iters times. The result is appended to the signature list.

As a result, a signature for a message is a list of $32$ hashes, that correspond to some iterated hash of each private key.

Solution

There might be a better way to solve this challenge (maybe addressed in WOTS up 2), but it happens that the SHA256 hash of "WOTS Up???" starts with ff:

$ echo -n 'WOTS Up???' | sha256sum
ff3ae04c073c4d935ab9f42271795cdaf537b2c619aeedf0b92f3de17b33fd95  -  

This means that the first element of the signature list is just the first private key, since hash_iters = 255 - 255 = 0, so there is no hash at all.

And remember how the private keys were constructed. Since we have the first one, we can find all $32$ private keys by induction and therefore sign the second message.

Flag

Once having the expected signature, we can find the AES key and find the flag:

$ python3 solve.py
ECSC{h4sh1ng_ch41n_r34ct1on_ff_}  

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