1 /* 2 * Copyright 2017-2020 The OpenSSL Project Authors. All Rights Reserved. 3 * Copyright 2015-2016 Cryptography Research, Inc. 4 * 5 * Licensed under the OpenSSL license (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 "curve448_local.h" 16 #include "word.h" 17 #include "ed448.h" 18 #include "internal/numbers.h" 19 20 #define COFACTOR 4 21 22 static c448_error_t oneshot_hash(uint8_t *out, size_t outlen, 23 const uint8_t *in, size_t inlen) 24 { 25 EVP_MD_CTX *hashctx = EVP_MD_CTX_new(); 26 27 if (hashctx == NULL) 28 return C448_FAILURE; 29 30 if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL) 31 || !EVP_DigestUpdate(hashctx, in, inlen) 32 || !EVP_DigestFinalXOF(hashctx, out, outlen)) { 33 EVP_MD_CTX_free(hashctx); 34 return C448_FAILURE; 35 } 36 37 EVP_MD_CTX_free(hashctx); 38 return C448_SUCCESS; 39 } 40 41 static void clamp(uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES]) 42 { 43 secret_scalar_ser[0] &= -COFACTOR; 44 secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 1] = 0; 45 secret_scalar_ser[EDDSA_448_PRIVATE_BYTES - 2] |= 0x80; 46 } 47 48 static c448_error_t hash_init_with_dom(EVP_MD_CTX *hashctx, uint8_t prehashed, 49 uint8_t for_prehash, 50 const uint8_t *context, 51 size_t context_len) 52 { 53 #ifdef CHARSET_EBCDIC 54 const char dom_s[] = {0x53, 0x69, 0x67, 0x45, 55 0x64, 0x34, 0x34, 0x38, 0x00}; 56 #else 57 const char dom_s[] = "SigEd448"; 58 #endif 59 uint8_t dom[2]; 60 61 if (context_len > UINT8_MAX) 62 return C448_FAILURE; 63 64 dom[0] = (uint8_t)(2 - (prehashed == 0 ? 1 : 0) 65 - (for_prehash == 0 ? 1 : 0)); 66 dom[1] = (uint8_t)context_len; 67 68 if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL) 69 || !EVP_DigestUpdate(hashctx, dom_s, strlen(dom_s)) 70 || !EVP_DigestUpdate(hashctx, dom, sizeof(dom)) 71 || !EVP_DigestUpdate(hashctx, context, context_len)) 72 return C448_FAILURE; 73 74 return C448_SUCCESS; 75 } 76 77 /* In this file because it uses the hash */ 78 c448_error_t c448_ed448_convert_private_key_to_x448( 79 uint8_t x[X448_PRIVATE_BYTES], 80 const uint8_t ed [EDDSA_448_PRIVATE_BYTES]) 81 { 82 /* pass the private key through oneshot_hash function */ 83 /* and keep the first X448_PRIVATE_BYTES bytes */ 84 return oneshot_hash(x, X448_PRIVATE_BYTES, ed, 85 EDDSA_448_PRIVATE_BYTES); 86 } 87 88 c448_error_t c448_ed448_derive_public_key( 89 uint8_t pubkey[EDDSA_448_PUBLIC_BYTES], 90 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES]) 91 { 92 /* only this much used for keygen */ 93 uint8_t secret_scalar_ser[EDDSA_448_PRIVATE_BYTES]; 94 curve448_scalar_t secret_scalar; 95 unsigned int c; 96 curve448_point_t p; 97 98 if (!oneshot_hash(secret_scalar_ser, sizeof(secret_scalar_ser), privkey, 99 EDDSA_448_PRIVATE_BYTES)) 100 return C448_FAILURE; 101 102 clamp(secret_scalar_ser); 103 104 curve448_scalar_decode_long(secret_scalar, secret_scalar_ser, 105 sizeof(secret_scalar_ser)); 106 107 /* 108 * Since we are going to mul_by_cofactor during encoding, divide by it 109 * here. However, the EdDSA base point is not the same as the decaf base 110 * point if the sigma isogeny is in use: the EdDSA base point is on 111 * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when 112 * converted it effectively picks up a factor of 2 from the isogenies. So 113 * we might start at 2 instead of 1. 114 */ 115 for (c = 1; c < C448_EDDSA_ENCODE_RATIO; c <<= 1) 116 curve448_scalar_halve(secret_scalar, secret_scalar); 117 118 curve448_precomputed_scalarmul(p, curve448_precomputed_base, secret_scalar); 119 120 curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p); 121 122 /* Cleanup */ 123 curve448_scalar_destroy(secret_scalar); 124 curve448_point_destroy(p); 125 OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser)); 126 127 return C448_SUCCESS; 128 } 129 130 c448_error_t c448_ed448_sign( 131 uint8_t signature[EDDSA_448_SIGNATURE_BYTES], 132 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES], 133 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES], 134 const uint8_t *message, size_t message_len, 135 uint8_t prehashed, const uint8_t *context, 136 size_t context_len) 137 { 138 curve448_scalar_t secret_scalar; 139 EVP_MD_CTX *hashctx = EVP_MD_CTX_new(); 140 c448_error_t ret = C448_FAILURE; 141 curve448_scalar_t nonce_scalar; 142 uint8_t nonce_point[EDDSA_448_PUBLIC_BYTES] = { 0 }; 143 unsigned int c; 144 curve448_scalar_t challenge_scalar; 145 146 if (hashctx == NULL) 147 return C448_FAILURE; 148 149 { 150 /* 151 * Schedule the secret key, First EDDSA_448_PRIVATE_BYTES is serialised 152 * secret scalar,next EDDSA_448_PRIVATE_BYTES bytes is the seed. 153 */ 154 uint8_t expanded[EDDSA_448_PRIVATE_BYTES * 2]; 155 156 if (!oneshot_hash(expanded, sizeof(expanded), privkey, 157 EDDSA_448_PRIVATE_BYTES)) 158 goto err; 159 clamp(expanded); 160 curve448_scalar_decode_long(secret_scalar, expanded, 161 EDDSA_448_PRIVATE_BYTES); 162 163 /* Hash to create the nonce */ 164 if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len) 165 || !EVP_DigestUpdate(hashctx, 166 expanded + EDDSA_448_PRIVATE_BYTES, 167 EDDSA_448_PRIVATE_BYTES) 168 || !EVP_DigestUpdate(hashctx, message, message_len)) { 169 OPENSSL_cleanse(expanded, sizeof(expanded)); 170 goto err; 171 } 172 OPENSSL_cleanse(expanded, sizeof(expanded)); 173 } 174 175 /* Decode the nonce */ 176 { 177 uint8_t nonce[2 * EDDSA_448_PRIVATE_BYTES]; 178 179 if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce))) 180 goto err; 181 curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce)); 182 OPENSSL_cleanse(nonce, sizeof(nonce)); 183 } 184 185 { 186 /* Scalarmul to create the nonce-point */ 187 curve448_scalar_t nonce_scalar_2; 188 curve448_point_t p; 189 190 curve448_scalar_halve(nonce_scalar_2, nonce_scalar); 191 for (c = 2; c < C448_EDDSA_ENCODE_RATIO; c <<= 1) 192 curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2); 193 194 curve448_precomputed_scalarmul(p, curve448_precomputed_base, 195 nonce_scalar_2); 196 curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p); 197 curve448_point_destroy(p); 198 curve448_scalar_destroy(nonce_scalar_2); 199 } 200 201 { 202 uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES]; 203 204 /* Compute the challenge */ 205 if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len) 206 || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point)) 207 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES) 208 || !EVP_DigestUpdate(hashctx, message, message_len) 209 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) 210 goto err; 211 212 curve448_scalar_decode_long(challenge_scalar, challenge, 213 sizeof(challenge)); 214 OPENSSL_cleanse(challenge, sizeof(challenge)); 215 } 216 217 curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar); 218 curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar); 219 220 OPENSSL_cleanse(signature, EDDSA_448_SIGNATURE_BYTES); 221 memcpy(signature, nonce_point, sizeof(nonce_point)); 222 curve448_scalar_encode(&signature[EDDSA_448_PUBLIC_BYTES], 223 challenge_scalar); 224 225 curve448_scalar_destroy(secret_scalar); 226 curve448_scalar_destroy(nonce_scalar); 227 curve448_scalar_destroy(challenge_scalar); 228 229 ret = C448_SUCCESS; 230 err: 231 EVP_MD_CTX_free(hashctx); 232 return ret; 233 } 234 235 c448_error_t c448_ed448_sign_prehash( 236 uint8_t signature[EDDSA_448_SIGNATURE_BYTES], 237 const uint8_t privkey[EDDSA_448_PRIVATE_BYTES], 238 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES], 239 const uint8_t hash[64], const uint8_t *context, 240 size_t context_len) 241 { 242 return c448_ed448_sign(signature, privkey, pubkey, hash, 64, 1, context, 243 context_len); 244 } 245 246 c448_error_t c448_ed448_verify( 247 const uint8_t signature[EDDSA_448_SIGNATURE_BYTES], 248 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES], 249 const uint8_t *message, size_t message_len, 250 uint8_t prehashed, const uint8_t *context, 251 uint8_t context_len) 252 { 253 curve448_point_t pk_point, r_point; 254 c448_error_t error; 255 curve448_scalar_t challenge_scalar; 256 curve448_scalar_t response_scalar; 257 /* Order in little endian format */ 258 static const uint8_t order[] = { 259 0xF3, 0x44, 0x58, 0xAB, 0x92, 0xC2, 0x78, 0x23, 0x55, 0x8F, 0xC5, 0x8D, 260 0x72, 0xC2, 0x6C, 0x21, 0x90, 0x36, 0xD6, 0xAE, 0x49, 0xDB, 0x4E, 0xC4, 261 0xE9, 0x23, 0xCA, 0x7C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 262 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 263 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x3F, 0x00 264 }; 265 int i; 266 267 /* 268 * Check that s (second 57 bytes of the sig) is less than the order. Both 269 * s and the order are in little-endian format. This can be done in 270 * variable time, since if this is not the case the signature if publicly 271 * invalid. 272 */ 273 for (i = EDDSA_448_PUBLIC_BYTES - 1; i >= 0; i--) { 274 if (signature[i + EDDSA_448_PUBLIC_BYTES] > order[i]) 275 return C448_FAILURE; 276 if (signature[i + EDDSA_448_PUBLIC_BYTES] < order[i]) 277 break; 278 } 279 if (i < 0) 280 return C448_FAILURE; 281 282 error = 283 curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey); 284 285 if (C448_SUCCESS != error) 286 return error; 287 288 error = 289 curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature); 290 if (C448_SUCCESS != error) 291 return error; 292 293 { 294 /* Compute the challenge */ 295 EVP_MD_CTX *hashctx = EVP_MD_CTX_new(); 296 uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES]; 297 298 if (hashctx == NULL 299 || !hash_init_with_dom(hashctx, prehashed, 0, context, 300 context_len) 301 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES) 302 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES) 303 || !EVP_DigestUpdate(hashctx, message, message_len) 304 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) { 305 EVP_MD_CTX_free(hashctx); 306 return C448_FAILURE; 307 } 308 309 EVP_MD_CTX_free(hashctx); 310 curve448_scalar_decode_long(challenge_scalar, challenge, 311 sizeof(challenge)); 312 OPENSSL_cleanse(challenge, sizeof(challenge)); 313 } 314 curve448_scalar_sub(challenge_scalar, curve448_scalar_zero, 315 challenge_scalar); 316 317 curve448_scalar_decode_long(response_scalar, 318 &signature[EDDSA_448_PUBLIC_BYTES], 319 EDDSA_448_PRIVATE_BYTES); 320 321 /* pk_point = -c(x(P)) + (cx + k)G = kG */ 322 curve448_base_double_scalarmul_non_secret(pk_point, 323 response_scalar, 324 pk_point, challenge_scalar); 325 return c448_succeed_if(curve448_point_eq(pk_point, r_point)); 326 } 327 328 c448_error_t c448_ed448_verify_prehash( 329 const uint8_t signature[EDDSA_448_SIGNATURE_BYTES], 330 const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES], 331 const uint8_t hash[64], const uint8_t *context, 332 uint8_t context_len) 333 { 334 return c448_ed448_verify(signature, pubkey, hash, 64, 1, context, 335 context_len); 336 } 337 338 int ED448_sign(uint8_t *out_sig, const uint8_t *message, size_t message_len, 339 const uint8_t public_key[57], const uint8_t private_key[57], 340 const uint8_t *context, size_t context_len) 341 { 342 return c448_ed448_sign(out_sig, private_key, public_key, message, 343 message_len, 0, context, context_len) 344 == C448_SUCCESS; 345 } 346 347 int ED448_verify(const uint8_t *message, size_t message_len, 348 const uint8_t signature[114], const uint8_t public_key[57], 349 const uint8_t *context, size_t context_len) 350 { 351 return c448_ed448_verify(signature, public_key, message, message_len, 0, 352 context, (uint8_t)context_len) == C448_SUCCESS; 353 } 354 355 int ED448ph_sign(uint8_t *out_sig, const uint8_t hash[64], 356 const uint8_t public_key[57], const uint8_t private_key[57], 357 const uint8_t *context, size_t context_len) 358 { 359 return c448_ed448_sign_prehash(out_sig, private_key, public_key, hash, 360 context, context_len) == C448_SUCCESS; 361 362 } 363 364 int ED448ph_verify(const uint8_t hash[64], const uint8_t signature[114], 365 const uint8_t public_key[57], const uint8_t *context, 366 size_t context_len) 367 { 368 return c448_ed448_verify_prehash(signature, public_key, hash, context, 369 (uint8_t)context_len) == C448_SUCCESS; 370 } 371 372 int ED448_public_from_private(uint8_t out_public_key[57], 373 const uint8_t private_key[57]) 374 { 375 return c448_ed448_derive_public_key(out_public_key, private_key) 376 == C448_SUCCESS; 377 } 378