6
$\begingroup$

Take for example a curve from a recent question such as #25519:-

$$y^2 = x^3 + 486662x^2 + x$$

It's considered "safe". What are are the implications of amending it very slightly to:-

$$y^2 = x^3 + 486664x^2 + x$$

I'm trying to get a layman's feel for what this would mean. For example, is it now entirely invalid and can't be used at all, very easy to break or just a little easier to break? Or does this tiny change suddenly allow specific attacks to come into play?

$\endgroup$
2
  • 5
    $\begingroup$ That equation actually defines curve25519 and not Ed25519. $\endgroup$
    – Ruggero
    Commented Sep 3, 2018 at 10:36
  • $\begingroup$ @Ruggero Indeed. Curve25519 is the curve used in various ECC algorithms like Ed25519 (signing) and x25519 (key exchange). Pretty much any property of that curve will affect all algorithms that use it. However I would say that it is accurate to call $y^2 = x^3 + 486662x^2 + x$ the curve of Ed25519, since it does use it. It's just that Curve25519 is not unique to Ed25519. $\endgroup$
    – forest
    Commented Sep 4, 2018 at 1:45

2 Answers 2

7
$\begingroup$

Extremely sensitive. In fact, there are only three other positive values that would not violate various security guarantees, and the example you provided was not among them. And even of those three, only the one chosen protects from all edge cases. Now, in a little more detail...

Curve25519 is a Montgomery curve in the form of $y^2 = x^3 + Ax^2 + x$ for efficiency reasons. For the curve to be secure, an adequate $A$ must be chosen. The three possible choices for $A$ that would be secure under the definitions set forth in the paper introducing the curve are $358990$, $464586$, and $486662$. The first two have prime factors smaller than $2^{252}$, which is an issue in the very unlikely situation that a given secret key matches the prime. Rather than amend the security definitions of the curve and place limits on the choice of key, Bernstein went with $A = 486662$ for simplicity.

If you go with a completely different $A$, then all sorts of unpredictable things can happen. Various security guarantees may be broken, and a number of vital performance features will go down the drain. The choices of $A$ must have curve and twist orders of $\{4 \cdot \mathrm{prime}, 8 \cdot \mathrm{prime} \}$ to avoid a number of attacks specified in section 3 of the Curve25519 paper. The specific change you proposed does not match these criteria, so any number of attacks may apply. This is really the crux of the answer. Anything can happen once the security constraints are violated.

$\endgroup$
12
$\begingroup$

An elliptic curve equation is very sensitive to any change of its parameters.

That small change result in a complete different curve. Its security could be good or bad, but you have to check it explicitly and cannot make predictions beforehand.

Specifically, your resulting curve will have a composite order whose largest factor is $833860344743147476600479140946265460420135480673538361531$ which implies your curve's security won't exceed $2^{94.5}$. I said "won't exceed" because I haven't checked all the other security properties of the curve (twist security, transfers, etc), which could result in a security downgrade.

$\endgroup$
5
  • 3
    $\begingroup$ TLDR: very${ }$ $\endgroup$
    – fgrieu
    Commented Sep 3, 2018 at 10:41
  • $\begingroup$ I can't quite determine what you're saying. So it won't have the required 128 bits for certain, but might be even lower? That would suggest it's rendered pretty useless then, even with such a small change? But conversely, it might give 256 bits of security with a different coefficient on the $x^2$ term which we can't know without testing? $\endgroup$
    – Paul Uszak
    Commented Sep 3, 2018 at 22:58
  • $\begingroup$ So the answer is that it's extremely sensitive to parameters? $\endgroup$
    – Paul Uszak
    Commented Sep 3, 2018 at 22:59
  • 1
    $\begingroup$ @Paul A curve over $\mathbf F_p$ where $p$ is 256 bits cannot give 256 bits of security because Hasse. $\endgroup$
    – fkraiem
    Commented Sep 4, 2018 at 0:08
  • $\begingroup$ @Paul "In layman's terms", if you want high security, you need an accordingly high number of points, but we know that the number of points can't differ much from the size of the base field. $\endgroup$
    – fkraiem
    Commented Sep 4, 2018 at 0:19

Your Answer

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

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