crypto/ec/curve448/eddsa.c

   1 /*
   2  * Copyright 2017 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 <openssl/crypto.h>
  13 #include <openssl/evp.h>
  14
  15 #include "curve448_lcl.h"
  16 #include "word.h"
  17 #include "ed448.h"
  18 #include <string.h>
  19 #include "internal/numbers.h"
  20
  21 #define API_NAME "decaf_448"
  22
  23 #define NO_CONTEXT DECAF_EDDSA_448_SUPPORTS_CONTEXTLESS_SIGS
  24 #define EDDSA_USE_SIGMA_ISOGENY 0
  25 #define COFACTOR 4
  26 #define EDDSA_PREHASH_BYTES 64
  27
  28 #if NO_CONTEXT
  29 const uint8_t NO_CONTEXT_POINTS_HERE = 0;
  30 const uint8_t *const DECAF_ED448_NO_CONTEXT = &NO_CONTEXT_POINTS_HERE;
  31 #endif
  32
  33 /*
  34  * EDDSA_BASE_POINT_RATIO = 1 or 2 Because EdDSA25519 is not on E_d but on the
  35  * isogenous E_sigma_d, its base point is twice ours.
  36  */
  37 #define EDDSA_BASE_POINT_RATIO (1+EDDSA_USE_SIGMA_ISOGENY) /* TODO: remove */
  38
  39 static decaf_error_t oneshot_hash(uint8_t *out, size_t outlen,
  40                                   const uint8_t *in, size_t inlen)
  41 {
  42     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
  43
  44     if (hashctx == NULL)
  45         return DECAF_FAILURE;
  46
  47     if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL)
  48         || !EVP_DigestUpdate(hashctx, in, inlen)
  49         || !EVP_DigestFinalXOF(hashctx, out, outlen)) {
  50         EVP_MD_CTX_free(hashctx);
  51         return DECAF_FAILURE;
  52     }
  53
  54     EVP_MD_CTX_free(hashctx);
  55     return DECAF_SUCCESS;
  56 }
  57
  58 static void clamp(uint8_t secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES])
  59 {
  60     uint8_t hibit = (1 << 0) >> 1;
  61
  62     /* Blarg */
  63     secret_scalar_ser[0] &= -COFACTOR;
  64     if (hibit == 0) {
  65         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 1] = 0;
  66         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 2] |= 0x80;
  67     } else {
  68         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 1] &= hibit - 1;
  69         secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES - 1] |= hibit;
  70     }
  71 }
  72
  73 static decaf_error_t hash_init_with_dom(EVP_MD_CTX *hashctx,
  74                                         uint8_t prehashed,
  75                                         uint8_t for_prehash,
  76                                         const uint8_t *context,
  77                                         size_t context_len)
  78 {
  79     const char *dom_s = "SigEd448";
  80     uint8_t dom[2];
  81
  82     dom[0] = 2 + word_is_zero(prehashed) + word_is_zero(for_prehash);
  83     dom[1] = (uint8_t)context_len;
  84
  85     if (context_len > UINT8_MAX)
  86         return DECAF_FAILURE;
  87
  88 #if NO_CONTEXT
  89     if (context_len == 0 && context == DECAF_ED448_NO_CONTEXT) {
  90         (void)prehashed;
  91         (void)for_prehash;
  92         (void)context;
  93         (void)context_len;
  94         return DECAF_SUCCESS;
  95     }
  96 #endif
  97
  98     if (!EVP_DigestInit_ex(hashctx, EVP_shake256(), NULL)
  99         || !EVP_DigestUpdate(hashctx, dom_s, strlen(dom_s))
 100         || !EVP_DigestUpdate(hashctx, dom, sizeof(dom))
 101         || !EVP_DigestUpdate(hashctx, context, context_len))
 102         return DECAF_FAILURE;
 103
 104     return DECAF_SUCCESS;
 105 }
 106
 107 /* In this file because it uses the hash */
 108 decaf_error_t decaf_ed448_convert_private_key_to_x448(
 109                             uint8_t x[DECAF_X448_PRIVATE_BYTES],
 110                             const uint8_t ed [DECAF_EDDSA_448_PRIVATE_BYTES])
 111 {
 112     /* pass the private key through oneshot_hash function */
 113     /* and keep the first DECAF_X448_PRIVATE_BYTES bytes */
 114     return oneshot_hash(x,
 115                         DECAF_X448_PRIVATE_BYTES,
 116                         ed, DECAF_EDDSA_448_PRIVATE_BYTES);
 117 }
 118
 119 decaf_error_t decaf_ed448_derive_public_key(
 120                         uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 121                         const uint8_t privkey[DECAF_EDDSA_448_PRIVATE_BYTES])
 122 {
 123     /* only this much used for keygen */
 124     uint8_t secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES];
 125     curve448_scalar_t secret_scalar;
 126     unsigned int c;
 127     curve448_point_t p;
 128
 129     if (!oneshot_hash(secret_scalar_ser, sizeof(secret_scalar_ser), privkey,
 130                       DECAF_EDDSA_448_PRIVATE_BYTES))
 131         return DECAF_FAILURE;
 132
 133     clamp(secret_scalar_ser);
 134
 135     curve448_scalar_decode_long(secret_scalar, secret_scalar_ser,
 136                                 sizeof(secret_scalar_ser));
 137
 138     /*
 139      * Since we are going to mul_by_cofactor during encoding, divide by it
 140      * here. However, the EdDSA base point is not the same as the decaf base
 141      * point if the sigma isogeny is in use: the EdDSA base point is on
 142      * Etwist_d/(1-d) and the decaf base point is on Etwist_d, and when
 143      * converted it effectively picks up a factor of 2 from the isogenies.  So
 144      * we might start at 2 instead of 1.
 145      */
 146     for (c = 1; c < DECAF_448_EDDSA_ENCODE_RATIO; c <<= 1)
 147         curve448_scalar_halve(secret_scalar, secret_scalar);
 148
 149     curve448_precomputed_scalarmul(p, curve448_precomputed_base, secret_scalar);
 150
 151     curve448_point_mul_by_ratio_and_encode_like_eddsa(pubkey, p);
 152
 153     /* Cleanup */
 154     curve448_scalar_destroy(secret_scalar);
 155     curve448_point_destroy(p);
 156     OPENSSL_cleanse(secret_scalar_ser, sizeof(secret_scalar_ser));
 157
 158     return DECAF_SUCCESS;
 159 }
 160
 161 decaf_error_t decaf_ed448_sign(
 162                         uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 163                         const uint8_t privkey[DECAF_EDDSA_448_PRIVATE_BYTES],
 164                         const uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 165                         const uint8_t *message, size_t message_len,
 166                         uint8_t prehashed, const uint8_t *context,
 167                         size_t context_len)
 168 {
 169     curve448_scalar_t secret_scalar;
 170     EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
 171     decaf_error_t ret = DECAF_FAILURE;
 172     curve448_scalar_t nonce_scalar;
 173     uint8_t nonce_point[DECAF_EDDSA_448_PUBLIC_BYTES] = { 0 };
 174     unsigned int c;
 175     curve448_scalar_t challenge_scalar;
 176
 177     if (hashctx == NULL)
 178         return DECAF_FAILURE;
 179
 180     {
 181         /* Schedule the secret key */
 182         struct {
 183             uint8_t secret_scalar_ser[DECAF_EDDSA_448_PRIVATE_BYTES];
 184             uint8_t seed[DECAF_EDDSA_448_PRIVATE_BYTES];
 185         } __attribute__ ((packed)) expanded;
 186
 187         if (!oneshot_hash((uint8_t *)&expanded, sizeof(expanded), privkey,
 188                           DECAF_EDDSA_448_PRIVATE_BYTES))
 189             goto err;
 190         clamp(expanded.secret_scalar_ser);
 191         curve448_scalar_decode_long(secret_scalar, expanded.secret_scalar_ser,
 192                                     sizeof(expanded.secret_scalar_ser));
 193
 194         /* Hash to create the nonce */
 195         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
 196             || !EVP_DigestUpdate(hashctx, expanded.seed, sizeof(expanded.seed))
 197             || !EVP_DigestUpdate(hashctx, message, message_len)) {
 198             OPENSSL_cleanse(&expanded, sizeof(expanded));
 199             goto err;
 200         }
 201         OPENSSL_cleanse(&expanded, sizeof(expanded));
 202     }
 203
 204     /* Decode the nonce */
 205     {
 206         uint8_t nonce[2 * DECAF_EDDSA_448_PRIVATE_BYTES];
 207
 208         if (!EVP_DigestFinalXOF(hashctx, nonce, sizeof(nonce)))
 209             goto err;
 210         curve448_scalar_decode_long(nonce_scalar, nonce, sizeof(nonce));
 211         OPENSSL_cleanse(nonce, sizeof(nonce));
 212     }
 213
 214     {
 215         /* Scalarmul to create the nonce-point */
 216         curve448_scalar_t nonce_scalar_2;
 217         curve448_point_t p;
 218
 219         curve448_scalar_halve(nonce_scalar_2, nonce_scalar);
 220         for (c = 2; c < DECAF_448_EDDSA_ENCODE_RATIO; c <<= 1) {
 221             curve448_scalar_halve(nonce_scalar_2, nonce_scalar_2);
 222         }
 223
 224         curve448_precomputed_scalarmul(p, curve448_precomputed_base,
 225                                        nonce_scalar_2);
 226         curve448_point_mul_by_ratio_and_encode_like_eddsa(nonce_point, p);
 227         curve448_point_destroy(p);
 228         curve448_scalar_destroy(nonce_scalar_2);
 229     }
 230
 231     {
 232         uint8_t challenge[2 * DECAF_EDDSA_448_PRIVATE_BYTES];
 233
 234         /* Compute the challenge */
 235         if (!hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
 236             || !EVP_DigestUpdate(hashctx, nonce_point, sizeof(nonce_point))
 237             || !EVP_DigestUpdate(hashctx, pubkey, DECAF_EDDSA_448_PUBLIC_BYTES)
 238             || !EVP_DigestUpdate(hashctx, message, message_len)
 239             || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge)))
 240             goto err;
 241
 242         curve448_scalar_decode_long(challenge_scalar, challenge,
 243                                     sizeof(challenge));
 244         OPENSSL_cleanse(challenge, sizeof(challenge));
 245     }
 246
 247     curve448_scalar_mul(challenge_scalar, challenge_scalar, secret_scalar);
 248     curve448_scalar_add(challenge_scalar, challenge_scalar, nonce_scalar);
 249
 250     OPENSSL_cleanse(signature, DECAF_EDDSA_448_SIGNATURE_BYTES);
 251     memcpy(signature, nonce_point, sizeof(nonce_point));
 252     curve448_scalar_encode(&signature[DECAF_EDDSA_448_PUBLIC_BYTES],
 253                            challenge_scalar);
 254
 255     curve448_scalar_destroy(secret_scalar);
 256     curve448_scalar_destroy(nonce_scalar);
 257     curve448_scalar_destroy(challenge_scalar);
 258
 259     ret = DECAF_SUCCESS;
 260  err:
 261     EVP_MD_CTX_free(hashctx);
 262     return ret;
 263 }
 264
 265 decaf_error_t decaf_ed448_sign_prehash(uint8_t
 266                                        signature
 267                                        [DECAF_EDDSA_448_SIGNATURE_BYTES],
 268                                        const uint8_t
 269                                        privkey[DECAF_EDDSA_448_PRIVATE_BYTES],
 270                                        const uint8_t
 271                                        pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 272                                        const uint8_t hash[64],
 273                                        const uint8_t *context,
 274                                        size_t context_len)
 275 {
 276     return decaf_ed448_sign(signature, privkey, pubkey, hash, 64, 1, context,
 277                             context_len);
 278 }
 279
 280 decaf_error_t decaf_ed448_verify(const uint8_t
 281                                  signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 282                                  const uint8_t
 283                                  pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 284                                  const uint8_t *message, size_t message_len,
 285                                  uint8_t prehashed, const uint8_t *context,
 286                                  uint8_t context_len)
 287 {
 288     curve448_point_t pk_point, r_point;
 289     decaf_error_t error =
 290         curve448_point_decode_like_eddsa_and_mul_by_ratio(pk_point, pubkey);
 291     curve448_scalar_t challenge_scalar;
 292     curve448_scalar_t response_scalar;
 293     unsigned int c;
 294
 295     if (DECAF_SUCCESS != error)
 296         return error;
 297
 298     error =
 299         curve448_point_decode_like_eddsa_and_mul_by_ratio(r_point, signature);
 300     if (DECAF_SUCCESS != error)
 301         return error;
 302
 303     {
 304         /* Compute the challenge */
 305         EVP_MD_CTX *hashctx = EVP_MD_CTX_new();
 306         uint8_t challenge[2 * DECAF_EDDSA_448_PRIVATE_BYTES];
 307
 308         if (hashctx == NULL
 309             || !hash_init_with_dom(hashctx, prehashed, 0, context, context_len)
 310             || !EVP_DigestUpdate(hashctx, signature,
 311                                  DECAF_EDDSA_448_PUBLIC_BYTES)
 312             || !EVP_DigestUpdate(hashctx, pubkey, DECAF_EDDSA_448_PUBLIC_BYTES)
 313             || !EVP_DigestUpdate(hashctx, message, message_len)
 314             || !EVP_DigestFinalXOF(hashctx, challenge, sizeof(challenge))) {
 315             EVP_MD_CTX_free(hashctx);
 316             return DECAF_FAILURE;
 317         }
 318
 319         EVP_MD_CTX_free(hashctx);
 320         curve448_scalar_decode_long(challenge_scalar, challenge,
 321                                     sizeof(challenge));
 322         OPENSSL_cleanse(challenge, sizeof(challenge));
 323     }
 324     curve448_scalar_sub(challenge_scalar, curve448_scalar_zero,
 325                         challenge_scalar);
 326
 327     curve448_scalar_decode_long(response_scalar,
 328                                 &signature[DECAF_EDDSA_448_PUBLIC_BYTES],
 329                                 DECAF_EDDSA_448_PRIVATE_BYTES);
 330
 331     for (c = 1; c < DECAF_448_EDDSA_DECODE_RATIO; c <<= 1)
 332         curve448_scalar_add(response_scalar, response_scalar, response_scalar);
 333
 334     /* pk_point = -c(x(P)) + (cx + k)G = kG */
 335     curve448_base_double_scalarmul_non_secret(pk_point,
 336                                               response_scalar,
 337                                               pk_point, challenge_scalar);
 338     return decaf_succeed_if(curve448_point_eq(pk_point, r_point));
 339 }
 340
 341 decaf_error_t decaf_ed448_verify_prehash(
 342                     const uint8_t signature[DECAF_EDDSA_448_SIGNATURE_BYTES],
 343                     const uint8_t pubkey[DECAF_EDDSA_448_PUBLIC_BYTES],
 344                     const uint8_t hash[64], const uint8_t *context,
 345                     uint8_t context_len)
 346 {
 347     decaf_error_t ret;
 348
 349     ret = decaf_ed448_verify(signature, pubkey, hash, 64, 1, context,
 350                              context_len);
 351
 352     return ret;
 353 }
 354
 355 int ED448_sign(uint8_t *out_sig, const uint8_t *message, size_t message_len,
 356                const uint8_t public_key[57], const uint8_t private_key[57],
 357                const uint8_t *context, size_t context_len)
 358 {
 359
 360     return decaf_ed448_sign(out_sig, private_key, public_key, message,
 361                             message_len, 0, context, context_len)
 362         == DECAF_SUCCESS;
 363 }
 364
 365 int ED448_verify(const uint8_t *message, size_t message_len,
 366                  const uint8_t signature[114], const uint8_t public_key[57],
 367                  const uint8_t *context, size_t context_len)
 368 {
 369     return decaf_ed448_verify(signature, public_key, message, message_len, 0,
 370                               context, context_len) == DECAF_SUCCESS;
 371 }
 372
 373 int ED448ph_sign(uint8_t *out_sig, const uint8_t hash[64],
 374                  const uint8_t public_key[57], const uint8_t private_key[57],
 375                  const uint8_t *context, size_t context_len)
 376 {
 377     return decaf_ed448_sign_prehash(out_sig, private_key, public_key, hash,
 378                                     context, context_len) == DECAF_SUCCESS;
 379
 380 }
 381
 382 int ED448ph_verify(const uint8_t hash[64], const uint8_t signature[114],
 383                    const uint8_t public_key[57], const uint8_t *context,
 384                    size_t context_len)
 385 {
 386     return decaf_ed448_verify_prehash(signature, public_key, hash, context,
 387                                       context_len) == DECAF_SUCCESS;
 388 }
 389
 390 int ED448_public_from_private(uint8_t out_public_key[57],
 391                               const uint8_t private_key[57])
 392 {
 393     return decaf_ed448_derive_public_key(out_public_key, private_key)
 394         == DECAF_SUCCESS;
 395 }