0
$\begingroup$

As far as I understand, the Winternitz one-time signature is made by:

  1. Making an array of private keys.
  2. Making an array of public keys by hashing each private key X times, X being the number of different possibilities of characters that can appear in each position of the message (or the hash of the message) to verify.
  3. Making an array of hashes as signature by hashing each private key X minus "the character's ordinal number" times.
  4. Verifying the signature by counting the times each of the signature hashes needs to be hashed to reach the public key and interpreting that count as the character's ordinal number. With these numbers, we can then form the message (or the hash of the message), which would then demonstrate that the message was valid.

Hence, for example, if we are signing by HEX digits, X would be 15, as characters would go from 0 (1st character, representing 0 iterations) to F (16th character, representing 15 iterations). So then, however times we need to hash the signature to reach the public key, it will represent a certain value, from 0 times to 15 times (giving effectively 16 possibilities). And if it never reaches it, then it is invalid.

Having said that, I have read that the weakness is that the signature can be altered, because, for example, if one character signed is A, then there is enough information to hash also B, C, D, E, and F. Then, according to many, including this website, the solution is to make a checksum.

And here is where I am stuck. Nor do I understand how to implement the checksum. I have found some explanations, but they are all too technical or too vague and do not tell me exactly, in simple words, how to make that checksum.

Please explain to me how to do the checksum in simple language that anyone can understand.

And, if possible, comment how that checksum could not be also tainted. Thank you.

$\endgroup$
1
$\begingroup$

Please explain to me how to do the checksum in simple language that anyone can understand.

Actually, it is an 'inverse checksum'; when you sign a character X, you also add the value 15-X to the checksum; for example, if you sign an A, you add 5 to the checksum (because A+5=F, at least in hex). You then take that sum, and sign that as well.

For example, if the value you are signing consists of the 4 character A, 4, F, 0, then you sum up the inverses (F-A)+(F-4)+(F-F)+(F-0)=1F, and so include the two characters 1, F in the signature.

It should be easy to see that, if the attacker attempts to increment a character in the hashed message, he decreases the value of the inverse checksum, which means that some character in the sum decreases (and the attacker can't generate a signature for that decremented character).

For example, if the attacker attempted to forge with the 4 characters B, 4, F, 0, the inverse checksum the verifier would get is 1E, the attacker is unable to generate the WOTS valid for 'E' (given that he knows only the value for 'F')

$\endgroup$
4
  • $\begingroup$ Thank you very much. My first thought was that then, why could they not also modify another character too to compensate for the lost in the inverted checksum, so, instead of going from A4F0 to B4F0, go to B3F0, to equilibrate it, but then I understood that it would be impossible to 'go lower' as they do not have the private key, they can only increase. $\endgroup$
    – algo
    Aug 9 at 10:54
  • $\begingroup$ So, it seems that whenever a character is increased, the value of the checksum gets decreased, and also, characters cannot be decreased. $\endgroup$
    – algo
    Aug 9 at 10:56
  • $\begingroup$ My only question is, how is it that they could not mess the checksum too? For example, the checksum in your example was like this: A4F0 1F If the attacker changes the character of the message, but also some character in the checksum... B4F0 1E However, it seems that the checksum 1F could not be changed into 1E indeed, as characters cannot be decreased, so that seems to be the reason why the checksum must be inverted... Is this correct? Because I still have a little feeling of suspicion regarding the messing with the checksum. $\endgroup$
    – algo
    Aug 9 at 11:00
  • $\begingroup$ @algo: yes, that is correct; the idea is that the attacker cannot mess with the checksum directly; he can only mess with the hash (and the checksum is computed based on that). And, if he increments some character somewhere, he must decrement some other character - and because he doesn't know the preimage to that WOTS element, he can't. $\endgroup$
    – poncho
    Aug 9 at 12:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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