[Cryptography] Why doesn't elliptic curve point addition check for equality?

[Kyle Butt]

On Fri, Jan 26, 2024 at 02:45:23AM -0500, Pierre Abbat wrote:
> On Monday, January 22, 2024 7:33:47 PM EST Kyle Butt wrote:
> > I've never seen a binary-ternary ladder.
> 
> Here's the code: https://github.com/phma/random-ladder .
> Let's say we want to multiply g by 23. We could use these sequences of 
> operations:
> [21,21,21,32]
> [21,21,32,21]
> [21,32,21,21]
> [21,32,30,21]
> [32,21,21,21]
> [32,21,30,21]
> [32,31,32]
> where 32 means multiply by 3 and add 2g and the operations are performed from 
> right to left. If this is in a Weierstrass curve, the operations, as far as 
> time of execution goes, are . for trivial addition or doubling, + for general 
> addition, and 2 for general doubling. Converting the two-digit numbers to 
> these symbols, we get
> [21,21,21,32] ..2.2+2+2+
> [21,21,32,21] ..2+2+2+2+
> [21,32,21,21] ..2+2+2+2+
> [21,32,30,21] ..2+2+2+2+
> [32,21,21,21] ..2+2+2+2+
> [32,21,30,21] ..2+2+2+2+
> [32,31,32]    ..2.2++2++
> where ..2+2+2+2+ is evaluated from left to right. Note that 2g is evaluated at 
> most once in 32, though it's added twice in the last sequence:
> ..	Double 0, then add 0 to it
> 2	Double g
> .	Add 2g to 0
> 2++	Double 2g, then add 2g to get 6g, then add g to get 6g+g=7g
> 2++	Double 7g, then add 7g to it, then add already computed 2g.
> This is because Haskell is lazy; if there were no 32s in the sequence, it 
> wouldn't evaluate 2g at all.
> 
> Now suppose we want to multiply g by 25. The sequences are:
> [21,20,20,21,21] ..2+222+
> [21,20,30,32]    ..2.2+22+
> [21,30,20,32]    ..2.22+2+
> [21,30,31,21]    ..2++2+2+
> [31,20,20,32]    ..2.222++
> [31,20,31,21]    ..2++22++
> [31,32,32]       ..2.2++2++
> The last sequence, ..2.2++2++, corresponds to both [32,31,32] and [31,32,32], 
> and also [31,31,32] (22) and [32,32,32] (26).
> 
> 2+ can correspond to [21] or [30], 2++ can correspond to [31] or [32,...
> (32)...], and 2+2+ can correspond to [32,(no 32)] or [21,21]. These sequences 
> occur many times in the ladder of a big number, leaving a side-channeler in 
> doubt as to what the number is.

Ignoring the .'s, we have the choices of '2', and of '+'. Leaking information
about a scalar like this is bad. If you assume that you leaked half the bits,
then the search space for the key is that much smaller. I wouldn't want to use a
system that relied on leaking side channel information like this. I would
instead use either a system based on montgomery or edwards curves if possible,
and if not possible, I would implement something like the neutral point
avoidance mentioned here:
https://www.shiftleft.org/papers/ladder/ladder-preprint3.pdf

Also if the pattern is randomized, but tied to a specific scalar, it's possible
that by observing multiple uses of the same scalar, an attacker could learn more
information about the same scalar. This strikes me as really dangerous and
unnecessary when there is a lot of literature about how to compute elliptic
curve math without side channel leaks.

> 
> Pierre
> -- 
> ro nu co'i cortu cu nu co'a certu
> 
> 
> 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> https://www.metzdowd.com/mailman/listinfo/cryptography
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 297 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20240129/d01f7b59/attachment.sig>