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