crypto/ec/curve448/eddsa.c

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