4
$\begingroup$

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?

$\endgroup$

1 Answer 1

5
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ @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! $\endgroup$
    – fgrieu
    Commented Oct 19, 2022 at 10:24
  • $\begingroup$ Where did the 136 come from in the muli-target attack? $\endgroup$ Commented Oct 19, 2022 at 17:35
  • 1
    $\begingroup$ @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. $\endgroup$
    – fgrieu
    Commented Oct 19, 2022 at 17:39

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.