Fast Multiplication with Slow Additions
loup-vaillant.fr
loup-vaillant.fr
There is a huge body of quite diverse side channel attacks against all of these "fast" techniques for scalar multiplication, and the article is too weakly making references to pitfalls for each approach and the importance of constant time logic (also, no mention of masking techniques! Though those are routinely overlooked by way too many speed-obsessed practitioners).
Up untill sliding windows, there is at least a paragraph dedicated to making the algorithm constant time. It is not mentioned why this is important, but at least it is somewhat noticeable. After that, the idea of being constant time gradually disappears.
At one point, he moves towards EdDSA. Ironically, (if I recall correctly) EdDSA was seen as an improvement over EcDsa partially because it is easier to avoid timing side-channel attacks.
It does make a come back for combs (considering that fixed point multiplication is used to process secrets). The very last words of the article are "constant time".
> Ironically, (if I recall correctly) EdDSA was seen as an improvement over EcDsa partially because it is easier to avoid timing side-channel attacks.
It is. It's just that EdDSA verification doesn't need to be constant time at all. That's why sliding windows are so useful. Signatures and public key generation do need to be constant time, so I haven't mentioned sliding combs.
This is an advanced topic. If the reader is in a position to use such knowledge, I felt I could safely assume they would know when it is safe not to be constant time. (For instance, signature verification doesn't process secrets, and can be variable time.)
> also, no mention of masking techniques!
Out of scope. Those are hidden behind magical constant time routines.
> Out of scope. Those are hidden behind magical constant time routines.
How is that? Side-channel resistance is largely a matter of reducing the Signal-to-Noise ratio for traces an attacker can leverage to extract secrets. A constant-time logic reduces the Signal; a masking logic increases the noises. The two are largely independent and at times at odds. For instance, recent fast curves (like DJB's) are good because they can be easily implemented in constant time in software (as far as we know) but they are actually much harder to mask (in software or hardware).
> Side-channel resistance is largely a matter of reducing the Signal-to-Noise ratio for traces an attacker can leverage to extract secrets.
Who cares about resistance when you can have immunity? Constant time crypto leaks zero signal through timings, who needs any noise to mask that utter absence of signal?
Unless maybe you were thinking about other side channels, such as energy consumption, or electromagnetic emissions? I'd agree those are worth pursuing for smart cards and dongles, but on regular computers (from palmtops to servers), the threat is mostly academic.
I think they're different. In booth recoding, the windows are fixed, and non adjacent form is a special case of sliding windows (2-bit wide). I don't think booth recoding does minimise the number of non-zero digits. That said, it does seem to produce similar results in some cases:
01111111 100 (binary)
10000000-100 (NAF)
-- radix-4 Booth recoding
01111111100
000 -> 00
110 -> 0-1
111 -> 00
111 -> 00
111 -> 00
001 -> 01
010000000-100 (same as NAF)