7
$\begingroup$

I'm learning about Ed25519. It depends on a bunch of magic values: The finite field of order $2^{255}-19$, the specific elliptic curve over that field, a specific point on that curve. This is in contrast to Diffie-Hellman or RSA.

Why is that? And conversely, why doesn't DH fix the prime number & the generator, or RSA fix, say, the $n = pq$ value?

I suspect that in case of DH & RSA it's very easy to generate new instances of the protocol. We know a lot about primes, so it's easy to generate new ones, and also conversely, if we fixed a prime for all instances of the protocol, we could analyze the hell out of it, and break it.

So is it that in case of elliptic curves it's not that easy to find a curve & generator?

$\endgroup$
0
8
$\begingroup$

The reason to not fix a specific curve/group/whatever to work over is if it hurts security, namely if:

  1. There are precomputation attacks — an attack that costs $T$ that can be amortized over $n$ users now effectively costs $T/n$. For $n\approx$ 1 billion this can potentially change cost/benefit calculations.

  2. It is possible for a malicious standards body to standardize a "weak" curve/group/whatever, for example a backdoored one, or one that is simply weaker than a "random" one in some way.

These are issues for certain hard problems — the LWE problem and finite-field DH both admit precomputation attacks, for example. For LWE, this is used as justification for not standardizing an "LWE Matrix $\mathbf{A}$".

That being said, there can be benefits to fixing a particular curve/group/whatever. Namely:

  1. You no longer have to generate it during protocols, saving some efficiency.
  2. You no longer have to transmit it (or can transmit a succinct description of the constant number of standardized objects), saving some bandwidth
  3. You can optimize operations for that curve/group/whatever, saving efficiency
  4. It is harder to choose "weak" curves/groups/whatever accidentally.

As for why curve 25519 takes the particular form that it does, see for example the Safe Curves page for some descriptions/comparisons of various curves properties.

For these questions:

Why doesn't DH fix the prime number & the generator

They do in certain applications. Here is a list of finite field DH groups used in TLS (including 1.3). Note that one has to be careful with this though — there used to be "weak" groups standardized ($\approx 512$ bits) that nobody would realistically use. Their presence in this list of standardized groups led to the Logjam attack, where one mounts the precomputation attack against them + combines it with a certain "downgrade attack".

Or RSA fix, say, the $n=pq$ value?

It is not clear how you could use this practically, as there is really only a single private key associated with it, so two distinct users could not both use a single $n$ for encryption. In fact, even if they use $n, n'$ that share a common factor, it leads to attacks (and another Nadia Heninger paper, Mining your P's and Q's). That being said, there are special applications where it may be useful, see for example this paper on distributed RSA modulus generation for some discussion of applications.

$\endgroup$
3
  • 3
    $\begingroup$ "You no longer have to generate it during protocols, saving some efficiency" is a very important reason: I have yet to see any simple and efficient algorithm to generate a secure Elliptic curve. With such algorithm, "You no longer have to transmit" (the curve's parameter) would be a non-issue: just transmit the seed of the RNG used by this algorithm to express the curve. $\endgroup$
    – fgrieu
    Jun 25 at 6:49
  • $\begingroup$ Lenstra tried. $\endgroup$ Jun 25 at 15:25
  • 1
    $\begingroup$ Before 7919 for TLS1.0-2 some people used the 'Oakley' groups created for IPsec/IKE (rfc2412 and rfc3526), some of which SSH also uses, but the smallest is 768-bit (which Logjam assessed 'feasible' to break but did not actually do so). The 512-bit group Logjam found widespread was a default then provided by Apache and not any standard. $\endgroup$ Jun 25 at 23:00
2
$\begingroup$

The typical reason that people typically use pre-specified elliptic curves instead of generating them is efficiency. It isn't very difficult to generate an elliptic curve, but it is generally difficult to generate a secure elliptic curve, and moreover, it's relatively difficult to convince the other party that the curve is secure over the limited bandwidth of the protocol. The SafeCurves website explains many of the attributes that are desirable in a curve, and explains part of the decisions of Curve25519.

Most of the well-known elliptic curves are also specifically chosen for efficiency, using a prime or a form that is designed to be as efficient as possible. For example, using curves with a fixed prime near a power of two makes specific operations much, much faster, and implementations are typically hard-coded to take advantage of specific primes.

Moreover, using pre-specified elliptic curves means that it's much easier to write constant-time implementations. This is very important in online protocols like TLS where non-constant time implementations can be demonstrated to be exploitable. It is possible to write generic constant-time implementations of elliptic curves, but it's complex, and people don't practically do it.

It is certainly possible to use fixed groups in non-EC Diffie-Hellman; TLS does this, and SSH does it as well. As long as a sufficiently large group of the proper form is chosen, that is secure. Using a fixed group is also more efficient in terms of protocol bandwidth because the parameters don't need to be sent.

It is also possible to generate random secure finite field groups and this is far faster than generating secure elliptic curves, but it's still slow enough that typically people precompute the parameters once and then use them for a period of time.

As for RSA, reusing the parameters isn't usually secure. Additionally, for efficiency reasons, the private key often includes $p$ and $q$, which would immediately compromise the private key of anyone sharing $N$. Even if sharing $N$ didn't have security problems, because $p$ and $q$ couldn't be exposed, this would be much less efficient than generating new parameters per user.

$\endgroup$

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.