A multi-target attack on 128-bit ECDSA private keys

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?

• 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. May 26, 2020 at 13:59
• Just storing the X coordinate alone will cost you 256 exbibytes according to my incredibly simple calculations. May 26, 2020 at 16:00
• "(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? May 26, 2020 at 18:40

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.

• "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 May 26, 2020 at 20:15
• "Competence of the attacker, which matters immensely" - against a sufficiently incompetent attacker, double ROT13 is secure... May 26, 2020 at 20:16