Winternitz One-Time Signature(OTS)

2024, May 30

Introduction
- General description
  - Winternitz parameter (w)
- Hash chain
Schema
Operation
Checksum
- Details
Use
Security
WOTS+
Reference

Faced with the threat of quantum computers (not yet current), there are many supposedly quantum-resistant cryptographic algorithms.

One of them is the algorithm Winternitz One-Time Signature (W-OST)

Winternitz is considered quantum safe since its security is not based on a difficult problem like the logarithm discrete, but relies on hash function (e.g SHA-256). In short, it consists of computing each element in a chain by hashing the previous element.

W-OTS iteratively applies a function on a secret input, the private key, whereas the number of iterations depends on the message to be signed.

Unlike traditional signature schemes that use a single private key for multiple signatures, Winternitz OTS generates a new private key for each signature. Therefore, a private key can only be used one time reason why they are called One-Time signature.

I am not totally sure about the source, but it seems It was introduced by Robert Winternitz in 1982.
It is an extension of the Lamport one-time-signature scheme which offers the possibility to decide how many bits will be signed together.
In short, W-OTS iteratively applies a function on a secret input, the private key, whereas the number of iterations depends on the message to be signed.

Reference: 1. eprint.iacr.org/2011/191.pdf, 6. sphere10.com, github.com/ - Winternitz one time signature

[TOC]

Introduction

General description

Winternitz are One-time Signatures, meaning that a privite key can only be used to create one signature
They are slower than Lamport signature, but it uses smaller keys.
Winternitz works on element of 256 bits, for example a 256-bit hash of a message
- For example, the 256-bit hash can be produced with SHA-256.
Winternitz does not sign bit by bit, but sign bytes
Private key is a set of 32 seeds (sk0).
Public key is a set of 32 values (pk). This is also the last value computed with the different hash operation.
Signatures are (32 + checksum) elements.
Storing all lists makes too large keys → compute them on the fly using the hash function.
Add a checksum since the final secret list is the public key.

Winternitz parameter (w)

The Winternitz parameter (w) defines the amount of numbers those bits can represent (w = 2^{bits}).

Winternitz OTS introduces a parameter w, which controls the trade-off between the size of the signature and the efficiency of the signing process. The parameter w is referred to as the Winternitz parameter and affects the signature in two ways:

A larger value of w results in shorter signatures but slower overall signing operations; it has little effect on security.
A big w makes for a small sequence of big numbers, a small w makes a big sequence of small numbers. Bigger sequences (so a small wtend to result in bigger signatures. Bigger numbers increase the amount of hashes you need to calculate.
In WOTS+, according to the XMSS RFC, choices of w are limited to the values 4 and 16 since these values yield optimal trade-offs and easy implementation.

See crypto.stackexchange.com - Winternitz Parameter in WOTS+ and XMSS and XMSS - rfc8391

Hash chain

Winternitz is based on the concept of hash chain

It consists of computing each element in a chain by hashing the previous element.

[\begin{aligned} X_i = HASH(X_i−1) \end{aligned}]

Only need to know starting value–can compute all other
You can’t go backward in chain because of preimage resistance, a propriety of the hash function used.

Schema

Reference: asecuritysite.com/hashsig/wint

schema

Operation

The algorithm generates a pair of private/public keys.

Private key generation

It generates 32x256-bit random private keys.

We then hash these keys several times, and is defined by a parameter (w)

Public keys

If we use w=8, we hash the private keys by (2^w).

This creates 32x256 bits public keys.

Signature

The signature is then created by taking eight bits at a time,

A) The message is hashed using SHA-256. This produces 32x 8-bit values (N0, N1 … N31)

B) The 8-bit binary int (N) is subtracted from 256

C) The private key is then hashed 256-N times.

Example for the first byte

[\begin{aligned}[b] s[0] =H(sk[0])^{256-N0} \end{aligned}]

D) The signature is composed of 32 hashes derived from our random private key.

To verify the signature:

a) The recipient parses the hash of the signature using 1 byte / 8 bits at a time, and extracting the 8-bit int, N. It the same principle as for step A.

b) Each byte is then hashed, defined by the number of times defined by the message hash value, N. Contrary to B, you take directly N instead of 256-N.

Example for the first byte

[\begin{aligned}[b] s[0] =H(sk[0])^{256-N0} \end{aligned}]

If N = 4, you have 252 $\begin{aligned}[b] s[0] =H(sk[0])^{252} \end{aligned}$ By applying N on the signature, you get the same number of rounds that are used to generate the public key.

Example for the first byte

$\begin{aligned}[b] H(H(sk[0])^{252})^{4} = H^{256}(sk[0]) = pk[0] \end{aligned}$ c) Since the public key is the last value computed, the final value get in step b must be the public key. If it is not the case, the signature is invalid.

Reference: asecuritysite.com/hashsig/wint

But in this construction, it misses a last very important point: the checksum.

Checksum

The Winternitz signature uses a checksum to protect against signature forgeries.

The checksum ensures that an attacker:

can not increment any byte of the message proper without invalidating the checksum
they can not destroy/modify the checksum in a way that would help them.

The construction of the checksum is very similar to the approach used in Merkle’s scheme.

The checksum is the sum of the differences between the 255 (the maximum value of a message byte) and each actual message byte being signed.

The resulting sum is encoded as a base-256 integer and added to the message.

Both the message and checksum are signed.

For an $\ell$ -byte message, the checksum formula is: $\sum_{l}^{i=1}255 - Mi$

Details

Since the hash function is publicly known, an attacker can decide to take a message which its byte values are lower than the first message signed to forge a signature for a message m’.

If you take the example of the previous section where N0 = 4. If N0’ = 3, the attacker can just perform a supplementary hash operation on the first signature to create a valid signature s` for its message m`

Signature for m’ $s'[0] =H(sk[0])^{256-N0'} = H(sk[0])^{253}$

If we use our first signature s in our equation, where $\begin{aligned}[b] s[0] =H(sk[0])^{252} \end{aligned}$ we have now

$\begin{aligned}[b] s'[0] =H(s)^{1} = H(sk[0])^{253} \end{aligned}$ Indeed, to pass from 252 (s) hash operation to 253 (s`) , we only have to perform one supplementary hash operation.

The verification process works as usual on our message m` and the signature s`.

[\begin{aligned}[b] H(H(sk[0])^{253})^{3}) = H^{256}(sk[0]) = pk[0] \end{aligned}]

Reference:

Use

Winternitz was used by the “crypto” project iota, a distributed ledger technology using a DAG data structure instead of a blockchain.

Using Winternitz for a crypto project is an audacious choice since each private key can only be used one time to sign one transaction.

Therefore, it requires to generate a new private key for each transaction which is not convenient.

Moreover, in case of an error, for example if a private key is used twice, the security of the account is totally compromised.

Moreover, at the beginning, they used their own hash function Curl, which has revealed to be vulnerable to collision.

They have finally switched in 2021 for ECDSA, which is not quantum safe but offers a better adaptability to the blockchain world.

Reference: lekkertech.net - IOTA IOTAs Multisig Problem, domschiener - Private Keys and Addresses, iota - introduction, Cryptographic vulnerabilities in IOTA

Security

The seed/private key must be generated in a random way. Otherwise, the algorithm is broken. The donjon CTF has a challenge if you want an example.
A private key generated to make a Winternitz signature should be only used one time.

If it is not the case, it is possible to forge a new valid signature under the following condition:

You need to have two messages m1 and m2 such that each byte of the h1 of m1 are less than each byte of the hash of m2, we can forge a new signature by computing: $\begin{aligned}[b] 256−n1< 256−n2 \end{aligned}$ $\begin{aligned}[b] \tilde{s_i} = H^{\tilde{n_i}-n_i}(s_i) \end{aligned}$

The cidectf has a nice challenge on that and you can find a writeup here.

WOTS+

According to this document, WOTS+ is specific variant of Winternitz used in SPHINCS+, XMSS, LMS for one-time signature.

According to this document, W-OTS is suitable for combining it with Merkle’s tree authentication scheme (MSS) because of the following reason:

The small verification key size
The flexible trade-off between signature size and signature generation time.
Further it is possible to compute the corresponding verification key given a W-OTS signature. So a MSS signature does not need to contain the verification key. T