# Is a padded 128 bit private key enough for ecdsa 256?

According to the following, ecdsa-256 only provides ~128 bit security even for 256 bit private key:

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

If the private key has only 128 bit entropy but constant-padded to 256 bit, then the corresponding 256 bit public key is distributed. Would it provide the same 128 bits security?

Summarizing the question:

Would ECDSA-256 still provide 128 bit security for a 128 bit private key padded to 256-bit?

No, for fixed public 128-bit padding. Given ECDSA curve parameters, the ECDSA public key $$Q$$ and the padding method that produced the private key $$d$$, it's possible to devise an attack that finds the private key $$d$$ with $$Q=dG$$ using about $$2^{65}$$ point additions, that is like $$65$$-bit security.

Left padding extends a 128-bit secret $$s$$ to $$d=k\mathbin\| s=2^{128}k+s$$ for some known 128-bit $$k$$. Thus the problem is to find $$s$$ given $$Q=(2^{128}k+s)G$$, that is find $$s$$ such that $$sG=Q-2^{128}kG$$. The right hand side can be readily computed. That $$s$$ can be found using Baby Step/Giant Step, or Pollard's rho.

For right padding, $$d=s\mathbin\|k=2^{128}s+k$$ and the problem is to find $$s$$ given $$Q=(2^{128}s+k)G$$, that is find $$s$$ such that $$s(2^{128}G)=Q-kG$$, which is equally easy.

On the other hand, if we build $$d$$ from $$s$$ using a hash, for example as $$d=(\operatorname{SHA-512}(s)\bmod(n-1))+1$$, then we get 128-bit security for single target attack (that is when the adversary attacks a single public key $$Q$$).

In multi-target attack, the attacker has a collection of $$r$$ public keys $$Q_i$$ and is content with finding any $$d$$ with $$dG$$ among the $$Q_i$$. Even with 128-bit to 256-bit expansion with a hash, an attack that simply tries various $$s$$ (e.g. sequentially) succeeds with about $$2^{128}/r$$ hashes and scalar multiplications, thus security can't exceed like $$\min(136-\log_2(r),128)$$ bit.

If we want multi-target security with a 128-bit secret and no diversifier/salt, we need some level of key stretching with e.g. Argon2.

• @kelalaka: I had missed that my reasoning for 128-bit security when using a hash to expand the 128-bit secret to 256-bit is good only for single (or few)-target attack, but fails for multi-target attack and plausible number of keys, for the reason at the beginning of your answer. Thanks for pointing that!
– fgrieu
Commented Oct 19, 2022 at 10:24
• Where did the 136 come from in the muli-target attack? Commented Oct 19, 2022 at 17:35
• @Aman Grewal: I make the approximation that a point multiplication is $2^8$ point additions/doubling, thus add 8 bits to the standard 128. That's rough.
– fgrieu
Commented Oct 19, 2022 at 17:39