6
$\begingroup$

From Wikipedia:

One of the attractive feature of the Edwards Addition law is that it is strongly unified i.e. it can also be used to double a point, simplifying protection against side-channel attack.

Could you explain with more detail how an explicit doubling can protect against side-channel attacks?

$\endgroup$
  • 1
    $\begingroup$ I believe the passage was saying that because there is only one formula for both addition and doubling. If you have a constant time addition formula, you also have a constant time doubling formula. The alternative would be that you would need to make sure that both addition and doubling are constant time $\endgroup$ – user679128 Jul 17 at 20:53
5
$\begingroup$

Some formulas like the usual short Weierstrass addition formula for curves over fields of characteristic ${>}3$, involve terms like $$\frac{y(P) - y(Q)}{x(P) - x(Q)}$$ which don't work when $P = Q$. So to reliably add two points, you have to write logic like:

if P == Q:
    return doubling_formula(P)
else:
    return addition_formula(P, Q)

This conditional may take a different amount of time depending on potentially secret points $P$ and $Q$. Even if doubling_formula and addition_formula take exactly the same amount of time, the machine may take a different amount of time depending on which way the branch goes because it may predict one way and take more time if the prediction is wrong, or it may have different effects on CPU caches depending on which branch is taken. In general, CPUs do not keep branch conditions secret.

One way to do this is to compute both doubling_formula(P) and addition_formula(P, Q) and then choose between them with arithmetic like (d & m) | (a & ~m) where d is the outcome of doubling, a is the outcome of addition, and m is all 1 bits if $P = Q$ and all 0 bits if $P \ne Q$. But this costs more to compute because now you have to compute the addition formula and the doubling formula, even if you're going to use the result of only one of them, whenever you want to add two points.

The Edwards addition formula, in contrast, does not have any such terms, and it works for all pairs of points, even if $P = Q$. Consequently you don't need to write conditionals and you don't need to spend the cost of computing multiple different formulas. But it only works for some curves like edwards25519; it doesn't work for, e.g., secp256k1.

(While there are complete addition formulas for arbitrary curves, they are considerably costlier than the Edwards addition formula, so like the do-every-branch-and-select-with-arithmetic approach, they present a conflict between performance and security.)

$\endgroup$
  • $\begingroup$ Mathematically there are two special cases: $P = Q$ (use doubling) and $P = -Q$ (result 'zero'). But the latter case doesn't occur in X9.62-type signature, because we multiply $G$ by a number less than its order. $\endgroup$ – dave_thompson_085 Aug 25 at 7:52
  • $\begingroup$ The question didn't mention signatures, let alone any particular signature scheme, so I assumed nothing about the application. $\endgroup$ – Squeamish Ossifrage Aug 25 at 21:58
  • $\begingroup$ Just wanted to add that there are scalar multiplication algorithms for short weierstrass curves without all that overhead that are guaranteed to avoid those problems (e.g. here) but are still more complex than what you can do with Edwards. $\endgroup$ – Ruggero Aug 26 at 8:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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