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