ct: Use more volatile

real-or-random commented at 2:52 pm on May 10, 2023: contributor

The first commit adds a volatile to fix a constant-time issue in the ECDH code with GCC 13.1. The second commit adds a few more volatiles to conditional “flag” variables.

All of these cases were missed in #1257. I haven’t looked at the entire code base, but I think this should cover most (all?) of it. All of this is of course a bit arbitrary, but I think a good rule of thumb is to use volatile whenever we turn a secret boolean variable into a bitmask.

real-or-random force-pushed on May 10, 2023

real-or-random added the label bug on May 10, 2023

real-or-random added the label assurance on May 10, 2023

real-or-random added the label side-channel on May 10, 2023

in src/scalar_4x64_impl.h:194 in d73eadb51c outdated

189@@ -189,7 +190,8 @@ static int secp256k1_scalar_is_high(const secp256k1_scalar *a) {
190 static int secp256k1_scalar_cond_negate(secp256k1_scalar *r, int flag) {
191     /* If we are flag = 0, mask = 00...00 and this is a no-op;
192      * if we are flag = 1, mask = 11...11 and this is identical to secp256k1_scalar_negate */
193-    uint64_t mask = !flag - 1;
194+    volatile int vflag = flag;
195+    uint64_t mask = 0 - vflag;

real-or-random commented at 3:06 pm on May 10, 2023:

nb: this is intentionally 0 - vflag instead of -vflag to avoid warnings in MSVC, see #1293

real-or-random commented at 2:33 pm on May 11, 2023:

I’ve changed my mind. This should not be the concern of this PR.

jonasnick commented at 5:07 pm on May 10, 2023: contributor

Are we not missing the conditional operations in divststeps_30 and divsteps_59?

jonasnick added this to the milestone 0.3.2 (or 0.4.0) on May 11, 2023

real-or-random force-pushed on May 11, 2023

ct: Use volatile trick in scalar_cond_negate 5fb336f9ce

ct: Be cautious and use volatile trick in more "conditional" paths

 - secp256k1_scalar_cadd_bit
 - secp256k1_modinvXX_normalize_YY
 - secp256k1_modinvXX_divsteps_ZZ
 - ECMULT_CONST_TABLE_GET_GE

Even though those code loations are not problematic right now
(with current compilers).

17fa21733a

real-or-random force-pushed on May 11, 2023

real-or-random commented at 2:33 pm on May 11, 2023: contributor

Are we not missing the conditional operations in divststeps_30 and divsteps_59?

thanks! added.

sipa commented at 4:11 pm on May 11, 2023: contributor

ACK 17fa21733aae97bf671fede3ce528c7a3b2f5f14

I’ve benchmarked on a Intel Core i5-12500H CPU and didn’t see any noticeable performance impact on 64-bit. A 0.5% CPU performance is seen for signing in 32-bit mode (by @real-or-random), but I don’t think that weighs up against the additional assurance we get here.

jonasnick commented at 4:12 pm on May 11, 2023: contributor

ACK 17fa21733aae97bf671fede3ce528c7a3b2f5f14

I have not benchmarked performance

jonasnick merged this on May 11, 2023

jonasnick closed this on May 11, 2023

real-or-random added the label needs-changelog on May 11, 2023

sipa referenced this in commit b4eb644b6c on May 12, 2023

real-or-random referenced this in commit 5612a4196d on May 12, 2023

real-or-random referenced this in commit ab29c47ad2 on May 12, 2023

real-or-random referenced this in commit 76b43f3443 on May 12, 2023

real-or-random referenced this in commit 3e3d125b83 on May 12, 2023

hebasto referenced this in commit 49c52ea2b1 on May 13, 2023

real-or-random removed the label needs-changelog on May 13, 2023

real-or-random commented at 5:19 pm on May 14, 2023: contributor

For posterity, here’s the full output of the constant-time tests.

  0==31021== Memcheck, a memory error detector
  1==31021== Copyright (C) 2002-2022, and GNU GPL'd, by Julian Seward et al.
  2==31021== Using Valgrind-3.21.0 and LibVEX; rerun with -h for copyright info
  3==31021== Command: /home/tim/bs/dev/secp256k1/.libs/ctime_tests
  4==31021== 
  5==31021== Conditional jump or move depends on uninitialised value(s)
  6==31021==    at 0x4856355: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
  7==31021==    by 0x4856355: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:196)
  8==31021==    by 0x485DD3F: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:305)
  9==31021==    by 0x485DD3F: secp256k1_ecdsa_sign_inner (secp256k1.c:532)
 10==31021==    by 0x486165A: secp256k1_ecdsa_sign (secp256k1.c:567)
 11==31021==    by 0x10974D: run_tests (ctime_tests.c:98)
 12==31021==    by 0x109252: main (ctime_tests.c:53)
 13==31021== 
 14==31021== Conditional jump or move depends on uninitialised value(s)
 15==31021==    at 0x4856371: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 16==31021==    by 0x4856371: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:199)
 17==31021==    by 0x485DD3F: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:305)
 18==31021==    by 0x485DD3F: secp256k1_ecdsa_sign_inner (secp256k1.c:532)
 19==31021==    by 0x486165A: secp256k1_ecdsa_sign (secp256k1.c:567)
 20==31021==    by 0x10974D: run_tests (ctime_tests.c:98)
 21==31021==    by 0x109252: main (ctime_tests.c:53)
 22==31021== 
 23==31021== Conditional jump or move depends on uninitialised value(s)
 24==31021==    at 0x48563A8: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 25==31021==    by 0x48563A8: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:202)
 26==31021==    by 0x485DD3F: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:305)
 27==31021==    by 0x485DD3F: secp256k1_ecdsa_sign_inner (secp256k1.c:532)
 28==31021==    by 0x486165A: secp256k1_ecdsa_sign (secp256k1.c:567)
 29==31021==    by 0x10974D: run_tests (ctime_tests.c:98)
 30==31021==    by 0x109252: main (ctime_tests.c:53)
 31==31021== 
 32==31021== Conditional jump or move depends on uninitialised value(s)
 33==31021==    at 0x4856355: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 34==31021==    by 0x4856355: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:196)
 35==31021==    by 0x485B304: secp256k1_wnaf_const.constprop.0 (ecmult_const_impl.h:99)
 36==31021==    by 0x4862657: secp256k1_ecmult_const (ecmult_const_impl.h:155)
 37==31021==    by 0x4862657: secp256k1_ecdh (main_impl.h:53)
 38==31021==    by 0x1098F0: run_tests (ctime_tests.c:107)
 39==31021==    by 0x109252: main (ctime_tests.c:53)
 40==31021== 
 41==31021== Conditional jump or move depends on uninitialised value(s)
 42==31021==    at 0x4856371: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 43==31021==    by 0x4856371: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:199)
 44==31021==    by 0x485B304: secp256k1_wnaf_const.constprop.0 (ecmult_const_impl.h:99)
 45==31021==    by 0x4862657: secp256k1_ecmult_const (ecmult_const_impl.h:155)
 46==31021==    by 0x4862657: secp256k1_ecdh (main_impl.h:53)
 47==31021==    by 0x1098F0: run_tests (ctime_tests.c:107)
 48==31021==    by 0x109252: main (ctime_tests.c:53)
 49==31021== 
 50==31021== Conditional jump or move depends on uninitialised value(s)
 51==31021==    at 0x48563A8: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 52==31021==    by 0x48563A8: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:202)
 53==31021==    by 0x485B304: secp256k1_wnaf_const.constprop.0 (ecmult_const_impl.h:99)
 54==31021==    by 0x4862657: secp256k1_ecmult_const (ecmult_const_impl.h:155)
 55==31021==    by 0x4862657: secp256k1_ecdh (main_impl.h:53)
 56==31021==    by 0x1098F0: run_tests (ctime_tests.c:107)
 57==31021==    by 0x109252: main (ctime_tests.c:53)
 58==31021== 
 59==31021== Conditional jump or move depends on uninitialised value(s)
 60==31021==    at 0x4856355: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 61==31021==    by 0x4856355: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:196)
 62==31021==    by 0x485B304: secp256k1_wnaf_const.constprop.0 (ecmult_const_impl.h:99)
 63==31021==    by 0x4862683: secp256k1_ecmult_const (ecmult_const_impl.h:156)
 64==31021==    by 0x4862683: secp256k1_ecdh (main_impl.h:53)
 65==31021==    by 0x1098F0: run_tests (ctime_tests.c:107)
 66==31021==    by 0x109252: main (ctime_tests.c:53)
 67==31021== 
 68==31021== Conditional jump or move depends on uninitialised value(s)
 69==31021==    at 0x4856371: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 70==31021==    by 0x4856371: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:199)
 71==31021==    by 0x485B304: secp256k1_wnaf_const.constprop.0 (ecmult_const_impl.h:99)
 72==31021==    by 0x4862683: secp256k1_ecmult_const (ecmult_const_impl.h:156)
 73==31021==    by 0x4862683: secp256k1_ecdh (main_impl.h:53)
 74==31021==    by 0x1098F0: run_tests (ctime_tests.c:107)
 75==31021==    by 0x109252: main (ctime_tests.c:53)
 76==31021== 
 77==31021== Conditional jump or move depends on uninitialised value(s)
 78==31021==    at 0x48563A8: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 79==31021==    by 0x48563A8: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:202)
 80==31021==    by 0x485B304: secp256k1_wnaf_const.constprop.0 (ecmult_const_impl.h:99)
 81==31021==    by 0x4862683: secp256k1_ecmult_const (ecmult_const_impl.h:156)
 82==31021==    by 0x4862683: secp256k1_ecdh (main_impl.h:53)
 83==31021==    by 0x1098F0: run_tests (ctime_tests.c:107)
 84==31021==    by 0x109252: main (ctime_tests.c:53)
 85==31021== 
 86==31021== Conditional jump or move depends on uninitialised value(s)
 87==31021==    at 0x4856355: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 88==31021==    by 0x4856355: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:196)
 89==31021==    by 0x485DD3F: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:305)
 90==31021==    by 0x485DD3F: secp256k1_ecdsa_sign_inner (secp256k1.c:532)
 91==31021==    by 0x4863B36: secp256k1_ecdsa_sign_recoverable (main_impl.h:132)
 92==31021==    by 0x1099ED: run_tests (ctime_tests.c:115)
 93==31021==    by 0x109252: main (ctime_tests.c:53)
 94==31021== 
 95==31021== Conditional jump or move depends on uninitialised value(s)
 96==31021==    at 0x4856371: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
 97==31021==    by 0x4856371: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:199)
 98==31021==    by 0x485DD3F: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:305)
 99==31021==    by 0x485DD3F: secp256k1_ecdsa_sign_inner (secp256k1.c:532)
100==31021==    by 0x4863B36: secp256k1_ecdsa_sign_recoverable (main_impl.h:132)
101==31021==    by 0x1099ED: run_tests (ctime_tests.c:115)
102==31021==    by 0x109252: main (ctime_tests.c:53)
103==31021== 
104==31021== Conditional jump or move depends on uninitialised value(s)
105==31021==    at 0x48563A8: secp256k1_u128_accum_u64 (int128_native_impl.h:20)
106==31021==    by 0x48563A8: secp256k1_scalar_cond_negate (scalar_4x64_impl.h:202)
107==31021==    by 0x485DD3F: secp256k1_ecdsa_sig_sign (ecdsa_impl.h:305)
108==31021==    by 0x485DD3F: secp256k1_ecdsa_sign_inner (secp256k1.c:532)
109==31021==    by 0x4863B36: secp256k1_ecdsa_sign_recoverable (main_impl.h:132)
110==31021==    by 0x1099ED: run_tests (ctime_tests.c:115)
111==31021==    by 0x109252: main (ctime_tests.c:53)
112==31021== 
113==31021== 
114==31021== HEAP SUMMARY:
115==31021==     in use at exit: 0 bytes in 0 blocks
116==31021==   total heap usage: 1 allocs, 1 frees, 208 bytes allocated
117==31021== 
118==31021== All heap blocks were freed -- no leaks are possible
119==31021== 
120==31021== Use --track-origins=yes to see where uninitialised values come from
121==31021== For lists of detected and suppressed errors, rerun with: -s
122==31021== ERROR SUMMARY: 12 errors from 12 contexts (suppressed: 0 from 0)

The violation in ECDSA is a false positive because the affected scalar is public at this point, but the violation in ECDH is real.

dderjoel referenced this in commit 53c88ce13c on May 23, 2023

dderjoel referenced this in commit 826f023db0 on May 23, 2023

vmta referenced this in commit e1120c94a1 on Jun 4, 2023

dderjoel referenced this in commit 3660c048d5 on Jun 21, 2023

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

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

jonasnick cross-referenced this on Jul 24, 2023 from issue Upstream PRs 1268, 1276, 1267, 1265, 1230, 1279, 1273, 1263, 1231, 1285, 1283, 1205, 1286, 1275, 1234, 1239, 1240, 1284, 1277, 1289, 1270, 1296, 1301, 1299, 1066, 1300, 1292, 1305, 1303, 1133, 1306, 1207, 1304, 1307, 1311, 1309, 1312 by jonasnick

ct: Use more volatile #1303