Page MenuHomePhabricator

[secp256k1] Implement Schnorr signatures
ClosedPublic

Authored by deadalnix on Dec 2 2018, 19:48.

Details

Summary

This implement Schnorr signatures on secp256k1 as per https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr.mediawiki

This implement a variation of Schnorr similar to edDSA by Daniel J. Bernstein.

Test Plan

Added test cases for the signature scheme.

Diff Detail

Repository
rABC Bitcoin ABC
Branch
schnorr
Lint
Lint OK
Unit
No Unit Test Coverage
Build Status
Buildable 4467
Build 6998: Bitcoin ABC Teamcity Staging
Build 6997: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Fix comments on test cases

jasonbcox requested changes to this revision.Dec 21 2018, 01:33
jasonbcox added a subscriber: jasonbcox.
jasonbcox added inline comments.
src/secp256k1/include/secp256k1_schnorr.h
50 ↗(On Diff #6341)

Shouldn't the pubkey be derived from the seckey? Seems strange to pass both in.

src/secp256k1/src/modules/schnorr/schnorr_impl.h
40 ↗(On Diff #6341)

I don't see these checks being made. Am I missing something?

74 ↗(On Diff #6341)

Shouldn't this be r instead of Rx?

79 ↗(On Diff #6341)

Any reason to use sig64 here instead of r?

107 ↗(On Diff #6341)

Either this should be r or Rx to be consistent with the above code.

This revision now requires changes to proceed.Dec 21 2018, 01:33
Fabien added inline comments.Dec 21 2018, 07:19
src/secp256k1/src/modules/schnorr/main_impl.h
49 ↗(On Diff #6305)

Actually the signing process won't fail, seckey will be silently reduced by this call (and e*x output will be correct, I was wrong in my previous comment).
I think that if an invalid key is given, it should return an error. This is the behavior of the other signature functions, or secp256k1_ec_pubkey_create.

src/secp256k1/src/modules/schnorr/tests_impl.h
214 ↗(On Diff #6305)

The remark was not about including it but rather about the numbering. Maybe you could add a link to the source CSV file in a comment ?
Also you dismissed test 4c (message should not be reduced), which is more relevant.

deadalnix added inline comments.Dec 22 2018, 18:30
src/secp256k1/src/modules/schnorr/schnorr_impl.h
40 ↗(On Diff #6341)

Yes

79 ↗(On Diff #6341)

Yes

107 ↗(On Diff #6341)

ok

deadalnix updated this revision to Diff 6411.Dec 22 2018, 18:30

rx => r

Fabien requested changes to this revision.Dec 24 2018, 11:38
Fabien added inline comments.
src/secp256k1/src/modules/schnorr/schnorr_impl.h
62 ↗(On Diff #6411)

This can be optimized by checking the output in secp256k1_schnorr_compute_e.
Also you may want to check that the pubkey is on the curve.

This revision now requires changes to proceed.Dec 24 2018, 11:38
deadalnix requested review of this revision.Dec 26 2018, 17:33
deadalnix added inline comments.
src/secp256k1/src/modules/schnorr/schnorr_impl.h
62 ↗(On Diff #6411)

secp256k1_ge represent a point on the curve, so it'd better be on the curve. I suspect secp256k1_schnorr_compute_e would fail the hard way rather than returning an error when the point is at infinity.

Fabien added inline comments.Dec 28 2018, 14:20
src/secp256k1/src/modules/schnorr/schnorr_impl.h
62 ↗(On Diff #6411)

You can check the output of secp256k1_eckey_pubkey_serialize which test against infinity

markblundeberg requested changes to this revision.Jan 4 2019, 02:20

A few comments. Most notably the computation of e should not be failing on overflow.

src/secp256k1/src/modules/schnorr/schnorr_impl.h
62 ↗(On Diff #6411)

If this is a totally private function (only called by secp256k1_schnorr_verify) then no check is necessary since secp256k1_schnorr_verify is passed a secp256k1_pubkey type, where the point at infinity cannot even be encoded.

80 ↗(On Diff #6411)

This seems to be incorrectly coded to fail for (rare) hashes above group order.

In contrast, in the spec for Schnorr we have e = SHA256(...) mod n, which never fails.

see:

131 ↗(On Diff #6411)

see above comment

175 ↗(On Diff #6411)

Not that it creates an insecurity, but why not follow sipa's determistic approach? Fine either way though: some may argue this is slow but it's wallet side only so eh, whatever.

This revision now requires changes to proceed.Jan 4 2019, 02:20
deadalnix requested review of this revision.Jan 4 2019, 13:52

I'm not convinced that the mod approach is a good idea. In general this is known to be a problem. BIPSCHNORR argues that this is not a problem because the range of number that are twice as probable is small, but I'm not convinced this is desirable.

src/secp256k1/src/modules/schnorr/schnorr_impl.h
62 ↗(On Diff #6411)

Defining a function from the callsites is a very bad idea.

80 ↗(On Diff #6411)

I'm not convinced that this approach is correct. It causes a range of number to be twice as probable as others, which is not good.

131 ↗(On Diff #6411)

dito

175 ↗(On Diff #6411)

This is deterministic as well.

A few replies. I have to still review some other parts of code so some more comments may be coming.

src/secp256k1/src/modules/schnorr/schnorr_impl.h
80 ↗(On Diff #6411)

I think it's it's fine either way, given the twice-probable numbers are so rare. We can do it this way, no problem and I think it's certainly the 'safer' way. It's also fully compatible with batch verification. Of course, we should modify the spec to match our system.

BTW a thought occurred to me in my sleep regarding this, which is that if a third party is somehow able to crack sha256 far enough to produce e==0, then under sipa's construction they can trivially forge a signature since the key drops out of the signature curve equation (it becomes R = s*G). I suppose output == 0 (or output == group order) is not a particularly special number in sha256, so it would effectively require a full preimage break of sha256. But still, it is a curious property.

163 ↗(On Diff #6411)

If we go with the approach of having invalid e values, then it would make sense to write the nonce-retry loop to cover this code as well.

When Schnorr one day makes it to hardware wallets, will the discrepancy be an issue? Hardware wallets may initially do things 'the BTC way' and rarely produce out-of-range e values, though it wouldn't hurt for them to opt in to restricting the range of e.

175 ↗(On Diff #6411)

No problem, I just have to alter the spec to reflect the 'recommended' nonce generation algo and this is a fine way to do it.

Seems good then. A couple more remarks added.

I am not really able to review the test data but the tests themselves seem to have the right idea. It looks like there are a few more test vectors at https://github.com/sipa/bips/blob/bip-schnorr/bip-schnorr/test-vectors.csv , for example there are two tests for the case R=0 not just one.

src/secp256k1/src/modules/schnorr/main_impl.h
30 ↗(On Diff #6411)

Redundant? Can generate pubkey from seckey, and then have same function signature as secp256k1_ecdsa_sign.

Compare https://github.com/bitcoin-core/secp256k1/blob/8ea54254ad9012e56f3acf06cd6943a3e6b96a38/src/modules/schnorrsig/main_impl.h#L61-L62

src/secp256k1/src/modules/schnorr/schnorr_impl.h
80 ↗(On Diff #6411)

Another curiousity -- if I happen to accidentally (and improbably) produce a signature with e=0, then it is freely malleable by any third party. Also likely just a curiosity, but weird.

markblundeberg added inline comments.Jan 4 2019, 17:10
src/secp256k1/src/modules/schnorr/schnorr_impl.h
80 ↗(On Diff #6411)

Wait no, that is incorrect.

deadalnix added inline comments.Jan 4 2019, 17:26
src/secp256k1/src/modules/schnorr/main_impl.h
30 ↗(On Diff #6411)

Ok.

src/secp256k1/src/modules/schnorr/schnorr_impl.h
163 ↗(On Diff #6411)

e cannot be generated in a loop like k is. Generating k is generating a random number (blinding factor). The signer can use any method as long as nobody else can predict anything about k. So looping until you find a suitable value for k is doable.

One the other hand, e is a challenge. The whole point of the challenge is that it cannot be chosen by the signer. You should think of e as a random challenge generated by the verifier, but, because we don't want to proof to be interactive, everybody using the algorithm can decide they trust SHA256 to be as good as a randomly selected challenge by the verifier.

You might want to loop the whole signature procedure if computing e fails, starting with a new value for k, but at this point we might as well return false and let the caller deal with it.

175 ↗(On Diff #6411)

The nonce can be generated any way really, these are just recommendations.

markblundeberg added inline comments.Jan 4 2019, 17:43
src/secp256k1/src/modules/schnorr/schnorr_impl.h
163 ↗(On Diff #6411)

"You might want to loop the whole signature procedure if computing e fails, starting with a new value for k" -- yes, this is what I was imagining, that the rfc6979 counter should be incremented also if e fails. That way the signing is guaranteed to succeed for all msg32 and key.

Otherwise, the caller would be faced with a few undesirable options:

  • give up and pass error message to user,
  • somehow automatically malleate msg32 and try again,
  • automatically fallback to a different noncefp instead of rfc6979 (instead use CSPRNG?) and keep retrying.
jasonbcox added inline comments.Jan 4 2019, 18:18
src/secp256k1/src/modules/schnorr/main_impl.h
30 ↗(On Diff #6411)

+1 I think reducing the public API to it's simplest form is important for reducing any potential attack surface.

markblundeberg added a comment.EditedJan 4 2019, 23:13

I'm not convinced that the mod approach is a good idea. In general this is known to be a problem. BIPSCHNORR argues that this is not a problem because the range of number that are twice as probable is small, but I'm not convinced this is desirable.

Hmm, I have been looking around some more and I can't find any other discrete log signature algos that constrain e in this way: at least DSA, ECDSA, basic Schnorr, EdDSA, ElGamal, all do a modulo wraparound on the hash rather than having extra fail conditions during verification/signing. Seems cryptographers are generally ok with it.

The BIPSCHNORR only makes this biasing comment (footnote 8) about k generation, where biases are generally concern. No such comment about bias in e. From what I understand, small biases in the e hash function are not a problem since e just has to be second-preimage resistant for security, and its preimage is fully public; unlike with k where preimage is private and the hash function has to act as a 'randomizer'.

Note to observers: Much discussion about e selection was had in other avenues... interesting cryptography behind this.

Regarding the e=0 case in particular, I posted a question on stackexchange https://crypto.stackexchange.com/questions/66334/why-is-e-0-allowed-in-schnorr-signatures and got back an insightful answer.

deadalnix updated this revision to Diff 6585.Jan 10 2019, 14:28

Update the signature algorithm to accept any value for e. It ensures there are less hard ot test special codepath. It is not a problem because:

  • We require preimage reisstance, which is 256 bits secuity and the curve is assumed to be 128 bits security. We can weaken this 256 bits security by pickinig e in a non uniform manner without weakening the overall security of the construction.
  • e = 0 is not a problem because one can grind s in e' = H(m || compressed(P) || s*G + e*P) until e' = e for any value of e.
deadalnix added inline comments.Jan 14 2019, 15:51
src/secp256k1/src/modules/schnorr/main_impl.h
30 ↗(On Diff #6411)

ECDSA doesn't need the pubkey for signing, so that wouldn't make sense to pass it. The comment on attack surface makes no sense to me. The public key is public anyways, so in what case can I attack anything using the public key ?

deadalnix updated this revision to Diff 6648.Jan 14 2019, 15:53
  • rebase
  • clear the nonce when secp256k1_schnorr_sig_generate_k fails. While it shouldn't be set to begin with, it makes the code more solid as it is not a good idea to rely on implementation detail of secp256k1_schnorr_sig_generate_k in its caller.
jasonbcox added inline comments.Jan 14 2019, 20:23
src/secp256k1/src/modules/schnorr/main_impl.h
30 ↗(On Diff #6411)

I'm referring to the attack surface of the API itself, not the use of the public key. If you derive the public key from the private key that's provided, the attack surface is reduced by removing the case of providing a mismatching pub-priv keypair.

markblundeberg added inline comments.Jan 20 2019, 11:55
src/secp256k1/src/modules/schnorr/main_impl.h
30 ↗(On Diff #6411)

Regardless of attacks, it looks like it is not helpful to have pubkey argument in the first place:

  • If the secp256k1_schnorr_sign caller would have ready access to a cached pubkey that would give a speed-up, but that doesn't seem to me like it will be a common situation:
  • The main place this will get called (SignSchnorr in D2348) currently has to do the work of regenerating the pubkey itself.
  • It doesn't seem useful to ever allow the caller to provide a different pubkey. In particular this function cannot be used for multi-key aggregation.
  • It's inconsistent API anyway, see my first comment above.

Is the reason to keep this pubkey argument because of the speedup for other hypothetical codebases, or am I missing something? If so, it would be even more optimized to require the pubkey to be passed in compressed form (unsigned char * type, instead of secp256k1_pubkey * type).

jasonbcox accepted this revision.Jan 30 2019, 22:06
markblundeberg accepted this revision.Jan 31 2019, 01:21

Went over this in fine detail all over again. Still good. 👍

src/secp256k1/src/modules/schnorr/schnorr_impl.h
129 ↗(On Diff #6648)

now unnecessary to make these computations -- nobody uses return value.

Fabien accepted this revision.Jan 31 2019, 08:12
Fabien added inline comments.
src/secp256k1/src/modules/schnorr/main_impl.h
13 ↗(On Diff #6411)

Could you please format this on multiple lines ? clang-format does not proceed on secp256k1 lib

src/secp256k1/src/modules/schnorr/schnorr_impl.h
158 ↗(On Diff #6411)

I'm not sure how/if this could be exploited, but this leaves an intermediate variable t on the stack which contains data from the nonce.

This revision is now accepted and ready to land.Jan 31 2019, 08:12
Fabien added a comment.Jan 31 2019, 08:27

Please don't care about the last comment, this has already been discussed offline.
I failed to found how to delete my comment, if possible at all.

deadalnix updated this revision to Diff 7056.Jan 31 2019, 13:25

remove the pubkey parameter

This revision was automatically updated to reflect the committed changes.