15
$\begingroup$

I think we're all aware of the Logjam attack.

From now on we know that re-using primes for DH is a bad idea.

But we also say that elliptic curves are safe from the attack (relying on the NFS), because it cannot be applied. I understand this.

Now in my mind this question arose:

Assuming we had enough computational power (maybe using ASICs) is there a similar pre-computation attack on ECDH?

And if it is possible, how high would the gains be?
Could one reduce the workload per connection to a modest value ($\approx 2^{20}$), while still not needing to maintain a gigantic table ($>2^{60}$ storage)?
It would already suffice if such an attack would work on secp256....

Improve this question
$\endgroup$
2
  • $\begingroup$ According to the Logjam paper, "Current elliptic curve discrete log algorithms for strong curves do not gain as strong an advantage from precomputation." $\endgroup$
    – cpast
    Commented May 22, 2015 at 18:26
  • $\begingroup$ @cpast, so it's not as much broken as prime-field DH, but still, an overview over the available pre-computation algorithms and their speed relations would be nice and was asked. $\endgroup$
    – SEJPM
    Commented May 22, 2015 at 18:37

1 Answer 1

Reset to default
12
$\begingroup$

Let's recall how discrete logarithms are solved in strong elliptic curve groups. The basic idea is to iteratively walk through many combinations of the form $x_i = a_iP + b_iQ$ until we find a distinguished one, i.e., one that shares some common property (like the lowest $k$ bits of $x_i$ set to 0). We accumulate enough distinguished points until we find a collision.

When we find two distinct pairs $(a_1, b_1)$, $(a_2, b_2)$ that evaluate to the same value $x_1 = x_2$, we recover the logarithm by finding $Q = dP = \frac{a_2 - a_1}{b_1 - b_2}P$, which follows from $a_1P + b_1Q$ $=$ $a_2P + b_2Q$. We expect this to happen after $\sqrt{\pi n / 2}$ elliptic curve group operations.

Since by the time we get to the second discrete log we already know the first one, we can reuse the distinguished points found during that log computation. This slightly increases the chances of finding a collision. Suppose we have a hit $a_1P + b_1Q_1$ $=$ $a_2P + b_2Q_2$, where $Q_1$ was the first discrete logarithm target, and $Q_2$ is the current one. Rewrite this as $(a_1 + b_1d_1)P$ $=$ $a_2P + b_2Q_2$, where $d_1$ is the first discrete logarithm. Now we have $d_2 = \frac{a_1 - a_2 + b_1d_1}{b_2}$.

This accelerates the second logarithm by a factor of $2$, the third one by a factor of $8/3$, and the $i$th one by a factor $\approx \sqrt{i}$ compared to if they were solved independently. So as you see, the benefits of precomputation exist, but are much more limited than in the number field sieve case.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You need $i$ times the storage for solving the $i$th discrete logarithm? So it would be possible to reach a speedup of $2^{30}$ with storing $2^{60}$ samples resulting in a general effort of $2^{98}$ to break something like secp256? $\endgroup$
    – SEJPM
    Commented May 23, 2015 at 13:17
  • $\begingroup$ The first logarithm requires $\sqrt{\pi n / 2} / 2^k$ storage, where $k$ is, as above, the number of bits defining a distinguished point. For a 256-bit curve, your $2^{60}$ storage bound implies $k \ge 68$, since that is the amount of storage needed for a single discrete log. Bernstein and Lange suggested (eprint.iacr.org/2012/318) $k = 86$ and a precomputation of $2^{86}$ distinguished points---at a cost of $2^{172}$---making individual logarithms computable with $2^{86}$ effort. Reducing $k$ greatly increases the amount of work; I doubt $2^{30}$ speedup would be achievable. $\endgroup$
    – Samuel Neves
    Commented May 23, 2015 at 14:57

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.