Changeset View
Standalone View
src/secp256k1/src/modules/schnorr/schnorr_impl.h
- This file was added.
/*********************************************************************** | |||||
* Copyright (c) 2017 Amaury SÉCHET * | |||||
* Distributed under the MIT software license, see the accompanying * | |||||
* file COPYING or http://www.opensource.org/licenses/mit-license.php. * | |||||
***********************************************************************/ | |||||
#ifndef _SECP256K1_SCHNORR_IMPL_H_ | |||||
#define _SECP256K1_SCHNORR_IMPL_H_ | |||||
#include <string.h> | |||||
#include "schnorr.h" | |||||
#include "field.h" | |||||
#include "group.h" | |||||
#include "hash.h" | |||||
#include "ecmult.h" | |||||
#include "ecmult_gen.h" | |||||
/** | |||||
* Custom Schnorr-based signature scheme. | |||||
* | |||||
* Signing: | |||||
* Inputs: | |||||
* 32-byte message m, | |||||
* 32-byte scalar key x (!=0) | |||||
* public key point P, | |||||
* 32-byte scalar nonce k (!=0) | |||||
* | |||||
* Compute point R = k * G. Negate nonce if R.y is not a quadratic residue. | |||||
* Compute scalar e = Hash(R.x || compressed(P) || m). Reject nonce if e == 0 or e >= order. | |||||
* Compute scalar s = k + e * x. | |||||
* The signature is (R.x, s). | |||||
* | |||||
* Verification: | |||||
* Inputs: | |||||
* 32-byte message m, | |||||
* public key point P, | |||||
* signature: (32-byte r, scalar s) | |||||
* | |||||
* Signature is invalid if s >= order or r >= p. | |||||
* Compute scalar e = Hash(r || compressed(P) || m). Reject e == 0 or e >= order. | |||||
* Option 1 (faster for single verification): | |||||
* Compute point R = s * G - e * P. | |||||
* Reject if R is infinity or R.y is not a quadratic residue. | |||||
* Signature is valid if the serialization of R.x equals r. | |||||
* Option 2 (allows batch validation): | |||||
* Decompress x coordinate r into point R, with R.y a quadratic residue. | |||||
* Reject if R is not on the curve. | |||||
* Signature is valid if R + e * P - s * G == 0. | |||||
*/ | |||||
static int secp256k1_schnorr_sig_verify( | |||||
const secp256k1_ecmult_context* ctx, | |||||
const unsigned char *sig64, | |||||
secp256k1_ge *pubkey, | |||||
const unsigned char *msg32 | |||||
) { | |||||
secp256k1_gej Pj, Rj; | |||||
secp256k1_fe Rx; | |||||
secp256k1_scalar e, s; | |||||
int overflow; | |||||
if (secp256k1_ge_is_infinity(pubkey)) { | |||||
Fabien: This can be optimized by checking the output in secp256k1_schnorr_compute_e.
Also you may want… | |||||
deadalnixAuthorUnsubmitted Done Inline Actionssecp256k1_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. deadalnix: `secp256k1_ge` represent a point on the curve, so it'd better be on the curve. I suspect… | |||||
FabienUnsubmitted Not Done Inline ActionsYou can check the output of secp256k1_eckey_pubkey_serialize which test against infinity Fabien: You can check the output of `secp256k1_eckey_pubkey_serialize` which test against infinity | |||||
markblundebergUnsubmitted Not Done Inline ActionsIf 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. markblundeberg: If this is a totally private function (only called by `secp256k1_schnorr_verify`) then no check… | |||||
deadalnixAuthorUnsubmitted Done Inline ActionsDefining a function from the callsites is a very bad idea. deadalnix: Defining a function from the callsites is a very bad idea. | |||||
return 0; | |||||
} | |||||
/* Extract s */ | |||||
overflow = 0; | |||||
secp256k1_scalar_set_b32(&s, sig64 + 32, &overflow); | |||||
if (overflow) { | |||||
return 0; | |||||
} | |||||
/* Extract R.x */ | |||||
if (!secp256k1_fe_set_b32(&Rx, sig64)) { | |||||
return 0; | |||||
} | |||||
/* Compute e */ | |||||
if (!secp256k1_schnorr_compute_e(&e, sig64, pubkey, msg32)) { | |||||
return 0; | |||||
markblundebergUnsubmitted Not Done Inline ActionsThis 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: markblundeberg: This seems to be incorrectly coded to fail for (rare) hashes above group order.
In contrast… | |||||
deadalnixAuthorUnsubmitted Done Inline ActionsI'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. deadalnix: I'm not convinced that this approach is correct. It causes a range of number to be twice as… | |||||
markblundebergUnsubmitted Not Done Inline ActionsI 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. markblundeberg: I think it's it's fine either way, given the twice-probable numbers are so rare. We can do it… | |||||
markblundebergUnsubmitted Not Done Inline ActionsAnother 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: Another curiousity -- if I happen to accidentally (and improbably) produce a signature with e=0… | |||||
markblundebergUnsubmitted Not Done Inline ActionsWait no, that is incorrect. markblundeberg: Wait no, that is incorrect. | |||||
} | |||||
/* Verify the signature */ | |||||
secp256k1_scalar_negate(&e, &e); | |||||
secp256k1_gej_set_ge(&Pj, pubkey); | |||||
secp256k1_ecmult(ctx, &Rj, &Pj, &e, &s); | |||||
if (secp256k1_gej_is_infinity(&Rj)) { | |||||
return 0; | |||||
} | |||||
/* Check that R.x is what we expect */ | |||||
if (!secp256k1_gej_eq_x_var(&Rx, &Rj)) { | |||||
return 0; | |||||
} | |||||
/* Check that jacobi(R.y) is 1 */ | |||||
if (!secp256k1_gej_has_quad_y_var(&Rj)) { | |||||
return 0; | |||||
} | |||||
/* All good, we have a valid signature. */ | |||||
return 1; | |||||
} | |||||
static int secp256k1_schnorr_compute_e( | |||||
secp256k1_scalar* e, | |||||
const unsigned char *r, | |||||
secp256k1_ge *p, | |||||
const unsigned char *msg32 | |||||
) { | |||||
int overflow = 0; | |||||
size_t size; | |||||
secp256k1_sha256 sha; | |||||
unsigned char buf[33]; | |||||
secp256k1_sha256_initialize(&sha); | |||||
/* R.x */ | |||||
secp256k1_sha256_write(&sha, r, 32); | |||||
/* compressed P */ | |||||
secp256k1_eckey_pubkey_serialize(p, buf, &size, 1); | |||||
VERIFY_CHECK(size == 33); | |||||
secp256k1_sha256_write(&sha, buf, 33); | |||||
/* msg */ | |||||
secp256k1_sha256_write(&sha, msg32, 32); | |||||
/* compute e */ | |||||
secp256k1_sha256_finalize(&sha, buf); | |||||
secp256k1_scalar_set_b32(e, buf, &overflow); | |||||
return !overflow & !secp256k1_scalar_is_zero(e); | |||||
markblundebergUnsubmitted Not Done Inline Actionssee above comment markblundeberg: see above comment | |||||
deadalnixAuthorUnsubmitted Done Inline Actionsdito deadalnix: dito | |||||
} | |||||
static int secp256k1_schnorr_sig_sign( | |||||
const secp256k1_ecmult_gen_context* ctx, | |||||
unsigned char *sig64, | |||||
const secp256k1_scalar *privkey, | |||||
secp256k1_ge *pubkey, | |||||
const secp256k1_scalar *nonce, | |||||
const unsigned char *msg32 | |||||
) { | |||||
secp256k1_gej Rj; | |||||
secp256k1_ge Ra; | |||||
secp256k1_scalar e, s, k; | |||||
if (secp256k1_scalar_is_zero(privkey) || secp256k1_scalar_is_zero(nonce)) { | |||||
return 0; | |||||
} | |||||
k = *nonce; | |||||
secp256k1_ecmult_gen(ctx, &Rj, &k); | |||||
secp256k1_ge_set_gej(&Ra, &Rj); | |||||
if (!secp256k1_fe_is_quad_var(&Ra.y)) { | |||||
/** | |||||
* R's y coordinate is not a quadratic residue, which is not allowed. | |||||
* Negate the nonce to ensure it is. | |||||
*/ | |||||
secp256k1_scalar_negate(&k, &k); | |||||
FabienUnsubmitted Not Done Inline ActionsI'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. Fabien: I'm not sure how/if this could be exploited, but this leaves an intermediate variable t on the… | |||||
} | |||||
secp256k1_fe_normalize(&Ra.x); | |||||
secp256k1_fe_get_b32(sig64, &Ra.x); | |||||
if (!secp256k1_schnorr_compute_e(&e, sig64, pubkey, msg32)) { | |||||
markblundebergUnsubmitted Not Done Inline ActionsIf 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. markblundeberg: If we go with the approach of having invalid `e` values, then it would make sense to write the… | |||||
deadalnixAuthorUnsubmitted Done Inline Actionse 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. deadalnix: `e` cannot be generated in a loop like `k` is. Generating `k` is generating a random number… | |||||
markblundebergUnsubmitted Not Done Inline Actions"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:
markblundeberg: "You might want to loop the whole signature procedure if computing e fails, starting with a new… | |||||
secp256k1_scalar_clear(&k); | |||||
return 0; | |||||
} | |||||
secp256k1_scalar_mul(&s, &e, privkey); | |||||
secp256k1_scalar_add(&s, &s, &k); | |||||
secp256k1_scalar_clear(&k); | |||||
secp256k1_scalar_get_b32(sig64 + 32, &s); | |||||
return 1; | |||||
} | |||||
static int secp256k1_schnorr_sig_generate_k( | |||||
markblundebergUnsubmitted Not Done Inline ActionsNot 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. markblundeberg: Not that it creates an insecurity, but why not follow sipa's determistic approach? Fine either… | |||||
deadalnixAuthorUnsubmitted Done Inline ActionsThis is deterministic as well. deadalnix: This is deterministic as well. | |||||
markblundebergUnsubmitted Not Done Inline ActionsNo problem, I just have to alter the spec to reflect the 'recommended' nonce generation algo and this is a fine way to do it. markblundeberg: No problem, I just have to alter the spec to reflect the 'recommended' nonce generation algo… | |||||
deadalnixAuthorUnsubmitted Done Inline ActionsThe nonce can be generated any way really, these are just recommendations. deadalnix: The nonce can be generated any way really, these are just recommendations. | |||||
secp256k1_scalar *k, | |||||
const unsigned char *msg32, | |||||
const unsigned char *seckey, | |||||
secp256k1_nonce_function noncefp, | |||||
const void *ndata | |||||
) { | |||||
int overflow = 0; | |||||
int ret = 0; | |||||
unsigned int count = 0; | |||||
unsigned char nonce32[32]; | |||||
/* Seed used to make sure we generate different values of k for schnorr */ | |||||
const unsigned char secp256k1_schnorr_algo16[17] = "Schnorr+SHA256 "; | |||||
if (noncefp == NULL) { | |||||
noncefp = secp256k1_nonce_function_default; | |||||
} | |||||
while (1) { | |||||
ret = noncefp(nonce32, msg32, seckey, secp256k1_schnorr_algo16, (void*)ndata, count++); | |||||
if (!ret) { | |||||
break; | |||||
} | |||||
secp256k1_scalar_set_b32(k, nonce32, &overflow); | |||||
if (!overflow && !secp256k1_scalar_is_zero(k)) { | |||||
break; | |||||
} | |||||
} | |||||
memset(nonce32, 0, 32); | |||||
return ret; | |||||
} | |||||
#endif |
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.