Do not invoke fe_is_zero on failed set_b32

sipa commented at 12:27 pm on May 15, 2023: contributor

Noticed in the CI output of #1313 (https://cirrus-ci.com/task/5117786435878912)

The code violates the field element contract that states that a field element that comes out of a failed secp256k1_fe_set_b32_limit call cannot be used before overwriting it. This is not an issue in practice, as such failure can only occur with negligible probability, but the experimental compiler in that CI setting is technically correct in detecting this possibility.

Fix it by setting it to 1 based on a secp256k1_fe_normalizes_to_zero test rather than a secp256k1_fe_is_zero one (which does not require normalization).

sipa cross-referenced this on May 15, 2023 from issue ci: Test on development snapshots of GCC and Clang by real-or-random

real-or-random approved

real-or-random commented at 8:54 pm on May 15, 2023: contributor

utACK 9fb5f2d3b0fdd00a9f5b51499a8f7d694725a8a5

I was about to open the same PR… :) And yes, ignoring the issue seems to be the simplest and most reasonable solution in this case.

stratospher commented at 10:28 am on May 18, 2023: contributor

ACK 9fb5f2d.

real-or-random commented at 7:53 am on May 19, 2023: contributor

Now that I look at it again, I wonder if this is the right fix.

The code violates the field element contract that states that a field element that comes out of a failed secp256k1_fe_set_b32_limit call cannot be used before overwriting it. This is not an issue in practice, as such failure can only occur with negligible probability, but the experimental compiler in that CI setting is technically correct in detecting this possibility.

The new code violates the precondition of secp256k1_gej_rescale with negligible probability. If we want to avoid negligible failures, how is the new code better (except that it makes the compiler happy)? One possible answer is that it is just simpler than the old code, and that’s a good argument. (But at least it’s not the rationale you brought up, so I’m not sure if this matches your thinking.)

We could simply cmov twice… Not nice, but I don’t think we care about performance a lot here. If we really want to assert it, we could actually abort (by calling the error callback). I don’t know.

stratospher commented at 8:18 am on May 19, 2023: contributor

The new code violates the precondition of secp256k1_gej_rescale with negligible probability.

which precondition? did i miss something?

the preconditions for s in secp256k1_gej_rescale are that it should pass the checks for:

secp256k1_fe_verify (magnitude = [0, 32] and normalized = 0 or 1)
secp256k1_fe_sqr (magnitude <= 8)

these would be satisfied because secp256k1_fe_set_b32_mod sets magnitude = 1 and normalized=0 for s.

in src/ecmult_gen_impl.h:114 in 9fb5f2d3b0 outdated

113+    secp256k1_fe_set_b32_mod(&s, nonce32);
114+#ifdef VERIFY
115+    /* Rescaling with s=0 would be invalid, but can only happen with negligible probability as it
116+     * is the output of a CSPRNG. */
117+    VERIFY_CHECK(!secp256k1_fe_normalizes_to_zero_var(&s));
118+#endif

real-or-random commented at 8:18 am on May 19, 2023:

0    secp256k1_fe_set_b32_mod(&s, nonce32);
1    secp256k1_fe_cmov(&s, &secp256k1_fe_one, secp256k1_fe_normalizes_to_zero(&s);

or just this.

sipa commented at 12:38 pm on May 19, 2023:

Done. That’s even simpler…

real-or-random commented at 8:22 am on May 19, 2023: contributor

which precondition?

Ok yes, I didn’t mean magnitude or normalization. secp256k1_gej_rescale requires that s is not zero, or more technically, that !secp256k1_fe_normalizes_to_zero(&s) (which is why the current code checks for this).

stratospher commented at 8:31 am on May 19, 2023: contributor

Ok yes, I didn’t mean magnitude or normalization. secp256k1_gej_rescale requires that s is not zero, or more technically, that !secp256k1_fe_normalizes_to_zero(&s) (which is why the current code checks for this).

oh! makes sense.

sipa force-pushed on May 19, 2023

sipa commented at 12:38 pm on May 19, 2023: contributor

@real-or-random This makes me wonder if a “nonzero” property (like magnitude/normalized) could be added…

Do not invoke fe_is_zero on failed set_b32_limit 6433175ffe

sipa force-pushed on May 19, 2023

in src/ecmult_gen_impl.h:109 in 6433175ffe

104@@ -106,11 +105,9 @@ static void secp256k1_ecmult_gen_blind(secp256k1_ecmult_gen_context *ctx, const
105     memcpy(keydata + 32, seed32, 32);
106     secp256k1_rfc6979_hmac_sha256_initialize(&rng, keydata, 64);
107     memset(keydata, 0, sizeof(keydata));
108-    /* Accept unobservably small non-uniformity. */

real-or-random commented at 2:25 pm on May 19, 2023:

nit: maybe bring that comment back (ideally one line below, i.e., above the secp256k1_fe_set_b32_mod call )

edit: Okay, ignore me. Now that we have two separate functions, calling the _mod variant makes the fact that we accept non-uniformity always explicit. That is, the code is self-documenting and the comment is superfluous.

real-or-random approved

real-or-random commented at 2:27 pm on May 19, 2023: contributor

utACK 6433175ffe2435bcee7333e21480e4194083caae

real-or-random commented at 2:36 pm on May 19, 2023: contributor

@real-or-random This makes me wonder if a “nonzero” property (like magnitude/normalized) could be added…

That would be true if the fe is guaranteed to be nonzero? (Rust has this in the type system: https://doc.rust-lang.org/std/num/struct.NonZeroU64.html)

Hm, not sure if it’s worth the hassle. It’s pretty hard to guarantee that numbers are nonzero. I mean not mean operations keep the guarantees (mostly just neg and mul). Do we need the property that things nonzero in many other places? Inversions perhaps?

stratospher commented at 9:39 am on May 23, 2023: contributor

ACK 6433175

real-or-random merged this on May 23, 2023

real-or-random closed this on May 23, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

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

Do not invoke fe_is_zero on failed set_b32_limit #1316