scalar_split_lambda requires that the input pointer is different to both output pointers. Without this fix, the internal benchmarks crash when compiled with -DVERIFY.
This was introduced in commit https://github.com/bitcoin-core/secp256k1/commit/362bb25608dbcd724a07dd5170c4ebe081c3dd84 (which requires configuring with --enable-endomorphism to exhibit the crash).
I tested that the new CI job would have caught this bug.
The new CI job is failing. Looks like the ctime_test doesn't like being compiled with VERIFY.
Concept ACK
We have the VERIFY_CHECKs in secp256k1_scalar_split_lambda already but I think this can be documented better. Can you add restrict to the pointers in secp256k1_scalar_split_lambda, or alternatively add a comment to the function?
And can you add the same VERIFY_CHECKs to the exhaustive test variant of secp256k1_scalar_split_lambda. The code there has similar aliasing problems (though it's not a big deal in the end because the result of this function is anyway arbitrary in the exhaustive tests...)
I added better documentation and the same VERIFY_CHECKs to the exhaustive test variant of secp256k1_scalar_split_lambda.
73 | @@ -71,6 +74,14 @@ static void secp256k1_scalar_split_lambda_verify(const secp256k1_scalar *r1, con 74 | #endif 75 | 76 | /* 77 | + * The function below splits k into r1 and r2, such that 78 | + * - r1 + lambda * r2 == k (mod n) 79 | + * - either r1 < 2^128 or -r1 mod n < 2^128 80 | + * - either r2 < 2^128 or -r2 mod n < 2^128 81 | + * 82 | + * It is required that `r1`, `r2`, and `k` all point to different objects. An
nit: I think this should be documented in scalar.h instead.
Thanks. I totally missed the declaration there. Fixed.
utACK e9a3d3f35dc4e0ba3124d34e4885373d927a3a39
scalar_split_lambda requires that the input pointer is different to both output
pointers. Without this fix, the internal benchmarks crash when compiled with
-DVERIFY.
This was introduced in commit 362bb25608dbcd724a07dd5170c4ebe081c3dd84 (which
requires configuring with --enable-endomorphism to exhibit the crash).
91 | @@ -92,8 +92,9 @@ static int secp256k1_scalar_eq(const secp256k1_scalar *a, const secp256k1_scalar 92 | 93 | /** Find r1 and r2 such that r1+r2*2^128 = k. */ 94 | static void secp256k1_scalar_split_128(secp256k1_scalar *r1, secp256k1_scalar *r2, const secp256k1_scalar *k); 95 | -/** Find r1 and r2 such that r1+r2*lambda = k, 96 | - * where r1 and r2 or their negations are maximum 128 bits long (see secp256k1_ge_mul_lambda). */ 97 | +/** Find r1 and r2 such that r1+r2*lambda = k, where r1 and r2 or their 98 | + * negations are maximum 128 bits long (see secp256k1_ge_mul_lambda). It is 99 | + * required that r1, r2, and k all point to different objects. */
Add SECP256K1_RESTRICTs to the function declaration (allowing the compiler to complain about incorrect usage statically).
Fwiw, I had discussed this with @jonasnick somewhere else.
TL;DR: The promise you give by restrict is more involved than we assumed.
He had tried just restrict k but that it turns out that doesn't change anything at all (and the compiler won't complain about incorrect usage), because *k is not modified in the function. After looking up the standard and other explanation, at least I was pretty convinced that restrict r1, restrict r2, restrict k is correct and meaningful, but @jonasnick preferred not to use it to keep things simple (which is a reasonable conclusion, I think).
The best simple but precise explanation we found is this:
The restrict modifier means that the compiler can assume that the object to which that pointer points either is not modified or is not referenced in any other way in the function. If the object is modified, then all access to that object must be done through that pointer. (https://www.reddit.com/r/C_Programming/comments/1xqf90/comment/cfdoon2/?context=3)
I wasn't aware about the "modified" part at all, I had assumed restrict has only to do with references.
Yes, restrict r1, restrict r2, restrict k is what I'd have suggested is added. I don't really see the downside, as it seems exactly what we want to convey? These pointers are the only pointers to their respective objects, and the objects pointed to are not modified through any other mechanism.
Fwiw, I'm happy to ACK either solution.
As far as I can see, if restrict is added and there's a violation (some pointers point to the same object), then
VERIFY_CHECK(r1 != k);
VERIFY_CHECK(r2 != k);
VERIFY_CHECK(r1 != r2);
may not actually abort the program because we told the compiler that these conditions will never happen. It's not guaranteed that the compiler will be able to determine that violation statically and warn us about it. On the other hand, if we don't add restrict then the VERIFY_CHECKs will always (in the tests) find violations of the function's contract.
That's why SECP256K1_RESTRICT is #define'd as nothing in VERIFY mode.
Great, then I don't see a downside either!
Ok, I added the restricts.
CI seems unhappy here with asm=no for valgrind-based ctime_tests, though I can't reproduce it...
This detects benchmarks that crash when VERIFY is defined.
VERIFY_CHECK(r1 != r2) is added because otherwise the verify_scalar_split fails.
Should be fixed now. I missed the CTIMETEST -> CTIMETESTS rename when rebasing.
(I was able to reproduce this issue by copying the print_environment output of cirrus.sh. So seems like the PR that added this did indeed end up being useful)
utACK eb6bebaee3947f8bca46816fa6bf6182085f1b56
utACK eb6bebaee3947f8bca46816fa6bf6182085f1b56
Post Merge: MacOS: Arm64 tACK https://github.com/bitcoin-core/secp256k1/commit/eb6bebaee3947f8bca46816fa6bf6182085f1b56 MacOS: X86_64 tACK https://github.com/bitcoin-core/secp256k1/commit/eb6bebaee3947f8bca46816fa6bf6182085f1b56