4
$\begingroup$

I am new to Elliptic Curve Cryptography and I was reading up on it online when I came across this link. It stated the following.

Unfortunately, there is a gap between ECDLP difficulty and ECC security. None of these standards do a good job of ensuring ECC security. There are many attacks that break real-world ECC without solving ECDLP. The core problem is that if you implement the standard curves, chances are you're doing it wrong:

  1. Your implementation produces incorrect results for some rare curve points.
  2. Your implementation leaks secret data when the input isn't a curve point.
  3. Your implementation leaks secret data through branch timing.
  4. Your implementation leaks secret data through cache timing.

So, I was curious about the second point. How is it possible to leak secret data when the input isn't a curve point. I am assuming it means the base point(P) is not on the curve, but then how would P+P be calculated and how would it make the implementation insecure?

$\endgroup$
3

1 Answer 1

7
$\begingroup$

Suppose you publish a public key $P = [n]G$ for a secret scalar $n$, where $G$ is the standard base point.

If you are willing to tell me $H([n]Q)$ given $Q = (x, y)$ for any coordinates $x$ and $y$ of my choice, then I can send you a point $Q$ of (say) order 2 on some other curve whose arithmetic law happens to coincide with the curve you meant to use, and learn $H([n]Q) = H([n \bmod 2]Q)$.

How does this work? Suppose you use the short Weierstrass form $y^2 = x^3 + a_4 x + a_6$. Since the addition law doesn't involve the constants $a_4$ or $a_6$ at all, and the doubling law involve only $a_4$, it turns out that you will happily compute scalar multiplication of points on any curve with the same $a_4$, so all I need to do is find some $a'_6$ whose curve has low-order points.

When I get back the answer, it is either $H([0]Q) = H(\mathcal O)$ or $H([1]Q) = H(Q)$, so by examining which one you returned, I can learn $n \bmod 2$. The same applies if I send a point of order 3, 4, 5, etc., and I can combine the results with the Chinese remainder theorem to interactively compute the discrete log $n$ of your public key $P = [n]G$ with your help.

Of course, if you expose the point $[n]Q$ instead of the hash $H([n]Q)$, then my task may be even easier!

$\endgroup$
3
  • $\begingroup$ That makes a lot of sense! Thanks a lot! So, to counter this I should first check if the point lies on the curve and then proceed further right? $\endgroup$
    – InertFluid
    Jun 12, 2019 at 3:59
  • 1
    $\begingroup$ @InertFluid Better: For, e.g., DH, you can work exclusively in $x$ coordinates, which is cheaper anyway with the Montgomery ladder if it suffices to compute $H(x([n]P))$ given $x(P)$, so that the only curve you need to worry about is the quadratic twist, and you can choose curves so that ECDLP is hard on your curve and on its quadratic twist, like Curve25519. Caveat: in protocols beyond vanilla DH, the cofactor may cause trouble, so you may want to use Ristretto or Decaf. $\endgroup$ Jun 12, 2019 at 4:03
  • $\begingroup$ @InertFluid But, in legacy systems that deal in both coordinates and/or don't support the Montgomery ladder, yes, you can check whether the point lies on the curve first. It's better if you can avoid this, because in legitimate usage, the logic will work whether or not you include the check, so it's easy to forget, and it's not free. $\endgroup$ Jun 12, 2019 at 4:12

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.