1 /*
2 * Copyright 2017-2024 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright 2015-2016 Cryptography Research, Inc.
4 *
5 * Licensed under the Apache License 2.0 (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 *
10 * Originally written by Mike Hamburg
11 */
12 #include <string.h>
13 #include <openssl/crypto.h>
14 #include <openssl/evp.h>
15 #include "crypto/ecx.h"
16 #include "curve448_local.h"
17 #include "word.h"
18 #include "ed448.h"
19 #include "internal/numbers.h"
20
21 #define COFACTOR 4
22
oneshot_hash(OSSL_LIB_CTX * ctx,uint8_t * out,size_t outlen,const uint8_t * in,size_t inlen,const char * propq)23 static c448_error_t oneshot_hash(OSSL_LIB_CTX *ctx, uint8_t *out, size_t outlen,
24 const uint8_t *in, size_t inlen,
25 const char *propq)
26 {
27 EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
28 EVP_MD *shake256 = NULL;
29 c448_error_t ret = C448_FAILURE;
30
31 if (hashctx == NULL)
32 return C448_FAILURE;
33
34 shake256 = EVP_MD_fetch(ctx, "SHAKE256", propq);
35 if (shake256 == NULL)
36 goto err;
37
38 if (!EVP_DigestInit_ex(hashctx, shake256, NULL)
39 || !EVP_DigestUpdate(hashctx, in, inlen)
40 || !EVP_DigestFinalXOF(hashctx, out, outlen))
41 goto err;
42
43 ret = C448_SUCCESS;
44 err:
45 EVP_MD_CTX_free(hashctx);
46 EVP_MD_free(shake256);
47 return ret;
48 }
49
clamp(uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES])50 static void clamp(uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES])
51 {
52 secret_scalar_ser[0] &= -COFACTOR;
53 secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 1] = 0;
54 secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 2] |= 0x80;
55 }
56
hash_init_with_dom(OSSL_LIB_CTX * ctx,EVP_MD_CTX * hashctx,uint8_t prehashed,uint8_t for_prehash,const uint8_t * context,size_t context_len,const char * propq)57 static c448_error_t hash_init_with_dom(OSSL_LIB_CTX *ctx, EVP_MD_CTX *hashctx,
58 uint8_t prehashed,
59 uint8_t for_prehash,
60 const uint8_t *context,
61 size_t context_len,
62 const char *propq)
63 {
64 /* ASCII: "SigEd448", in hex for EBCDIC compatibility */
65 const char dom_s[] = "\x53\x69\x67\x45\x64\x34\x34\x38";
66 uint8_t dom[2];
67 EVP_MD *shake256 = NULL;
68
69 if (context_len > UINT8_MAX)
70 return C448_FAILURE;
71
72 dom[0] = (uint8_t)(2 - (prehashed == 0 ? 1 : 0)
73 - (for_prehash == 0 ? 1 : 0));
74 dom[1] = (uint8_t)context_len;
75
76 shake256 = EVP_MD_fetch(ctx, "SHAKE256", propq);
77 if (shake256 == NULL)
78 return C448_FAILURE;
79
80 if (!EVP_DigestInit_ex(hashctx, shake256, NULL)
81 || !EVP_DigestUpdate(hashctx, dom_s, sizeof(dom_s)-1)
82 || !EVP_DigestUpdate(hashctx, dom, sizeof(dom))
83 || !EVP_DigestUpdate(hashctx, context, context_len)) {
84 EVP_MD_free(shake256);
85 return C448_FAILURE;
86 }
87
88 EVP_MD_free(shake256);
89 return C448_SUCCESS;
90 }
91
92 /* In this file because it uses the hash */
93 c448_error_t
ossl_c448_ed448_convert_private_key_to_x448(OSSL_LIB_CTX * ctx,uint8_t x[X448_PRIVATE_BYTES],const uint8_t ed[EDDSA_448_PRIVATE_BYTES],const char * propq)94 ossl_c448_ed448_convert_private_key_to_x448(
95 OSSL_LIB_CTX *ctx,
96 uint8_t x[X448_PRIVATE_BYTES],
97 const uint8_t ed [EDDSA_448_PRIVATE_BYTES],
98 const char *propq)
99 {
100 /* pass the private key through oneshot_hash function */
101 /* and keep the first X448_PRIVATE_BYTES bytes */
102 return oneshot_hash(ctx, x, X448_PRIVATE_BYTES, ed,
103 EDDSA_448_PRIVATE_BYTES, propq);
104 }
105
106 c448_error_t
ossl_c448_ed448_derive_public_key(OSSL_LIB_CTX * ctx,uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],const char * propq)107 ossl_c448_ed448_derive_public_key(
108 OSSL_LIB_CTX *ctx,
109 uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
110 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
111 const char *propq)
112 {
113 /* only this much used for keygen */
114 uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES];
115 curve448_scalar_t secret_scalar;
116 unsigned int c;
117 curve448_point_t p;
118
119 if (!oneshot_hash(ctx, secret_scalar_ser, sizeof(secret_scalar_ser),
120 privkey,
121 EDDSA_448_PRIVATE_BYTES,
122 propq))
123 return C448_FAILURE;
124
125 clamp(secret_scalar_ser);
126
127 ossl_curve448_scalar_decode_long(secret_scalar, secret_scalar_ser,
128 sizeof(secret_scalar_ser));
129
130 /*
131 * Since we are going to mul_by_cofactor during encoding, divide by it
132 * here. However, the EdDSA base point is not the same as the decaf base
133 * point if the sigma isogeny is in use: the EdDSA base point is on
134 * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when
135 * converted it effectively picks up a factor of 2 from the isogenies. So
136 * we might start at 2 instead of 1.
137 */
138 for (c = 1; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
139 ossl_curve448_scalar_halve(secret_scalar, secret_scalar);
140
141 ossl_curve448_precomputed_scalarmul(p, ossl_curve448_precomputed_base,
142 secret_scalar);
143
144 ossl_curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p);
145
146 /* Cleanup */
147 ossl_curve448_scalar_destroy(secret_scalar);
148 ossl_curve448_point_destroy(p);
149 OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser));
150
151 return C448_SUCCESS;
152 }
153
154 c448_error_t
ossl_c448_ed448_sign(OSSL_LIB_CTX * ctx,uint8_t signature[EDDSA_448_SIGNATURE_BYTES],const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],const uint8_t * message,size_t message_len,uint8_t prehashed,const uint8_t * context,size_t context_len,const char * propq)155 ossl_c448_ed448_sign(OSSL_LIB_CTX *ctx,
156 uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
157 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
158 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
159 const uint8_t *message, size_t message_len,
160 uint8_t prehashed, const uint8_t *context,
161 size_t context_len, const char *propq)
162 {
163 curve448_scalar_t secret_scalar;
164 EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
165 c448_error_t ret = C448_FAILURE;
166 curve448_scalar_t nonce_scalar;
167 uint8_t nonce_point[EDDSA_448_PUBLIC_BYTES] = { 0 };
168 unsigned int c;
169 curve448_scalar_t challenge_scalar;
170
171 if (hashctx == NULL)
172 return C448_FAILURE;
173
174 {
175 /*
176 * Schedule the secret key, First EDDSA_448_PRIVATE_BYTES is serialized
177 * secret scalar,next EDDSA_448_PRIVATE_BYTES bytes is the seed.
178 */
179 uint8_t expanded[EDDSA_448_PRIVATE_BYTES * 2];
180
181 if (!oneshot_hash(ctx, expanded, sizeof(expanded), privkey,
182 EDDSA_448_PRIVATE_BYTES, propq))
183 goto err;
184 clamp(expanded);
185 ossl_curve448_scalar_decode_long(secret_scalar, expanded,
186 EDDSA_448_PRIVATE_BYTES);
187
188 /* Hash to create the nonce */
189 if (!hash_init_with_dom(ctx, hashctx, prehashed, 0, context,
190 context_len, propq)
191 || !EVP_DigestUpdate(hashctx,
192 expanded + EDDSA_448_PRIVATE_BYTES,
193 EDDSA_448_PRIVATE_BYTES)
194 || !EVP_DigestUpdate(hashctx, message, message_len)) {
195 OPENSSL_cleanse(expanded, sizeof(expanded));
196 goto err;
197 }
198 OPENSSL_cleanse(expanded, sizeof(expanded));
199 }
200
201 /* Decode the nonce */
202 {
203 uint8_t nonce[2 * EDDSA_448_PRIVATE_BYTES];
204
205 if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce)))
206 goto err;
207 ossl_curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce));
208 OPENSSL_cleanse(nonce, sizeof(nonce));
209 }
210
211 {
212 /* Scalarmul to create the nonce-point */
213 curve448_scalar_t nonce_scalar_2;
214 curve448_point_t p;
215
216 ossl_curve448_scalar_halve(nonce_scalar_2, nonce_scalar);
217 for (c = 2; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
218 ossl_curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2);
219
220 ossl_curve448_precomputed_scalarmul(p, ossl_curve448_precomputed_base,
221 nonce_scalar_2);
222 ossl_curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p);
223 ossl_curve448_point_destroy(p);
224 ossl_curve448_scalar_destroy(nonce_scalar_2);
225 }
226
227 {
228 uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
229
230 /* Compute the challenge */
231 if (!hash_init_with_dom(ctx, hashctx, prehashed, 0, context, context_len,
232 propq)
233 || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point))
234 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
235 || !EVP_DigestUpdate(hashctx, message, message_len)
236 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge)))
237 goto err;
238
239 ossl_curve448_scalar_decode_long(challenge_scalar, challenge,
240 sizeof(challenge));
241 OPENSSL_cleanse(challenge, sizeof(challenge));
242 }
243
244 ossl_curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar);
245 ossl_curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar);
246
247 OPENSSL_cleanse(signature, EDDSA_448_SIGNATURE_BYTES);
248 memcpy(signature, nonce_point, sizeof(nonce_point));
249 ossl_curve448_scalar_encode(&signature[EDDSA_448_PUBLIC_BYTES],
250 challenge_scalar);
251
252 ossl_curve448_scalar_destroy(secret_scalar);
253 ossl_curve448_scalar_destroy(nonce_scalar);
254 ossl_curve448_scalar_destroy(challenge_scalar);
255
256 ret = C448_SUCCESS;
257 err:
258 EVP_MD_CTX_free(hashctx);
259 return ret;
260 }
261
262 c448_error_t
ossl_c448_ed448_sign_prehash(OSSL_LIB_CTX * ctx,uint8_t signature[EDDSA_448_SIGNATURE_BYTES],const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],const uint8_t hash[64],const uint8_t * context,size_t context_len,const char * propq)263 ossl_c448_ed448_sign_prehash(
264 OSSL_LIB_CTX *ctx,
265 uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
266 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
267 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
268 const uint8_t hash[64], const uint8_t *context,
269 size_t context_len, const char *propq)
270 {
271 return ossl_c448_ed448_sign(ctx, signature, privkey, pubkey, hash, 64, 1,
272 context, context_len, propq);
273 }
274
275 static c448_error_t
c448_ed448_pubkey_verify(const uint8_t * pub,size_t pub_len)276 c448_ed448_pubkey_verify(const uint8_t *pub, size_t pub_len)
277 {
278 curve448_point_t pk_point;
279
280 if (pub_len != EDDSA_448_PUBLIC_BYTES)
281 return C448_FAILURE;
282
283 return ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pub);
284 }
285
286 c448_error_t
ossl_c448_ed448_verify(OSSL_LIB_CTX * ctx,const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],const uint8_t * message,size_t message_len,uint8_t prehashed,const uint8_t * context,uint8_t context_len,const char * propq)287 ossl_c448_ed448_verify(
288 OSSL_LIB_CTX *ctx,
289 const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
290 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
291 const uint8_t *message, size_t message_len,
292 uint8_t prehashed, const uint8_t *context,
293 uint8_t context_len, const char *propq)
294 {
295 curve448_point_t pk_point, r_point;
296 c448_error_t error;
297 curve448_scalar_t challenge_scalar;
298 curve448_scalar_t response_scalar;
299 /* Order in little endian format */
300 static const uint8_t order[] = {
301 0xF3, 0x44, 0x58, 0xAB, 0x92, 0xC2, 0x78, 0x23, 0x55, 0x8F, 0xC5, 0x8D,
302 0x72, 0xC2, 0x6C, 0x21, 0x90, 0x36, 0xD6, 0xAE, 0x49, 0xDB, 0x4E, 0xC4,
303 0xE9, 0x23, 0xCA, 0x7C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
304 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
305 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x3F, 0x00
306 };
307 int i;
308
309 /*
310 * Check that s (second 57 bytes of the sig) is less than the order. Both
311 * s and the order are in little-endian format. This can be done in
312 * variable time, since if this is not the case the signature if publicly
313 * invalid.
314 */
315 for (i = EDDSA_448_PUBLIC_BYTES - 1; i >= 0; i--) {
316 if (signature[i + EDDSA_448_PUBLIC_BYTES] > order[i])
317 return C448_FAILURE;
318 if (signature[i + EDDSA_448_PUBLIC_BYTES] < order[i])
319 break;
320 }
321 if (i < 0)
322 return C448_FAILURE;
323
324 error =
325 ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
326
327 if (C448_SUCCESS != error)
328 return error;
329
330 error =
331 ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
332 if (C448_SUCCESS != error)
333 return error;
334
335 {
336 /* Compute the challenge */
337 EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
338 uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
339
340 if (hashctx == NULL
341 || !hash_init_with_dom(ctx, hashctx, prehashed, 0, context,
342 context_len, propq)
343 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES)
344 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
345 || !EVP_DigestUpdate(hashctx, message, message_len)
346 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
347 EVP_MD_CTX_free(hashctx);
348 return C448_FAILURE;
349 }
350
351 EVP_MD_CTX_free(hashctx);
352 ossl_curve448_scalar_decode_long(challenge_scalar, challenge,
353 sizeof(challenge));
354 OPENSSL_cleanse(challenge, sizeof(challenge));
355 }
356 ossl_curve448_scalar_sub(challenge_scalar, ossl_curve448_scalar_zero,
357 challenge_scalar);
358
359 ossl_curve448_scalar_decode_long(response_scalar,
360 &signature[EDDSA_448_PUBLIC_BYTES],
361 EDDSA_448_PRIVATE_BYTES);
362
363 /* pk_point = -c(x(P)) + (cx + k)G = kG */
364 ossl_curve448_base_double_scalarmul_non_secret(pk_point,
365 response_scalar,
366 pk_point, challenge_scalar);
367 return c448_succeed_if(ossl_curve448_point_eq(pk_point, r_point));
368 }
369
370 c448_error_t
ossl_c448_ed448_verify_prehash(OSSL_LIB_CTX * ctx,const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],const uint8_t hash[64],const uint8_t * context,uint8_t context_len,const char * propq)371 ossl_c448_ed448_verify_prehash(
372 OSSL_LIB_CTX *ctx,
373 const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
374 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
375 const uint8_t hash[64], const uint8_t *context,
376 uint8_t context_len, const char *propq)
377 {
378 return ossl_c448_ed448_verify(ctx, signature, pubkey, hash, 64, 1, context,
379 context_len, propq);
380 }
381
382 int
ossl_ed448_sign(OSSL_LIB_CTX * ctx,uint8_t * out_sig,const uint8_t * message,size_t message_len,const uint8_t public_key[57],const uint8_t private_key[57],const uint8_t * context,size_t context_len,const uint8_t phflag,const char * propq)383 ossl_ed448_sign(OSSL_LIB_CTX *ctx, uint8_t *out_sig,
384 const uint8_t *message, size_t message_len,
385 const uint8_t public_key[57], const uint8_t private_key[57],
386 const uint8_t *context, size_t context_len,
387 const uint8_t phflag, const char *propq)
388 {
389 return ossl_c448_ed448_sign(ctx, out_sig, private_key, public_key, message,
390 message_len, phflag, context, context_len,
391 propq) == C448_SUCCESS;
392 }
393
394 /*
395 * This function should not be necessary since ossl_ed448_verify() already
396 * does this check internally.
397 * For some reason the FIPS ACVP requires a EDDSA KeyVer test.
398 */
399 int
ossl_ed448_pubkey_verify(const uint8_t * pub,size_t pub_len)400 ossl_ed448_pubkey_verify(const uint8_t *pub, size_t pub_len)
401 {
402 return c448_ed448_pubkey_verify(pub, pub_len);
403 }
404
405 int
ossl_ed448_verify(OSSL_LIB_CTX * ctx,const uint8_t * message,size_t message_len,const uint8_t signature[114],const uint8_t public_key[57],const uint8_t * context,size_t context_len,const uint8_t phflag,const char * propq)406 ossl_ed448_verify(OSSL_LIB_CTX *ctx,
407 const uint8_t *message, size_t message_len,
408 const uint8_t signature[114], const uint8_t public_key[57],
409 const uint8_t *context, size_t context_len,
410 const uint8_t phflag, const char *propq)
411 {
412 return ossl_c448_ed448_verify(ctx, signature, public_key, message,
413 message_len, phflag, context, (uint8_t)context_len,
414 propq) == C448_SUCCESS;
415 }
416
417 int
ossl_ed448_public_from_private(OSSL_LIB_CTX * ctx,uint8_t out_public_key[57],const uint8_t private_key[57],const char * propq)418 ossl_ed448_public_from_private(OSSL_LIB_CTX *ctx, uint8_t out_public_key[57],
419 const uint8_t private_key[57], const char *propq)
420 {
421 return ossl_c448_ed448_derive_public_key(ctx, out_public_key, private_key,
422 propq) == C448_SUCCESS;
423 }
424
