What does the special form of the base point of secp256k1 allow?

Question

The popular ECC parameters secp256k1 are documented in SEC2 as using curve $y^2\equiv x^3+a\cdot x+b\pmod p$ with $a=0$, $b=7$, $p=2^{256}-2^{32}-\mathtt{3d1_h}$, base point $G$ with the apparently haphazard $(x,y)$ coordinates (hex)

79be667ef9dcbbac55a06295ce870b07029bfcdb2dce28d959f2815b16f81798
483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

and order $n=2^{256}-\mathtt{14551231950b75fc4402da1732fc9bebf_h}$, cofactor $h=1$.

However, it turns out that $G$ is $G'+G'$ with $G'$ having $(x',y')$ coordinates (hex)

00000000000000000000003b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
c0c686408d517dfd67c2367651380d00d126e4229631fd03f8ff35eef1a61e3c

which is easily computable as $\displaystyle\frac{n+1}2\times G$. The 90 leading zero bits in $x'$ show beyond doubt that this is a deliberate choice. What does it allow (faster computation, attack..)?

As an aside: is it known how $x'$ was chosen? The earliest mentions of that number that I could find are in this answer (January 5, 2015) without mention of its property, and in this challenge (date unknown but it existed on June 5, 2015) where its property is meaningful.

Update: I notice that the generator of secp224k1 is also twice a $G'$ with the very same anomalously small $x'$ as above (this time with 58 leading zero bits, which is still remarkable). I found nothing similar about the generator of secp192k1 or secp160k1. I did not check other SEC curves (but secp112r1 secp112r2 secp128r1 secp128r2 secp160r1 secp160r2 secp192r1 secp224r1 secp256r1 secp384r1 secp521r1 are reportedly verifiably random, thus nothing similar should occur).

---

The special form of $G$ seems to allow some perceptible speedup when computing $k\times G$ for arbitrary $k$ by some elementary methods. We can rewrite $k\times G$ as $(2k\bmod n)\times G'$, and the frequent point additions of $G'$ or ($-G'$) occurring in left-to-right binary scan of the scalar multiplier can be sped up a little (at least when using affine, projective or Jacobian coordinates), because multiplication by $x'$ occurs in the point additions, and some of the word multiplications can be skipped.

However, I do not know if the fastest methods used in practice can take advantage of the special form of $G$ (or what these methods are).

Answer 1

FWIW, AFAIK I was the first person in modern times at least to notice G/2 had an anomalously small x. I spent an awfully large amount of cpu cycles looking for a similar sha1 preimage. :)

I found it while trying to come up with an origin of the generator for historical curiosity sake. In some other standards the generator is things like the hash of a birth day or what not. Many prior efforts to find an explanation had failed.

I tried to make a new generator myself. I picked the smallest point on the curve. Then I thought "Hm, this very small value might result in differential power analysis side-channels in some implementations". The only operation you can really do with a single point is double it. This resulted in a random looking X. So I thought to try halving the secp256k1 generator.

Unfortunately, the constant is 166 bits long-- too long to be a sha1 output alone!

I found that several other curves use the same constant (224k1 and the 160k1, IIRC).

Thomas' point about blindly following the SEC 1 procedure for binary curves sounds great to me.

I do very slightly disagree with the argument that unknown origin of the generator is totally irrelevant. You can imagine protocols which are not completely contrived where control of the generator lets you create a weakness because it allows you to know one additional discrete log that you wouldn't otherwise be expected to know.

For example, I could ask you to adopt a secp256k1 pedersen commitment scheme which uses G and a new generator H = to_point(sha256("certicom rocks" || counter)). Well clearly I don't know the discrete log of some SHA2 output! ... except if G was generated as H*random-- then I do and I can break the soundness of the commitment scheme.

Obviously, I don't think there was any funny business like this here, for one-- "2" is a pretty non-random 'key'. And any vaguely competent effort to create H would commit to G, e.g. H = to_point(sha256(to_bits(G) || "certicom rocks" || counter). :)

FWIW, I have seen people try to construct such schemes where they failed to commit to the other generators-- e.g. people attempting to implement my confidential transactions writeup, even though I mention including G in the hash-- so it's a plausible mistake.

I think that this is a nitpick but it does show that even the most benign properties could trip up a sufficiently advanced idiot. :)

In terms of actual use: In a sufficiently dumb world, no dumb property is so dumb that it can't find a use. In Bitcoin someone spammed the network with tiny payments to tens of thousands of addresses where the private keys were sha256($dictionary_word). It was desirable to sweep up this dust with the smallest signatures possible. Bitcoin signatures are DER encoded, so a signature with a small R results in a smaller signature. Obviously using an R with a known DL leaks the key, but this isn't an issue when the key is already public. I wrote a patch to sign using that property as well as a bug that lets you use a signature of the message 'hash' 1 be used to spend any coin. As a result, this value is the most common R value used in the Bitcoin blockchain by a wide margin, most of them with a completely constant signature for a constant message hash. Those blocks gzip really well.

Answer 2

One thing we know is that it doesn't allow any special attack.

Let us assume that we knew a special point $G$ that makes computing the discrete log easy, that is, given $xG$, it's easy (or at least, easier than expected) to recover $x$.

Then, given $H$ and $xH$, here's what we could do; we know that $H = yG$ for some $y$ (as $G$ is a generator), and so we can use our special purpose discrete log problem to recover $y$. Similarly, we have that $xH = zG$ for some $z$, again, we can recover $z$. So, we have $x(yG) = zG$, or $x = y^{-1}z$; that immediately gives us the value $x$.

Hence, if they knew a 'weak point' $G$, that would imply that the entire curve is weak. Since we don't believe that, we can assume that their special value $G$ is no weaker than any other point (as long as $G$ generators the entire group, which is true in this case)

Answer 3

Information on how the specific base point was chosen is scarce. If you look at SEC1 (section 3.1.3.2), you will find a pseudo-random method in which a given seed is hashed (along with some parameters, in particular a counter value) into a bit string, which is then interpreted as the $X$ coordinate of the candidate point (if there is no valid point with that $X$ coordinate, the counter is incremented and a new candidate $X$ is obtained, and so on).

If you are doing that in the late 1990s, i.e. before the invention of the SHA-2 functions, chances are that you will use SHA-1 (or possibly RIPEMD-160), with a 160-bit output, in which case you naturally get a "short" $X$.

Now, in the case of secp256k1, we see that the $X$ coordinate is slightly longer (it has length 166 bits, not 160); moreover, the actual generator is twice the point you obtain with the $X$ above. The algorithm in SEC 1 calls for multiplying the candidate point with the cofactor $h$, but, for secp256k1, this cofactor is $1$, not $2$.

My guess is that the following happened:

• In the mid-1990s, some people involved in defining new standard curves (which would happen under the aegis of SECG starting in 1998) tried to generate verifiably random curve elements.

• These people were working notably on curves over binary field, in particular the famous Koblitz curves ($y^2 + xy = x^3 + ax^2 + 1$, with $a = 0$ or $1$, in $\mathbb{F}_{2^m}$). Such curves have an even cofactor, in practice $2$ or $4$. The algorithm expressed in SEC 1 will then produce (with SHA-1) a "short $X$" point, and there would be a multiplication of the point by 2.

• Somebody, at some point, worked over the other kind of Koblitz curves, those that are over prime fields ($y^2 = x^3 + b$ over $\mathbb{F}_p$, with $p$ prime and $p = 1 \bmod 3$). Curve secp256k1 is of that kind. By analogy with the first kind of Koblitz curves, the same generating code may have been imported "as is", or with only a slight variant, and including the final multiplication by 2 of the point, which is not needed (but harmless) for a prime order curve.

• It is probable that however the points were initially chosen, they just "stuck". This is a common phenomenon: once some test values have been disseminated, it is very very hard to correct them afterwards, because that would imply that several people must fix their code accordingly. This won't happen if there is not a good reason to do so. And, as @poncho points out, the general understanding is that the choice of the generator has no significance for security, and cannot be "backdoored", and thus does not require verifiable randomness.

We may note that SEC1 and SEC2 were not the last word on curve standardization; most of it was lifted into ANSI X9.62, and also in IEEE p1363, and also into FIPS 186-4. In FIPS 186-4, the curve parameter selection was described again, but only for the curves that NIST was interested on, and these do not include secp256k1 (they have Koblitz curves on binary fields, not on prime fields). Even for the NIST curves such as secp256r1 (P-256), the generator is not explained: section D.1.1.5 of FIPS 186-4 even says:

Any point of order n can serve as the base point. Each curve is supplied with a sample base point $G = (G_x, _y)$. Users may want to generate their own base points to ensure cryptographic separation of networks. See ANS X9.62 or IEEE Standard 1363-2000.

---

Summary: exactly how the base point was generated is lost in the mists of time. For the last two decades, this was considered as "not very important" and people did not bother even keeping track of the method; they just recopied the values from standard to standard, and from implementation to implementation. My guess is that, at the source, some hashing with SHA-1 was involved, explaining the "short values". These were later rediscovered and exploited to get some (very slight) performance improvement in some operations.