ecdsa sign-to-contract module, with anti nonce covert chan util functions

benma commented at 4:33 pm on October 8, 2019: contributor

Alternative to #637, where the main s2c signing function lives in secp256k1.c. See this thread for some discussion about this: #637 (review)

in src/secp256k1.c:778 in baec472ef4 outdated

773+        noncefp = secp256k1_nonce_function_default;
774+    }
775+    /* sign-to-contract commitments only work with the default nonce function,
776+     * because we need to ensure that s2c_data is actually hashed into the nonce and
777+     * not just ignored. */
778+    ARG_CHECK(s2c_data32 == NULL || noncefp == secp256k1_nonce_function_default);

benma commented at 4:40 pm on October 8, 2019:

Since secp256k1_ecdsa_sign() and secp256k1_ecdsa_s2c_sign() are the only public api functions calling this, and they choose the correct arguments, some of the branches here are never reached. It seems a bit silly to add unit tests for internal functions for lines which can never be reached. Not sure what to do about that, maybe just drop the checks?

jonasnick commented at 2:37 pm on November 11, 2019:

Yes it doesn’t make sense for them to be ARG_CHECKs. You can make them VERIFY_CHECKs. They are only enabled in tests and only when not compiling for coverage.

benma commented at 7:54 pm on December 29, 2019:

Done

in src/secp256k1.c:787 in baec472ef4 outdated

782+    ARG_CHECK(s2c_data32 == NULL || noncedata == NULL);
783+    if (s2c_opening != NULL) {
784+        secp256k1_s2c_opening_init(s2c_opening);
785+    }
786+
787+    if(s2c_data32 != NULL) {

benma commented at 4:40 pm on October 8, 2019:

The diff of this function to the previous secp256k1_ecdsa_sign could be reduced much more if the s2c module’s secp256k1_ecdsa_s2c_sign() did the hashing and provided it through noncedata. It seems also to be the right place for it, as it is closer to the rest of the anti-nonce-covert-channel protocol implementation. What do you think, @jonasnick ?

jonasnick commented at 2:26 pm on November 11, 2019:

Agreed

jonasnick commented at 2:59 pm on November 11, 2019:

In my implementation this also hashes noncedata into the single value, because otherwise the noncedata would be unused. Your ecdsa_s2c_sign doesn’t use noncedata but it could in principle and I think it should because it allows “synthetic nonces” (i.e. nonces which have a deterministically derived and a random component).

benma commented at 7:26 pm on December 29, 2019:

As discussed previously (in the other PR possibly), we settled on removing noncedata from secp256k1_ecdsa_s2c_sign(), as we couldn’t think of a good use case. SInce I will be moving the noncedata=hash(s2c_data) computation over there, there is no noncedata to mix in anymore. Sounds overall simpler than adding code for an unclear future use.

benma commented at 9:16 am on October 10, 2019: contributor

I added a commit (recovery: re-use secp256k1_ecdsa_sign_helper) to show that the recovery module can also re-use the sign-helper as it was basically a copy/paste of secp256k1_ecdsa_sign().

Seeing this, after fixing up some cosmetics, I would prefer this alternative.

benma referenced this in commit a1105721bf on Oct 13, 2019

benma referenced this in commit 64e56f8354 on Oct 13, 2019

in include/secp256k1_ecdsa_sign_to_contract.h:10 in db0ea252a9 outdated

 5+
 6+#ifdef __cplusplus
 7+extern "C" {
 8+#endif
 9+
10+/** Same as secp256k1_ecdsa_sign, but s2c_data32 is committed to by adding `hash(R1, s2c_data32)` to

jonasnick commented at 1:01 pm on November 11, 2019:

what’s R1?

benma commented at 7:54 pm on December 29, 2019:

Fixed.

in src/secp256k1.c:449 in db0ea252a9 outdated

457-    ARG_CHECK(signature != NULL);
458-    ARG_CHECK(seckey != NULL);
459-    if (noncefp == NULL) {
460-        noncefp = secp256k1_nonce_function_default;
461-    }
462+/* TODO: re-order functions in this file so forward declarations are not needed? */

jonasnick commented at 2:31 pm on November 11, 2019:

At least move sign_helper here for a nicer diff and forward declare ec_commit_seckey.

benma commented at 7:55 pm on December 29, 2019:

Done.

in include/secp256k1_ecdsa_sign_to_contract.h:72 in baec472ef4 outdated

67+ *  Args:           ctx: pointer to a context object (cannot be NULL)
68+ *  Out:  client_commit: pointer to a pubkey where the clients public nonce will be
69+ *                       placed. (cannot be NULL)
70+ *  In:           msg32: the 32-byte message hash to be signed (cannot be NULL)
71+ *             seckey32: the 32-byte secret key used for signing (cannot be NULL)
72+ *              noncefp: pointer to a nonce generation function. If NULL, secp256k1_nonce_function_default is used

jonasnick commented at 3:17 pm on November 11, 2019:

not an argument

in include/secp256k1_ecdsa_sign_to_contract.h:90 in baec472ef4 outdated

85+ *  Returns 1 on success, 0 on failure.
86+ *  Args:              ctx: pointer to a context object (cannot be NULL)
87+ *  Out: rand_commitment32: pointer to 32-byte array to store the returned commitment (cannot be NULL)
88+ *  In:             rand32: the 32-byte randomness to commit to (cannot be NULL)
89+ */
90+SECP256K1_API int secp256k1_ecdsa_s2c_anti_nonce_covert_channel_host_commit(

jonasnick commented at 3:21 pm on November 11, 2019:

perhaps put this before client_commit?

in src/modules/ecdsa_sign_to_contract/tests_impl.h:12 in db0ea252a9 outdated

 7+#ifndef SECP256K1_MODULE_ECDSA_SIGN_TO_CONTRACT_TESTS_H
 8+#define SECP256K1_MODULE_ECDSA_SIGN_TO_CONTRACT_TESTS_H
 9+
10+static int mock_noncefp_result = 1;
11+static uint8_t* mock_noncefp_nonce = NULL;
12+static int nonce_function_non_rfc6979(unsigned char *nonce32, const unsigned char *msg32, const unsigned char *key32, const unsigned char *algo16, void *data, unsigned int counter) {

jonasnick commented at 4:10 pm on November 11, 2019:

this seems to be unused?

in src/modules/ecdsa_sign_to_contract/tests_impl.h:333 in baec472ef4 outdated

345+            CHECK(secp256k1_ecdsa_s2c_anti_nonce_covert_channel_host_verify(ctx, &signature, host_nonce_contribution, &s2c_opening, &client_commitment) == 0);
346+            /* revert */
347+            sigbytes[i] = (((int)sigbytes[i]) + 255) % 256;
348+        }
349+    }
350+    { /* host_verify: client commitment != opening original pubnonce */

jonasnick commented at 4:58 pm on November 13, 2019:

A few cases could be added, like wrong host_nonce_contribution or wrong s2c_opening (same in my PR). Also, what if host_nonce_contribution doesn’t match it’s commitment?

in src/modules/ecdsa_sign_to_contract/main_impl.h:120 in baec472ef4 outdated

71+    }
72+
73+    secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &rj, &k);
74+    secp256k1_ge_set_gej(&r, &rj);
75+    secp256k1_pubkey_save(client_commit, &r);
76+    return 1;

jonasnick commented at 4:59 pm on November 13, 2019:

We should explicitly zeroize nonce32 and k (same in my PR).

benma commented at 7:44 pm on December 29, 2019:

Done; though in your PR it seems to be missing? https://github.com/bitcoin-core/secp256k1/pull/590/files#diff-313ca26f0048bc16a608709915d0111eR94

In the future, we should use a safe memory zeroing function, otherwise there is no guarantee the compiler won’t optimize it away.

in include/secp256k1_ecdsa_sign_to_contract.h:88 in baec472ef4 outdated

83+/** Create a randomness commitment on the host as part of the ECDSA Anti Nonce Covert Channel Protocol.
84+ *
85+ *  Returns 1 on success, 0 on failure.
86+ *  Args:              ctx: pointer to a context object (cannot be NULL)
87+ *  Out: rand_commitment32: pointer to 32-byte array to store the returned commitment (cannot be NULL)
88+ *  In:             rand32: the 32-byte randomness to commit to (cannot be NULL)

jonasnick commented at 5:06 pm on November 13, 2019:

Need to make very clear that this “randomness” must come from a cryptographically secure RNG, and it’s not supposed to be shared with the client before receiving the client commitment. I thought about renaming it to session_secret to better convey what it is, but it doesn’t make too much sense either.

benma commented at 2:49 pm on December 30, 2019:

Done.

in src/modules/ecdsa_sign_to_contract/main_impl.h:58 in db0ea252a9 outdated

28+
29+    if (!secp256k1_ec_commit(ctx, &commitment, &opening->original_pubnonce, data32, 32)) {
30+        return 0;
31+    }
32+
33+    /* Check that sigr (x coordinate of R) matches the x coordinate of the commitment. */

jonasnick commented at 9:18 pm on November 13, 2019:

nit: stress somehow that sigr is a scalar and the x coordinate of the commitment is a field element. I overlooked it at first. Also that sig[0:32] could be greater than the group order and signature_load won’t complain. Perhaps `Check that sigr (x coordinate of R represented by a scalar) matches the x coordinate of the commitment (field element). Note that sig[0:32] can be greater than group order and therefore sigr will be reduced. But in that case ecdsa_verify doesn’t pass"

jonasnick commented at 9:32 pm on November 13, 2019:

More importantly, there needs to be a sentence explaining why comparing the x coordinate is sufficient. For example, because there’s only two y coordinates per x coordinate and given an opening for a point, it’s as difficult finding an opening to the negation of the point as to any other point. However, I do think there’s some reduction in security because it’s more likely to find a collision with a point and it’s negation.

benma commented at 2:55 pm on January 16, 2020:

nit: stress somehow that sigr is a scalar and the x coordinate of the commitment is a field element.

Will do, though I thought that was clear as it is the same way with regular ecdsa verification.

Note that sig[0:32] can be greater than group order and therefore sigr will be reduced. But in that case ecdsa_verify doesn’t pass

That is not true, is it? ecdsa_verify can still pass in this case, as the condition is sig_r == x (mod n) (the field element x is also reduced modulo n).

In the current code a few lines down, there actually might be a “mistake”: we memory-compare the byte representation of the scalar sigr and the field element x, without first reducing x modulo n, which might fail for actually valid commitments with very low (negligible) probability.

Shouldn’t this be implemented the same way as the actual secp256k1_ecdsa_verify()? Basically convert the field element x to a scalar and use secp256k1_scalar_eq() instead of memcmp, like here:

https://github.com/bitcoin-core/secp256k1/blob/074ab582ddb9085611cba8a0495828dadb645345/src/ecdsa_impl.h#L236-L238

benma commented at 3:27 pm on January 16, 2020:

edit: seems like secp256k1_scalar_set_b32() reduces modulo n

~Generally a bit confused, I don’t see “modulo n” reduction happening in signing nor verification despite it being part of the algorithm as described here:~

~https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm~

benma commented at 4:51 pm on January 16, 2020:

Added one commit to extend the comment, and one to change to secp256k1_scalar_eq() to properly compare the values modulo n. The second comment about the reduced security will follow soon.

benma commented at 12:21 pm on January 17, 2020:

More importantly, there needs to be a sentence explaining why comparing the x coordinate is sufficient. For example, because there’s only two y coordinates per x coordinate and given an opening for a point, it’s as difficult finding an opening to the negation of the point as to any other point. However, I do think there’s some reduction in security because it’s more likely to find a collision with a point and it’s negation.

Done.

in src/modules/ecdsa_sign_to_contract/tests_impl.h:155 in db0ea252a9 outdated

150+    }
151+}
152+
153+static void test_ecdsa_s2c_sign_verify(void) {
154+    unsigned char privkey[32];
155+    uint8_t zero_privkey[32] = {0};

jonasnick commented at 9:35 pm on November 13, 2019:

Better to standardize on unsigned char for bytes?

benma commented at 7:56 pm on December 29, 2019:

Done

in include/secp256k1.h:484 in 93067b1ddd outdated

479+ *
480+ */
481+SECP256K1_API SECP256K1_WARN_UNUSED_RESULT int secp256k1_s2c_opening_parse(
482+    const secp256k1_context* ctx,
483+    secp256k1_s2c_opening* opening,
484+    const unsigned char *input34

jonasnick commented at 10:18 pm on November 13, 2019:

feel free to cherry-pick my fixups in #589 (for 33 byte in/outputs).

benma commented at 2:06 pm on December 30, 2019:

Done.

jonasnick commented at 10:19 pm on November 13, 2019: contributor

The approach in this alternative looks good. I didn’t find any obvious critical vulnerabilities. It passes valgrind and coverage looks good. Being able to subsume recovery into the signing helper is a nice bonus.

Some of the things in this PR don’t make much sense anymore because we’re using a different public key type for schnorrsigs (xonly_pubkey) and therefore there’s no reason anymore to have a unified s2c_opening for both ecdsa and schnorr. Also, the ec_commit functions don’t apply to xonly_pubkey. I will rip this out of my PR and see if there’s still some code that can be shared.

I’m wondering if a stable s2c api should allow the callers to provide their own hash function through a callback for example to create tagged hashes.

As an aside, this PR taken on its own lacks a detailed explanation for how it works. There is a more detailed writeup in my PR and I don’t think we need both the protocol steps in this PR + the more detailed writeup.

There are some api artefacts in this PR (shared with mine) which are not ideal. For example secp256k1_pubkey *client_commit which isn’t a pubkey (but a point).

benma force-pushed on Dec 29, 2019

benma commented at 7:57 pm on December 29, 2019: contributor

Rebased and addressed some comments; I will take care of the others soon.

benma renamed this:
~~[alternative] ecdsa sign-to-contract module, with anti nonce covert chan util functions~~
~[alternative] ~ecdsa sign-to-contract module, with anti nonce covert chan util functions
on Dec 30, 2019

benma renamed this:
~~~[alternative] ~ecdsa sign-to-contract module, with anti nonce covert chan util functions~~
~[alternative]~ ecdsa sign-to-contract module, with anti nonce covert chan util functions
on Dec 30, 2019

benma renamed this:
~~~[alternative]~ ecdsa sign-to-contract module, with anti nonce covert chan util functions~~
ecdsa sign-to-contract module, with anti nonce covert chan util functions
on Dec 30, 2019

benma force-pushed on Dec 30, 2019

benma force-pushed on Jan 16, 2020

benma force-pushed on Jan 17, 2020

benma commented at 12:40 pm on January 17, 2020: contributor

Some of the things in this PR don’t make much sense anymore because we’re using a different public key type for schnorrsigs (xonly_pubkey) and therefore there’s no reason anymore to have a unified s2c_opening for both ecdsa and schnorr. Also, the ec_commit functions don’t apply to xonly_pubkey. I will rip this out of my PR and see if there’s still some code that can be shared.

Let me know what to do - I’m okay to move the opening to the module, or keep it as it is and let you figure out what can be reused in your PR (if this PR is merged first).

I’m wondering if a stable s2c api should allow the callers to provide their own hash function through a callback for example to create tagged hashes.

My feeling is that we should keep it simple for now and move towards merging. If someone comes up with the need for this, I’d be happy to extend it then. It wouldn’t be an invasive API change, so clients could update easily.

As an aside, this PR taken on its own lacks a detailed explanation for how it works. There is a more detailed writeup in my PR and I don’t think we need both the protocol steps in this PR + the more detailed writeup.

Maybe once both PRs are merged, we can move the description to docs/anti_nonce_covert_channel_protocol.md and link to it from both modules? For now I copy/pasted the extended details of your docs to mine, I hope that’s ok. The docs seem sufficient to me for a start, and of course can always be improved.

benma force-pushed on Jan 17, 2020

Add ec_commitments which are essentially the pay-to-contract-style tweaks of public keys.

The functionality is not exposed.

437ef77ea8

Add and expose sign-to-contract opening with parse and serialize functions ad4b6853ce

modules: add ecdsa_sign_to_contract

Sign a message while comitting to some data at the same time by by
adding `hash(k1*G, data)` to the rfc6979 deterministic nonce. Includes
verification function to check that the signature commits to the data.

43df8e10d6

ecdsa_sign_to_contract: add Anti Nonce Covert Channel util functions 99d639b5ac

recovery: re-use secp256k1_ecdsa_sign_helper

The body of the recovery sign function is 99% the same
secp256k1_ecdsa_sign. Now that this has moved to the sign helper, it
can be re-used not only by the sign-to-contract module, but also by
the recovery module.

0b74a94775

f serialize s2c_opening as 33 bytes instead of 34 59113abda5

f Add ec_commitments 2fcd7990ae

use reduce field element x modulo n, use secp256k1_scalar_eq over memcmp 1a0f2edfdb

benma force-pushed on Apr 21, 2020

benma commented at 12:53 pm on April 21, 2020: contributor

Rebased / fixed conflicts. @jonasnick any chance of getting this merged soon? :)

apoelstra commented at 9:42 pm on November 27, 2020: contributor

I think we can merge this into -zkp soon. I have https://github.com/ElementsProject/secp256k1-zkp/pull/111. If you do your own rebase it might be easier to start from that since I did the work of combing the new unified ecdsa/recovery code with this PR’s implementation of the same thing.

benma commented at 3:53 pm on December 3, 2020: contributor

I think we can merge this into -zkp soon. I have ElementsProject/secp256k1-zkp#111. If you do your own rebase it might be easier to start from that since I did the work of combing the new unified ecdsa/recovery code with this PR’s implementation of the same thing.

:heart_eyes: :heart_eyes: :heart_eyes:

I will make time for this as soon as I can. Been eager to get this working in production for a long time.

Edit: I did not realize that your PR is already there and rebased. Great.

benma commented at 10:23 pm on December 16, 2020: contributor

This PR was rebased and reopened at https://github.com/ElementsProject/secp256k1-zkp/pull/111, where review and improvements continue.

benma closed this on Dec 16, 2020

real-or-random referenced this in commit 673e551f4d on Jan 4, 2021

generalsunion approved

ecdsa sign-to-contract module, with anti nonce covert chan util functions #669