crypto/ec/curve448/eddsa.c

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