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:

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 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 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 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.