Line data Source code
1 : #include "fd_curve25519.h"
2 :
3 : #if FD_HAS_AVX512
4 : #include "avx512/fd_curve25519_secure.c"
5 : #else
6 : #include "ref/fd_curve25519_secure.c"
7 : #endif
8 : #ifndef FD_ED25519_UNIT_TESTS
9 :
10 : /* All the functions in this file are considered "secure", specifically:
11 :
12 : - Constant time in the input, i.e. the input can be a secret
13 : - Small and auditable code base, incl. simple types
14 : - Either, no local variables = no need to clear them before exit (most functions)
15 : - Or, only static allocation + clear local variable before exit (fd_ed25519_scalar_mul_base_const_time)
16 : - Clear registers via FD_FN_SENSITIVE
17 : - C safety
18 : */
19 :
20 : FD_25519_INLINE void FD_FN_SENSITIVE
21 : fd_ed25519_scalar_radix16( char secret_e[ 64 ], /* output: 64-entry in [-8;8] */
22 : uchar const secret_a[ 32 ], /* input: 32-byte, assumes valid scalar */
23 1709355 : char * tmp_secret_carry ) {
24 1709355 : (*tmp_secret_carry) = 0;
25 :
26 56408715 : for( int i=0; i<32; i++ ) {
27 54699360 : secret_e[2*i+0] = (char)((secret_a[i] ) & 0xF);
28 54699360 : secret_e[2*i+1] = (char)((secret_a[i] >> 4) & 0xF);
29 54699360 : }
30 :
31 : /* At this point, e[0:62] are in [0:15], e[63] is in [0:7] */
32 :
33 109398720 : for( int i=0; i<63; i++ ) {
34 107689365 : secret_e[i] = (char)(secret_e[i] + (*tmp_secret_carry));
35 107689365 : (*tmp_secret_carry) = (char)((secret_e[i] + 8) >> 4);
36 107689365 : secret_e[i] = (char)(secret_e[i] - ((*tmp_secret_carry) << 4));
37 107689365 : }
38 1709355 : secret_e[63] = (char)(secret_e[63] + (*tmp_secret_carry));
39 1709355 : }
40 :
41 : /* const_time_eq returns a==b ? 1 : 0.
42 : Note: this is const time. */
43 : FD_25519_INLINE uchar FD_FN_SENSITIVE
44 875189760 : const_time_eq( const uchar secret_a, const uchar secret_b ) {
45 875189760 : return (uchar)((((uint)(secret_a ^ secret_b))-1U) >> 31);
46 875189760 : }
47 :
48 : /* fd_ed25519_table_select selects an element in the table of pre-computed
49 : points &fd_ed25519_base_point_const_time_table.
50 :
51 : Given (j, secret), j in 0..31, secret in -8..7:
52 : - if secret==0 return 0 (point at infinity)
53 : - if secret>0 return table[j][secret-1]
54 : - if secret<0 return table[j][-secret-1]
55 :
56 : Note: this is const time, equivalent to the following code:
57 : if ( secret == 0 ) {
58 : fd_ed25519_point_set_zero_precomputed( r );
59 : } else if ( secret > 0 ) {
60 : fd_ed25519_point_set( r, &fd_ed25519_base_point_const_time_table[j][secret-1] );
61 : } else {
62 : fd_ed25519_point_neg( r, &fd_ed25519_base_point_const_time_table[j][-secret-1] );
63 : }
64 : */
65 : FD_25519_INLINE void FD_FN_SENSITIVE
66 : fd_ed25519_table_select( fd_ed25519_point_t * r,
67 : fd_ed25519_point_t * tmp,
68 : int j,
69 : char secret,
70 : uchar * tmp_secret_idx,
71 109398720 : uchar * tmp_secret_sgn ) {
72 : // (*tmp_secret_sgn) = secret < 0 ? 1 : 0;
73 109398720 : (*tmp_secret_sgn) = ((uchar)(secret)) >> 7;
74 : // (*tmp_secret_idx) = (secret < 0) ? (uchar)(-secret-1) : (secret > 0) ? (uchar)secret-1 : 0xff;
75 109398720 : (*tmp_secret_idx) = (uchar)(secret - (2*(*tmp_secret_sgn)*secret) - 1); // e = e - (2*e) = -e = |e| if e<0, e - 2*0 = e = |e| o.w.
76 :
77 : /* select the point from table in const time */
78 109398720 : fd_ed25519_point_set_zero_precomputed( tmp );
79 :
80 : /* for( uchar i=0; i<8; i++ ) unrolled */
81 109398720 : fd_ed25519_point_if( r, const_time_eq( 0, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][0], tmp );
82 109398720 : fd_ed25519_point_if( tmp, const_time_eq( 1, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][1], r );
83 109398720 : fd_ed25519_point_if( r, const_time_eq( 2, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][2], tmp );
84 109398720 : fd_ed25519_point_if( tmp, const_time_eq( 3, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][3], r );
85 109398720 : fd_ed25519_point_if( r, const_time_eq( 4, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][4], tmp );
86 109398720 : fd_ed25519_point_if( tmp, const_time_eq( 5, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][5], r );
87 109398720 : fd_ed25519_point_if( r, const_time_eq( 6, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][6], tmp );
88 109398720 : fd_ed25519_point_if( tmp, const_time_eq( 7, (*tmp_secret_idx) ), &fd_ed25519_base_point_const_time_table[j][7], r );
89 :
90 : /* negate point if needed, in const time */
91 109398720 : fd_ed25519_point_neg_if( r, tmp, (*tmp_secret_sgn) );
92 109398720 : }
93 :
94 : /* fd_ed25519_scalar_mul_base_const_time computes a scalar mul of the base point
95 : in const time wrt secret_scalar, clearing stack and registers before returning.
96 : This is the main function used by fd_ed25519_sign.
97 : All sub-functions called by fd_ed25519_scalar_mul_base_const_time are expected
98 : to be static inline, have no local variable, and clear their registers. */
99 :
100 : fd_ed25519_point_t * FD_FN_SENSITIVE
101 : fd_ed25519_scalar_mul_base_const_time( fd_ed25519_point_t * r,
102 1709355 : uchar const secret_scalar[ 32 ] ) { /* can be a secret */
103 :
104 : //TODO: add input ptr to secure memory from the caller?
105 :
106 : /* memory areas that will contain (partial) secrets and will be cleared at the end */
107 1709355 : char secret_scalar_naf[64 + 2];
108 1709355 : fd_ed25519_point_t secret_tmp_points[5];
109 :
110 : /* human-readable variables */
111 1709355 : char * tmp_secret_carry = &secret_scalar_naf[64];
112 1709355 : uchar * tmp_secret_idx = (uchar *)&secret_scalar_naf[64];
113 1709355 : uchar * tmp_secret_sgn = (uchar *)&secret_scalar_naf[65];
114 1709355 : fd_ed25519_point_t * selected = &secret_tmp_points[0]; // selected point from precomput table
115 1709355 : fd_ed25519_point_t * r2 = &secret_tmp_points[1]; // temp result, to 2-unroll loop
116 1709355 : fd_ed25519_point_t * selected2 = &secret_tmp_points[2]; // temp selectedc point, to 2-unroll loop
117 1709355 : fd_ed25519_point_t * add_secure_tmp0 = &secret_tmp_points[3]; // tmp0 point for fd_ed25519_point_add_secure
118 1709355 : fd_ed25519_point_t * add_secure_tmp1 = &secret_tmp_points[4]; // tmp1 point for fd_ed25519_point_add_secure
119 :
120 1709355 : fd_ed25519_scalar_radix16( secret_scalar_naf, secret_scalar, tmp_secret_carry );
121 :
122 1709355 : fd_ed25519_point_set_zero( r );
123 29059035 : for( int i=1; i<64; i+=4 ) {
124 27349680 : fd_ed25519_table_select( selected, selected2, i/2, secret_scalar_naf[i], tmp_secret_idx, tmp_secret_sgn );
125 27349680 : fd_ed25519_point_add_secure( r2, r, selected, add_secure_tmp0, add_secure_tmp1 );
126 27349680 : fd_ed25519_table_select( selected2, selected, i/2+1, secret_scalar_naf[i+2], tmp_secret_idx, tmp_secret_sgn );
127 27349680 : fd_ed25519_point_add_secure( r, r2, selected2, add_secure_tmp0, add_secure_tmp1 );
128 27349680 : }
129 :
130 1709355 : fd_ed25519_point_dbln_secure( r, r, 4, add_secure_tmp0, add_secure_tmp1 );
131 :
132 29059035 : for( int i=0; i<64; i+=4 ) {
133 27349680 : fd_ed25519_table_select( selected, selected2, i/2, secret_scalar_naf[i], tmp_secret_idx, tmp_secret_sgn );
134 27349680 : fd_ed25519_point_add_secure( r2, r, selected, add_secure_tmp0, add_secure_tmp1 );
135 27349680 : fd_ed25519_table_select( selected2, selected, i/2+1, secret_scalar_naf[i+2], tmp_secret_idx, tmp_secret_sgn );
136 27349680 : fd_ed25519_point_add_secure( r, r2, selected2, add_secure_tmp0, add_secure_tmp1 );
137 27349680 : }
138 :
139 : /* Sanitize */
140 :
141 1709355 : fd_memset_explicit( secret_scalar_naf, 0, sizeof(secret_scalar_naf) );
142 1709355 : fd_memset_explicit( secret_tmp_points, 0, sizeof(secret_tmp_points) );
143 :
144 1709355 : return r;
145 1709355 : }
146 :
147 : #endif
|
