1 /*
2 * Copyright 2017-2021 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 #ifdef CHARSET_EBCDIC
65 const char dom_s[] = {0x53, 0x69, 0x67, 0x45,
66 0x64, 0x34, 0x34, 0x38, 0x00};
67 #else
68 const char dom_s[] = "SigEd448";
69 #endif
70 uint8_t dom[2];
71 EVP_MD *shake256 = NULL;
72
73 if (context_len > UINT8_MAX)
74 return C448_FAILURE;
75
76 dom[0] = (uint8_t)(2 - (prehashed == 0 ? 1 : 0)
77 - (for_prehash == 0 ? 1 : 0));
78 dom[1] = (uint8_t)context_len;
79
80 shake256 = EVP_MD_fetch(ctx, "SHAKE256", propq);
81 if (shake256 == NULL)
82 return C448_FAILURE;
83
84 if (!EVP_DigestInit_ex(hashctx, shake256, NULL)
85 || !EVP_DigestUpdate(hashctx, dom_s, strlen(dom_s))
86 || !EVP_DigestUpdate(hashctx, dom, sizeof(dom))
87 || !EVP_DigestUpdate(hashctx, context, context_len)) {
88 EVP_MD_free(shake256);
89 return C448_FAILURE;
90 }
91
92 EVP_MD_free(shake256);
93 return C448_SUCCESS;
94 }
95
96 /* In this file because it uses the hash */
97 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)98 ossl_c448_ed448_convert_private_key_to_x448(
99 OSSL_LIB_CTX *ctx,
100 uint8_t x[X448_PRIVATE_BYTES],
101 const uint8_t ed [EDDSA_448_PRIVATE_BYTES],
102 const char *propq)
103 {
104 /* pass the private key through oneshot_hash function */
105 /* and keep the first X448_PRIVATE_BYTES bytes */
106 return oneshot_hash(ctx, x, X448_PRIVATE_BYTES, ed,
107 EDDSA_448_PRIVATE_BYTES, propq);
108 }
109
110 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)111 ossl_c448_ed448_derive_public_key(
112 OSSL_LIB_CTX *ctx,
113 uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
114 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
115 const char *propq)
116 {
117 /* only this much used for keygen */
118 uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES];
119 curve448_scalar_t secret_scalar;
120 unsigned int c;
121 curve448_point_t p;
122
123 if (!oneshot_hash(ctx, secret_scalar_ser, sizeof(secret_scalar_ser),
124 privkey,
125 EDDSA_448_PRIVATE_BYTES,
126 propq))
127 return C448_FAILURE;
128
129 clamp(secret_scalar_ser);
130
131 ossl_curve448_scalar_decode_long(secret_scalar, secret_scalar_ser,
132 sizeof(secret_scalar_ser));
133
134 /*
135 * Since we are going to mul_by_cofactor during encoding, divide by it
136 * here. However, the EdDSA base point is not the same as the decaf base
137 * point if the sigma isogeny is in use: the EdDSA base point is on
138 * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when
139 * converted it effectively picks up a factor of 2 from the isogenies. So
140 * we might start at 2 instead of 1.
141 */
142 for (c = 1; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
143 ossl_curve448_scalar_halve(secret_scalar, secret_scalar);
144
145 ossl_curve448_precomputed_scalarmul(p, ossl_curve448_precomputed_base,
146 secret_scalar);
147
148 ossl_curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p);
149
150 /* Cleanup */
151 ossl_curve448_scalar_destroy(secret_scalar);
152 ossl_curve448_point_destroy(p);
153 OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser));
154
155 return C448_SUCCESS;
156 }
157
158 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)159 ossl_c448_ed448_sign(OSSL_LIB_CTX *ctx,
160 uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
161 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
162 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
163 const uint8_t *message, size_t message_len,
164 uint8_t prehashed, const uint8_t *context,
165 size_t context_len, const char *propq)
166 {
167 curve448_scalar_t secret_scalar;
168 EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
169 c448_error_t ret = C448_FAILURE;
170 curve448_scalar_t nonce_scalar;
171 uint8_t nonce_point[EDDSA_448_PUBLIC_BYTES] = { 0 };
172 unsigned int c;
173 curve448_scalar_t challenge_scalar;
174
175 if (hashctx == NULL)
176 return C448_FAILURE;
177
178 {
179 /*
180 * Schedule the secret key, First EDDSA_448_PRIVATE_BYTES is serialized
181 * secret scalar,next EDDSA_448_PRIVATE_BYTES bytes is the seed.
182 */
183 uint8_t expanded[EDDSA_448_PRIVATE_BYTES * 2];
184
185 if (!oneshot_hash(ctx, expanded, sizeof(expanded), privkey,
186 EDDSA_448_PRIVATE_BYTES, propq))
187 goto err;
188 clamp(expanded);
189 ossl_curve448_scalar_decode_long(secret_scalar, expanded,
190 EDDSA_448_PRIVATE_BYTES);
191
192 /* Hash to create the nonce */
193 if (!hash_init_with_dom(ctx, hashctx, prehashed, 0, context,
194 context_len, propq)
195 || !EVP_DigestUpdate(hashctx,
196 expanded + EDDSA_448_PRIVATE_BYTES,
197 EDDSA_448_PRIVATE_BYTES)
198 || !EVP_DigestUpdate(hashctx, message, message_len)) {
199 OPENSSL_cleanse(expanded, sizeof(expanded));
200 goto err;
201 }
202 OPENSSL_cleanse(expanded, sizeof(expanded));
203 }
204
205 /* Decode the nonce */
206 {
207 uint8_t nonce[2 * EDDSA_448_PRIVATE_BYTES];
208
209 if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce)))
210 goto err;
211 ossl_curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce));
212 OPENSSL_cleanse(nonce, sizeof(nonce));
213 }
214
215 {
216 /* Scalarmul to create the nonce-point */
217 curve448_scalar_t nonce_scalar_2;
218 curve448_point_t p;
219
220 ossl_curve448_scalar_halve(nonce_scalar_2, nonce_scalar);
221 for (c = 2; c < C448_EDDSA_ENCODE_RATIO; c <<= 1)
222 ossl_curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2);
223
224 ossl_curve448_precomputed_scalarmul(p, ossl_curve448_precomputed_base,
225 nonce_scalar_2);
226 ossl_curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p);
227 ossl_curve448_point_destroy(p);
228 ossl_curve448_scalar_destroy(nonce_scalar_2);
229 }
230
231 {
232 uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
233
234 /* Compute the challenge */
235 if (!hash_init_with_dom(ctx, hashctx, prehashed, 0, context, context_len,
236 propq)
237 || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point))
238 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
239 || !EVP_DigestUpdate(hashctx, message, message_len)
240 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge)))
241 goto err;
242
243 ossl_curve448_scalar_decode_long(challenge_scalar, challenge,
244 sizeof(challenge));
245 OPENSSL_cleanse(challenge, sizeof(challenge));
246 }
247
248 ossl_curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar);
249 ossl_curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar);
250
251 OPENSSL_cleanse(signature, EDDSA_448_SIGNATURE_BYTES);
252 memcpy(signature, nonce_point, sizeof(nonce_point));
253 ossl_curve448_scalar_encode(&signature[EDDSA_448_PUBLIC_BYTES],
254 challenge_scalar);
255
256 ossl_curve448_scalar_destroy(secret_scalar);
257 ossl_curve448_scalar_destroy(nonce_scalar);
258 ossl_curve448_scalar_destroy(challenge_scalar);
259
260 ret = C448_SUCCESS;
261 err:
262 EVP_MD_CTX_free(hashctx);
263 return ret;
264 }
265
266 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)267 ossl_c448_ed448_sign_prehash(
268 OSSL_LIB_CTX *ctx,
269 uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
270 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES],
271 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
272 const uint8_t hash[64], const uint8_t *context,
273 size_t context_len, const char *propq)
274 {
275 return ossl_c448_ed448_sign(ctx, signature, privkey, pubkey, hash, 64, 1,
276 context, context_len, propq);
277 }
278
279 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)280 ossl_c448_ed448_verify(
281 OSSL_LIB_CTX *ctx,
282 const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
283 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
284 const uint8_t *message, size_t message_len,
285 uint8_t prehashed, const uint8_t *context,
286 uint8_t context_len, const char *propq)
287 {
288 curve448_point_t pk_point, r_point;
289 c448_error_t error;
290 curve448_scalar_t challenge_scalar;
291 curve448_scalar_t response_scalar;
292 /* Order in little endian format */
293 static const uint8_t order[] = {
294 0xF3, 0x44, 0x58, 0xAB, 0x92, 0xC2, 0x78, 0x23, 0x55, 0x8F, 0xC5, 0x8D,
295 0x72, 0xC2, 0x6C, 0x21, 0x90, 0x36, 0xD6, 0xAE, 0x49, 0xDB, 0x4E, 0xC4,
296 0xE9, 0x23, 0xCA, 0x7C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
297 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
298 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x3F, 0x00
299 };
300 int i;
301
302 /*
303 * Check that s (second 57 bytes of the sig) is less than the order. Both
304 * s and the order are in little-endian format. This can be done in
305 * variable time, since if this is not the case the signature if publicly
306 * invalid.
307 */
308 for (i = EDDSA_448_PUBLIC_BYTES - 1; i >= 0; i--) {
309 if (signature[i + EDDSA_448_PUBLIC_BYTES] > order[i])
310 return C448_FAILURE;
311 if (signature[i + EDDSA_448_PUBLIC_BYTES] < order[i])
312 break;
313 }
314 if (i < 0)
315 return C448_FAILURE;
316
317 error =
318 ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
319
320 if (C448_SUCCESS != error)
321 return error;
322
323 error =
324 ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
325 if (C448_SUCCESS != error)
326 return error;
327
328 {
329 /* Compute the challenge */
330 EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
331 uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
332
333 if (hashctx == NULL
334 || !hash_init_with_dom(ctx, hashctx, prehashed, 0, context,
335 context_len, propq)
336 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES)
337 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
338 || !EVP_DigestUpdate(hashctx, message, message_len)
339 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
340 EVP_MD_CTX_free(hashctx);
341 return C448_FAILURE;
342 }
343
344 EVP_MD_CTX_free(hashctx);
345 ossl_curve448_scalar_decode_long(challenge_scalar, challenge,
346 sizeof(challenge));
347 OPENSSL_cleanse(challenge, sizeof(challenge));
348 }
349 ossl_curve448_scalar_sub(challenge_scalar, ossl_curve448_scalar_zero,
350 challenge_scalar);
351
352 ossl_curve448_scalar_decode_long(response_scalar,
353 &signature[EDDSA_448_PUBLIC_BYTES],
354 EDDSA_448_PRIVATE_BYTES);
355
356 /* pk_point = -c(x(P)) + (cx + k)G = kG */
357 ossl_curve448_base_double_scalarmul_non_secret(pk_point,
358 response_scalar,
359 pk_point, challenge_scalar);
360 return c448_succeed_if(ossl_curve448_point_eq(pk_point, r_point));
361 }
362
363 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)364 ossl_c448_ed448_verify_prehash(
365 OSSL_LIB_CTX *ctx,
366 const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
367 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
368 const uint8_t hash[64], const uint8_t *context,
369 uint8_t context_len, const char *propq)
370 {
371 return ossl_c448_ed448_verify(ctx, signature, pubkey, hash, 64, 1, context,
372 context_len, propq);
373 }
374
375 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 char * propq)376 ossl_ed448_sign(OSSL_LIB_CTX *ctx, uint8_t *out_sig, const uint8_t *message,
377 size_t message_len, const uint8_t public_key[57],
378 const uint8_t private_key[57], const uint8_t *context,
379 size_t context_len, const char *propq)
380 {
381 return ossl_c448_ed448_sign(ctx, out_sig, private_key, public_key, message,
382 message_len, 0, context, context_len,
383 propq) == C448_SUCCESS;
384 }
385
386 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 char * propq)387 ossl_ed448_verify(OSSL_LIB_CTX *ctx, const uint8_t *message, size_t message_len,
388 const uint8_t signature[114], const uint8_t public_key[57],
389 const uint8_t *context, size_t context_len, const char *propq)
390 {
391 return ossl_c448_ed448_verify(ctx, signature, public_key, message,
392 message_len, 0, context, (uint8_t)context_len,
393 propq) == C448_SUCCESS;
394 }
395
396 int
ossl_ed448ph_sign(OSSL_LIB_CTX * ctx,uint8_t * out_sig,const uint8_t hash[64],const uint8_t public_key[57],const uint8_t private_key[57],const uint8_t * context,size_t context_len,const char * propq)397 ossl_ed448ph_sign(OSSL_LIB_CTX *ctx, uint8_t *out_sig, const uint8_t hash[64],
398 const uint8_t public_key[57], const uint8_t private_key[57],
399 const uint8_t *context, size_t context_len, const char *propq)
400 {
401 return ossl_c448_ed448_sign_prehash(ctx, out_sig, private_key, public_key,
402 hash, context, context_len,
403 propq) == C448_SUCCESS;
404 }
405
406 int
ossl_ed448ph_verify(OSSL_LIB_CTX * ctx,const uint8_t hash[64],const uint8_t signature[114],const uint8_t public_key[57],const uint8_t * context,size_t context_len,const char * propq)407 ossl_ed448ph_verify(OSSL_LIB_CTX *ctx, const uint8_t hash[64],
408 const uint8_t signature[114], const uint8_t public_key[57],
409 const uint8_t *context, size_t context_len,
410 const char *propq)
411 {
412 return ossl_c448_ed448_verify_prehash(ctx, signature, public_key, hash,
413 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