Remove secret-dependant non-constant time operation in ecmult

gmaxwell commented at 3:11 PM on January 8, 2020: contributor

ECMULT_CONST_TABLE_GET_GE was branching on its secret input.

Also makes secp256k1_gej_double_var implemented as a wrapper on secp256k1_gej_double_nonzero instead of the other way around. This wasn't a constant time bug but it was fragile and could easily become one in the future if the double_var algorithm is changed.

gmaxwell cross-referenced this on Jan 8, 2020 from issue Review if ECDH is still experimental by ysangkok

gmaxwell cross-referenced this on Jan 8, 2020 from issue Constant-time behaviour test using valgrind memtest. by gmaxwell

sipa commented at 4:20 PM on January 8, 2020: contributor

Obvious Concept ACK

Is there any measurable impact on performance?

in src/ecmult_const_impl.h:18 in 9cc02a41a6 outdated

  14 | @@ -15,7 +15,8 @@
  15 |  /* This is like `ECMULT_TABLE_GET_GE` but is constant time */
  16 |  #define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \
  17 |      int m; \
  18 | -    int abs_n = (n) * (((n) > 0) * 2 - 1); \
  19 | +    int mask = n >> (sizeof(n) * CHAR_BIT - 1); \

real-or-random commented at 4:33 PM on January 8, 2020:

Add parentheses around n? Also in the line below.

gmaxwell commented at 4:40 PM on January 8, 2020:

doh. Thanks. done.

real-or-random commented at 4:33 PM on January 8, 2020: contributor

Great find!

gmaxwell commented at 4:51 PM on January 8, 2020: contributor

The project doesn't have any good way to benchmark really small changes, you just end up measuring noise from cache alignment of code and differences in branch predictor aliasing.

There has been some academic work on randomizing binary layout and running tests a bunch of times and averaging over them, but the implementation I found was unusably bitrotted. :(

But-- best effort,

Before: ecdh: min 89.7us / avg 89.7us / max 90.0us ecdsa_verify: min 77.7us / avg 77.7us / max 77.9us

After: ecdh: min 88.0us / avg 88.0us / max 88.3us ecdsa_verify: min 77.8us / avg 77.9us / max 77.9us

Wouldn't be shocking if there were a real improvement for those ECDHs, but I'd just assume that's noise.

in src/group.h:98 in 6994530fcd outdated

  96 | @@ -97,7 +97,7 @@ static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a);
  97 |  
  98 |  /** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0).

real-or-random commented at 9:22 AM on January 9, 2020:

The comment still mentions the removed parameter.

in src/group.h:101 in 6994530fcd outdated

  96 | @@ -97,7 +97,7 @@ static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a);
  97 |  
  98 |  /** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0).
  99 |   * a may not be zero. Constant time. */
 100 | -static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a, secp256k1_fe *rzr);
 101 | +static void secp256k1_gej_double_nonzero(secp256k1_gej *r, const secp256k1_gej *a);
 102 |  
 103 |  /** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0). */

real-or-random commented at 9:31 AM on January 9, 2020:

Sorry, again not your change. But I don't understand the rzr comment anyway. The comment indicates that *rzr is an input argument but in the code it's an output argument. Or am I just reading it in the wrong way?

gmaxwell commented at 11:26 AM on January 9, 2020:

The comment is giving an algebraic identity, not a procedure. rzr stores the value such that r->z == a->z * *rzr

gmaxwell commented at 11:43 AM on January 9, 2020:

I don't know how to write it as a procedure where it won't sound like it's computing an expensive inverse inside the function.

real-or-random commented at 12:11 PM on January 9, 2020:

Ah, uh, sure. I guess == would have helped me already.

/** Set r equal to the double of a. If rzr is not-NULL, then this sets *rzr such that r->z == a->z * *rzr (where infinity means an implicit z = 0). */

gmaxwell commented at 1:08 PM on January 9, 2020:

Sounds great.

in src/group.h:99 in 6994530fcd outdated

  96 | @@ -97,7 +97,7 @@ static int secp256k1_gej_has_quad_y_var(const secp256k1_gej *a);
  97 |  
  98 |  /** Set r equal to the double of a. If rzr is not-NULL, r->z = a->z * *rzr (where infinity means an implicit z = 0).
  99 |   * a may not be zero. Constant time. */

real-or-random commented at 9:41 AM on January 9, 2020:

And when you change the comment here, could you add that zero means infinity? It's kind of confusing to have two different things for the same thing, in the same comment.

Or should we even change the function name (can be a different PR of course)? I think we always say infinity.

elichai commented at 11:34 AM on January 9, 2020:

I think Tim means that we use infinity always everywhere in the code, but here we use zero (ie secp256k1_gej_double_nonzero)

real-or-random commented at 10:15 AM on January 9, 2020: contributor

Compiler output for the new abs looks good to me for the common targets, see https://godbolt.org/#g:!((g:!((g:!((h:codeEditor,i:(fontScale:14,j:1,lang:___c,selection:(endColumn:19,endLineNumber:5,positionColumn:19,positionLineNumber:5,selectionStartColumn:19,selectionStartLineNumber:5,startColumn:19,startLineNumber:5),source:'%23include+%3Climits.h%3E%0A%0A/*+unsigned+*/+int+abs_n(int+n)+%7B%0A++++int+mask+%3D+(n)+%3E%3E+(sizeof(n)+*+CHAR_BIT+-+1)%3B%0A++++/*+unsigned+*/+int+abs_n+%3D+((n)+%2B+mask)+%5E+mask%3B%0A++++/*+unsigned+*/+int+idx_n+%3D+abs_n+/+2%3B%0A++++return+idx_n%3B%0A%7D'),l:'5',n:'0',o:'C+source+%231',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0'),(g:!((h:compiler,i:(compiler:cclang900,filters:(b:'0',binary:'1',commentOnly:'0',demangle:'0',directives:'0',execute:'1',intel:'0',libraryCode:'1',trim:'1'),fontScale:14,j:1,lang:___c,libs:!(),options:'-O3',selection:(endColumn:12,endLineNumber:6,positionColumn:12,positionLineNumber:6,selectionStartColumn:12,selectionStartLineNumber:6,startColumn:12,startLineNumber:6),source:1),l:'5',n:'0',o:'x86-64+clang+9.0.0+(Editor+%231,+Compiler+%231)+C',t:'0')),k:50,l:'4',n:'0',o:'',s:0,t:'0')),l:'2',n:'0',o:'',t:'0')),version:4

Two observations here:

clang is clever and uses cmov
this code gets faster on gcc and msvc if you make abs_n unsigned

Remove secret-dependant non-constant time operation in ecmult_const.

ECMULT_CONST_TABLE_GET_GE was branching on its secret input.

Also makes secp256k1_gej_double_var implemented as a wrapper
 on secp256k1_gej_double_nonzero instead of the other way
 around.  This wasn't a constant time bug but it was fragile
 and could easily become one in the future if the double_var
 algorithm is changed.

2241ae6d14

gmaxwell commented at 12:21 PM on January 9, 2020: contributor

this code gets faster on gcc and msvc if you make abs_n unsigned

I don't especially like peppering code with unsigned values where it's not needed (e.g. for overflow or range purposes), as it risks creating bugs due to promotion and it prevents some optimizations that depend on static analysis being able to assume overflow won't happen. ... in this case the only justification for the performance difference is / behaviour using >> 1 instead of /2 should result in the same behaviour as changing things to unsigned.

I also prefer the shift because on virtually every system an actual div instruction is extremely non-constant time. This means that the code is making a strong assumption that the compiler will perform strength reduction. I'm confident this isn't true and that sometimes they'll emit a div or a huge blob of division code on cpus without a divider arm (try -Os builds on older GCC).

I think it would be best from a reviewability perspective if we just never use '/' or % on secret data.

Thanks for drawing my attention to this.

real-or-random commented at 1:19 PM on January 10, 2020: contributor

ACK 9b3969c9d6076953faeaf9e96134ac2bab8ba7ee I read the diff carefully and tested the code with ECDH enabled and various settings, also on valgrind

in src/ecmult_const_impl.h:19 in 9b3969c9d6 outdated

  14 | @@ -15,8 +15,9 @@
  15 |  /* This is like `ECMULT_TABLE_GET_GE` but is constant time */
  16 |  #define ECMULT_CONST_TABLE_GET_GE(r,pre,n,w) do { \
  17 |      int m; \
  18 | -    int abs_n = (n) * (((n) > 0) * 2 - 1); \
  19 | -    int idx_n = abs_n / 2; \
  20 | +    int mask = (n) >> (sizeof(n) * CHAR_BIT - 1); \

sipa commented at 7:38 PM on January 10, 2020:

Maybe add a comment here explaining what it does (or give the old code as explanation)?

gmaxwell commented at 2:17 AM on January 11, 2020:

OK.

sipa commented at 7:42 PM on January 10, 2020: contributor

ACK.

I've benchmarked this on a Core i7-7820HQ with Intel PState disabled and CPU locked to 1.7 GHz. bench_ecdh goes from approximately 155.1 us to 154.7 us. This is a tiny (0.25%) performance improvement, but it seems significant as the standard deviation is still smaller (around 0.1-0.2 us).

Clarify comments about use of rzr on ge functions and abs function. d567b779fe

real-or-random commented at 12:57 PM on January 11, 2020: contributor

ACK d567b779fe446fd18820a9d2968ecb703c8dea19 I read the diff carefully and tested the code with ECDH enabled and various settings, also on valgrind

gmaxwell commented at 8:01 PM on January 14, 2020: contributor

What is needed to move this forward?

sipa commented at 9:24 PM on January 14, 2020: contributor

ACK d567b779fe446fd18820a9d2968ecb703c8dea19

sipa referenced this in commit 227a4f2d07 on Jan 14, 2020

sipa merged this on Jan 14, 2020

sipa closed this on Jan 14, 2020

elichai commented at 10:19 AM on January 15, 2020: contributor

ACK d567b779fe446fd18820a9d2968ecb703c8dea19 after merge. checked the asm of the abs/2 in godbolt on multiple different architectures and different compilers and non of them seem to use known variable time instructions.

benma cross-referenced this on Apr 21, 2020 from issue rebase on bitcoin-core/secp256k1 by benma

elichai cross-referenced this on May 13, 2020 from issue Bump libsecp256k1 by elichai

sipa cross-referenced this on Jun 9, 2020 from issue Update libsecp256k1 subtree by sipa

fanquake referenced this in commit 8c97780db8 on Jun 13, 2020

sidhujag referenced this in commit 8a3a072968 on Jun 13, 2020

ComputerCraftr referenced this in commit b98f1c6e6c on Jun 16, 2020

UdjinM6 referenced this in commit 9d36ba6570 on Aug 10, 2021

5tefan referenced this in commit 8ded2caa74 on Aug 12, 2021

gades referenced this in commit d855cc511d on May 8, 2022

Remove secret-dependant non-constant time operation in ecmult_const. #709