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

benma commented at 11:33 am on June 11, 2019: contributor

This is based on the description of the fix by Stepan: https://medium.com/cryptoadvance/hardware-wallets-can-be-hacked-but-this-is-fine-a6156bbd199

The protocol wording and functions are copied/adapted from Jonas Nick’s PRs which do the same for BIP-Schnorr:

#590

https://github.com/bitcoin-core/secp256k1/pull/590/commits/ae5fb7f8f143244de07e17fee6671e0dd68c81a6#diff-b19c5ee427283d4d82bc5beb4e2f4777R59

https://github.com/bitcoin-core/secp256k1/pull/590/commits/ae5fb7f8f143244de07e17fee6671e0dd68c81a6#diff-313ca26f0048bc16a608709915d0111eR70

1. Add secp256k1_ecdsa_anti_nonce_sidechan_client_commit to return the curve point committing to the signing client nonce.

This is a convenience function and can technically be emulated by calling secp256k1_ecdsa_sign() and reconstructing the curve point from the signature r/s values.

2.

secp256k1_ecdsa_sign_nonce_tweak_add, which is the same as secp256k1_ecdsa_sign_nonce, but with an additional optional tweak parameter to add to the nonce.

The nicer way to do this is to redefine secp256k1_nonce_function to have a tweak param, but this would break API compatiblity. The way it is implemented is fully backwards compatible.

benma force-pushed on Jun 11, 2019

benma commented at 12:04 pm on June 11, 2019: contributor

cc @jonasnick

Is this the right direction? If so I can add the host functions and some unit tests.

benma force-pushed on Jun 11, 2019

in include/secp256k1.h:537 in ba34c6efd3 outdated

532+ * 1. The host draws randomness `k2`, commits to it with sha256 and sends the commitment to the client.
533+ * 2. The client commits to it's original nonce `k1` using the host commitment by calling
534+ *    `secp256k1_ecdsa_anti_nonce_sidechan_client_commit`. The client sends the resulting commitment
535+ *   `R1` to the host.
536+ * 3. The host replies with `k2` generated in step 1.
537+ * 4. The client checks that the host commitment from step 1 commits to `k2` from step 3 and signs

jonasnick commented at 8:58 pm on June 11, 2019:

The client actually doesn’t need to check that it matches because it derives its nonce using the hosts randomness commitment. If the randomness commitment doesn’t match hash(k2) then it will derive a different “original” nonce and the host will not be able to verify the sign-to-contract commitment. The only reason of the host commitment is to allow the client to derive a unique nonce for every host randomness.

benma commented at 9:04 pm on June 15, 2019:

:+1: fixed

in include/secp256k1.h:556 in ba34c6efd3 outdated

551+SECP256K1_API int secp256k1_ecdsa_anti_nonce_sidechan_client_commit(
552+    const secp256k1_context* ctx,
553+    secp256k1_pubkey *client_commit,
554+    const unsigned char *msg32,
555+    const unsigned char *seckey32,
556+    secp256k1_nonce_function noncefp,

jonasnick commented at 9:03 pm on June 11, 2019:

The reason why I’m not supporting arbitrary noncefps in my PR is to avoid giving a nonce function that doesn’t make use of the noncedata. In the Schnorr case that would lead to nonce reuse and allows the host to extract the secret key. I suspect the same is true for ECDSA.

benma commented at 9:04 pm on June 15, 2019:

fixed

in src/secp256k1.c:492 in ba34c6efd3 outdated

487+
488 int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata) {
489+    return secp256k1_ecdsa_sign_nonce_tweak_add(ctx, signature, msg32, seckey, noncefp, noncedata, NULL);
490+}
491+
492+int secp256k1_ecdsa_sign_nonce_tweak_add(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata, const unsigned char* nonce_tweak32) {

jonasnick commented at 9:36 pm on June 11, 2019:

If this function assumes that the caller gives a matching noncedata to the nonce_tweak instead of deriving the host commitment from the nonce_tweak by hashing it, the caller can’t be stateless.

benma commented at 9:05 pm on June 15, 2019:

fixed (copied the solution from your PR).

in src/secp256k1.c:526 in ba34c6efd3 outdated

521@@ -472,6 +522,9 @@ int secp256k1_ecdsa_sign(const secp256k1_context* ctx, secp256k1_ecdsa_signature
522                 break;
523             }
524             secp256k1_scalar_set_b32(&non, nonce32, &overflow);
525+            if (nonce_tweak32 != NULL) {
526+                secp256k1_scalar_add(&non, &non, &nonce_tweak);

jonasnick commented at 9:38 pm on June 11, 2019:

This is not a sign-to-contract commitment, but it works for the anti nonce covertchan because the host already has the nonce. I think it would be much better if ecdsa_sign would generally support sign to contract commitments and not only this protocol. Sign to contract would be R = R1 + H(R1, k2)*G.

benma commented at 2:48 pm on June 15, 2019:

Thanks a lot for the great review!

I can try to make a general sign to contract ecdsa sign function.

Peeking at your Schnorr implementation of it, I am unsure about a few things:

There is secp256k1_s2c_opening, which seems to return the original R1 from the sign function. Why is this needed when there is already a function to produce the same commitment (secp256k1_(schnorrsig|ecdsa)_anti_nonce_sidechan_client_commit) beforehand?

~~2. What is nonce_is_negated and when is it set? Here the check is if (!secp256k1_fe_is_quad_var(&r.y)) {, but I don’t know what this means. Does it apply for ecdsa?~~

In the ecdsa case, do I need to add all of that, or is just adding H(R1, k2) instead of k2 sufficient?

benma commented at 9:31 pm on June 15, 2019:

I now pushed a commit which simply adds H(R1, k2) to the nonce k1 to produce R = (k1 + H(R1, k2))*G. Seemed less intrusive and more efficient than computing R2 and adding it to R1 to get R = R1 + R2.

benma commented at 11:34 am on June 17, 2019:

Question 2. is resolved by reading BIP-Schnorr. Unless I misunderstand, it seems that it does not apply to ecdsa.

jonasnick commented at 4:04 pm on July 5, 2019:

To question 1: True, but if you want sign-to-contract outside of the anti-nonce-sidechan context then it’s much simpler to just have a single opening structure that contains the negated nonce and original nonce and that you can just give to s2c_verify.

in include/secp256k1.h:538 in ba34c6efd3 outdated

533+ * 2. The client commits to it's original nonce `k1` using the host commitment by calling
534+ *    `secp256k1_ecdsa_anti_nonce_sidechan_client_commit`. The client sends the resulting commitment
535+ *   `R1` to the host.
536+ * 3. The host replies with `k2` generated in step 1.
537+ * 4. The client checks that the host commitment from step 1 commits to `k2` from step 3 and signs
538+ *    with `secp256k1_ecdsa_sign_nonce_tweak_add`, using the `k2` as the tweak and the host

jonasnick commented at 9:42 pm on June 11, 2019:

In general I’m trying to avoid the name tweak because it carries little information.

benma commented at 9:04 pm on June 15, 2019:

fixed

jonasnick commented at 9:46 pm on June 11, 2019: contributor

I’m happy to see that someone cares about this for ECDSA. Backwards compatibility is important, so creating a new signing function is the right way to go. We should probably replace the word sidechan with covertchan because it’s more precise. Fwiw your naming it’s only semi-consistent with mine ;P

benma force-pushed on Jun 15, 2019

in include/secp256k1.h:592 in 8c1c940dfe outdated

590     const unsigned char *msg32,
591     const unsigned char *seckey,
592     secp256k1_nonce_function noncefp,
593     const void *ndata,
594-    const unsigned char* nonce_tweak32
595+    const unsigned char* s2c_data32

jonasnick commented at 9:04 pm on July 5, 2019:

nit: we should standardize on the position (in my PR it’s before the noncefp, but I don’t really care which way it is).

in src/secp256k1.c:489 in 8c1c940dfe outdated

486+    return secp256k1_ecdsa_sign_to_contract(ctx, signature, msg32, seckey, noncefp, noncedata, NULL);
487 }
488 
489-int secp256k1_ecdsa_sign_nonce_tweak_add(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata, const unsigned char* nonce_tweak32) {
490+/* Compute an ec commitment tweak as hash(pubkey, data). */
491+static int secp256k1_ec_commit_tweak(const secp256k1_context *ctx, unsigned char *tweak32, const secp256k1_pubkey *pubkey, const unsigned char *data, size_t data_size) {

jonasnick commented at 9:06 pm on July 5, 2019:

Looks like this is copy and pasted from my commit. Why not cherry-pick them? Would be easier to review.

benma commented at 7:29 pm on July 6, 2019:

I guess I only needed this function and not the rest, though now I see the commit is not that much bigger than this (https://github.com/bitcoin-core/secp256k1/commit/0b4bef4527e2b4694a83306f495ca61d574d2c1f), so I can do it anyway

in src/secp256k1.c:526 in 013526b893 outdated

521+    secp256k1_ecmult_gen(&ctx->ecmult_gen_ctx, &rp, seckey);
522+    secp256k1_ge_set_gej(&r, &rp);
523+    return secp256k1_ec_commit_tweak(tweak32, &r, data, data_size);
524+}
525+
526+int secp256k1_ecdsa_sign_to_contract(const secp256k1_context* ctx, secp256k1_ecdsa_signature *signature, const unsigned char *msg32, const unsigned char *seckey, secp256k1_nonce_function noncefp, const void* noncedata, const unsigned char* s2c_data32) {

jonasnick commented at 9:29 pm on July 5, 2019:

So right now you can’t get the original nonce when using pure sign-to-contract, unless you do secp256k1_ecdsa_anti_nonce_sidechan_client_commit ?

benma commented at 7:37 pm on July 6, 2019:

Yeah, Part of it is that it seemed redundant, and part of it is that I am not very knowledgeable about sign-to-contract, e.g. what other uses of it there are where one would not use something akin to secp256k1_ecdsa_anti_nonce_sidechan_client_commit beforehand anyway.

I can add an opening struct here too if you think it will be helpful, let me know.

jonasnick commented at 1:27 pm on July 12, 2019:

I don’t know a specific application for s2c besides the anti nonce sidechannel and committing to the signer set in threshold signatures. I’d add an opening struct argument.

jonasnick commented at 9:33 pm on July 5, 2019: contributor

It looks like this is missing a verification function for ecdsa sign-to-contract.

I know that this PR is an experiment but to move forward this PR needs API tests and functionality tests that should cover every reachable line.

jonasnick commented at 9:34 pm on July 5, 2019: contributor

By the way feel free to squash.

benma commented at 7:43 pm on July 6, 2019: contributor

It looks like this is missing a verification function for ecdsa sign-to-contract.

I know that this PR is an experiment but to move forward this PR needs API tests and functionality tests that should cover every reachable line.

I am very much interested in moving this from an experiment to production, so I will definitely add those. I will only get a chance to work on it after next week.

Should I move all of this over to a new module? I assume modifications directly to secp256k1_ecdsa_sign should be avoided, right?

jonasnick commented at 1:29 pm on July 12, 2019: contributor

Should I move all of this over to a new module?

I think that’s a good idea. Having this as an experimental module would probably reduce the barrier for getting merged

benma force-pushed on Jul 18, 2019

benma force-pushed on Jul 19, 2019

benma renamed this:
~~[experiment/wip] ecdsa nonce anti sidechan util functions~~
[experiment/wip] ecdsa sign-to-contract module, with anti nonce covert chan util functions
on Jul 19, 2019

benma referenced this in commit 4b9e8035a2 on Jul 19, 2019

benma referenced this in commit 6cc0975c2d on Jul 19, 2019

benma referenced this in commit 642d5bea38 on Jul 19, 2019

benma commented at 8:50 am on July 22, 2019: contributor

@jonasnick I pushed a re-do, please take a look.

Since most of my PR is based on your Schnorr PR and your help, I added your name to the copyright header. Let me know if you are okay with this.
It now lives in the ecdsa_sign_to_contract module: ./configure --enable-module-ecdsa-sign-to-contract --enable-experimental
Using “covert channel” instead of “side channel” now according to your comment in your PR.
I cherry-picked two of your commits to pull in the opening struct/functions and secp256k1_ec_commit_seckey
Tests added for commit/verify and the anti nonce covert channel workflow
secp256k1_ecdsa_s2c_anti_nonce_covert_channel_host_commit is literally the same as the one in the schnorr module, but copied since it’s a module function (can think adding a module_common.c or similar at some point)

:warning: my biggest question mark is: the host verify function is slightly different to the Schnorr version: it checks that the x coordinate of R1 + H(R1, k2) matches r of the signature, whereas in in the Schnorr module, the check is for the full R, not just the x-coordinate. Rationale: reconstructing R from (r,s) is a lot more involved in ecdsa, and also needs the message, which the host does not need to know otherwise. Also, Stepan’s article describes the verification like this.

Is this sufficient for security? Otherwise, we’d need to do one of:

calculate the full R anyway like linked above
encode the sign of the R (not the original pubnonce R1) in opening->nonce_is_negated
?

in include/secp256k1_ecdsa_sign_to_contract.h:11 in 5408a2f7ba outdated

 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
11+ *  the nonce generated by noncefp, with `ndata=hash(s2c_data32, ndata)`.

jonasnick commented at 7:53 pm on July 27, 2019:

nit: The with [...] part is a bit difficult to understand. Also noncefp is always secp256k1_nonce_function_default. Perhaps for this function we can remove the noncefp and ndata argument because they don’t have a purpose anyway.

benma commented at 2:59 pm on July 29, 2019:

Are we sure that there is no use case for ndata when you could also provide s2c_data? I am not familiar with uses of ndata in general, but if s2c_data alone is enough for all cases, then ndata could also be removed from secp256k1_schnorrsig_sign?

I can remove noncefp, but we could also keep it so other functions could be allowed in the future without breaking API compatibility.

jonasnick commented at 12:26 pm on July 31, 2019:

ndata is for giving additional information to the nonce function. Since it is hashed with s2c_data I don’t see how you’d transmit usable information to the nonce function in that way. ndata shouldn’t be removed from schnorrsig_sign because schnorrsig_sign can be used with other nonce functions than just the default. Imo, simpler is better than optimizing for some unknown future usecase.

benma commented at 3:53 pm on October 9, 2019:

Dropped the noncefp and ndata params from the function in the alternative here. Can also do it for this version if we choose this alternative over the other.

in include/secp256k1_ecdsa_sign_to_contract.h:19 in 5408a2f7ba outdated

14+ *  Args:    ctx:  pointer to a context object, initialized for signing (cannot be NULL)
15+ *  Out:     sig:  pointer to an array where the signature will be placed (cannot be NULL)
16+ *   s2c_opening:  pointer to an secp256k1_s2c_opening structure which can be
17+ *                 NULL but is required to be not NULL if this signature creates
18+ *                 a sign-to-contract commitment (i.e. the `s2c_data` argument
19+ *                 is not NULL). nonce_is_negated is always 0 for ecdsa.

jonasnick commented at 7:55 pm on July 27, 2019:

nonce_is_negated is irrelevant because users of this API should never look into s2c_opening structs.

benma commented at 5:12 pm on July 29, 2019:

removed mention of it

in src/modules/ecdsa_sign_to_contract/main_impl.h:12 in 5408a2f7ba outdated

 7+#ifndef SECP256K1_MODULE_ECDSA_SIGN_TO_CONTRACT_MAIN_H
 8+#define SECP256K1_MODULE_ECDSA_SIGN_TO_CONTRACT_MAIN_H
 9+
10+#include "include/secp256k1_ecdsa_sign_to_contract.h"
11+
12+int secp256k1_ecdsa_s2c_sign(

jonasnick commented at 7:56 pm on July 27, 2019:

Imo much easier to read if it was consistent with the rest of secp where the function signature is a single line.

jonasnick commented at 8:14 pm on July 27, 2019:

The previous version in this PR was easier to review. I don’t remember how exactly it looked like but you’d get there by doing something like this:

move this function to secp256k1.c and rename it to secp256k1_ecdsa_sign_helper.
change regular ecdsa_sign function to just call ecdsa_sign_helper function but with s2c_data and s2c_opening set to NULL.

Then we wouldn’t have all this code duplication. The downside is that we wouldn’t be able to fully test ecdsa_sign_helper without enabling the s2c module.

benma commented at 2:14 pm on July 29, 2019:

I copied it to the module with the goal of not touching secp256k1_ecdsa_sign. I thought that was the goal, otherwise wouldn’t this nullify the purpose of an experimental module and increase the barrier to merge?

For comparison, the recoverable module also copied the whole function with the minimal change of extracting the recid.

Here, it is also a copy except for the if(s2c_data32 != NULL) { clauses and s2c_data32 related arg checks.

Imho it would make sense to postpone this refactoring to a future PR, and also cover the recoverable module. Since the tests for the helper and the main signing functions would overlap >90%, the tests should also be refactored to not copy all the tests with slightly different call signature.

benma commented at 5:13 pm on July 29, 2019:

imho long lines are less readable, but consistency first :+1: fixed

jonasnick commented at 12:34 pm on July 31, 2019:

wouldn’t this nullify the purpose of an experimental module and increase the barrier to merge?

No because the point is that people can use sign-to-contract only if they pass the --enable-experimental-modules option. That the helper doesn’t change ecdsa signing if s2c_data is not set is much easier to check in review than having to diff ecdsa_sign and ecdsa_s2c_sign. @sipa Summarizing above discussion, do you prefer copying the ecdsa code into the ecdsa_s2c module or should we make the main ecdsa function accept s2c_data but don’t expose the argument in secp256k1.h - only in secp256k1_ecdsa_sign_to_contract?

benma commented at 10:51 am on September 4, 2019:

Just to give a quick update: I have been a bit busy the past weeks, but I still intend to move this to production on the bitbox02 (prototype already working).

I will happily refactor the current code like you suggested, then we can compare. I expect to be able to do this two weeks from now.

In the meantime, I’d still be eager to hear @sipa’s opinion on how to best structure this.

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

I rebased this PR, and made PR to compare both alternatives: https://github.com/bitcoin-core/secp256k1/pull/669

in src/modules/ecdsa_sign_to_contract/main_impl.h:117 in 5408a2f7ba outdated

112+        memset(signature, 0, sizeof(*signature));
113+    }
114+    return ret;
115+}
116+
117+int secp256k1_ecdsa_s2c_verify_commit(

jonasnick commented at 7:57 pm on July 27, 2019:

misses VERIFY and ARG_CHECKs.

benma commented at 5:13 pm on July 29, 2019:

fixed

in src/modules/ecdsa_sign_to_contract/main_impl.h:135 in 5408a2f7ba outdated

130+    }
131+
132+    /* Check that sigr (x coordinate of R) matches the x coordinate of the commitment. */
133+    secp256k1_ecdsa_signature_load(ctx, &sigr, &sigs, sig);
134+
135+    secp256k1_pubkey_load(ctx, &commitment_ge, &commitment);

jonasnick commented at 7:57 pm on July 27, 2019:

Return value should be checked.

benma commented at 5:16 pm on July 29, 2019:

fixed, though the negative branch cannot be hit I think, as secp256k1_ec_commit() always produces a valid pubkey.

in src/modules/ecdsa_sign_to_contract/main_impl.h:134 in 5408a2f7ba outdated

133+    secp256k1_ecdsa_signature_load(ctx, &sigr, &sigs, sig);
134+
135+    secp256k1_pubkey_load(ctx, &commitment_ge, &commitment);
136+    secp256k1_fe_normalize(&commitment_ge.x);
137+    secp256k1_fe_get_b32(b, &commitment_ge.x);
138+    secp256k1_scalar_set_b32(&computed_r, b, NULL);

jonasnick commented at 7:59 pm on July 27, 2019:

Let’s avoid having to deal with subtle issues regarding modular reduction and either check the overflow argument or compare b with scalar_get_b32(sigr) using memcmp.

benma commented at 5:24 pm on July 29, 2019:

Done, went with memcmp

jonasnick commented at 8:15 pm on July 27, 2019: contributor

I did another relatively shallow review round without taking a look at the covert channel protection. It would make sense to split the ecdsa_s2c and anti_covert_chan things into two commits.

Is this sufficient for security?

Yes, it’s still binding. Informally, to break the binding property an attacker would need to find data and original_pubnonce for a given R such that R = commit(data, original_pubnonce) = original_pubnonce + hash(original_pubnonce, data)*G. Since we’re just comparing x-coordinates here, the attacker would have to find x(R) = x(commit(data, original_pubnonce)) which is not asymptotically easier because there are only two points with the same x-coordinates. Also, since we can’t batch verify these commitments anyway comparing the x-coordinates is just fine.

Regarding tests it seems like API tests are missing. They verify that the the right context flags are used and the correct ARG_CHECKS are there. Also, there need to be some negative s2c_verify tests, where you flip a bit in the committed data, etc. (see my PR), also a test where the opening is not initialized. Ideally you check with gcov that every line that’s reachable is hit by the tests.

benma force-pushed on Jul 29, 2019

benma commented at 5:30 pm on July 29, 2019: contributor

Thanks again! I split it into two commits (s2c / nonce covert channel funcs) and added a lot of tests. There are very few lines which I’m not sure how to exercise, e.g. how to get a zero/overflowing nonce with secp256k1_nonce_function_default, but other than that everything should be covered.

jonasnick commented at 12:35 pm on July 31, 2019: contributor

how to get a zero/overflowing nonce with secp256k1_nonce_function_default

Yeah, not possible. In the future we should consistently mark unreachable lines.

benma renamed this:
~~[experiment/wip] 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 Aug 1, 2019

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

The functionality is not exposed.

0929853031

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

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.

962ce23f89

ecdsa_sign_to_contract: add Anti Nonce Covert Channel util functions 18cb435503

benma force-pushed on Oct 8, 2019

benma cross-referenced this on Oct 8, 2019 from issue ecdsa sign-to-contract module, with anti nonce covert chan util functions by benma

benma commented at 2:09 pm on December 20, 2019: contributor

Closing in favour of #669 as discussed here. Thanks for the detailed review!

benma closed this on Dec 20, 2019

paulmillr cross-referenced this on May 18, 2023 from issue Implement anti-klepto protocol to protect against covert nonces by paulmillr

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