Initialize field elements when resulting in infinity

elichai commented at 4:13 pm on December 10, 2019: contributor

Currently if secp256k1_gej_add_var / secp256k1_gej_add_ge_var / secp256k1_gej_add_zinv_var receive P + (-P) it will set gej->infinity = 1 but doesn’t call initialize the field elements. Notice that this is the only branch in the function that results in an uninitialized output.

By using secp256k1_gej_set_infinity() it will set the field elements to zero while also setting the infinity flag.

I also added a test that fails with valgrind on current master but passes with the fix.

EDIT: This isn’t a bug or something necessary, I just personally found this helpful.

Added test with additions resulting in infinity 61d1ecb028

Clear field elements when writing infinity 47a7b8382f

elichai commented at 4:13 pm on December 10, 2019: contributor

Output of valgrind without commit 47a7b83 :

 0==945841== Memcheck, a memory error detector
 1==945841== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
 2==945841== Using Valgrind-3.15.0 and LibVEX; rerun with -h for copyright info
 3==945841== Command: ./tests ___track-origins=yes --exit-on-first-error
 4==945841== 
 5test count = 0
 6random seed = 00000000000000000000000000000000
 7==945841== Conditional jump or move depends on uninitialised value(s)
 8==945841==    at 0x12DEF6: secp256k1_fe_is_zero (field_5x52_impl.h:241)
 9==945841==    by 0x12DEF6: test_intialized_inf (tests.c:2274)
10==945841==    by 0x10A4BF: main (tests.c:5292)
11==945841== 
12==945841== Conditional jump or move depends on uninitialised value(s)
13==945841==    at 0x10DA79: secp256k1_fe_verify (field_5x52_impl.h:34)
14==945841==    by 0x12DF03: secp256k1_fe_is_zero (field_5x52_impl.h:242)
15==945841==    by 0x12DF03: test_intialized_inf (tests.c:2274)
16==945841==    by 0x10A4BF: main (tests.c:5292)
17==945841== 
18==945841== Conditional jump or move depends on uninitialised value(s)
19==945841==    at 0x10DB38: secp256k1_fe_verify (field_5x52_impl.h:45)
20==945841==    by 0x12DF03: secp256k1_fe_is_zero (field_5x52_impl.h:242)
21==945841==    by 0x12DF03: test_intialized_inf (tests.c:2274)
22==945841==    by 0x10A4BF: main (tests.c:5292)
23==945841== 
24src/field_5x52_impl.h:49: test condition failed: r == 1
25==945841== 
26==945841== Process terminating with default action of signal 6 (SIGABRT): dumping core
27==945841==    at 0x4B8BF25: raise (in /usr/lib/libc-2.30.so)
28==945841==    by 0x4B75896: abort (in /usr/lib/libc-2.30.so)
29==945841==    by 0x10DB9C: secp256k1_fe_verify (field_5x52_impl.h:49)
30==945841==    by 0x12DF03: secp256k1_fe_is_zero (field_5x52_impl.h:242)
31==945841==    by 0x12DF03: test_intialized_inf (tests.c:2274)
32==945841==    by 0x10A4BF: main (tests.c:5292)
33==945841== 
34==945841== HEAP SUMMARY:
35==945841==     in use at exit: 524,528 bytes in 1 blocks
36==945841==   total heap usage: 27 allocs, 26 frees, 6,823,016 bytes allocated
37==945841== 
38==945841== LEAK SUMMARY:
39==945841==    definitely lost: 0 bytes in 0 blocks
40==945841==    indirectly lost: 0 bytes in 0 blocks
41==945841==      possibly lost: 0 bytes in 0 blocks
42==945841==    still reachable: 524,528 bytes in 1 blocks
43==945841==         suppressed: 0 bytes in 0 blocks
44==945841== Rerun with --leak-check=full to see details of leaked memory
45==945841== 
46==945841== Use --track-origins=yes to see where uninitialised values come from
47==945841== For lists of detected and suppressed errors, rerun with: -s
48==945841== ERROR SUMMARY: 3 errors from 3 contexts (suppressed: 0 from 0)
49Aborted (core dumped)

sipa commented at 4:25 pm on December 10, 2019: contributor

I don’t expect this to have a measurable performance impact, so ok.

But conceptually, why is this necessary? Not initializing variables in C is very much allowed by the language.

elichai commented at 4:28 pm on December 10, 2019: contributor

@sipa It’s not necessary, and I wanted to add a line saying that it’s fine if people disagree :) (but forgot) It’s just an unexpected result when writing new things in the internals, you don’t expect to get uninitialized type back from a function, especially if it happens only in a single branch. (unless of course it’s documented)

so this shouldn’t really affect things. it’s just that I spent the whole day on valgrind figuring this out :) (ran a check on the field element without first checking if it’s infinity and one of my tests triggered an infinity)

(you can easily encounter it when writing protocols that allow infinities (unlike ECDSA/Schnorr etc.))

apoelstra commented at 5:23 pm on December 10, 2019: contributor

Yeah, I think it’s worth doing this. I’ve run into this issue as well when writing unit tests (though now that I know about it it’s usually a quick fix).

gmaxwell commented at 4:05 am on December 13, 2019: contributor

The FE are meaningless when infinity is set, any code accessing them is buggy– in the var functions they can be set to zero but elsewhere they could end up as random numbers and I don’t think setting them to zero can always be costless. I suppose if it’s actually costless then it would be okay if its done consistently.

apoelstra commented at 8:30 pm on December 17, 2019: contributor

Regarding “any code accessing them is buggy”, I believe the places I ran into valgrind-apparent trouble were memcpy’ing or assigning infinite group elements. This is very rarely (never?) done in the real code but in unit tests it’s pretty common.

gmaxwell commented at 11:54 am on December 18, 2019: contributor

Memcpying uninitilized data should be hunky dory, otherwise you could essentially never copy structs which may have uninitilable padding.

real-or-random commented at 12:18 pm on December 28, 2019: contributor

I think I’d be fine with either accepting or not accepting this PR but I’m somewhat reluctant to changes of this kind. The current code is correct. And some parts of the library are heavily written with performance in mind, and this PR would break with this style in some sense.

I guess there are lots of similar things that we could make “safer” but I think this is not worth the effort and it may be a step back in terms of performance.

real-or-random commented at 12:31 pm on December 28, 2019: contributor

Memcpying uninitilized data should be hunky dory, otherwise you could essentially never copy structs which may have uninitilable padding.

Ignoring versions, even the C committee itself does not really agree on whether this should be UB or not. So who knows what compilers will assume in the future?

So in this particular case, it may actually be preferable to be careful and make sure we err on side of caution…

real-or-random cross-referenced this on Feb 12, 2020 from issue Eliminate harmless non-constant time operations on secret data. by gmaxwell

real-or-random cross-referenced this on Sep 2, 2020 from issue Cleaner infinity handling in group law and ecmult_const. by gmaxwell

sipa commented at 5:53 pm on September 2, 2020: contributor

Given the discussion in #791, ACK.

The changes here are all in exceptional branches (doubling/infinity being hit in generic addition functions, which should in non-adverserial cases only be hit with negligible probability).

real-or-random commented at 6:07 pm on September 2, 2020: contributor

The changes here are all in exceptional branches (doubling/infinity being hit in generic addition functions, which should in non-adverserial cases only be hit with negligible probability).

That’s a great point.

ACK 47a7b8382fd6f1458d859b315cf3bcd3b9790b68

real-or-random merged this on Sep 9, 2020

real-or-random closed this on Sep 9, 2020

elichai deleted the branch on Sep 10, 2020

jasonbcox referenced this in commit 13f2aeb050 on Sep 28, 2020

deadalnix referenced this in commit 792f4ce344 on Sep 29, 2020

Initialize field elements when resulting in infinity #699