1
$\begingroup$

I was thinking about a brute force attack on Curve25519. For this, we need to solve the discrete Logarithm problem $P = [n]Q \bmod 2^{255} - 19$. $P$ and $Q$ are known Points on the elliptic curve, so we 'only' need to find $n$. The $n$ is in $ \{2^{254} + 8 \cdot \{0,1,2,\ldots,2^{251}-1 \} \}$. So there are $2^{251}$ different possibilities for n. On average the brute force attack needs to test $2^{250}$ different n.

We want to calculate how much time the best supercomputer in the world would need. Bernstein says that it needs 640383 cycles for one multiplication. 92% are floating points operations (flop) so i approximated this to 100% flop. The best supercomputer can do $148600 \cdot 10^{12}$ flops. Combining this information, I achieved the following result:

$$\dfrac{2^{250} \cdot 640838}{148600 \cdot 10^{12}} \cdot \dfrac{1}{60\cdot 60\cdot 24\cdot 365.25} \approx 2.47243\cdot 10^{56} \text{ years}$$

Do I have an error in reasoning?

$\endgroup$
  • $\begingroup$ You are missing the increase in computing power over time. $\endgroup$ – A. Hersean Jun 26 at 15:09
  • $\begingroup$ Actually, the discrete log problem isn't $P = n*Q \bmod 2^{255} - 19$ (which is actually rather easy); instead, it's the problem $P = nQ$, where $P, Q$ are elliptic curve points and $nQ$ is point multiplication. $\endgroup$ – poncho Jun 26 at 15:13
  • $\begingroup$ @poncho You are right, i just did not mention it. I edited it! $\endgroup$ – Titanlord Jun 26 at 15:28
  • 2
    $\begingroup$ Standard brute DLog force is not parallelizable! The supercomputers achieve their peak with parallel computation. You have to consider one CPU/ASIC etc. $\endgroup$ – kelalaka Jun 26 at 15:47
  • 1
    $\begingroup$ Might I ask about the purpose of this computation? Is it to gain some insight into how secure Curve25519 is (and if so, wouldn't it be better to use the best-known attack)? Or, it is some academic exercise about "brute force"? $\endgroup$ – poncho Jun 26 at 19:41
2
$\begingroup$

Ok, it answer the specific question you asked:

Bernstein says that it needs 640383 cycles for one multiplication

Actually, when Dan talks about "multiplication", he is referring to a "point multiplication", that is, to the computation of $[n]P$ (given a large integer $n$ and a point $P$).

In your simple-minded brute force search, you don't need to do a full multiplication each time. Instead, when you have computed $[a]P$ (and decided it is not $Q$), you can step to the next one by computing $[a]P + P = [a+1]P$; this is a point addition (and incrementing the value $a$ you're keeping track of), this is much cheaper than the full point multiplication operation.

Now that is mentioned the obvious misstatement in your analysis, some general advice; to do a reasonably thorough security analysis, you'd need to consider:

  • The various computational models that an adversary may have available; in addition to a single large computer, the adversary may have a large number of smaller computers, a set of GPUs, a set of FPGAs2 or even (if his budget allows) some ASICs. Dan used floating point in his implementation, but that's because modern CPUs have some pretty fast floating point logic, and he took advantage - however, there are a lot of gates tied up in this fast floating point logic; some of the other computational models would use different strategies.

  • The various attacks; in addition to the rather naïve brute force search, you would also need to consider various "square root" attacks (such as Baby Step Giant Step and Pollard Rho (and parallelized versions), and also the MOV (which doesn't apply to Curve25519, however you'd need to learn why).

What Dan wrote is a decent starting point; however he assumes that the reader is already familiar with the basics of elliptic curves; I suspect you'd want to do some reading to catch up...

| improve this answer | |
$\endgroup$
  • $\begingroup$ Wow thank you very much! This is a great answer! $\endgroup$ – Titanlord Jun 28 at 8:57
  • $\begingroup$ So you optimized my brute force. But can it be optimized again? Doubling and Addition need a different amount of operations using projective montgomery arithmetic. Is it possible to check every key using Doubling? $\endgroup$ – Titanlord Jun 28 at 10:48
  • 1
    $\begingroup$ @Titanlord: Hmmmm, good question. I don't know the answer off the top, but it appears likely; repeated doubling (starting at any non-POI element) will cover every element (other than POI) iff 2 is a primitive root modulo $n$ (the size of the Curve25519 group); that is, if the smallest positive solution to $2^x \equiv 1 \bmod n$ is $x = n-1$. Verifying if that is true would depend on the factorization of $n-1$ (which I don't have at hand); I can verify that $2$ is not a quadratic residue (and hence the 2 factors of $n-1$ are irrelevant); I don't know about any larger factors. $\endgroup$ – poncho Jun 28 at 12:32
  • 1
    $\begingroup$ @Titanlord: correction to above: the above observation applies to the prime-sized subgroup of Curve25519, where $n$ is the size of that subgroup. That's the case you care about anyways... $\endgroup$ – poncho Jun 28 at 15:34

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.