Normalize ge produced from secp256k1_pubkey

stratospher commented at 7:03 pm on June 15, 2023: contributor

The output ge in secp256k1_pubkey_load is normalized when sizeof(secp256k1_ge_storage) = 64 but not when it’s not 64. ARG_CHECK at the end of the function assumes normalization. So normalize ge in the other code path too.

context: #1129(comment)

stratospher cross-referenced this on Jun 15, 2023 from issue ElligatorSwift + integrated x-only DH by sipa

theStack approved

theStack commented at 8:07 am on June 16, 2023: contributor

ACK aac0ec9a309820f0122ed32b43d638fcac3692ff

Tested the bugfix by modifying the if-conditions in secp256k1_pubkey_{save,load} to trigger the “ge_storage doesn’t have size 64” code paths (first I tried to add another member into secp256k1_ge_storage to increase its size but this would need more changes, as the new member is uninitialized and some comparison tests failed):

 0diff --git a/src/secp256k1.c b/src/secp256k1.c
 1index bdbd97c..1664968 100644
 2--- a/src/secp256k1.c
 3+++ b/src/secp256k1.c
 4@@ -237,7 +237,7 @@ static SECP256K1_INLINE void secp256k1_declassify(const secp256k1_context* ctx,
 5 }
 6 
 7 static int secp256k1_pubkey_load(const secp256k1_context* ctx, secp256k1_ge* ge, const secp256k1_pubkey* pubkey) {
 8-    if (sizeof(secp256k1_ge_storage) == 64) {
 9+    if (sizeof(secp256k1_ge_storage) == 63) {
10         /* When the secp256k1_ge_storage type is exactly 64 byte, use its
11          * representation inside secp256k1_pubkey, as conversion is very fast.
12          * Note that secp256k1_pubkey_save must use the same representation. */
13@@ -256,7 +256,7 @@ static int secp256k1_pubkey_load(const secp256k1_context* ctx, secp256k1_ge* ge,
14 }
15 
16 static void secp256k1_pubkey_save(secp256k1_pubkey* pubkey, secp256k1_ge* ge) {
17-    if (sizeof(secp256k1_ge_storage) == 64) {
18+    if (sizeof(secp256k1_ge_storage) == 63) {
19         secp256k1_ge_storage s;
20         secp256k1_ge_to_storage(&s, ge);
21         memcpy(&pubkey->data[0], &s, sizeof(s));

On master:

0$ ./tests
1test count = 64
2random seed = 91438e2c4c9f4db70f8f45f9b2b9e2fd
3src/field_impl.h:243: test condition failed: a->normalized
4Abort trap (core dumped)

On the PR branch, all tests succeed as expected. :heavy_check_mark:

in src/secp256k1.c:253 in aac0ec9a30 outdated

248@@ -249,6 +249,8 @@ static int secp256k1_pubkey_load(const secp256k1_context* ctx, secp256k1_ge* ge,
249         secp256k1_fe x, y;
250         secp256k1_fe_set_b32_mod(&x, pubkey->data);
251         secp256k1_fe_set_b32_mod(&y, pubkey->data + 32);
252+        secp256k1_fe_normalize_var(&x);
253+        secp256k1_fe_normalize_var(&y);

real-or-random commented at 11:47 am on June 16, 2023:

Now that I see what secp256k1_pubkey_save does, we should simply do this:

0        ARG_CHECK(secp256k1_fe_set_b32_limit(&x, pubkey->data));
1        ARG_CHECK(secp256k1_fe_set_b32_limit(&y, pubkey->data + 32));

Here, ARG_CHECK(cond) is a macro that calls the “illegal-argument callback” if cond is false, see https://github.com/bitcoin-core/secp256k1/blob/67214f5f7d8e0bdf193ceb1f47ba8277d1a0871a/include/secp256k1.h#L317 It’s also used below for the !secp256k1_fe_is_zero(&ge->x) check that triggers the test failure.

stratospher commented at 5:10 am on June 17, 2023:

makes sense! i’ve updated the PR to use this.

real-or-random added the label bug on Jun 16, 2023

real-or-random commented at 11:49 am on June 16, 2023: contributor

The bug has been introduced in https://github.com/bitcoin-core/secp256k1/commit/5b32602295ff7ad9e1973f96b8ee8344b82f4af0.

Tested the bugfix by modifying the if-conditions in secp256k1_pubkey_{save,load} to trigger the “ge_storage doesn’t have size 64” code paths

Yeah, I think currently don’t test this code path at all. :/ We should consider adding a test override like SECP256K1_MSVC_MULH_TEST_OVERRIDE. But this can be done in a separate PR.

Normalize ge produced from secp256k1_pubkey_load

The output ge is normalized when sizeof(secp256k1_ge_storage) = 64
but not when it's not 64. ARG_CHECK at the end of the function
assumes normalization. So normalize ge in the other code path too.

f1652528be

stratospher force-pushed on Jun 17, 2023

stratospher commented at 5:18 am on June 17, 2023: contributor

We should consider adding a test override like SECP256K1_MSVC_MULH_TEST_OVERRIDE.

this code path is only triggered in secp256k1_pubkey_load and secp256k1_pubkey_save though. I could give this a shot if it’s desirable.

real-or-random commented at 3:06 pm on June 17, 2023: contributor

this code path is only triggered in secp256k1_pubkey_load and secp256k1_pubkey_save though. I could give this a shot if it’s desirable.

Hm, I’m not convinced yet. A test override does the job, but it adds a lot of complexity for a small optimization, and it also adds another dimension to the test matrix… I lean towards getting rid of the code path entirely because I don’t think it’s relevant in the real world:

secp256k1_ge_storage is a struct with two secp256k1_fe_storage fields. The C standard allows the compiler to add padding between the fields and at the end of the struct, but no sane compiler in the end would do this: The only reason to add padding is to ensure alignment, but such padding is never necessary between two fields of the same type. (If this was an array with two members instead of a struct with two members, then the alignment requirements would be the same, but no padding would be allowed.)

Similarly, secp256k1_fe_storage is a struct with a single array of uintXX_t. No padding is allowed between array elements. Again, C allows the compiler to insert padding at the end of the struct, but there’s no absolute reason to do so in this case.

For the uintXX_t itself, this guaranteed to have no padding bits, i.e., it’s guaranteed to have exactly XX bits.

So claim that for any existing compiler in the real world, sizeof(secp256k1_ge_storage) == 64, and we could assert this in assumptions.h.

Alternatives:

Get rid of the optimization and just never rely on the fact that sizeof(secp256k1_ge_storage) == 64 (but that’s slower)
Switch secp256k1_ge_storage and secp256k1_fe_storage to be actual array types so that the compiler is not allowed to add padding (but that’s pretty bad C style: sizeof() has different semantics on array types, = assignment is not possible, returning and passing by value is not possible, …)
Have a test override (but that’s complex and makes testing harder)

Anyway, I suggest we get this fix here merged first. It fixes a bug and it’s not controversial.

sipa commented at 3:10 pm on June 17, 2023: contributor

@real-or-random Alternatively, we could add a static assert in our assumptions that ge_storage is 64 bytes, and only support that. If we ever get a complaint about someone compiling for a platform where that’s not the case, we can still choose to reintroduce the non-64byte branch we currently have.

EDIT: just realized that’s what you suggested as first option. I agree.

real-or-random approved

real-or-random commented at 3:13 pm on June 17, 2023: contributor

ACK f1652528be5a287a3c33a4fae1e5763693333c2b tested by changing the two == 64 checks to == 65

sipa commented at 3:38 pm on June 17, 2023: contributor

utACK f1652528be5a287a3c33a4fae1e5763693333c2b

real-or-random merged this on Jun 18, 2023

real-or-random closed this on Jun 18, 2023

real-or-random cross-referenced this on Jun 18, 2023 from issue "sizeof(secp256k1_ge_storage) != 64" path not tested by real-or-random

theStack approved

theStack commented at 6:38 pm on June 18, 2023: contributor

ACK f1652528be5a287a3c33a4fae1e5763693333c2b

(retested with the “modify if-conditions to trigger else-paths”-approach)

One thing I noticed: this seems to be the only instance in the codebase now where an ARG_CHECK argument has side-effects. Is this just fine or will there e.g. ever be a build option which skips those checks for performance reasons? (in that case, uninitialized field elements would be passed to secp256k1_ge_set_xy).

real-or-random commented at 6:40 pm on June 18, 2023: contributor

One thing I noticed: this seems to be the only instance in the codebase now where an ARG_CHECK argument has side-effects. Is this just fine or will there e.g. ever be a build option which skips those checks for performance reasons? (in that case, uninitialized field elements would be passed to secp256k1_ge_set_xy).

Interesting observation! This should not be an issue. We always execute ARG_CHECKs and I can’t imagine a reason to disable them.

sipa referenced this in commit 901336eee7 on Jun 21, 2023

vmta referenced this in commit 8f03457eed on Jul 1, 2023

hebasto referenced this in commit 270d2b37b8 on Jul 21, 2023

jonasnick cross-referenced this on Jul 26, 2023 from issue Upstream PRs 1314, 1317, 1318, 1316, 1327, 1310, 1328, 1333, 1330, 1334, 1337, 1341, 1339, 1350, 1349, 1338, 1129, 1347, 1336, 1295, 1354, 1355, 1356 by jonasnick

Normalize ge produced from secp256k1_pubkey_load #1349