VERIFY_CHECK precondition for secp256k1_fe_set

roconnor-blockstream commented at 3:22 pm on May 13, 2021: contributor

Also set the magnitude to 0 when setting the value to 0.

roconnor-blockstream commented at 6:13 pm on May 13, 2021: contributor

This PR overlaps with #636.

real-or-random commented at 6:19 pm on May 13, 2021: contributor

@roconnor-blockstream Maybe cherry-pick https://github.com/bitcoin-core/secp256k1/pull/636/commits/b17a7df8145a6a86d49c354c7e7b59a432ea5346 (or just steal my improved comment for here.) and then add the VERIFY_CHECK here.

roconnor-blockstream force-pushed on May 13, 2021

roconnor-blockstream commented at 7:19 pm on May 13, 2021: contributor

Cherry-picked.

Now that I look at it again, do you think the VERIFY_CHECK’s I add are really needed? Any overflow will be caught by the subsequent secp256k1_fe_verify. So maybe I should just stick with your one commit.

real-or-random approved

real-or-random commented at 7:28 pm on May 13, 2021: contributor

Now that I look at it again, do you think the VERIFY_CHECK’s I add are really needed? Any overflow will be caught by the subsequent secp256k1_fe_verify. So maybe I should just stick with your one commit.

Ok maybe they’re not strictly necessary. But early assertions are better than late assertions for debugging. Moreover, this makes the code more self-documenting, so I think it’s an improvement.

utACK e3efa923d1e902220e8c4ec2c7797713db9b8e19

roconnor-blockstream force-pushed on Aug 28, 2021

roconnor-blockstream commented at 6:04 pm on August 28, 2021: contributor

rebased.

in src/field_5x52_impl.h:230 in cb7e902e85 outdated

226@@ -227,10 +227,11 @@ static int secp256k1_fe_normalizes_to_zero_var(const secp256k1_fe *r) {
227 }
228 
229 SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe *r, int a) {
230+    VERIFY_CHECK(0 <= a && a <= 0x7FFF);

jonasnick commented at 2:50 pm on October 15, 2021:

Where does 0x7FFF come from?

roconnor-blockstream commented at 3:02 pm on October 15, 2021:

0x7FFF is the largest portable value of for an int.

jonasnick commented at 3:13 pm on October 15, 2021:

Oh, the smallest INT_MAX, I see. Would be better to add a note to the doc that the definition of small is <= 0x7FFF imo.

roconnor-blockstream commented at 3:37 pm on October 15, 2021:

Done.

in src/field_10x26_impl.h:271 in cb7e902e85 outdated

263@@ -264,10 +264,11 @@ static int secp256k1_fe_normalizes_to_zero_var(const secp256k1_fe *r) {
264 }
265 
266 SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe *r, int a) {
267+    VERIFY_CHECK(0 <= a && a <= 0x7FFF);
268     r->n[0] = a;
269     r->n[1] = r->n[2] = r->n[3] = r->n[4] = r->n[5] = r->n[6] = r->n[7] = r->n[8] = r->n[9] = 0;
270 #ifdef VERIFY
271-    r->magnitude = 1;
272+    r->magnitude = (a != 0);

jonasnick commented at 2:52 pm on October 15, 2021:

Wouldn’t it make sense to add a test that would have spotted this mistake? Otherwise secp256k1_fe_set_int(r, 0) is untested.

roconnor-blockstream commented at 3:13 pm on October 15, 2021:

What sort of test are you imagining?

The previous code is not in error in the sense that the magnitude only provides an upper bound on the size of the value. This change simply makes that bound tighter in some cases.

jonasnick commented at 3:29 pm on October 15, 2021:

I was told previously that the tests error when when one replaces fe_clear with fe_set_int(..,0) because the magnitude is incorrect. But since the magnitude is only an upper bound, adding a test just for this specific magnitude isn’t worth the loc. Nevermind.

roconnor-blockstream commented at 3:34 pm on October 15, 2021:

I find that plausible. The consequences of having too loose upper bounds is that some code that is correct may fail various magnitude checks.

P.S. I think there is a general plan to have fe_clear mark memory as if it were uninitiated for the purposed of valgrind, and then use fe_set_int(...,0) for those situations where we explicitly want a 0 value. Like when we clear the coordinates when calling gej_set_infinity, it ought to be the case that those cleared values are never read from.

Make _set_fe_int( . , 0 ) set magnitude to 0 d49011f54c

VERIFY_CHECK precondition for secp256k1_fe_set_int. 2888640132

roconnor-blockstream force-pushed on Oct 15, 2021

real-or-random approved

real-or-random commented at 3:50 pm on October 15, 2021: contributor

ACK d49011f54c2b31807158bdf06364f331558cccc7

peterdettman commented at 3:51 pm on October 15, 2021: contributor

IMO, magnitudes should not depend on actual runtime values of the data. I was going to suggest secp256k1_fe_cmov as a similar example, but I see that was also changed (https://github.com/bitcoin-core/secp256k1/commit/34a67c773b0871e5797c7ab506d004e80911f120#diff-804d86c08a0081110a76bd942bd5f0f3663c5a9a4c4e6d2e7093c11c433306c8).

We can argue it out, but first: has it already been discussed somewhere?

roconnor-blockstream commented at 3:58 pm on October 15, 2021: contributor

@peterdettman I think this is a reasonable concern. In production, set_int is only ever called with literals (and moreover only the literals 0 and 1). Of course, this is not guaranteed to be called with literals.

I was basing this code change on the existing behaviour of secp256k1_fe_mul_int, which is also “dynamic” in the same way, and is also only called with literal values in production (but again isn’t guaranteed to be called only with literals).

real-or-random commented at 3:59 pm on October 15, 2021: contributor

IMO, magnitudes should not depend on actual runtime values of the data. I was going to suggest secp256k1_fe_cmov as a similar example, but I see that was also changed (34a67c7#diff-804d86c08a0081110a76bd942bd5f0f3663c5a9a4c4e6d2e7093c11c433306c8).

We can argue it out, but first: has it already been discussed somewhere?

I don’t think it has been discussed.

Why do you think so? Because it should always be possible to reason about the magnitude statically? I can buy that argument.

real-or-random commented at 4:18 pm on October 15, 2021: contributor

So the reason behind https://github.com/bitcoin-core/secp256k1/commit/b17a7df8145a6a86d49c354c7e7b59a432ea5346 (which @roconnor-blockstream cherry-picked here) was that in the current code base we’re using _fe_clear to set value and magnitude to 0. Now my plan in #636 was to separate “clearing” memory (for security reasons) and setting to 0 properly into _clear and _set_int( , 0), see https://github.com/bitcoin-core/secp256k1/pull/636/commits/b33a8e49e89f5a1ea02a9b9b9b208cb4f3d59e44 (where by the way I argued for making the int another type, e.g., char). And this would break the tests without b17a7df8145a6a86d49c354c7e7b59a432ea5346.

Let me note that this does not contradict your assumption that magnitude should be determined statically. So if we want to have this, then we should have three functions in the end: _clear (for clearing memory) _set_zero and _set_int(, x) where x > 0.

But maybe for now, it’s then easier to restrict this PR to just @roconnor-blockstream’s initital commit and then have the other discussion about magnitude? This would anyway require more changes you’ve already pointed out, namely at least in _fe_cmov and _fe_mul_int.

peterdettman commented at 6:06 pm on October 15, 2021: contributor

Happy to pick up the discussion on a separate issue somewhere, but it basically boils down to static reasoning, yes. Also, yes to _set_zero as a better option to set a static constant 0 value.

jonasnick commented at 1:22 pm on October 20, 2021: contributor

ACK 2888640132eb64ed30a8a208931f27447c3e0366

real-or-random cross-referenced this on Oct 28, 2021 from issue Make fe magnitude implied statically by real-or-random

real-or-random commented at 3:05 pm on October 28, 2021: contributor

ACK 2888640132eb64ed30a8a208931f27447c3e0366

I talked to @jonasnick elsewhere and he told me that he read over my suggesting to remove b17a7df8145a6a86d49c354c7e7b59a432ea5346 from this PR. We were in agreement that this PR in its current form (with b17a7df8145a6a86d49c354c7e7b59a432ea5346 included) is an improvement, and now that we have the reviews, we should get it merged. In particular, magnitude is statically implied neither before (e.g. due to secp256k1_fe_mul_int) nor after this PR. I created #1001 to keep track of this.

real-or-random merged this on Oct 28, 2021

real-or-random closed this on Oct 28, 2021

sipa referenced this in commit f727914d7e on Oct 28, 2021

sipa referenced this in commit 440f7ec80e on Oct 31, 2021

sipa referenced this in commit d057eae556 on Dec 2, 2021

fanquake referenced this in commit c4a1e09a8c on Dec 3, 2021

sipa referenced this in commit 86dbc4d075 on Dec 15, 2021

jonasnick cross-referenced this on Jan 2, 2022 from issue Sync Upstream by jonasnick

real-or-random referenced this in commit 21e2d65b79 on Jan 5, 2022

gwillen referenced this in commit 35d6112a72 on May 25, 2022

janus referenced this in commit 879a9a27b9 on Jul 10, 2022

patricklodder referenced this in commit 21badcf9d2 on Jul 25, 2022

patricklodder referenced this in commit 03002a9013 on Jul 28, 2022

backpacker69 referenced this in commit 77186f4a04 on Jan 18, 2023

real-or-random cross-referenced this on Mar 2, 2023 from issue Add secp256k1_fe_add_int function by sipa

str4d referenced this in commit 6de4698bf9 on Apr 21, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

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

VERIFY_CHECK precondition for secp256k1_fe_set_int. #943