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?

up vote 0 down vote accepted

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.

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").

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.