Line data Source code
1 : #include "fd_x25519.h"
2 : #include "fd_f25519.h"
3 :
4 : /*
5 : * Constant time primitives
6 : */
7 :
8 : static inline int FD_FN_SENSITIVE
9 103722 : fd_x25519_is_zero_const_time( uchar const point[ 32 ] ) {
10 : //TODO: this is generally done by (x)or-ing the limbs, see also RFC 7748, page 13.
11 103722 : int is_zero = 1;
12 3422826 : for( ulong i=0UL; i<32UL; i++ ) {
13 3319104 : is_zero &= ( !point[ i ] );
14 3319104 : }
15 103722 : return is_zero;
16 103722 : }
17 :
18 : #ifdef FD_HAS_S2NBIGNUM
19 : #include "fd_x25519_s2n.c"
20 : #else
21 :
22 : static inline void FD_FN_SENSITIVE
23 : fd_x25519_montgomery_ladder( fd_f25519_t * x2,
24 : fd_f25519_t * z2,
25 : fd_f25519_t const * x1,
26 : uchar const * secret_scalar ) {
27 : /* memory areas that will contain (partial) secrets and will be cleared at the end */
28 : fd_f25519_t secret_tmp_f[4];
29 : int swap = 0;
30 : int b = 0;
31 :
32 : /* human-readable variables */
33 : fd_f25519_t * x3 = &secret_tmp_f[0];
34 : fd_f25519_t * z3 = &secret_tmp_f[1];
35 : fd_f25519_t * tmp0 = &secret_tmp_f[2];
36 : fd_f25519_t * tmp1 = &secret_tmp_f[3];
37 :
38 : fd_f25519_set( x2, fd_f25519_one );
39 : fd_f25519_set( z2, fd_f25519_zero );
40 :
41 : /* use fd_f25519_add to reduce x1 mod p. this is required (we have a test). */
42 : fd_f25519_add( x3, fd_f25519_zero, x1 );
43 : fd_f25519_set( z3, fd_f25519_one );
44 :
45 : for( long pos=254UL; pos>=0; pos-- ) {
46 : b = (secret_scalar[ pos / 8L ] >> ( pos & 7L )) & 1;
47 : swap ^= b;
48 : fd_f25519_swap_if( x2, x3, swap );
49 : fd_f25519_swap_if( z2, z3, swap );
50 : swap = b;
51 :
52 : fd_f25519_sub_nr( tmp0, x3, z3 );
53 : fd_f25519_sub_nr( tmp1, x2, z2 );
54 : fd_f25519_add_nr( x2, x2, z2 );
55 : fd_f25519_add_nr( z2, x3, z3 );
56 :
57 : fd_f25519_mul2( z3, tmp0, x2,
58 : z2, z2, tmp1 );
59 : fd_f25519_sqr2( tmp0, tmp1,
60 : tmp1, x2 );
61 : fd_f25519_add_nr( x3, z3, z2 );
62 : fd_f25519_sub_nr( z2, z3, z2 );
63 : fd_f25519_mul( x2, tmp1, tmp0 );
64 : fd_f25519_sqr( z2, z2 );
65 : fd_f25519_sub_nr( tmp1, tmp1, tmp0 );
66 :
67 : fd_f25519_mul_121666( z3, tmp1 );
68 :
69 : fd_f25519_add_nr( tmp0, tmp0, z3 );
70 : fd_f25519_sqr ( x3, x3 );
71 : fd_f25519_mul2( z3, x1, z2,
72 : z2, tmp1, tmp0 );
73 : }
74 :
75 : fd_f25519_swap_if( x2, x3, swap );
76 : fd_f25519_swap_if( z2, z3, swap );
77 :
78 : /* Sanitize */
79 :
80 : fd_memzero_explicit( secret_tmp_f, sizeof(secret_tmp_f) );
81 : fd_memzero_explicit( &b, sizeof(int) );
82 : fd_memzero_explicit( &swap, sizeof(int) );
83 : }
84 :
85 : /*
86 : * X25519 Protocol
87 : */
88 :
89 : static inline void FD_FN_SENSITIVE
90 : fd_x25519_scalar_mul_const_time( uchar out[ 32 ],
91 : uchar const * secret_scalar,
92 : fd_f25519_t const * point_x ) {
93 : fd_f25519_t x2[1], z2[1];
94 :
95 : fd_x25519_montgomery_ladder( x2, z2, point_x, secret_scalar );
96 :
97 : fd_f25519_inv( z2, z2 );
98 : fd_f25519_mul( x2, x2, z2 );
99 :
100 : fd_f25519_tobytes( out, x2 );
101 : }
102 :
103 : static const uchar fd_x25519_basepoint[ 32 ] = { 9 };
104 :
105 : uchar * FD_FN_SENSITIVE
106 : fd_x25519_public( uchar self_public_key [ 32 ],
107 : uchar const self_private_key[ 32 ] ) {
108 : /* IETF RFC 7748 Section 4.1 (page 3) */
109 : return fd_x25519_exchange( self_public_key, self_private_key, fd_x25519_basepoint );
110 : }
111 :
112 : uchar * FD_FN_SENSITIVE
113 : fd_x25519_exchange( uchar shared_secret [ 32 ],
114 : uchar const self_private_key[ 32 ],
115 : uchar const peer_public_key [ 32 ] ) {
116 :
117 : /* Memory areas that will contain secrets */
118 : uchar secret_scalar[ 32UL ];
119 :
120 : /* Public local variables */
121 : fd_f25519_t peer_public_key_point_u[1];
122 :
123 : // RFC 7748 - Elliptic Curves for Security
124 : //
125 : // 5. The X25519 and X448 Functions
126 : //
127 : // The "X25519" and "X448" functions perform scalar multiplication on
128 : // the Montgomery form of the above curves. (This is used when
129 : // implementing Diffie-Hellman.) The functions take a scalar and a
130 : // u-coordinate as inputs and produce a u-coordinate as output.
131 : // Although the functions work internally with integers, the inputs and
132 : // outputs are 32-byte strings (for X25519) or 56-byte strings (for
133 : // X448) and this specification defines their encoding.
134 :
135 : // The u-coordinates are elements of the underlying field GF(2^255 - 19)
136 : // or GF(2^448 - 2^224 - 1) and are encoded as an array of bytes, u, in
137 : // little-endian order such that u[0] + 256*u[1] + 256^2*u[2] + ... +
138 : // 256^(n-1)*u[n-1] is congruent to the value modulo p and u[n-1] is
139 : // minimal. When receiving such an array, implementations of X25519
140 : // (but not X448) MUST mask the most significant bit in the final byte.
141 : // This is done to preserve compatibility with point formats that
142 : // reserve the sign bit for use in other protocols and to increase
143 : // resistance to implementation fingerprinting.
144 :
145 : // Implementations MUST accept non-canonical values and process them as
146 : // if they had been reduced modulo the field prime. The non-canonical
147 : // values are 2^255 - 19 through 2^255 - 1 for X25519 and 2^448 - 2^224
148 : // - 1 through 2^448 - 1 for X448.
149 :
150 : /* From the text above:
151 : 1. When receiving such an array, implementations of X25519 [...]
152 : MUST mask the most significant bit in the final byte
153 : >> this is done by fd_f25519_frombytes
154 : 2. Implementations MUST accept non-canonical values
155 : >> no extra check needed */
156 : fd_f25519_frombytes( peer_public_key_point_u, peer_public_key );
157 :
158 : // Scalars are assumed to be randomly generated bytes. For X25519, in
159 : // order to decode 32 random bytes as an integer scalar, set the three
160 : // least significant bits of the first byte and the most significant bit
161 : // of the last to zero, set the second most significant bit of the last
162 : // byte to 1 and, finally, decode as little-endian. This means that the
163 : // resulting integer is of the form 2^254 plus eight times a value
164 : // between 0 and 2^251 - 1 (inclusive). Likewise, for X448, set the two
165 : // least significant bits of the first byte to 0, and the most
166 : // significant bit of the last byte to 1. This means that the resulting
167 : // integer is of the form 2^447 plus four times a value between 0 and
168 : // 2^445 - 1 (inclusive).
169 :
170 : /* decodeScalar25519
171 : note: e need to copy the private key, because we need to sanitize it. */
172 : memcpy( secret_scalar, self_private_key, 32UL );
173 : secret_scalar[ 0] &= (uchar)0xF8;
174 : secret_scalar[31] &= (uchar)0x7F;
175 : secret_scalar[31] |= (uchar)0x40;
176 :
177 : fd_x25519_scalar_mul_const_time( shared_secret, secret_scalar, peer_public_key_point_u );
178 :
179 : /* Sanitize */
180 : fd_memzero_explicit( secret_scalar, 32UL );
181 :
182 : /* Reject low order points */
183 : if( FD_UNLIKELY( fd_x25519_is_zero_const_time( shared_secret ) ) ) {
184 : return NULL;
185 : }
186 :
187 : return shared_secret;
188 : }
189 :
190 : #endif /* FD_HAS_S2NBIGNUM */
|
