Avoiding the EC multiplication during signing by using precomputed pubkey data

[real-or-random]

Split out discussion. This one is about avoiding the EC multiplication by using precomputed pubkey data.

It seems a question is whether we need to protect against the situation where the public key (or data derived from it), passed to the signing function, is actually computed by the signer itself, or untrusted.

In the case of signing devices with a fixed master BIP32 key, the public key is likely going be computed by the device itself anyway at signing time, so it's wasteful to have the signing algorithm redo it.

On the other hand, @real-or-random and @jonasnick correctly point out that if the public key data provided to the signing algorithm is untrusted, this public key data must also be an input to the derivation function. I don't think we have a proof that even with this modified derivation function, the resulting signature scheme is secure.

So I think that's an unfortunate situation to be in. We shouldn't standardize an (alternative) signing algorithm that takes untrusted pubkey data as input (because we have no proof it is secure), but simultaneously, having an API that takes in trusted pubkey data is scary (because if the API is abused with untrusted pubkey data, we have a known attack).

FWIW, the ed25519-donna implementation seems to happily take the public key as input to the signer. I wonder if the concern of an untrusted public key has been analysed in that context.

Originally posted by @sipa in https://github.com/bitcoin-core/secp256k1/pull/558

[sipa]

After some more discussion on IRC, it seems worthwhile to modify the signing algorithm to use a nonce function that always includes the public key + negation flag.

We don't have a proof, but I think there is a pretty decent informal argument that that is actually secure - there can't be any nonce leakage if the nonce is computed using a superset of all the data that goes into the challenge hash, and a signature with invalid P in the challenge hash should be useless otherwise. An actual proof would be nice, and perhaps a prerequisite before we actually advertise the untrusted-pubkey-input feature.

Still, given that it does not increase the amount of hashing in the nonce derivation to add the pubkey + neg flag makes it kind of an obvious improvement.

[sipa]

One consideration: if people sign with untrusted public keys (which are fed to nonce derivation), I suspect that whatever protections key-prefixed Schnorr has over non-key-prefixed disappear, as we need to assume the public keys are attacker controlled.

[sipa]

See also the post by @gmaxwell: https://moderncrypto.org/mail-archive/curves/2020/001012.html

[sipa]

Note that I think there are two independent questions here:

• Do we want to switch to including pubkey/neg in the nonce derivation function by default, without exposing/advertizing the untrusted-pubkey feature (or maybe exposing it, but still only intended it to be used with self-computed pubkeys).
• Specifying/analysing the security properties of untrusted-pubkey input to a signing algorithm that already does the above.

[real-or-random]

I agree, we should add the "full" pubkey to the nonce derivation.

One consideration: if people sign with untrusted public keys (which are fed to nonce derivation), I suspect that whatever protections key-prefixed Schnorr has over non-key-prefixed disappear, as we need to assume the public keys are attacker controlled.

Exactly, I was just typing this post to point this out. And this is a worse concern that noone has brought up so far in the discussion.

We heavily rely on key-prefixing for security with tweaked keys. Schnorr signature with attacker-controlled keys used as the prefix (like without key-prefixing) are not secure when we can tweak keys. Say I can trick you into signing with your correct secret key x but with wrong public key (x+H(xG, data))G . Then I can tweak your signature to be valid for the wrong public key.

This is a different attack, adding the public key to the nonce derivation does not help here.

[real-or-random]

And we're the first to rely on tweaked keys in practice, so the fact that we don't know about any real-world attacks on other signature schemes where the attacker provides the wrong public key (e.g., EdDSA) may not be so useful.

AFAIK EdDSA implementations often store the public key together with the secret key. But that breaks our model that the secret key is simply 256 bits, and it does not work well with tweaked keys again.

What we could do (related/same? as https://github.com/bitcoin-core/secp256k1/pull/558#discussion_r371436501) is to define an "auxilliary" key [0] that is the public key, MACed with the secret key, e.g., simply (pk, H(pk || sk)) for a newly tagged hash function H. This way of storing pk has integrity built in, and the signing algorithm can recompute the hash before trusting the pk over which the attacker potentially has control, e.g., because it read stored from an unstrusted cache on disk or the result of a computation in some interactive signing process.

That's not for free but also much cheaper than an EC multiplication. edit: If you're courageous you can share the H(pk || ... midstate with the challenge hash computation.

[0] Sorry for switching terms again but yes, the term "extended public key" exists already as in xpub.

[gmaxwell]

AFAIK EdDSA

I have found only a single one that did. The overwhelmingly common ones do not.

I think doing so is not unreasonable, but overall implementations do not.

and it does not work well with tweaked keys again.

It would work fine if there were tweak functions that operated on the same interface.

MACed with the secret key,

I think that might be a little excessive? If there is arbitrary corruption we're already in trouble. So long as the nonce function takes all the input, a corrupted key just risks signing for a related key. But if it's corruption rather than a maliciously generated point, no one will know the DL for the fixup. If the key is malicious and managed to get loaded into our extended secret key, then presumably the loading process is gonna end up setting the right mac too...

nonce derivation function by default, without exposing/advertizing the untrusted-pubkey feature

At a minimum. Even if the interface doesn't take the key and generates it internally, the nonce hash should get it. From a BIP perspective this should be the only question, and I think the answer is unambiguous.

I think just having a schnorr secret key object that has the pubkey and flag in it... and a function to load a regular secret key into that (that ecmults to generate the pubkey and extracts the flag). Callers that don't want to deal with storing the longer key can just always load it, for a performance penalty.

If the pubkey is loaded into a combined seckeypub object by functions that always generate it... then the security issue doesn't arise.

[jonasnick]

Given that untrusted pubkeys break the security of signing (see @real-or-random's related key attack), tying the pubkey to the seckey seems to be the only viable solution. Also, adding the public key to the deterministic nonce function to protect against corruption makes a lot of sense.

MAC'ing the pubkey indeed seems to be excessive. If attackers can write arbitrarily, they can set most bits of the secret key to zero and after signing brute force search x' via (s - H(...)x')G ?= R.

It's clear that if pubkey precomputation is used in libsecp, people will try to implement the same thing regardless of whether it's mentioned or even discouraged in the BIP. Therefore, we should specify how to do it correctly if we find a wording that's not "fragile".

[real-or-random]

I agree MACing is excessive in a simple implementation that stores secret keys in RAM (such as libsecp256k1). I guess I had a different scenario in mind when I mentioned this.

I think it can be interesting when you store your secret keys differently than the precomputed public keys, and you trust one storage more than the other. And I think that's not unrealistic, in particular with HD wallets where the seed is short and thus easier to store. Think of a hardware wallet that stores its HD seed in some (hopefully) very secure trusted storage but then wants to store precomputed public keys on some other drive. Using a MAC it could actually hand the precomputed public keys over to the host and then later query the host for the public key when necessary.

tying the pubkey to the seckey seems to be the only viable solution

Right, and one related issue here is what API will want to use for tweaking. In libsecp256k1, tweaking is an operation on the public key and on the secret key. Alternatively, one could think about this in terms of an API that still is able to tweak public keys but then has a sign_with_tweak function which never output the tweaked secret key, which then becomes an intermediate value. Not sure what is better, I haven't really thought about this so far.

[gmaxwell]

Interface wise, I think it's nice if the pubkey is optional. Signing is faster if you have it, if you don't care you don't bother with it. Unfortunately, that is incompatible with "pubkey is part of the secret". Pubkey is part of the secret is also incompatible with "you don't need a keygen function, you just need randomness" :(

[ajtowns]

One consideration: if people sign with untrusted public keys (which are fed to nonce derivation), I suspect that whatever protections key-prefixed Schnorr has over non-key-prefixed disappear, as we need to assume the public keys are attacker controlled.

I think that's half right -- with non-key-prefixed schnorr, you get a valid signature for pubkey P on message m, and can then convert that to a valid signature for pubkey P+aG on message m, provided you know a.

With this, I think you can still generate a valid signature for pubkey P+aG on message m but you have to specify P+aG as the pubkey at signing time and the signature can't be made valid for any other pubkey. That's technically not quite as powerful, but it seems like it's just as good in practice?

As written, we already calculate the pubkey P and squareness before generating the nonce, so throwing ext_bytes(P) into Hash_BIPSchnorrDerive seems easy (it adds an extra round though). I think passing in the pubkey can probably be briefly discussed as an Alternative Signing option, like synthetic nonces?

[gmaxwell]

(it adds an extra round though)

It shouldn't, it should be possible to have the same number of compression function calls as currently and still have 23 bytes left over for synthetic nonce input. (care should be taken to recommend the synthetic nonce input size to be small enough to avoid gratuitously adding another compression function run)

[jonasnick]

Signing is faster if you have it, if you don't care you don't bother with it. Unfortunately, that is incompatible with "pubkey is part of the secret" (@gmaxwell)

I don't see how this is incompatible. In libsecp lingo, if schnorrsig_sign could just be a wrapper for "sign_fast":

/* if you just want the pubkey */
xonly_pubkey_create(xonly_pubkey, seckey)
/* if you want the pubkey and sign */
xonly_keypair_create(keypair, seckey)
xonly_keypair_get_pubkey(xonly_pubkey, keypair)
/* perhaps also add serialize and parse function for keypairs */

schnorrsig_sign_fast(keypair, m)
schnorrsig_sign(seckey, m) {
  xonly_keypair_create(keypair, seckey)
  sign_fast(keypair, m)
}

[gmaxwell]

That doesn't sound bad.

[ajtowns]

I think this issue is resolved