WOTS#
Author: Herman Schoenfeld
Version: 1.0
Date: 20200720
Copyright: (c) Sphere 10 Software Pty Ltd
License: MIT
Abstract
A very simple modification to the standard WOTS scheme is presented called WOTS# that achieves a security enhancement similar to WOTS+[1] but without the overhead of hashing a
randomization vector in every round of the chaining function. The idea proffered by WOTS# is to simply thwart Birthdayattacks[2] altogether by signing an HMAC of the messagedigest (keyed
with cryptographically random salt) rather than the messagedigest itself. The signer thwarts a birthday attack by virtue of requiring that the attacker guess the salt bits in addition to the
messagedigest bits during the collision scanning process. By choosing a salt length matching the messagedigest length, the security of WOTS# reduces to that of the cryptographic hash
function. This essentially doubles the security level of WOTS and facilitates the use of shorter hash functions which provide shorter and faster signatures for same security. For example, WOTS# 128bit signatures have commensurate security to standard WOTS 256bit signatures yet are roughly half the size and twice as fast. It is proposed that Blake2b128 and Winternitz
parameter w=4
(i.e. base16 digits) be adopted as the default parameter set for the WOTS# scheme.
1. Birthday Attack
A birthday attack involves an attacker forging a signature for a "malicious" message M
by reusing a signature for an "agreed" message m
. In this class of attack, the attacker has preknowledge of a message m
that the victim is willing and intending to sign in the future.
The attacker creates variations of m
as {m_1..m_k}
any of which will also be deemed "valid" and signed by the victim. Whilst the victim considers each message m_i
"identical", their hash digests are unique. This can be achieved by simply varying nonces or whitespace within m
to create this set.
The attacker simultaneously generates variations of a "malicious" message M
as the set {M1..M_l}
and stops until a collision H(m_i) = H(M_j)
is found (where H
is the hash function
used in the scheme).
NOTE the probability of finding such collisions is far more likely than a standard bruteforce attack by virtue of the Birthday problem[2][3].
When a collisionpair (m_i, M_j)
is found, the attacker asks the victim to sign valid m_i
giving s = Sign(m_i, key) = SignDigest(H(m_i), key)
. The attacker then proceeds to forge a
signature for invalid M_i
by simply reusing s
, as follows:
1: S = Sign(M_j, key)
2: = SignDigest(H(M_j), key)
3: = SignDigest(H(m_i), key)
4: = s
Unbeknownst to the victim, by signing m_i
, they have also signed M_j
.
2. WOTS & WOTS+
The Winternitz scheme is a welldocumented[4][5] scheme whose description is beyond the scope of this document. However, of relevance is the relationship between the WOTS "security
parameter" n
(the bitlength of H
) and it's "security level" which is generally n/2
. This follows from the fact that if a bruteforce attack on H requires 2^n
hash rounds then a birthday attack
requires 2^(n/2)
[2] hash rounds. By eliminating the birthday attack, and assuming no such other class of attacks exist for H
, the security level of the scheme is restored back to that of a
bruteforce attack on H
which is n
.
WOTS+ achieves a similar security enhancement through obfuscation of preimages in the hashing chains, however they are performed during the chaining function which adds an
overhead (significant in some implementations). WOTS# is similar to WOTS+ in this regard except it only obfuscates the messagedigest once via an HMAC (keyed with the salt) and uses the
standard WOTS chaining function, which is faster than WOTS+. Despite the concatenation of the salt to the signature, the overall signature size decreases by virtue of selecting a shorter hash
function H
.
3. WOTS#
The WOTS# construction is identical to a standard WOTS construction for Winternitz parameter w
and cryptographic hash function H
. The security parameter n is inferred from the the bitlength of H
.
In WOTS, a messagedigest md
is computed as md=H(message)
. During signing, digits of base 2^w
are read from md
and signed in a Winternitz chain. In WOTS#, the messagedigest md
is
replaced with the "sigmac" smac
defined as:
3.1 Signature Message Authentication Code (SMAC)
1: smac = SMAC(m, salt)
2: = HMAC(H(m), salt)
3: = H(Salt  H(Salt  H(m)))
The salt
is concatenated to the signature and used to compute smac
during verification.
NOTE the checksum digits are calculated and signed identically as per WOTS but derived from smac
not md
.
3.2 Salt
The Salt
is generated by the signer using cryptographic random number generator. The length of the Salt is n
bits which is the minimum value required to nullify a birthday attack (proven
below). The salt is defined as:
1: Salt = {0,1}^n (i.e. n cryptographically random bits)
3.2.2 Proof

A birthdaycollision is expected after
1.25 * SQRT(U)
[2] hashing rounds whereU
is maximum hashing rounds ever required (nonrepeating). 
In WOTS,
U=2^n
where n is the security parameter (bitslength ofH
) and thus (1) becomes1.25 * 2^(n/2)
. 
In WOTS#, adding a d bit salt hardens a birthdaycollision to
A = 1.25 * 2^((n+d)/2)
rounds. This follows from the fact that an attacker must scan for collision(HMAC(H(m_i), Salt), HMAC(H(M_j), Salt))
which involvesd
more bits (whereas in WOTS they just scan for(H(m_i), H(M_j)) )
. 
A bruteforce attack on H requires
B = 2^n
hashing rounds[2]. 
We need to choose
d
suchA = B
, since we only need to harden a birthday attack to match that of a bruteforce attack. Hardening beyond is redundant since the security level of the scheme is only as strong as the weakest attack vector. 
Evaluating (5) gives
d = 2 ln(0.8)/ln(0.2) + n = 0.2773 + n
which is approximatelyn

Thus choosing
d=n
is sufficient to thwart birthdayattack. QED.
References

Hülsing, A. "WOTS+ Shorter Signatures for HashBased Signature Schemes". 2013. Url: https://eprint.iacr.org/2017/965.pdf. Accessed:
20200722.

Wikipedia. "Birthday Attack". Url: https://en.wikipedia.org/wiki/Birthday_attack. Accessed: 20200722

Wikipedia. "Birthday Problem". Url: https://en.wikipedia.org/wiki/Birthday_problem. Accessed: 20200722

Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical
Engineering, Stanford University, 1979. Url: http://www.merkle.com/papers/Certified1979.pdf

Sphere 10 Software. "Winternitz OneTime Signature Scheme (WOTS)". URL: https://sphere10.com/articles/cryptography/pqc/wots.