4
$\begingroup$

An article How is NSA breaking so much crypto? describes NSA's methods for breaking encryption.

If a client and server are speaking Diffie-Hellman, they first need to agree on a large prime number [...] an adversary can perform a single enormous computation to "crack" a particular prime, then easily break any individual connection that uses that prime.

Why do we generate these primes using tools like dhparam when using DH, but in ECDH we often admit which particular curve (like Curve25519) we're using?

Isn't that exactly what we should avoid? Shouldn't we generate the curve properties in a similiar manner? Or is that hypothetically correct but the computation is not even in well-paid adversary's capabilities?

$\endgroup$
  • 1
    $\begingroup$ You can (and IMO should) hardcode primes for classical Diffie-Hellman. Just make sure they're big enough. $\endgroup$ – CodesInChaos Apr 2 '16 at 8:13
  • $\begingroup$ related: "Logjam on Elliptic Curves?" $\endgroup$ – SEJPM Apr 2 '16 at 11:59
3
$\begingroup$

The fact is that the discrete logarithm problem (DLP) is solved using different algorithms in the cases of multiplicative groups (where normal DH applies) and elliptic curves (where ECDH applies).

The behavior of these algorithms is quite different.

For multiplicative groups, where the NFS for logarithm is used, a huge part of the computation depends only on the multiplicative group itself and not on the single discrete logarithm.

See for example the logjam paper where in table 2 they mention the costs for sieving, linear algebra and descent (where descent is the only phase requiring the single logarithm as input, and therefore can't be precomputed). For DH-1024 sieving and linear algebra requires 45 million core years while just 30 core days are needed for the descent. This means that after having done a huge precomputation, single logarithms are quite easy to extract.

For elliptic curve groups the situation is different. The best attack is Pollard's rho, which requires $\mathcal{O}(\sqrt{n})$ group additions for a group of size $n$. Now, computing in parallel $l$ discrete logarithm costs $\mathcal{O}(\sqrt{ln})$, which is speedup over the trivial $\mathcal{O}(l\sqrt{n})$, but not a significant one. In fact, the attacker is expected to compute $\mathcal{O}(\sqrt{n})$ additions before finding the first among them (see the "Batch Disscrete Logarithms" of the curve25519 paper. Once the first discrete logarithm is found, the second one has still similar cost to the first one, not a much smaller one (like with the NFS).

Thus if $n$ is of reasonable size, it doesn't matter how $l$ is big as computing even the first logarithm will be out of reach.

Note: there are techniques that by using an extremely large precomputation effort allow to easily compute discrete logarithms. The important thing to understand the ineffectiveness of these approaches is that the precomputation effort costs significantly more than extracting a single logarithm (about $\sqrt[3]{n^2}$ additions which is greater than $\sqrt{n}$ for the single logarithm). See this paper for details.

| improve this answer | |
$\endgroup$
1
$\begingroup$

See this answer, and note that even for standard Diffie-Hellman,
we almost always "admit which particular" prime we're using.
In fact, since both honest parties need to know the prime, the only way to avoid that would
be already having a pre-shared secret and just using Diffie-Hellman for addition protection, mainly to limit the ongoing effect of key compromise by a passive adversary,
since symmetric cryptography can already achieve forward secrecy.

More relevantly, I haven't read about any way for attacks on elliptic curves to use
precomputation for more than a constant-factor improvement in online complexity,
and this is the only way I've read about for attacks on elliptic curves to use amortization.


(Also, I believe that's not known to be a theoretical vulnerability of standard Diffie-Hellman:
I'm not aware of any argument that there should be arbitrarily large primes q for which
there are positive integers k and g such that (k$\cdot$q)+1 is prime and the order of g mod that is
a multiple of q and, with ​ ​ S = exp$\hspace{-0.02 in}\left(\hspace{-0.03 in}(\hspace{.02 in}\log(q)\hspace{-0.03 in})^{1/4}\hspace{-0.04 in}\right)$ , ​ ​ there is an algorithm with size at most S and runtime at most S whose advantage against Diffie-Hellman with g mod (k$\cdot$q)+1 is at least 1/S.)

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think DJB published a paper about reducing DL computation time or cost to $n^{1/3}$ for ECC, but it requires ridiculous precomputations and I don't even think it reduces the DL cost in realistic cost models (that properly handle memory). $\endgroup$ – CodesInChaos Apr 7 '16 at 14:23

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.