Timeline for How to do the WOTS checksum
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 21 at 10:36 | comment | added | radix | @poncho thanks for the explanation, I had a misconception, but now I get it | |
| Apr 20 at 16:32 | comment | added | poncho | @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) | |
| Apr 20 at 16:21 | comment | added | radix | The checksum is smaller than the msg hash and thus can't reflect all "bit increments" in the msg hash with a inverted value in the checksum. E.g. in LMS with SHA256: message hash = 32 bytes, checksum 2 bytes. Couldn't it occur that an attacker can find (1) a message with a msg hash that's "greater" than the original hash and (b) a checksum that's also "greater" than the original checksum, due to some kind of underflow in its two bytes? (probably that's not possible, but I can't see why...) | |
| Jun 13, 2022 at 2:15 | vote | accept | algo | ||
| Aug 9, 2021 at 12:14 | comment | added | poncho | @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. | |
| Aug 9, 2021 at 11:00 | comment | added | algo | 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. | |
| Aug 9, 2021 at 10:56 | comment | added | algo | So, it seems that whenever a character is increased, the value of the checksum gets decreased, and also, characters cannot be decreased. | |
| Aug 9, 2021 at 10:54 | comment | added | algo | 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. | |
| Aug 9, 2021 at 3:43 | history | answered | poncho | CC BY-SA 4.0 |