DiceCTF 2024 - winter

This is the solution of the challenge “winter” from Dice CTF. Winternitz signature allowing to forge a signature from a previous valid signature.

Details

Author: defund

Points: 116

Description

A simple implementation of the Winternitz signature scheme.

1

nc mc.ax 31001

Downloads server.py

Solution

The scheme is a Winternitz signature. It should used only to sign a single message but here we are allowed to sign two of them. The message is hashed with SHA256. Then each byte is taken individually and interpreted as integer $n_0, n_1, …, n_{256}$

Each private key $q_0, q_1, …, q_{256}$ is iteratively hashed to obtain the signature $s_0, s_1, …, s_{256}$:

$$s_i = H^{256-n_i}(q_i)$$

The first signature is returned to us. Thus if we are able to find two messages $m_1$ and $m_2$ such that each bytes of the hash $h_1$ of $m_1$ are less than each bytes of the hash $h_2$ of $m_2$ we can forge a new signature by computing:

$$\tilde{s_i} = H^{\tilde{n_i}-n_i}(s_i)$$

To find such message I decided to used Bitcoin blocks which have a lot of null bytes, it would allow to reduce the search space. Then I iterated over bitcoin blocks until I found one with a maximum byte value not too high:

1
2
3
4
5
6
7

for i in range(828930,0,-1):
    height = i
    url = "https://blockchain.info/block-height/" + str(height) + "?format=json"
    response = json.loads(urlopen(url).read())
    h = bytes.fromhex(response['blocks'][0]['hash'])
    print(h.hex())
    print(max(list(h)))

It turns out that block 000000000000000000035796cb87b186324e5b0620312c413b9472895f302667 was a good candidate. I found the corresponding message with a tool I wrote previously:

1
2
3
4

python bitcoinHash.py -v -u  https://blockchain.info/rawblock/000000000000000000035796cb87b186324e5b0620312c413b9472895f302667

7d72cd3f54b8764df2a80a5253dbef5a9a7faf0329aa4664c30aaac5cbb0c4d5
6726305f8972943b412c3120065b4e3286b187cb965703000000000000000000

Then we need to find another message with the each hash byte bigger the the previous hash:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

m2 = bytes.fromhex("7d72cd3f54b8764df2a80a5253dbef5a9a7faf0329aa4664c30aaac5cbb0c4d5")
h1 = sha256(new_m).digest()
i = 0
while True:
    h2 = sha256(i.to_bytes(8)).digest()

    smaller = True
    for b in range(31,-1,-1):
        if h2[b] < h1[b]:
            smaller = False
            break
            
    if smaller:
        print(i.to_bytes(8).hex())
        break
    i += 1

m1 = i.to_bytes(8)

Now from the signature returned by the server we can forge a new signature for our message:

1
2
3
4
5
6

chunks = [sig[i:i+32] for i in range(0, len(sig), 32)]    
h1 = hash(m1, 1)
h2 = hash(m2, 1)

m = [i-j for i, j in zip(m1, m2)]
sig = b''.join([hash(x, n) for x, n in zip(chunks, m)])

Finally the server accepts the signature and prints the flag:

1

b' dice{according_to_geeksforgeeks}\n'