PublicKey::combine_keys doesn't have to fail on long slices

[Kixunil]

If my understanding is correct combine_keys does simply point addition. Therefore for any set of keys combine_keys(&[k1, k2, k3, ... , ki, kj, ... kn]) == combine_keys(&[k1, k2, k3, ... , ki]).combine(combine_keys(&[kj, ... kn])) which enables us to just split the slice and call the method multiple times. IIUC the reason to even have a special method is some optimized batch combining.

[apoelstra]

This method is basically deprecated and we would have deleted it long ago if the LN people hadn't baked it into their protocol. I do not want to improve the API. If anything I would like to make it worse. It is a dangerous function because it has no protection against rogue-key attacks.

[Kixunil]

It is a dangerous function because it has no protection against rogue-key attacks.

Yeah, I was wondering where the method is even useful since I know about the attacks. Does LN do some kind of pre-processing to avoid the attacks? Or is it used for something else?

[apoelstra]

I checked rust-lightning and found:

• They don't use combine_keys, but only the 2-key variant key.combine(&other_key)
• They use this inside add_public_key_tweak defined here https://github.com/lightningdevkit/rust-lightning/blob/669a4596a694ec966be0b8d0dcd37accd9adf867/lightning/src/ln/channel_keys.rs#L189
• They use this in a couple places, always using a Taproot-like construction where they hash the two keys together.

So I think we could drop the combine_keys method, add a LN-specific safe method that does the tweak thing, deprecate PublicKey::combine with a long notice explaining how LN can port to the new thing and requesting that other people file an issue if they have other usecases. This would fix our API wart, though of course it doesn't help upstream, who wants to remove their pubkey_combine function but can't.

In the PR that added this function #291 @Tibo-lg describes a discrete-log-contract construction that feels like it's into "roll your own crypto" territory (on the part of the DLC designers, not Tibo himself) but I don't know the details of that. But I think it's probably reasonable to say "if you want to do weird things like this you have to use unsafe code to call the pubkey_combine FFI function directly, because we want no part in this".

[apoelstra]

Or we could keep combine but perma-deprecate and feature-gate it, if there are some safe-but-not-safely-encapsulatable use cases out there that we still want to support in a nice way.

[Tibo-lg]

@apoelstra I was not aware that there was a difference in security between calling combine multiple times and combine_keys. FYI the usage we have of it in rust-dlc is as follow (skipping details and other similar usages):

• we compute a number of "anticipated signatures" from an oracle's public values as S_i = R_i + H(R_i|P|M_i)*P
• we combine these into a single point with combine_keys so that we get S = S_0 + ... + S_n, which is then used as an adaptor point

I don't think this use case is vulnerable to rogue key attacks, and it would be a big performance hit to call combine multiple time instead (I don't recall the exact numbers but can re-run the benchmark if you're interested). IIRC a big reason for the performance hit was having to go through the FFI many times, so if you really want to get rid of this method (both here and upstream), I wonder if it would be possible to have an implementation upstream that just calls combine multiple times.

[Kixunil]

@Tibo-lg it's not a difference in security, it's the fact that both functions promote unsecure crypto schemes (AKA "rolling your own crypto") and this library doesn't want to promote that. You can use them securely but you must really, really know what you're doing.

Regarding FFI, you could try to figure out cross-language LTO, though I've read that it only works on Debian.

@apoelstra I was thinking if upstream could add a function for whatever LN does it'd move things forward but if people also use it for other things rugging them sucks.

[apoelstra]

@apoelstra I was not aware that there was a difference in security between calling combine multiple times and combine_keys. FYI the usage we have of it in rust-dlc is as follow (skipping details and other similar usages):

There is no difference in security between calling combine multiple times and using combine_keys. They do exactly the same operation. The only difference is that we will get no complaints from the rust-lightning people if we remove combine_keys while removing combine can only be done by replacing the API they need.

@Tibo-lg if we removed combine_keys here would you be willing to reimplement it yourself using the FFI methods exposed from secp256k1-sys?

I don't know enough about your larger scheme, but it's definitely possible for an attacker oracle to grind a sum of anticipated signatures to equal the sum of a different set of anticipated signatures, using Wagner's algorithm. Is this a problem? I don't know. But this is the sort of thing that we don't want to expose in the rust-secp API.

[Tibo-lg]

Ah sorry I guess I didn't understand what you were talking about...

@Tibo-lg if we removed combine_keys here would you be willing to reimplement it yourself using the FFI methods exposed from secp256k1-sys?

Yeah that's no problem for me.

I don't know enough about your larger scheme, but it's definitely possible for an attacker oracle to grind a sum of anticipated signatures to equal the sum of a different set of anticipated signatures, using Wagner's algorithm. Is this a problem? I don't know. But this is the sort of thing that we don't want to expose in the rust-secp API.

You're right there is that problem in the multi oracle setting, and IIRC the fix was to have oracle prove they know the pre-images of the nonces they will use to sign (though just checked and it looks like this was never merged into the specs, probably should be).

[apoelstra]

Yep, that fix is sufficient to prevent rogue-key attacks. Glad we had this discussion :P. But it also illustrates why we want to keep our API limited to "things we are specifically support and are confident in".

[djordon]

Hey folks, just discovered this and thought that I should chime in. I'm a dev working on a new wrapped BTC token and we use this function to combine public keys (we do so here). So it would be nice to either have this method here or have the FFI functions so that we could copy the implementation ourselves.

---

Question following from @apoelstra #704 (comment):

I don't know enough about your larger scheme, but it's definitely possible for an attacker oracle to grind a sum of anticipated signatures to equal the sum of a different set of anticipated signatures, using Wagner's algorithm. Is this a problem? I don't know. But this is the sort of thing that we don't want to expose in the rust-secp API.

I think I'm missing something really important here; what foot-gun does this method expose? From the conversation so far, my sense of things is that the issue is that the PublicKey::combine_keys method (and the PublicKey::combine method) allow for users to implement insecure protocols too easily. Since one of the goals here is to make it very difficult for a user to implement insecure protocols, these methods should be removed. Is that basically right?

And is my understanding that the ideal here is that both of these methods would be removed, but users could implement it themselves using the FFI functions? Also, we cannot remove PublicKey::combine because the lightning folks would complain. Is that right?

[Kixunil]

Since one of the goals here is to make it very difficult for a user to implement insecure protocols, these methods should be removed. Is that basically right?

Yes.

but users could implement it themselves using the FFI functions?

Yes, at least until upstream drops them.

Also, we cannot remove PublicKey::combine because the lightning folks would complain. Is that right?

Kinda. We could just replace it with their scheme or some other better API so it wouldn't break them but it'd seal the API hole.

[djordon]

Okay cool, makes sense.

but users could implement it themselves using the FFI functions?

Yes, at least until upstream drops them.

Oh, are there any plans for them to be dropped in libsecp256k1, or is this just a general comment about the availability of the underlying functions?

[Kixunil]

IIUC they'd love to but it's not easy.