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.
Obvious Concept ACK
Is there any measurable impact on performance?
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); \
n? Also in the line below.
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.
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).
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). */
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?
Ah, uh, sure. I guess == would have helped me already.
0/** 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). */
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. */
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.
infinity always everywhere in the code, but here we use zero (ie secp256k1_gej_double_nonzero)
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:
abs_n unsigned
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.
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.
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); \
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).