Score:4

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

bh flag

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?

Score:5
ng flag

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.

fgrieu avatar
ng flag
@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!
Aman Grewal avatar
gb flag
Where did the 136 come from in the muli-target attack?
fgrieu avatar
ng flag
@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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.