0
$\begingroup$

I'm thinking about doing this as a project, but I'm not sure how I'm supposed to proceed.

So I have an 128-bit ECDSA, which would provide about 128 bits of security (if we do not use special methods like the baby-step giant-step algorithm or Pollard Rho's algorithm). I generate a list of 2^64 public keys, and I want to find the private keys to any one of them.

So essentially this is a multi-target attack on ECDSA private keys. With 2^64 targets (public keys), I would require 2^128/2^64=2^64 attempts on average to find a private key to any one of these targets.

I have a few questions:

(1) How long would it take for a computer to perform 2^64 ECDSA operations? Is 2^64 within the realm of possibility using commonly-available GPUs?

(2) I need to generate a list of 2^64 public keys (targets). Then I need to create a database for these keys, and index them (based on their x coordinate number size, in order to perform a structured search/lookup). Therefore, the size of this database would be bordering on several exabytes, which is completely infeasible using commonly-available resources. Is there any way to reduce the size of this database?

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ For comparison: The SHA-1 attack (shattered.it) required about $2^{63}$ SHA-1 compression function evaluations each of which is much cheaper than an ECC point multiplication and still took 110 GPU-years. $\endgroup$
    – SEJPM
    May 26, 2020 at 13:59
  • $\begingroup$ Just storing the X coordinate alone will cost you 256 exbibytes according to my incredibly simple calculations. $\endgroup$
    – Maarten Bodewes ♦
    May 26, 2020 at 16:00
  • $\begingroup$ "(if we do not use special methods like the baby-step giant-step algorithm or Pollard Rho's algorithm)"; is there a specific reason why you want to avoid using these better algorithms? Wouldn't an intelligent attacker use the best algorithm available to him? $\endgroup$
    – poncho
    May 26, 2020 at 18:40

1 Answer 1

Reset to default
3
$\begingroup$

One $n$-bit ECDSA private key can be found from the public key with about $2^{n/2+1}$ group operations, by Pollard's rho, which is relatively easily distributed. Nothing more costly is worth consideration. For $n=128$, this is $2^{65}$ field operations and would be feasible with a large effort. This is why people use at least $\approx160$-bit ECDSA, and more like $256$-bit ECDSA or more nowadays.

It's a more interesting problem to determine if a multi-target attack can take sizably less time. I do not immediately see that it does.

How long would it take for a computer to perform $2^{64}$ ECDSA operations?

That depends a lot on:

  • The computer. This one is millions times faster than most others.
  • What's an operation. A full ECDSA signature at $n$-bit costs in the order of $n$ times more than a group operation, wich costs several field operations.
  • The $n$ parameter. For medium values, doubling it multiplies the cost of a field operation by like 3, of a full ECDSA signature by like 6.
  • The curve used. Binary curves allow faster implementation and attacks.
  • Competence of the attacker, which matters immensely.

Ultra rough estimate with my PC for $2^{65}$ group operations: $2^{31}\,\text{Hz}$, $2^3\,$cores, $2^7\,$cycles per field operation, we are talking $2^{65-31-3+7}=2^{38}\,s$, that's many centuries. We need too many PCs and too much energy.

Therefore the attack for $n=128$ has no practical interest, is feasible only at sizable cost, and it's better to run it as a mind or small-scale experiment.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ "It's a more interesting problem to determine if a multi-target attack can take sizably less time. I do not immediately see that it does."; actually, it is pretty easy to show that it does not; suppose you had a black box method that, given a large number of dlog problems $x_i G$ solves one of them. Then, given a single Dlog problem you want to solve $xG$, you can randomize it a large number of times $r_ixG$ and then give the random instances to your black box. That'll give you the solution for one, which you can use to recover the original $x$. Hence, for ECC, multi-attacks are no easier $\endgroup$
    – poncho
    May 26, 2020 at 20:15
  • 1
    $\begingroup$ "Competence of the attacker, which matters immensely" - against a sufficiently incompetent attacker, double ROT13 is secure... $\endgroup$
    – poncho
    May 26, 2020 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.