Line data Source code
1 : #include "fd_ed25519.h"
2 : #include "fd_curve25519.h"
3 :
4 : /* Backend choice: AVX512 (zen4+), then S2N, then REF (no s2n) */
5 : #if defined(FD_HAS_S2NBIGNUM) && !FD_HAS_AVX512
6 : #define FD_ED25519_S2N 1
7 : #else
8 : #define FD_ED25519_S2N 0
9 : #endif
10 :
11 : #if FD_ED25519_S2N
12 : #include "fd_ed25519_s2n.c"
13 : #else
14 :
15 : /* The 2 functions below:
16 : - fd_ed25519_scalar_mul_base_tobytes (sensitive, const time)
17 : - fd_ed25519_verify_equation (var time)
18 : are a convenient interface to switch between our original
19 : implementations and s2n-bignum interface. */
20 :
21 : /* fd_ed25519_scalar_mul_base_tobytes writes the RFC 8032 encoding of
22 : [n]B to out. n can be a secret. */
23 : static inline void FD_FN_SENSITIVE
24 : fd_ed25519_scalar_mul_base_tobytes( uchar out[ 32 ],
25 122619 : uchar const n[ 32 ] ) {
26 122619 : fd_ed25519_point_t nB[1];
27 122619 : fd_ed25519_scalar_mul_base_const_time( nB, n );
28 122619 : fd_ed25519_point_tobytes( out, nB );
29 122619 : }
30 :
31 : /* fd_ed25519_verify_equation returns 1 iff [S]B == R + [k]A,
32 : computed as [k](-A) + [S]B == R. A and R must be affine (Z==1).
33 : A is clobbered. k and S are 32-byte little-endian scalars, S < L. */
34 : static inline int
35 : fd_ed25519_verify_equation( uchar const k[ 32 ],
36 : fd_ed25519_point_t * A,
37 : uchar const S[ 32 ],
38 36673 : fd_ed25519_point_t const * R ) {
39 36673 : fd_ed25519_point_t Rcmp[1];
40 36673 : fd_ed25519_point_neg( A, A );
41 36673 : fd_ed25519_double_scalar_mul_base( Rcmp, k, A, S );
42 36673 : return fd_ed25519_point_eq_z1( Rcmp, R );
43 36673 : }
44 :
45 : #endif
46 :
47 : uchar * FD_FN_SENSITIVE
48 : fd_ed25519_public_from_private( uchar public_key [ static 32 ],
49 : uchar const private_key[ static 32 ],
50 15777 : fd_sha512_t * sha ) {
51 :
52 : // RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
53 : //
54 : // 5.1.5. Key Generation
55 : //
56 : // The private key is 32 octets (256 bits, corresponding to b) of
57 : // cryptographically secure random data. See [RFC4086] for a discussion
58 : // about randomness.
59 : //
60 : // The 32-byte public key is generated by the following steps.
61 : //
62 : // 1. Hash the 32-byte private key using SHA-512, storing the digest in
63 : // a 64-octet large buffer, denoted h. Only the lower 32 bytes are
64 : // used for generating the public key.
65 :
66 15777 : uchar s[ FD_SHA512_HASH_SZ ];
67 15777 : fd_sha512_fini( fd_sha512_append( fd_sha512_init( sha ), private_key, 32UL ), s );
68 :
69 : // 2. Prune the buffer: The lowest three bits of the first octet are
70 : // cleared, the highest bit of the last octet is cleared, and the
71 : // second highest bit of the last octet is set.
72 :
73 15777 : s[ 0] &= (uchar)0xF8;
74 15777 : s[31] &= (uchar)0x7F;
75 15777 : s[31] |= (uchar)0x40;
76 :
77 : // 3. Interpret the buffer as the little-endian integer, forming a
78 : // secret scalar s. Perform a fixed-base scalar multiplication
79 : // [s]B.
80 :
81 : // 4. The public key A is the encoding of the point [s]B. First,
82 : // encode the y-coordinate (in the range 0 <= y < p) as a little-
83 : // endian string of 32 octets. The most significant bit of the
84 : // final octet is always zero. To form the encoding of the point
85 : // [s]B, copy the least significant bit of the x coordinate to the
86 : // most significant bit of the final octet. The result is the
87 : // public key.
88 :
89 15777 : fd_ed25519_scalar_mul_base_tobytes( public_key, s );
90 :
91 : /* Sanitize */
92 :
93 15777 : fd_memzero_explicit( s, FD_SHA512_HASH_SZ );
94 15777 : fd_sha512_clear( sha );
95 :
96 15777 : return public_key;
97 15777 : }
98 :
99 : uchar * FD_FN_SENSITIVE
100 : fd_ed25519_sign( uchar sig[ static 64 ],
101 : uchar const msg[], /* msg_sz */
102 : ulong msg_sz,
103 : uchar const public_key[ static 32 ],
104 : uchar const private_key[ static 32 ],
105 352178 : fd_sha512_t * sha ) {
106 :
107 : // RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
108 : //
109 : // 5.1.6. Sign
110 : //
111 : // The inputs to the signing procedure is the private key, a 32-octet
112 : // string, and a message M of arbitrary size. For Ed25519ctx and
113 : // Ed25519ph, there is additionally a context C of at most 255 octets
114 : // and a flag F, 0 for Ed25519ctx and 1 for Ed25519ph.
115 : //
116 : // 1. Hash the private key, 32 octets, using SHA-512. Let h denote the
117 : // resulting digest. Construct the secret scalar s from the first
118 : // half of the digest, and the corresponding public key A, as
119 : // described in the previous section. Let prefix denote the second
120 : // half of the hash digest, h[32],...,h[63].
121 :
122 352178 : uchar s[ FD_SHA512_HASH_SZ ];
123 352178 : fd_sha512_fini( fd_sha512_append( fd_sha512_init( sha ), private_key, 32UL ), s );
124 352178 : s[ 0] &= (uchar)0xF8;
125 352178 : s[31] &= (uchar)0x7F;
126 352178 : s[31] |= (uchar)0x40;
127 352178 : uchar * h = s + 32;
128 :
129 : /* public_key is an input */
130 :
131 : // 2. Compute SHA-512(dom2(F, C) || prefix || PH(M)), where M is the
132 : // message to be signed. Interpret the 64-octet digest as a little-
133 : // endian integer r.
134 :
135 352178 : uchar r[ FD_SHA512_HASH_SZ ];
136 352178 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ), h, 32UL ), msg, msg_sz ), r );
137 :
138 : // 3. Compute the point [r]B. For efficiency, do this by first
139 : // reducing r modulo L, the group order of B. Let the string R be
140 : // the encoding of this point.
141 :
142 352178 : fd_curve25519_scalar_reduce( r, r ); /* reduce r mod L */
143 352178 : fd_ed25519_scalar_mul_base_tobytes( sig, r ); /* R = [r]B */
144 :
145 : // 4. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
146 : // 64-octet digest as a little-endian integer k.
147 :
148 : /* note: all inputs to k are public values */
149 352178 : uchar k[ FD_SHA512_HASH_SZ ];
150 352178 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ),
151 352178 : sig, 32UL ), public_key, 32UL ), msg, msg_sz ), k );
152 :
153 : // 5. Compute S = (r + k * s) mod L. For efficiency, again reduce k
154 : // modulo L first.
155 : //
156 : // 6. Form the signature of the concatenation of R (32 octets) and the
157 : // little-endian encoding of S (32 octets; the three most
158 : // significant bits of the final octet are always zero).
159 :
160 352178 : fd_curve25519_scalar_reduce( k, k );
161 352178 : fd_curve25519_scalar_muladd( ((uchar *)sig)+32, k, s, r );
162 :
163 : /* Sanitize */
164 :
165 : /* note: no need to sanitize k as all inputs to k are public values */
166 352178 : fd_memzero_explicit( s, FD_SHA512_HASH_SZ );
167 352178 : fd_memzero_explicit( r, FD_SHA512_HASH_SZ );
168 352178 : fd_sha512_clear( sha );
169 :
170 352178 : return sig;
171 352178 : }
172 :
173 : uchar * FD_FN_SENSITIVE
174 : fd_ed25519_sign_batch8( uchar sig[], /* n*64 */
175 : uchar const * const msg[], /* n */
176 : ulong const msg_sz[], /* n */
177 : uchar const public_key[ 32 ],
178 : uchar const private_key[ 32 ],
179 48 : ulong n ) { /* in [1,8] */
180 :
181 48 : FD_TEST( 0UL<n && n<=8UL );
182 48 : if( FD_UNLIKELY( n==1UL ) ) {
183 6 : fd_sha512_t sha[1];
184 6 : return fd_ed25519_sign( sig, msg[0], msg_sz[0], public_key, private_key, sha );
185 6 : }
186 :
187 252 : for( ulong i=0UL; i<n; i++ ) FD_TEST( msg_sz[i]<=FD_ED25519_SIGN_BATCH_MSG_MAX );
188 :
189 42 : fd_sha512_batch_t batch[1];
190 42 : fd_sha512_batch_t * b;
191 :
192 : /* Expand the private keys: s[i] = SHA-512(private_key[i]), clamped.
193 : Lower 32 bytes are the secret scalar, upper 32 the prefix. */
194 :
195 42 : uchar s[ 8UL ][ FD_SHA512_HASH_SZ ] __attribute__((aligned(64)));
196 42 : b = fd_sha512_batch_init( batch );
197 252 : for( ulong i=0UL; i<n; i++ ) b = fd_sha512_batch_add( b, private_key, 32UL, s[i] );
198 42 : fd_sha512_batch_fini( b );
199 252 : for( ulong i=0UL; i<n; i++ ) {
200 210 : s[i][ 0] &= (uchar)0xF8;
201 210 : s[i][31] &= (uchar)0x7F;
202 210 : s[i][31] |= (uchar)0x40;
203 210 : }
204 :
205 : /* r[i] = SHA-512(prefix[i] || msg[i]). The batch API hashes one
206 : contiguous region per message, so the inputs are staged in buf,
207 : laid out as R[i] || A[i] || msg[i]: the message is parked once at
208 : buf[i]+64 for both hashes, the r hash reads from buf[i]+32 with
209 : the secret prefix in the A slot, and the k hash below overwrites
210 : the prefix with the public A. */
211 :
212 42 : static FD_TL uchar buf[ 8UL ][ 64UL+FD_ED25519_SIGN_BATCH_MSG_MAX ] __attribute__((aligned(64)));
213 42 : uchar r[ 8UL ][ FD_SHA512_HASH_SZ ] __attribute__((aligned(64)));
214 42 : b = fd_sha512_batch_init( batch );
215 252 : for( ulong i=0UL; i<n; i++ ) {
216 210 : memcpy( buf[i]+32UL, s[i]+32, 32UL );
217 210 : if( FD_LIKELY( msg_sz[i] ) ) memcpy( buf[i]+64UL, msg[i], msg_sz[i] );
218 210 : b = fd_sha512_batch_add( b, buf[i]+32UL, 32UL+msg_sz[i], r[i] );
219 210 : }
220 42 : fd_sha512_batch_fini( b );
221 :
222 : /* R[i] = [r[i] mod L]B */
223 :
224 42 : uchar R_bytes[ 8UL*32UL ];
225 28 : #if FD_ED25519_S2N
226 : /* s2n serial is faster than non-s2n batch */
227 168 : for( ulong i=0UL; i<n; i++ ) {
228 140 : fd_curve25519_scalar_reduce( r[i], r[i] );
229 140 : fd_ed25519_scalar_mul_base_tobytes( R_bytes+32UL*i, r[i] );
230 140 : }
231 : #else
232 : /* one field inversion shared across the n encodings */
233 14 : fd_ed25519_point_t R[ 8UL ];
234 84 : for( ulong i=0UL; i<n; i++ ) {
235 70 : fd_curve25519_scalar_reduce( r[i], r[i] );
236 70 : fd_ed25519_scalar_mul_base_const_time( &R[i], r[i] );
237 70 : }
238 14 : fd_ed25519_point_tobytes_batch8( R_bytes, R, n );
239 14 : #endif
240 :
241 : /* k[i] = SHA-512(R[i] || A[i] || msg[i]); all inputs are public */
242 :
243 42 : uchar k[ 8UL ][ FD_SHA512_HASH_SZ ] __attribute__((aligned(64)));
244 42 : b = fd_sha512_batch_init( batch );
245 252 : for( ulong i=0UL; i<n; i++ ) {
246 210 : memcpy( sig+64UL*i, R_bytes+32UL*i, 32UL );
247 210 : memcpy( buf[i], R_bytes+32UL*i, 32UL );
248 210 : memcpy( buf[i]+32UL, public_key, 32UL );
249 210 : b = fd_sha512_batch_add( b, buf[i], 64UL+msg_sz[i], k[i] );
250 210 : }
251 42 : fd_sha512_batch_fini( b );
252 :
253 : /* S[i] = (r[i] + k[i]*s[i]) mod L */
254 :
255 252 : for( ulong i=0UL; i<n; i++ ) {
256 210 : fd_curve25519_scalar_reduce( k[i], k[i] );
257 210 : fd_curve25519_scalar_muladd( sig+64UL*i+32UL, k[i], s[i], r[i] );
258 210 : }
259 :
260 : /* Sanitize */
261 :
262 42 : fd_memzero_explicit( s, n*FD_SHA512_HASH_SZ );
263 42 : fd_memzero_explicit( r, n*FD_SHA512_HASH_SZ );
264 :
265 42 : return sig;
266 42 : }
267 :
268 : int
269 : fd_ed25519_verify( uchar const msg[], /* msg_sz */
270 : ulong msg_sz,
271 : uchar const sig[ static 64 ],
272 : uchar const public_key[ static 32 ],
273 100875 : fd_sha512_t * sha ) {
274 :
275 : // RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
276 : //
277 : // 5.1.7. Verify
278 : //
279 : // 1. To verify a signature on a message M using public key A, with F
280 : // being 0 for Ed25519ctx, 1 for Ed25519ph, and if Ed25519ctx or
281 : // Ed25519ph is being used, C being the context, first split the
282 : // signature into two 32-octet halves. Decode the first half as a
283 : // point R, and the second half as an integer S, in the range
284 : // 0 <= s < L. Decode the public key A as point A'. If any of the
285 : // decodings fail (including S being out of range), the signature is
286 : // invalid.
287 :
288 100875 : uchar const * r = sig;
289 100875 : uchar const * S = sig + 32;
290 :
291 : /* Check scalar s */
292 100875 : if( FD_UNLIKELY( !fd_curve25519_scalar_validate( S ) )) {
293 6091 : return FD_ED25519_ERR_SIG;
294 6091 : }
295 :
296 : /* Decompress public_key and point r, concurrently */
297 94784 : fd_ed25519_point_t Aprime[1], R[1];
298 94784 : int res = fd_ed25519_point_frombytes_2x( Aprime, public_key, R, r );
299 :
300 : /* Check public key and point r:
301 : 1. both public key and point r decompress successfully (RFC)
302 : 2. both public key and point r are small order (verify_strict)
303 :
304 : There's another check that we currently do NOT enforce:
305 : whether public key and point r are canonical.
306 : Dalek 2.x (currently used by Agave) does NOT do any check.
307 : Dalek 4.x checks that the point r is canonical, but accepts
308 : a non canonical public key.
309 :
310 : Note: I couldn't find any test with non canonical points
311 : (all tests are non canonical + low order, that are excluded by
312 : the verify_strict rule). The reason is that to write such a
313 : test one needs to know the discrete log of a non canonical point.
314 :
315 : The following code checks that r is canonical (we can add it
316 : in when Agave switches to dalek 4.x).
317 :
318 : uchar compressed[ 32 ];
319 : fd_ed25519_affine_tobytes( compressed, R );
320 : if( FD_UNLIKELY( !fd_memeq( compressed, r, 32 ) ) ) {
321 : return FD_ED25519_ERR_SIG;
322 : }
323 : */
324 94784 : if( FD_UNLIKELY( res ) ) {
325 16245 : return res == -1 ? FD_ED25519_ERR_PUBKEY : FD_ED25519_ERR_SIG;
326 16245 : }
327 78539 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(Aprime) ) ) {
328 5367 : return FD_ED25519_ERR_PUBKEY;
329 5367 : }
330 73172 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(R) ) ) {
331 5715 : return FD_ED25519_ERR_SIG;
332 5715 : }
333 :
334 : // 2. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
335 : // 64-octet digest as a little-endian integer k.
336 :
337 67457 : uchar k[ 64 ];
338 67457 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ),
339 67457 : r, 32UL ), public_key, 32UL ), msg, msg_sz ), k );
340 67457 : fd_curve25519_scalar_reduce( k, k );
341 :
342 : // 3. Check the group equation [8][S]B = [8]R + [8][k]A'. It's
343 : // sufficient, but not required, to instead check [S]B = R + [k]A'.
344 :
345 : /* Compute R = [k](-A') + [S]B, with B base point.
346 : Note: this is not the same as R = [-k]A' + [S]B, because the order
347 : of A' is 8l (computing -k mod 8l would work).
348 :
349 : Compare R (computed) and R from signature.
350 : Note: many implementations do this comparison by compressing Rcmd,
351 : and compare it against the r buf as it appears in the signature.
352 : This implicitly prevents non-canonical R.
353 : In our implementation we compare the points (see the comment
354 : above on "Check public key and point r" for details). */
355 67457 : if( FD_LIKELY( fd_ed25519_verify_equation( k, Aprime, S, R ) ) ) {
356 31737 : return FD_ED25519_SUCCESS;
357 31737 : }
358 35720 : return FD_ED25519_ERR_MSG;
359 67457 : }
360 :
361 : int fd_ed25519_verify_batch_single_msg( uchar const msg[], /* msg_sz */
362 : ulong const msg_sz,
363 : uchar const signatures[ static 64 ], /* 64 * batch_sz */
364 : uchar const pubkeys[ static 32 ], /* 32 * batch_sz */
365 : fd_sha512_t * shas[ 1 ], /* batch_sz */
366 14469 : uchar const batch_sz ) {
367 14469 : #define MAX 16
368 14469 : if( FD_UNLIKELY( batch_sz == 0 || batch_sz > MAX ) ) {
369 135 : return FD_ED25519_ERR_SIG;
370 135 : }
371 :
372 : #if 0
373 : /* Naive */
374 : for( uchar i=0; i<batch_sz; i++ ) {
375 : int res = fd_ed25519_verify( msg, msg_sz, &signatures[ i*64 ], &pubkeys[ i*32 ], shas[0] );
376 : if( FD_UNLIKELY( res != FD_ED25519_SUCCESS ) ) {
377 : return res;
378 : }
379 : }
380 : return FD_ED25519_SUCCESS;
381 : #else
382 :
383 14334 : fd_ed25519_point_t R [MAX];
384 14334 : fd_ed25519_point_t Aprime[MAX];
385 14334 : uchar k [MAX * 32];
386 :
387 : /* The first batch_sz points are the R_j, the last are A'_j.
388 : Scalars will be stored accordingly. */
389 :
390 : /* First, we validate scalars, decompress public keys and points R_j,
391 : check low order points, and compute k_j.
392 : TODO: optimize, this is 20% of the total time. */
393 82301 : for( int j=0; j<batch_sz; j++ ) {
394 :
395 72885 : uchar const * r = signatures + 64*j;
396 72885 : uchar const * S = signatures + 32 + 64*j;
397 72885 : uchar const * public_key = pubkeys + 32*j;
398 :
399 : /* Check scalar s */
400 72885 : if( FD_UNLIKELY( !fd_curve25519_scalar_validate( S ) )) {
401 1400 : return FD_ED25519_ERR_SIG;
402 1400 : }
403 :
404 : /* Decompress public_key and point r, concurrently */
405 71485 : int res = fd_ed25519_point_frombytes_2x( &Aprime[j], public_key, &R[j], r );
406 :
407 : /* Check public key and point r */
408 71485 : if( FD_UNLIKELY( res ) ) {
409 2681 : return res == -1 ? FD_ED25519_ERR_PUBKEY : FD_ED25519_ERR_SIG;
410 2681 : }
411 68804 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(&Aprime[j]) ) ) {
412 570 : return FD_ED25519_ERR_PUBKEY;
413 570 : }
414 68234 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(&R[j]) ) ) {
415 267 : return FD_ED25519_ERR_SIG;
416 267 : }
417 :
418 : /* Compute scalars k_j */
419 67967 : uchar _k[ 64 ];
420 67967 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( shas[j] ),
421 67967 : r, 32UL ), public_key, 32UL ), msg, msg_sz ), _k );
422 67967 : fd_curve25519_scalar_reduce( &k[32*j], _k );
423 67967 : }
424 :
425 47880 : for( uchar j=0; j<batch_sz; j++ ) {
426 41790 : uchar const * S = signatures + 32 + 64*j;
427 41790 : if( FD_UNLIKELY( !fd_ed25519_verify_equation( &k[32*j], &Aprime[j], S, &R[j] ) ) ) {
428 3326 : return FD_ED25519_ERR_MSG;
429 3326 : }
430 41790 : }
431 6090 : return FD_ED25519_SUCCESS;
432 9416 : #endif
433 9416 : #undef MAX
434 9416 : }
435 :
436 : char const *
437 0 : fd_ed25519_strerror( int err ) {
438 0 : switch( err ) {
439 0 : case FD_ED25519_SUCCESS: return "success";
440 0 : case FD_ED25519_ERR_SIG: return "bad signature";
441 0 : case FD_ED25519_ERR_PUBKEY: return "bad public key";
442 0 : case FD_ED25519_ERR_MSG: return "bad message";
443 0 : default: break;
444 0 : }
445 0 : return "unknown";
446 0 : }
|
