2
$\begingroup$

I'm a beginner at working with Edwards Curves, and I'm trying to implement an Ed25519 signature. I have a question from a text. Please see the illustration below (in Python).

At the part of scalar multiplication it simply uses the double-and-add method:

def point_mul(s, P):
    Q = (0, 1, 1, 0)  # Neutral element
    while s > 0:
        if s & 1:
            Q = point_add(Q, P)
        P = point_add(P, P)
        s >>= 1
    return Q

Is that safe enough?

Why doesn't it use a constant time method like x25519 for DH key exchange? There is the Montgomery ladder as method of scalar multiplication of X25519 for DH key exchange to prevent side channel attack. How about Ed25519?

How can I protect against side channel attack when using scalar multiplication? How can I modify the function?

I will implement with a hardware design after finishing the python implementation. Is there any method to prevent the attack?

Improve this question
$\endgroup$
11
  • $\begingroup$ Perform dummy add when necessary. $\endgroup$
    – kelalaka
    May 7, 2019 at 19:24
  • $\begingroup$ May I know more about the detail? Is there any code I can refer to? $\endgroup$
    – luke
    May 7, 2019 at 20:05
  • $\begingroup$ Else T = point_add(Q, P) $\endgroup$
    – kelalaka
    May 7, 2019 at 20:08
  • $\begingroup$ @kelalaka Even assuming that you manage to convince the compiler not to optimize the calculation of T whose result is not used, that only reduces the side channel, it doesn't eliminate it. The timing of code memory accesses and the branch predictor state still leak the bits of s. $\endgroup$
    – Gilles 'SO- stop being evil'
    May 7, 2019 at 23:15
  • 1
    $\begingroup$ @Ruggero Cache-timing attacks are a subset of side-channel attacks. $\endgroup$
    – forest ♦
    May 11, 2019 at 2:27

1 Answer 1

Reset to default
2
$\begingroup$

As pointed out in section 8.1 of the RFC, "the example implementations in this document do not attempt to be side-channel silent".

You can't write the algorithm as is. Basically, you need to always compute the point addition:

T = point_add(Q, P)
Q = select(Q, T, s & 1)
P = point_add(P, P)
s >>= 1

The select function (also called "conditional copy") selects one of the two operands depending on the value of the third, in constant time (or "side-channel silent" to be more precise). This means that you can't use branches, but just arithmetic operations. The basic idea is to compute q ^= (q ^ t) & -b where q and t are the input and b is the select bit. If it is 0, q will stay the same; if it's 1, the -b will equal to 0xFFFF... and q will be set to t. You have to be careful to use the correct data types for it to work - though since you'll implement it in hardware that will be easy to handle. Of course, you'll need to do this for every word of every number in the elliptic curve points involved. There are many examples, here is one of them.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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