There should some warning note right at the top, given the topic is presented mainly for cryptographic purposes.
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).
I confess I'm quite tired of having to litter every article that might be about cryptography with the standard warnings. I might as well warn readers not to use this knowledge at all, because they shouldn't implement their own crypto to begin with (even though I did).
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).
Oh, I thought you were talking about the bit twiddling required to implement constant time lookup and constant time branching.
> 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.
This was my first instinct uppon reading the title.
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.
> After that, the idea of being constant time gradually disappears.
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.
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:
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).