1
$\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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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')

Improve this answer
$\endgroup$
7
  • $\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
    Commented Aug 9, 2021 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
    Commented Aug 9, 2021 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
    Commented Aug 9, 2021 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
    Commented Aug 9, 2021 at 12:14
  • 1
    $\begingroup$ @radix: no, 'underflow' is impossible. Suppose we have $W=8$ (that is, the 32 byte hash consists of 32 Winternitz digits, with each digit a value between 0 and 255. So, the sum of those 32 digits will be a value between 0 and 8160; we 'invert' it (that is, compute $8160 - sum$), yielding a value between $8160 = 8160-0$ and $0 = 8160 - 8160$; that value can be expressed in two Winternitz digits (that is, two bytes). If we do anything to make the msg hash greater, the checksum will necessarily become smaller (and hence one of the two checksum digits will decrease) $\endgroup$
    – poncho
    Commented Apr 20 at 16:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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