Score:1

Are there any public keys for which the private key can be easily derived (ECDSA)?

in flag

I know that generally it's infeasible to find the private for any given public key. But I also came across the question "Find ECDSA PrivKey to PubKey = 0", in which it was explained that the private key for a public key 0x0000...0000 can be easily derived.

From the answer to that question it appears that public key 0x0000...0000 is the only public key for which this is the case, but haven't understood it well enough to know for sure.

So the question is, are there any other possible public keys (e.g. 0xffff...ffff or 0x0000...0001) for which it is easy to derive the corresponding private key?

Score:1
in flag

Preamble

One side of the security of the ECDSA depends on the Discrete logarithm security of the used Elliptic Curve ( call it $E$). Elliptic curves form an additive algebraic group of order $n$. If the group formed by the used curve is a generic group then the best classical attack is $\mathcal{O}(\sqrt{2^n})$ - Pollard's Rho.

ECDSA

The private key $k$ is calculated as a random integer in the interval $[1,n-1]$ and kept secret all the time. Note that the private key $k$ is an integer, not a point on the curve $E$.

The public key $P$, on the other hand, is calculated as a point $p = [k]G$ where $G$ is the base point of the curve defined in the standards and the operation $[k]G$ is called the scalar multiplication defined as;

$$[k]G : = \underbrace{G + G + \cdots + G}_{k-times}$$

This should not be confused with multiplication, no this is what we write to simplify the $k$-times additions.

The $[k]P$ can be calculated at least with double-and-add algorithm to fasten the calculation in $\mathcal{O}(\log k)$-time.

The points

Now as we can see, even the $k=0$ is not a problem in ECDSA since it is not a valid value for $k$.

If the discrete log is easy

  • If the discrete log is easy on this curve, that is finding $k$ given $[k]G$, then every value is easily derived.

  • If the curve is backdoored with another base point $H$, i.e. someone can solve the discrete logarithm to the base $H$ on the curve group. Then they can use this to solve the Dlog on the base $G$ very easily;

    • They calculate $G = [t]H$ for $t \in [1,n-1]$ only once
    • They solve $P =[k\cdot a]G$ to the base $H$ for $a \in [0,n-1]$. Once $ka$ is found the $k$ can be calculated as $k = a \cdot k \cdot a^{-1}$ since we know the $a$ and $a^{-1} \cdot a = 1 \bmod n$.

If the discrete log is not easy

In this case, one can calculate some of them up to their maximal power. Let assume you can use the supercomputer Summit and you have the power to calculate $2^{70}$ double-and-add for a given number $t$. They calculate and set up a hash table to fast query for the existence of the discrete log in the range $[1,2^{70}]$. The run in one year, and the required storage is $2^{70}*256*3$-bits (~147574 Petabyte). Well, storage is one of the problems and the other is hash table may not be $\mathcal{O}(1)$ anymore. Let assume that you have solved this problem, then what is the probability that you can find a given private key from the public key. The exact value depends on the curve group, assume one uses a curve group of size $2^{256}$ to be secure against the standard Dlog attacks. The hit probability is $$\frac{2^{70}}{2^{256}} = \frac{1}{2^{186}}.$$ This even has far less probability than $\dfrac{1}{100}$, so we say it-is-not-going-to-happen!

Does Instead of sequential random choices of $t$s change the result, NO!


Special note 1:0x0000...0000 is the usual encoding of the $\mathcal{O}(n)$ since $(0,0)$ is not on the curve. This is not accepted as a valid public key in SEC 1 Ver. 2.0 section 3.2.2.1.


Special note 2: Some elliptic curves are prime curves this means that the group they formed has prime order. In this case, every element is a generator, except the identity element. If the order is not prime, like in the Curve25519, then we have the cofactor $h = \#E(K)/n$ where $n$ is the largest prime dividing the order of the curve. If the full group is used, it is easy to notice the small order elements, simply check $[o]P = \mathcal{O}$ or not, where $o$ is the small order. For Curve25519, the $o$ values are $2,4,$ and $8$. This is not a security problem since legitimate users always choose $k \equiv 0 \pmod 8$.

kelalaka avatar
in flag
Well, I've written a long answer to say almost no! Shoot me!
in flag
Thanks for the detailed answer, it's very insightful!
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.