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 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 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 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 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 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 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 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 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 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 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 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 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 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 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