Line data Source code
1 : #include "fd_ed25519.h"
2 : #include "fd_curve25519.h"
3 :
4 : uchar * FD_FN_SENSITIVE
5 : fd_ed25519_public_from_private( uchar public_key [ static 32 ],
6 : uchar const private_key[ static 32 ],
7 32361 : fd_sha512_t * sha ) {
8 :
9 : // RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
10 : //
11 : // 5.1.5. Key Generation
12 : //
13 : // The private key is 32 octets (256 bits, corresponding to b) of
14 : // cryptographically secure random data. See [RFC4086] for a discussion
15 : // about randomness.
16 : //
17 : // The 32-byte public key is generated by the following steps.
18 : //
19 : // 1. Hash the 32-byte private key using SHA-512, storing the digest in
20 : // a 64-octet large buffer, denoted h. Only the lower 32 bytes are
21 : // used for generating the public key.
22 :
23 32361 : uchar s[ FD_SHA512_HASH_SZ ];
24 32361 : fd_sha512_fini( fd_sha512_append( fd_sha512_init( sha ), private_key, 32UL ), s );
25 :
26 : // 2. Prune the buffer: The lowest three bits of the first octet are
27 : // cleared, the highest bit of the last octet is cleared, and the
28 : // second highest bit of the last octet is set.
29 :
30 32361 : s[ 0] &= (uchar)0xF8;
31 32361 : s[31] &= (uchar)0x7F;
32 32361 : s[31] |= (uchar)0x40;
33 :
34 : // 3. Interpret the buffer as the little-endian integer, forming a
35 : // secret scalar s. Perform a fixed-base scalar multiplication
36 : // [s]B.
37 :
38 32361 : fd_ed25519_point_t sB[1];
39 32361 : fd_ed25519_scalar_mul_base_const_time( sB, s );
40 :
41 : // 4. The public key A is the encoding of the point [s]B. First,
42 : // encode the y-coordinate (in the range 0 <= y < p) as a little-
43 : // endian string of 32 octets. The most significant bit of the
44 : // final octet is always zero. To form the encoding of the point
45 : // [s]B, copy the least significant bit of the x coordinate to the
46 : // most significant bit of the final octet. The result is the
47 : // public key.
48 :
49 32361 : fd_ed25519_point_tobytes( public_key, sB );
50 :
51 : /* Sanitize */
52 :
53 32361 : fd_memset_explicit( s, 0, FD_SHA512_HASH_SZ );
54 32361 : fd_sha512_clear( sha );
55 :
56 32361 : return public_key;
57 32361 : }
58 :
59 : uchar * FD_FN_SENSITIVE
60 : fd_ed25519_sign( uchar sig[ static 64 ],
61 : uchar const msg[], /* msg_sz */
62 : ulong msg_sz,
63 : uchar const public_key[ static 32 ],
64 : uchar const private_key[ static 32 ],
65 1727586 : fd_sha512_t * sha ) {
66 :
67 : // RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
68 : //
69 : // 5.1.6. Sign
70 : //
71 : // The inputs to the signing procedure is the private key, a 32-octet
72 : // string, and a message M of arbitrary size. For Ed25519ctx and
73 : // Ed25519ph, there is additionally a context C of at most 255 octets
74 : // and a flag F, 0 for Ed25519ctx and 1 for Ed25519ph.
75 : //
76 : // 1. Hash the private key, 32 octets, using SHA-512. Let h denote the
77 : // resulting digest. Construct the secret scalar s from the first
78 : // half of the digest, and the corresponding public key A, as
79 : // described in the previous section. Let prefix denote the second
80 : // half of the hash digest, h[32],...,h[63].
81 :
82 1727586 : uchar s[ FD_SHA512_HASH_SZ ];
83 1727586 : fd_sha512_fini( fd_sha512_append( fd_sha512_init( sha ), private_key, 32UL ), s );
84 1727586 : s[ 0] &= (uchar)0xF8;
85 1727586 : s[31] &= (uchar)0x7F;
86 1727586 : s[31] |= (uchar)0x40;
87 1727586 : uchar * h = s + 32;
88 :
89 : /* public_key is an input */
90 :
91 : // 2. Compute SHA-512(dom2(F, C) || prefix || PH(M)), where M is the
92 : // message to be signed. Interpret the 64-octet digest as a little-
93 : // endian integer r.
94 :
95 1727586 : uchar r[ FD_SHA512_HASH_SZ ];
96 1727586 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ), h, 32UL ), msg, msg_sz ), r );
97 :
98 : // 3. Compute the point [r]B. For efficiency, do this by first
99 : // reducing r modulo L, the group order of B. Let the string R be
100 : // the encoding of this point.
101 :
102 1727586 : fd_curve25519_scalar_reduce( r, r ); /* reduce r mod L */
103 1727586 : fd_ed25519_point_t R[1];
104 1727586 : fd_ed25519_scalar_mul_base_const_time( R, r ); /* R = [r]B */
105 1727586 : fd_ed25519_point_tobytes( sig, R );
106 :
107 : // 4. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
108 : // 64-octet digest as a little-endian integer k.
109 :
110 : /* note: all inputs to k are public values */
111 1727586 : uchar k[ FD_SHA512_HASH_SZ ];
112 1727586 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ),
113 1727586 : sig, 32UL ), public_key, 32UL ), msg, msg_sz ), k );
114 :
115 : // 5. Compute S = (r + k * s) mod L. For efficiency, again reduce k
116 : // modulo L first.
117 : //
118 : // 6. Form the signature of the concatenation of R (32 octets) and the
119 : // little-endian encoding of S (32 octets; the three most
120 : // significant bits of the final octet are always zero).
121 :
122 1727586 : fd_curve25519_scalar_reduce( k, k );
123 1727586 : fd_curve25519_scalar_muladd( ((uchar *)sig)+32, k, s, r );
124 :
125 : /* Sanitize */
126 :
127 : /* note: no need to sanitize k as all inputs to k are public values */
128 1727586 : fd_memset_explicit( s, 0, FD_SHA512_HASH_SZ );
129 1727586 : fd_memset_explicit( r, 0, FD_SHA512_HASH_SZ );
130 1727586 : fd_sha512_clear( sha );
131 :
132 1727586 : return sig;
133 1727586 : }
134 :
135 : int
136 : fd_ed25519_verify( uchar const msg[], /* msg_sz */
137 : ulong msg_sz,
138 : uchar const sig[ static 64 ],
139 : uchar const public_key[ static 32 ],
140 975420 : fd_sha512_t * sha ) {
141 :
142 : // RFC 8032 - Edwards-Curve Digital Signature Algorithm (EdDSA)
143 : //
144 : // 5.1.7. Verify
145 : //
146 : // 1. To verify a signature on a message M using public key A, with F
147 : // being 0 for Ed25519ctx, 1 for Ed25519ph, and if Ed25519ctx or
148 : // Ed25519ph is being used, C being the context, first split the
149 : // signature into two 32-octet halves. Decode the first half as a
150 : // point R, and the second half as an integer S, in the range
151 : // 0 <= s < L. Decode the public key A as point A'. If any of the
152 : // decodings fail (including S being out of range), the signature is
153 : // invalid.
154 :
155 975420 : uchar const * r = sig;
156 975420 : uchar const * S = sig + 32;
157 :
158 : /* Check scalar s */
159 975420 : if( FD_UNLIKELY( !fd_curve25519_scalar_validate( S ) )) {
160 217547 : return FD_ED25519_ERR_SIG;
161 217547 : }
162 :
163 : /* Decompress public_key and point r, concurrently */
164 757873 : fd_ed25519_point_t Aprime[1], R[1];
165 757873 : int res = fd_ed25519_point_frombytes_2x( Aprime, public_key, R, r );
166 :
167 : /* Check public key and point r:
168 : 1. both public key and point r decompress successfully (RFC)
169 : 2. both public key and point r are small order (verify_strict)
170 :
171 : There's another check that we currently do NOT enforce:
172 : whether public key and point r are canonical.
173 : Dalek 2.x (currently used by Agave) does NOT do any check.
174 : Dalek 4.x checks that the point r is canonical, but accepts
175 : a non canonical public key.
176 :
177 : Note: I couldn't find any test with non canonical points
178 : (all tests are non canonical + low order, that are excluded by
179 : the verify_strict rule). The reason is that to write such a
180 : test one needs to know the discrete log of a non canonical point.
181 :
182 : The following code checks that r is canonical (we can add it
183 : in when Agave switches to dalek 4.x).
184 :
185 : uchar compressed[ 32 ];
186 : fd_ed25519_affine_tobytes( compressed, R );
187 : if( FD_UNLIKELY( !fd_memeq( compressed, r, 32 ) ) ) {
188 : return FD_ED25519_ERR_SIG;
189 : }
190 : */
191 757873 : if( FD_UNLIKELY( res ) ) {
192 132438 : return res == 1 ? FD_ED25519_ERR_PUBKEY : FD_ED25519_ERR_SIG;
193 132438 : }
194 625435 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(Aprime) ) ) {
195 3358 : return FD_ED25519_ERR_PUBKEY;
196 3358 : }
197 622077 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(R) ) ) {
198 1575 : return FD_ED25519_ERR_SIG;
199 1575 : }
200 :
201 : // 2. Compute SHA512(dom2(F, C) || R || A || PH(M)), and interpret the
202 : // 64-octet digest as a little-endian integer k.
203 :
204 620502 : uchar k[ 64 ];
205 620502 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( sha ),
206 620502 : r, 32UL ), public_key, 32UL ), msg, msg_sz ), k );
207 620502 : fd_curve25519_scalar_reduce( k, k );
208 :
209 : // 3. Check the group equation [8][S]B = [8]R + [8][k]A'. It's
210 : // sufficient, but not required, to instead check [S]B = R + [k]A'.
211 :
212 : /* Compute R = [k](-A') + [S]B, with B base point.
213 : Note: this is not the same as R = [-k]A' + [S]B, because the order
214 : of A' is 8l (computing -k mod 8l would work). */
215 620502 : fd_ed25519_point_t Rcmp[1];
216 620502 : fd_ed25519_point_neg( Aprime, Aprime );
217 620502 : fd_ed25519_double_scalar_mul_base( Rcmp, k, Aprime, S );
218 :
219 : /* Compare R (computed) and R from signature.
220 : Note: many implementations do this comparison by compressing Rcmd,
221 : and compare it against the r buf as it appears in the signature.
222 : This implicitly prevents non-canonical R.
223 : However this also hides a field inv to compress Rcmp.
224 : In our implementation we compare the points (see the comment
225 : above on "Check public key and point r" for details). */
226 620502 : if( FD_LIKELY( fd_ed25519_point_eq_z1( Rcmp, R ) ) ) {
227 249066 : return FD_ED25519_SUCCESS;
228 249066 : }
229 371436 : return FD_ED25519_ERR_MSG;
230 620502 : }
231 :
232 : int fd_ed25519_verify_batch_single_msg( uchar const msg[], /* msg_sz */
233 : ulong const msg_sz,
234 : uchar const signatures[ static 64 ], /* 64 * batch_sz */
235 : uchar const pubkeys[ static 32 ], /* 32 * batch_sz */
236 : fd_sha512_t * shas[ 1 ], /* batch_sz */
237 59412 : uchar const batch_sz ) {
238 59412 : #define MAX 16
239 59412 : if( FD_UNLIKELY( batch_sz == 0 || batch_sz > MAX ) ) {
240 0 : return FD_ED25519_ERR_SIG;
241 0 : }
242 :
243 : #if 0
244 : /* Naive */
245 : for( uchar i=0; i<batch_sz; i++ ) {
246 : int res = fd_ed25519_verify( msg, msg_sz, &signatures[ i*64 ], &pubkeys[ i*32 ], shas[0] );
247 : if( FD_UNLIKELY( res != FD_ED25519_SUCCESS ) ) {
248 : return res;
249 : }
250 : }
251 : return FD_ED25519_SUCCESS;
252 : #else
253 :
254 59412 : fd_ed25519_point_t R [MAX];
255 59412 : fd_ed25519_point_t Aprime[MAX];
256 59412 : uchar k [MAX * 32];
257 :
258 : /* The first batch_sz points are the R_j, the last are A'_j.
259 : Scalars will be stored accordingly. */
260 :
261 : /* First, we validate scalars, decompress public keys and points R_j,
262 : check low order points, and compute k_j.
263 : TODO: optimize, this is 20% of the total time. */
264 210303 : for( int j=0; j<batch_sz; j++ ) {
265 :
266 151455 : uchar const * r = signatures + 64*j;
267 151455 : uchar const * S = signatures + 32 + 64*j;
268 151455 : uchar const * public_key = pubkeys + 32*j;
269 :
270 : /* Check scalar s */
271 151455 : if( FD_UNLIKELY( !fd_curve25519_scalar_validate( S ) )) {
272 6 : return FD_ED25519_ERR_SIG;
273 6 : }
274 :
275 : /* Decompress public_key and point r, concurrently */
276 151449 : int res = fd_ed25519_point_frombytes_2x( &Aprime[j], public_key, &R[j], r );
277 :
278 : /* Check public key and point r */
279 151449 : if( FD_UNLIKELY( res ) ) {
280 69 : return res == 1 ? FD_ED25519_ERR_PUBKEY : FD_ED25519_ERR_SIG;
281 69 : }
282 151380 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(&Aprime[j]) ) ) {
283 331 : return FD_ED25519_ERR_PUBKEY;
284 331 : }
285 151049 : if( FD_UNLIKELY( fd_ed25519_affine_is_small_order(&R[j]) ) ) {
286 158 : return FD_ED25519_ERR_SIG;
287 158 : }
288 :
289 : /* Compute scalars k_j */
290 150891 : uchar _k[ 64 ];
291 150891 : fd_sha512_fini( fd_sha512_append( fd_sha512_append( fd_sha512_append( fd_sha512_init( shas[j] ),
292 150891 : r, 32UL ), public_key, 32UL ), msg, msg_sz ), _k );
293 150891 : fd_curve25519_scalar_reduce( &k[32*j], _k );
294 150891 : }
295 :
296 58848 : fd_ed25519_point_t res[1];
297 209121 : for( uchar j=0; j<batch_sz; j++ ) {
298 150303 : uchar const * S = signatures + 32 + 64*j;
299 :
300 150303 : fd_ed25519_point_neg( &Aprime[j], &Aprime[j] );
301 150303 : fd_ed25519_double_scalar_mul_base( res, &k[32*j], &Aprime[j], S );
302 150303 : if( FD_UNLIKELY( !fd_ed25519_point_eq_z1( res, &R[j] ) ) ) {
303 30 : return FD_ED25519_ERR_MSG;
304 30 : }
305 :
306 150303 : }
307 58818 : return FD_ED25519_SUCCESS;
308 58848 : #endif
309 58848 : #undef MAX
310 58848 : }
311 :
312 : char const *
313 0 : fd_ed25519_strerror( int err ) {
314 0 : switch( err ) {
315 0 : case FD_ED25519_SUCCESS: return "success";
316 0 : case FD_ED25519_ERR_SIG: return "bad signature";
317 0 : case FD_ED25519_ERR_PUBKEY: return "bad public key";
318 0 : case FD_ED25519_ERR_MSG: return "bad message";
319 0 : default: break;
320 0 : }
321 0 : return "unknown";
322 0 : }
|
