crypto/ec/curve448/eddsa.c

   1 /*
   2  * Copyright 2017-2023 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     /* 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
  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
 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
 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
 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 c448_error_t
 276 ossl_c448_ed448_verify(
 277                     OSSL_LIB_CTX *ctx,
 278                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
 279                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
 280                     const uint8_t *message, size_t message_len,
 281                     uint8_t prehashed, const uint8_t *context,
 282                     uint8_t context_len, const char *propq)
 283 {
 284     curve448_point_t pk_point, r_point;
 285     c448_error_t error;
 286     curve448_scalar_t challenge_scalar;
 287     curve448_scalar_t response_scalar;
 288     /* Order in little endian format */
 289     static const uint8_t order[] = {
 290         0xF3, 0x44, 0x58, 0xAB, 0x92, 0xC2, 0x78, 0x23, 0x55, 0x8F, 0xC5, 0x8D,
 291         0x72, 0xC2, 0x6C, 0x21, 0x90, 0x36, 0xD6, 0xAE, 0x49, 0xDB, 0x4E, 0xC4,
 292         0xE9, 0x23, 0xCA, 0x7C, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 293         0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
 294         0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0x3F, 0x00
 295     };
 296     int i;
 297
 298     /*
 299      * Check that s (second 57 bytes of the sig) is less than the order. Both
 300      * s and the order are in little-endian format. This can be done in
 301      * variable time, since if this is not the case the signature if publicly
 302      * invalid.
 303      */
 304     for (i = EDDSA_448_PUBLIC_BYTES - 1; i >= 0; i--) {
 305         if (signature[i + EDDSA_448_PUBLIC_BYTES] > order[i])
 306             return C448_FAILURE;
 307         if (signature[i + EDDSA_448_PUBLIC_BYTES] < order[i])
 308             break;
 309     }
 310     if (i < 0)
 311         return C448_FAILURE;
 312
 313     error =
 314         ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
 315
 316     if (C448_SUCCESS != error)
 317         return error;
 318
 319     error =
 320         ossl_curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
 321     if (C448_SUCCESS != error)
 322         return error;
 323
 324     {
 325         /* Compute the challenge */
 326         EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
 327         uint8_t challenge[2 * EDDSA_448_PRIVATE_BYTES];
 328
 329         if (hashctx == NULL
 330                 || !hash_init_with_dom(ctx, hashctx, prehashed, 0, context,
 331                                        context_len, propq)
 332                 || !EVP_DigestUpdate(hashctx, signature, EDDSA_448_PUBLIC_BYTES)
 333                 || !EVP_DigestUpdate(hashctx, pubkey, EDDSA_448_PUBLIC_BYTES)
 334                 || !EVP_DigestUpdate(hashctx, message, message_len)
 335                 || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
 336             EVP_MD_CTX_free(hashctx);
 337             return C448_FAILURE;
 338         }
 339
 340         EVP_MD_CTX_free(hashctx);
 341         ossl_curve448_scalar_decode_long(challenge_scalar, challenge,
 342                                          sizeof(challenge));
 343         OPENSSL_cleanse(challenge, sizeof(challenge));
 344     }
 345     ossl_curve448_scalar_sub(challenge_scalar, ossl_curve448_scalar_zero,
 346                              challenge_scalar);
 347
 348     ossl_curve448_scalar_decode_long(response_scalar,
 349                                      &signature[EDDSA_448_PUBLIC_BYTES],
 350                                      EDDSA_448_PRIVATE_BYTES);
 351
 352     /* pk_point = -c(x(P)) + (cx + k)G = kG */
 353     ossl_curve448_base_double_scalarmul_non_secret(pk_point,
 354                                                    response_scalar,
 355                                                    pk_point, challenge_scalar);
 356     return c448_succeed_if(ossl_curve448_point_eq(pk_point, r_point));
 357 }
 358
 359 c448_error_t
 360 ossl_c448_ed448_verify_prehash(
 361                     OSSL_LIB_CTX *ctx,
 362                     const uint8_t signature[EDDSA_448_SIGNATURE_BYTES],
 363                     const uint8_t pubkey[EDDSA_448_PUBLIC_BYTES],
 364                     const uint8_t hash[64], const uint8_t *context,
 365                     uint8_t context_len, const char *propq)
 366 {
 367     return ossl_c448_ed448_verify(ctx, signature, pubkey, hash, 64, 1, context,
 368                                   context_len, propq);
 369 }
 370
 371 int
 372 ossl_ed448_sign(OSSL_LIB_CTX *ctx, uint8_t *out_sig,
 373                 const uint8_t *message, size_t message_len,
 374                 const uint8_t public_key[57], const uint8_t private_key[57],
 375                 const uint8_t *context, size_t context_len,
 376                 const uint8_t phflag, const char *propq)
 377 {
 378     return ossl_c448_ed448_sign(ctx, out_sig, private_key, public_key, message,
 379                                 message_len, phflag, context, context_len,
 380                                 propq) == C448_SUCCESS;
 381 }
 382
 383 int
 384 ossl_ed448_verify(OSSL_LIB_CTX *ctx,
 385                   const uint8_t *message, size_t message_len,
 386                   const uint8_t signature[114], const uint8_t public_key[57],
 387                   const uint8_t *context, size_t context_len,
 388                   const uint8_t phflag, const char *propq)
 389 {
 390     return ossl_c448_ed448_verify(ctx, signature, public_key, message,
 391                                   message_len, phflag, context, (uint8_t)context_len,
 392                                   propq) == C448_SUCCESS;
 393 }
 394
 395 int
 396 ossl_ed448_public_from_private(OSSL_LIB_CTX *ctx, uint8_t out_public_key[57],
 397                                const uint8_t private_key[57], const char *propq)
 398 {
 399     return ossl_c448_ed448_derive_public_key(ctx, out_public_key, private_key,
 400                                              propq) == C448_SUCCESS;
 401 }