Why does WOTS+ need a checksum during signing operation?

Question

I was reviewing WOTS+ scheme for consideration in our private blockchain, and noticed that it had a small overhead of calculating a checksum as seen in the following pseudocode excerpt from the SPHINCS+ submission to NIST

wots_sign(M, SK.seed, PK.seed, ADRS) {
  csum = 0;

  // convert message to base w
  msg = base_w(M, w, len_1);

  // **compute checksum** <<<<============
  for ( i = 0; i < len_1; i++ ) {
    csum = csum + w - 1 - msg[i];
  }

  // convert csum to base w
  csum = csum << ( 8 - ( ( len_2 * lg(w) ) % 8 ));
  len_2_bytes = ceil( ( len_2 * lg(w) ) / 8 );
  msg = msg || base_w(toByte(csum, len_2_bytes), w, len_2);
  for ( i = 0; i < len; i++ ) {
    ADRS.setChainAddress(i);
    sk = PRF(SK.seed, ADRS);
    sig[i] = chain(sk, 0, msg[i], PK.seed, ADRS);
  }
  return sig;
}
//Algorithm 5: wots_sign – Generating a WOTS+ signature on a message M.

Why is it there? Is it necessary for the security of the scheme?

Update

According to "On the Security of the Winternitz One-Time Signature Scheme", the checksum deters "second-key" and "key-collision" attack should there be a functional forgery oracle. How relevant an attack is it to WOTS+ and to other regular signature schemes?

Answer 1

To understand why we need a "checksum", we can take a look all the way back to 1979 paper "A Certified Digital Signature" by Raphle Merkle.

From page 14 on the treatment of the Lamport-Diffie OTS:

The method as described thus far suffers from the defect that B can alter m by changing bits that are 1's into 0's. ... However, 0's cannot be changed to 1's.

This is because, if one changes 1 to 0, she/he can simply calculate the image of the hash for that bit and get another valid signature.

The countermeasure as proposed was, quote:

by signing a new message m', which is exactly twice as long as m and is computed by concatenating m with the bitwise complement of m.

The similar method was used in WOTS, except instead of concatenating m with its bitwise complement, it's concatenated with the "additive" complement of the sum of its indicies.

So this is more like a padding scheme (similar in purpose to that used in RSA), but since it's a number, we'll just call it a checksum.

As to the update in OP, the checksum also plays an important role in the provable security reduction of WOTS.

Answer 2

Recall the idea WOTS scheme in essence, without checksums yet: for a message $m = (m_1, m_2, ..., m_n), $ where $m_i\in \{{0,...,W\}}$, signature value is $\sigma = (\sigma_1, ..., \sigma_n)$, so that $\sigma_i$ is the $(m_i + 1)$-preimage of the public key value $p_i$. Verification check is: $$p_i = Hash^{m_i + 1}(\sigma_i).$$

This scheme (without checksum) could be simply broken: after the signer issued a valid signature for some message $m = (m_1, m_2, ..., m_n)$, anyone can trivially create a signature for any message $m' = (m'_1, ..., m'_n)$ if $m'_i \le m_i$ for all $i$. Indeed, if you have $(m_i+1)$-preimage of some value (in this case, $p_i$), you have also a $(m'_i+1)$-preimage.

How to fix the scheme? The idea is the following: in addition to "sign" (more precisely - find corresponding preimages of public key) message $m$, you must also "sign" some additional string $c=(c_1, ..., c_l)$, which is built from $m$ in a special way $c = c(m)$. This transformation ($c(m)$) guarantees the following property: if $m'_i < m_i$ for all $i$, then, vice-versa, $c'_j > c_j$ at least for some $j$ (for corresponding $c=c(m)$ and $c'=c(m')$ ). This property will block the forgery attack described above. Indeed, if the attacker decreases message value in some position, i.e. $m'_i < m_i$, she automatically increases at least some position in the checksum - $c'_j > c_j$.

How to find such a magic transformation $c$? It turns out, that it could be very simple. E.g., you can use just a "complement" - a string of the same length, so that $c_i = W - m_i$. Easy to see, that it guarantees the desired property ("if all $m'_i \le m_i$, then $c'_j > c_j$ for at least some $j$"). Although, it satisfies even a stronger property: "if $m'_i \le m_i$ for some $i$, then $c'_i > c_i$". But it doesn't help us in any way. Also, this transformation is a bit heavy (the length of checksum is the same as length of a message, so that it doubles the signature size and public key size).

Finally, the question is could we construct another, more space-effective transformation with the desired property? Yes, it could be shown that the most space-effective $c$ is a checksum described in WOTS scheme (as well as its successors - WOTS+, SPHINCS and so on). It has a length of roughly $log_W n$ (compare to $n$ - length of naive "complement").