WOTS Up 2
4 minutes to read
I fixed the problem with my last scheme, now I can confidently sign my WOTScoin transactions.
Challenge contributed by CryptoHack
Challenge files:
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
This time, we are given a total of
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
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:
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 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
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
.