Expose Generator and Point at Infinity as Constants #1117

Almost all of the EC Group Algebra is in this library, but notably we don't seem to have access to the Generator point (as a pubkey) nor the point at infinity (as a pubkey). I'm not sure what the representations of these values are internally and so it would be hard to synthesize the right buffer arrangements to do so.

Well, the idea of our API is to avoid exposing low level functionality such as the group algebra. You can argue we got it wrong in the past with the very powerful tweaking APIs but I don't think we'd like to move further into that direction. (See #1017)

What's your use case?

It cleans up substantially the implementation of a list sum of pubkey combination. I'm working on a new revision of Haskell bindings for this lib. Generally the Haskell ecosystem likes to have complete algebras and as such I intend to put it in my API regardless of which way this project decides. As a brief aside I don't think that a group algebra is low level at all though that is a matter of opinion.

I can definitely sidestep this in my API if need be but imo libraries providing clean consistent APIs is usually something they want, so I figured I'd bring it up, but if the goals here are different I can do it at a higher layer, and it won't be an issue, just makes my job a bit dirtier but nothing that can't be managed.

@ProofOfKeags The idea is to have APIs for cryptographic protocols, not primitives (think, ECDSA, Schnorr, BIP32, ... rather than group operations and field operations). There are two reasons for this:

• API safety: by providing APIs, the obvious way to use the library is a safe one. Much more can go wrong when you're building higher-level constructions yourself directly. To give one example, if you'd implement ECDH using the multiplicative pubkey tweaking, you're likely to fail constant-timeness guarantees, because APIs for public keys do not need such protections (it treats neither keys nor tweaks as secret), but ECDH does need to treat the tweak as secret.
• Performance: if you're going to use the API exposed by this library (e.g. using functions for key generations, and additive and multiplicative tweaking) for implementing group algebra, and then build things on top of that, you're going to see abysmal performance. This is because those operations operate on public keys, which use affine curve coordinates. Internally, group elements are represented using Jacobian coordinates and overcomplete field representations, which permit delaying expensive normalization operations until a public key needs to be returned. For something like point addition, I'd expect a 10x performance drop or so.

Of course, I can't stop you from writing bindings and exposing public keys as a group algebra, but the libsecp256k1 API is very much not designed for that. If you want something for experimentation with group laws, and don't care as much about safety, I'd suggest using a more exposed library that actually lets you operate on Jacobian group elements at least.

There has been a suggestion before to split out the internal field/group code in libsecp256k1 into a separate library, which would then permit things like building constructions, though the result would need a very different approach than we have now (among other things, because the representation of group/field elements isn't stable across versions and architectures, and that instability may need to be communicated very clearly to users, or create a problem for future performance improvements).

Thanks for the explanation @sipa. I guess where I'm being tripped up is how making the API return failure is any less of a side channel leakage than letting the monoidal unit identity return its nontrivial argument in a time that deviates from that constant time. Is it simply that it allows the caller to detect the possibility of side channel leakage and then abort the protocol?

I'm not familiar with how the internals or how the constant time guarantees are accomplished so forgive me if this is obvious. It just seems that the tweaking API could be at minimum a commutative monoid without a degradation in security per my above (possibly wrong) claim.

My suggestion was primarily one for completeness and indeed if the tweaking code was carved off into a separate lib then the need for the generator and PAI are less relevant since they wouldn't be needed to complete that algebra. I suppose I could leave the API at a semigroup for now though and just "forget" that it is a full abelian cyclic group because as you stated, external users should perhaps not try to use full group properties in cryptographic protocols without the requisite knowledge.

@ProofOfKeags Let me try again.

The tweak APIs do not support infinity, because infinity is not a valid public key, and these APIs are intended for tweaking public keys and nothing else. They are in the library because BIP32 needs additive tweaking, and BIP38 needs multiplicative tweaking. That's considered a historic mistake because they're lower level than what we generally aim for: ideally we'd just have a bip32 module and a bip38 module that include the specific hashing steps needed for these specific protocols inside the library, but at the time they were added, including hashing inside the library wasn't considered in scope.

I was trying to illustrate that you should not use these APIs for implementing a generic group interface, as it'll hide cryptographic pitfalls from the users of such an interface, as well as have bad performance:

• Imagine the ECDH module didn't exist in libsecp256k1, but you have a generic group API (on top of the tweaking functions), so you can simply compute the hash of the received public key multiplicatively tweaked by your own secret key. This would be semantically correct (as in compute the correct ECDH result), but be insecure, as the tweaking functions leak information about the tweak through timing, and thus aren't appropriate when the tweak is actually a private key which needs constant-time handling.
• Imagine you want to implement group addition, and use the point add libsecp256k1 function. This works, but it'll be an order of magnitude slower than the group addition that's implemented internally in libsecp256k1, for the simple reason that pubkey tweaking works on public keys, which use affine coordinates, and operations on affine coordinates are very slow. Internally the library uses a different more efficient coordinate system, which needs a slow conversion to affine coordinates, and the pubkey addition function must do this conversion before returning. If you're going to perform many group additions - as user of a generic group interface may expect to be supported - you'll end up with something many times slower than necessary, because it'll involve a conversion to affine coordinates after every group operation rather than just once at the end.

So to summarize: the lack of infinity has nothing to do with constant-time protection - it's because this API is for tweaking public keys, not for group operations, and public keys cannot be infinity. The constant-timeness is only an example of what can go wrong if you confuse public keys with generic group elements.

Is it simply that it allows the caller to detect the possibility of side channel leakage and then abort the protocol?

It is to allow to detect the caller to abort. But not to avoid side channel leakage, but for more direct reasons.

I'm not familiar with how the internals or how the constant time guarantees are accomplished so forgive me if this is obvious. It just seems that the tweaking API could be at minimum a commutative monoid without a degradation in security per my above (possibly wrong) claim.

I think it really depends on what "security" is for the tweaking functions. Let me try to explain. So we can look at:

• "Algorithmic" security: The tweaking functions are designed to error out on exceptional values, e.g., when they would output an infinity pubkey. This is based on a best guess that infinity pubkeys are bad in most cryptographic applications and protocols: For example, the infinity pubkey is invalid in ECDSA and other algorithms, and sometimes doesn't even have a valid serialization (see for example SEC 1, 3.2.2.1). When the tweaking functions were written, they were designed with BIP32 in mind, which is method to derive ECDSA pubkeys. In this case, it's really a good idea to inform that caller that they arrived at an invalid key. Typical callers would want to abort in this case.
• Sidechannel security: Aborts are a big sidechannel as you note (probably much more observable than timing). However, first of all, maybe this is used in a setting where the attacker will anyway learn the result of the computation, i.e., the tweaked pubkey. It is a pubkey after all. So then it doesn't matter if the attacker could observe the infinity pubkey or the abort, it would learn the same. Moreover, sidechannels due to the aborts in exceptional cases are not an issue in practice because they will happen only with negligible (= astronomically small) probably for proper inputs. And even for attacker-controlled inputs, if the attacker know which values lead to the infinity pubkey, then the attacker anyway knows your secrets. For example, in the attacker knows which tweak would make secp256k1_eckey_pubkey_tweak_mul abort due to the result being infinity with your specific pubkey, then it knows the secret key corresponding to the public key.

Anyway, sidechannel security is to protect against an attacker that can observe sidechannel information and learn something about a secret value. So this is all about protecting secrets. Now you'd need to ask what the secret here is. This really gets hairy in the case of the pubkey tweaking functions, because we don't really know what the caller has in mind (maybe the input public key is actually a secret, even though it's a public key). At the moment the tweaking functions are not really written in mind with sidechannel protection. And note how this is just an assumption because we as a library can only guess what they will be used for.

And this is exactly one of the problem with too generic functions. We don't actually know the intent of the caller, and so we don't know what the caller considers a secret and what not. (As mentioned above, we don't even really know if aborting is a good idea.) @sipa's example was: If you're doing ECDH, then the result of the computation is a group element (a "pubkey" if you want) but in ECDH it's the secret! So if you were to use secp256k1_eckey_pubkey_tweak_add, you'd get it wrong. (See this for more background on the various internal point multiplication functions).

I suppose I could leave the API at a semigroup for now though and just "forget" that it is a full abelian cyclic group because as you stated

Keep in mind at least that anyway the group operation is not really complete. Even if you restrict the inputs to be only non-infinity, the output could be infinity (and you get an abort). So I don't think this gives you semigroup (or any meaningful algebraic thing).

Thank you for the explanations. I really appreciate you taking the time to educate @sipa @real-or-random

I'll go ahead and close this issue and opt not to add a group interface to the bindings.