Diffie-Hellman groups are vulnerable to sieving precomputation attacks. These attacks allow a one-time computation against a given DH modulus that makes it practical to attack all subsequent key negotiation operations using the same group. It is speculated that, at least in 2015, it takes only $8M USD to build ASICs capable of performing this initial precomputation stage for any 1024-bit group in a single year.*

Section 5 of the above paper mentions that ECDH is merely less vulnerable to precomputation:

Transitioning to elliptic curve Diffie-Hellman (ECDH) key exchange with appropriate parameters avoids all known feasible cryptanalytic attacks. Current elliptic curve discrete log algorithms for strong curves do not gain as much of an advantage from precomputation.

Emphasis mine. This implies that these attacks can be used against ECDH, albeit with less benefit, despite the fact that ECDH is not run over a multiplicative group of integers modulo a prime, which precomputation exploits. I have three questions about these attacks and how they apply to ECDH:

  1. How can ECDH be attacked if it uses multiplicative groups of points on a curve?

  2. How much of an advantage does an attacker gain from said precomputation?

  3. Does the choice or class of curve have any impact on the feasibility of this attack?

* On a side-note, I'm skeptical that this cost estimate is accurate, since the authors of the paper assume that consumer SDRAM (in terms of price and access behavior) will be used instead of high-speed VIAs or other custom constructions.

  • $\begingroup$ The cheapest attack is some kind of parallel batch $\rho$, unless you have a special case in front of you, like pairing-friendly curves where it'll be a tossup between $\rho$ and index calculus. I'm not aware of any precomputation that reduces the net cost of a generic $\rho$ attack. $\endgroup$ – Squeamish Ossifrage Feb 28 '19 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.