From #1360. This PR:
secp256k1_scalar_verify to make sure scalars are reduced mod the group order in VERIFY modesecp256k1_scalar_verify in all the scalar functions except secp256k1_scalar_clear, secp256k1_scalar_reduce_512, secp256k1_scalar_mul_512 and secp256k1_scalar_*_var functions in scalar_low_impl.h
2 tests failed when performing secp256k1_scalar_verify checks in the scalar functions:
in the scalar_cmov_test where max scalar = ff…ff (>group order). i think we can update max scalar to be group order here.
Right, setting to ff…ff should just be invalid, even in the tests. So the max should be the group order - 1. Or make it some other other large argument like e3…e3. This is a test for cmov, and I don’t think min and max are better test cases here than any other value. ;)
in the exhaustive tests when the scalar is the EXHAUSTIVE_TEST_ORDER. unsure whether this is an actual behaviour we want to test.
EXHAUSTIVE_TEST_ORDER is the group order, so again this is an overflow. I think the simplest fix is that set_int in scalar_low take the input mod EXHAUSTIVE_TEST_ORDER. This masks the overflow, but I tend to think that this fine. I mean, set_int will never overflow in the real code because the real group size is much larger than unsigned int,.
18@@ -19,6 +19,34 @@
19 #error "Please select wide multiplication implementation"
20 #endif
21
22+#ifndef VERIFY
23+/* In non-VERIFY mode, we #define the scalar operations to be identical to their
24+ * internal scalar implementation, to avoid the potential overhead of a
25+ * function call (even though presumably inlinable). */
26+# define secp256k1_scalar_clear secp256k1_scalar_impl_clear
Hm, when I opened #1360 I didn’t except that we want this indirection also here, but I think it makes sense.
On the one hand, the situation here is similar to the field code in the sense that we have multiple scalar implementations. On the other hand, the invariant here (no overflow) is inherently a property of the implementation, and does not leak into the scalar interface. So, you could argue that checking this is a concern of the implementation. But hm, what you do here is simply introduce a generic way for implementations to provide a verify function (which happens to be very similar here in all three implementations). And this makes sense, I think.
To be clear: What you propose here makes sense and solves the problem, I’m just wrapping my around whether it’s the cleanest/most elegant solution. cc @sipa who worked on this in the field code.
I think that right now, the split approach which we used for secp256k1_fe, is overkill for secp256k1_scalar. It was meaningful there, because secp256k1_fe have meaningful properties (normalization, magnitude) which are independent from the chosen implementation, and thus are meaningful to check independently of the chosen implementation. That’s not the case for secp26k1_scalar, and I don’t think it’s likely to change:
It is true that the abstraction introduced here has an unrelated advantage, namely keeping the entry/exit secp256k1_scalar_verify calls out of the individual implementations, but I think the amount of code introduced here doesn’t justify that. I guess another advantage is uniformity with the field logic.
Still, I’m leaning towards not taking this approach, but I could be convinced otherwise.
It was meaningful there, because secp256k1_fe have meaningful properties (normalization, magnitude) which are independent from the chosen implementation, and thus are meaningful to check independently of the chosen implementation.
true, the reasons sounds convincing. will simply call secp256k1_scalar_verify inside the 3 implementations instead.
By the way, CI fails with:
0==3276==WARNING: MemorySanitizer: use-of-uninitialized-value
1 [#0](/bitcoin-core-secp256k1/0/) 0x55d56ff0370a in secp256k1_scalar_verify /tmp/cirrus-ci-build/src/scalar_impl.h:40:5
2 [#1](/bitcoin-core-secp256k1/1/) 0x55d56ff0370a in secp256k1_scalar_clear /tmp/cirrus-ci-build/src/scalar_impl.h:44:5
3 [#2](/bitcoin-core-secp256k1/2/) 0x55d56ff0370a in secp256k1_ecdsa_sign_inner /tmp/cirrus-ci-build/src/secp256k1.c:547:5
4 [#3](/bitcoin-core-secp256k1/3/) 0x55d57005097f in secp256k1_ecdsa_sign /tmp/cirrus-ci-build/src/secp256k1.c:567:11
5 [#4](/bitcoin-core-secp256k1/4/) 0x55d57005097f in test_ecdsa_edge_cases /tmp/cirrus-ci-build/src/tests.c:7378:9
6 [#5](/bitcoin-core-secp256k1/5/) 0x55d56ff8cea2 in run_ecdsa_edge_cases /tmp/cirrus-ci-build/src/tests.c:7462:5
7 [#6](/bitcoin-core-secp256k1/6/) 0x55d56ff8cea2 in main /tmp/cirrus-ci-build/src/tests.c:7854:5
8 [#7](/bitcoin-core-secp256k1/7/) 0x7f34b1aaa189 in __libc_start_call_main csu/../sysdeps/nptl/libc_start_call_main.h:58:16
9 [#8](/bitcoin-core-secp256k1/8/) 0x7f34b1aaa244 in __libc_start_main csu/../csu/libc-start.c:381:3
10 [#9](/bitcoin-core-secp256k1/9/) 0x55d56fe732b0 in _start (/tmp/cirrus-ci-build/tests+0x212b0) (BuildId: 8839613b681f146479fe0450db93bdb91ebc1e2b)
11SUMMARY: MemorySanitizer: use-of-uninitialized-value /tmp/cirrus-ci-build/src/scalar_impl.h:40:5 in secp256k1_scalar_verify
(https://cirrus-ci.com/task/4600089314852864?logs=cat_tests_log#L16)
scalar_clear() is simply supposed to overwrite the memory, it’s not supposed to produce a valid scalar. So no need to verify the output scalar. (Terms are bit confusing, as fe_clear() actually sets to 0…)
I’ve updated the PR to call secp256k1_scalar_verify check inside the scalar functions in the 3 implementations. The check isn’t added to secp256k1_scalar_clear, secp256k1_scalar_reduce_512, secp256k1_scalar_mul_512 and secp256k1_scalar_*_var functions in only scalar_low_impl.h
Also liked how we can add these checks to scalar functions not mentioned in the common scalar interface like secp256k1_scalar_reduce using this approach now.
EXHAUSTIVE_TEST_ORDER is the group order, so again this is an overflow. I think the simplest fix is that set_int in scalar_low take the input mod EXHAUSTIVE_TEST_ORDER. This masks the overflow, but I tend to think that this fine. I mean, set_int will never overflow in the real code because the real group size is much larger than unsigned int,.
doing mod EXHAUSTIVE_TEST_ORDER results in two s values having valid secp256k1_schnorrsig_verify and a failure later on in the tests https://github.com/bitcoin-core/secp256k1/blob/afd7eb4a55606bff640e30bb64bc3c43d1bb5b1c/src/modules/schnorrsig/tests_exhaustive_impl.h#L127
should we just skip the check in secp256k1_scalar_set_int, secp256k1_scalar_get_b32 instead in scalar_low_impl.h?
should we just skip the check in
secp256k1_scalar_set_int,secp256k1_scalar_get_b32instead inscalar_low_impl.h?
This means whether we check or not depends on the specifics of the tests, which sounds wrong. (Or in other words: In principle, the code should work for all valid tests, independently of whether we happen to have them in our test suite.)
And skipping the check it in some functions is somewhat inconsequential. I think we should either decide that we want to enforce the invariant in low (and then do it everywhere because otherwise it’s not an invariant) or we don’t want to enforce it. And I still think having the invariant is a good idea.
Now that I think about this more, I tend to believe that the test is flawed. Or at least, I don’t understand the test. Why would the test except two different representations of the same scalar yield different results? I think it should either not test EXHAUSTIVE_TEST_ORDER or if it does, it should expect that the result is the same as for 0 (but if we want to test the latter, then it should probably happen outside this loop, which is supposed to find exactly one valid sig).
This means whether we check or not depends on the specifics of the tests, which sounds wrong.
true, better to have it in the tests
i think the the intention of having s = EXHAUSTIVE_TEST_ORDER is to make sure secp256k1_schnorrsig_verify really computes as invalid. (this codepath)
i’ve updated the test so that sig64 stores EXHAUSTIVE_TEST_ORDER without reducing it mod the group order. would that work?
115@@ -116,7 +116,8 @@ static void test_exhaustive_schnorrsig_verify(const secp256k1_context *ctx, cons
116 if (s <= EXHAUSTIVE_TEST_ORDER) {
117 secp256k1_scalar s_s;
118 secp256k1_scalar_set_int(&s_s, s);
119- secp256k1_scalar_get_b32(sig64 + 32, &s_s);
120+ memset(sig64 + 32, 0, 32);
121+ sig64[63] = s;
I think this is equivalent and shorter:
0 secp256k1_write_be32(sig64 + 32, s);
(also need to change s_s to s below)
thanks! looks much better. also made these changes:
s_s needs to be written to sig64[60..63] and we’d memset the other locations to 0.s to be an unsigned int since the comparison on this line is with an unsigned int.
i’ve updated the test so that
sig64storesEXHAUSTIVE_TEST_ORDERwithout reducing it mod the group order. would that work?
Makes sense to me.
secp256k1_scalar_verify and other VERIFY_CHECKs) and the actual function body. I suggested the same in #1348, see https://github.com/bitcoin-core/secp256k1/pull/1348/commits/690b0fc05abd76cb7f6bd87e88bf7b8b0fd1ab70.
165 * have a composite group order; fix it in exhaustive_tests.c). */
166 VERIFY_CHECK(*r != 0);
167+ secp256k1_scalar_verify(r);
168 }
169
170 static void secp256k1_scalar_inverse_var(secp256k1_scalar *r, const secp256k1_scalar *x) {
secp256k1_scalar_inverse? I think it’s preferable to have the checks in every function. This makes the code easier to change, in the sense that we don’t need to bother with adding checks when change functions. (And even if we care about the runtime overhead of this in the tests, the compiler will most likely figure out that the duplicate call be dropped.)
i’ve updated the test so that
sig64storesEXHAUSTIVE_TEST_ORDERwithout reducing it mod the group order.
One more nit: It’s a good idea to reorder the commits such that this commit comes first. Then the tests will pass even on intermediate commits. (We have no strict rule on this, but it’s a good idea. For example, it helps with git bisect.)
- `secp256k1_scalar_set_int` in scalar_low uses input mod EXHAUSTIVE_TEST_ORDER
- directly store s in sig64 without reducing it mod the group order for testing
secp256k1_scalar_verify checks that scalars are reduced mod the
group order
120- secp256k1_scalar_set_int(&s_s, s);
121- secp256k1_scalar_get_b32(sig64 + 32, &s_s);
122+ memset(sig64 + 32, 0, 32);
123+ secp256k1_write_be32(sig64 + 60, s);
124 expect_valid = actual_k != -1 && s != EXHAUSTIVE_TEST_ORDER &&
125- (s_s == (actual_k + actual_d * e) % EXHAUSTIVE_TEST_ORDER);
secp256k1_scalar directly with an integer is possible, until I realized that it’s simply a uint32_t typedef in the scalar_low implementation (would have expected that it’s still wrapped in a struct), and that’s of course the only one used in exhaustive tests.