/* Copyright (c) 2020, Google Inc.
 *
 * Permission to use, copy, modify, and/or distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */

// Some of this code is taken from the ref10 version of Ed25519 in SUPERCOP
// 20141124 (http://bench.cr.yp.to/supercop.html). That code is released as
// public domain. Other parts have been replaced to call into code generated by
// Fiat (https://github.com/mit-plv/fiat-crypto) in //third_party/fiat.
//
// The field functions are shared by Ed25519 and X25519 where possible.

#include <openssl/curve25519.h>

#include <string.h>

#include <openssl/mem.h>
#include <openssl/rand.h>
#include <openssl/sha.h>

#include "internal.h"
#include "../../internal.h"
#include "../cpucap/internal.h"

// X25519 [1] and Ed25519 [2] is an ECDHE protocol and signature scheme,
// respectively. This file contains an implementation of both using two
// different backends:
// 1) One backend is a pure C backend that should work on any platform.
// 2) The other backend is machine-optimized using s2n-bignum [3] as backend.
//
// [1]: https://datatracker.ietf.org/doc/html/rfc7748
// [2]: https://datatracker.ietf.org/doc/html/rfc8032
// [3]: https://github.com/awslabs/s2n-bignum
//
// "Clamping":
// Both X25519 and Ed25519 contain "clamping" steps; bit-twiddling, masking or
// setting specific bits. Generally, the bit-twiddling is to avoid common
// implementation errors and weak instances. Details can be found through the
// following two references:
// * https://mailarchive.ietf.org/arch/msg/cfrg/pt2bt3fGQbNF8qdEcorp-rJSJrc/
// * https://neilmadden.blog/2020/05/28/whats-the-curve25519-clamping-all-about
//
// Ed25519 domain and pre-hash functions:
// For Ed25519, dom2(F,C) is the empty string and PH the identify function,
// cf. rfc8032 5.1.

void ed25519_sha512(uint8_t out[SHA512_DIGEST_LENGTH],
  const void *input1, size_t len1, const void *input2, size_t len2,
  const void *input3, size_t len3) {

  SHA512_CTX hash_ctx;
  SHA512_Init(&hash_ctx);
  SHA512_Update(&hash_ctx, input1, len1);
  SHA512_Update(&hash_ctx, input2, len2);
  if (len3 != 0) {
    SHA512_Update(&hash_ctx, input3, len3);
  }
  SHA512_Final(out, &hash_ctx);
}

// Public interface functions

void ED25519_keypair_from_seed(uint8_t out_public_key[ED25519_PUBLIC_KEY_LEN],
  uint8_t out_private_key[ED25519_PRIVATE_KEY_LEN],
  const uint8_t seed[ED25519_SEED_LEN]) {
  // ED25519_keypair already ensures this with the same check, and is also the
  // function that is approved for FIPS (sets the indicator). Ensuring it here
  // for brevity.
  boringssl_ensure_eddsa_self_test();

  // Step: rfc8032 5.1.5.1
  // Compute SHA512(seed).
  uint8_t az[SHA512_DIGEST_LENGTH];
  SHA512(seed, ED25519_SEED_LEN, az);

  // Step: rfc8032 5.1.5.2
  az[0] &= 248; // 11111000_2
  az[31] &= 127; // 01111111_2
  az[31] |= 64; // 01000000_2

  // Step: rfc8032 5.1.5.[3,4]
  // Compute [az]B and encode public key to a 32 byte octet.
#if defined(CURVE25519_S2N_BIGNUM_CAPABLE)
  ed25519_public_key_from_hashed_seed_s2n_bignum(out_public_key, az);
#else
  ed25519_public_key_from_hashed_seed_nohw(out_public_key, az);
#endif

  // Encoded public key is a suffix in the private key. Avoids having to
  // generate the public key from the private key when signing.
  OPENSSL_STATIC_ASSERT(ED25519_PRIVATE_KEY_LEN == (ED25519_SEED_LEN + ED25519_PUBLIC_KEY_LEN), ed25519_parameter_length_mismatch)
  OPENSSL_memcpy(out_private_key, seed, ED25519_SEED_LEN);
  OPENSSL_memcpy(out_private_key + ED25519_SEED_LEN, out_public_key,
    ED25519_PUBLIC_KEY_LEN);
}

void ED25519_keypair(uint8_t out_public_key[ED25519_PUBLIC_KEY_LEN],
  uint8_t out_private_key[ED25519_PRIVATE_KEY_LEN]) {
  boringssl_ensure_eddsa_self_test();
  SET_DIT_AUTO_RESET;

  // Ed25519 key generation: rfc8032 5.1.5
  // Private key is 32 octets of random data.
  uint8_t seed[ED25519_SEED_LEN];
  RAND_bytes(seed, ED25519_SEED_LEN);

  // Public key generation is handled in a separate function. See function
  // description why this is useful.
  ED25519_keypair_from_seed(out_public_key, out_private_key, seed);
  OPENSSL_cleanse(seed, ED25519_SEED_LEN);

  FIPS_service_indicator_update_state();
}

int ED25519_sign(uint8_t out_sig[ED25519_SIGNATURE_LEN],
                 const uint8_t *message, size_t message_len,
                 const uint8_t private_key[ED25519_PRIVATE_KEY_LEN]) {
  boringssl_ensure_eddsa_self_test();
  return ED25519_sign_no_self_test(out_sig, message, message_len, private_key);
}

int ED25519_sign_no_self_test(uint8_t out_sig[ED25519_SIGNATURE_LEN],
                              const uint8_t *message, size_t message_len,
                              const uint8_t private_key[ED25519_PRIVATE_KEY_LEN]) {
  // NOTE: The documentation on this function says that it returns zero on
  // allocation failure. While that can't happen with the current
  // implementation, we want to reserve the ability to allocate in this
  // implementation in the future.

  // Ed25519 sign: rfc8032 5.1.6
  //
  // Step: rfc8032 5.1.6.1
  // This step is a repeat of rfc8032 5.1.5.[1,2].
  // seed = private_key[0:31]
  // A = private_key[32:61] (per 5.1.5.4)
  // Compute az = SHA512(seed).
  SET_DIT_AUTO_RESET;
  uint8_t az[SHA512_DIGEST_LENGTH];
  SHA512(private_key, ED25519_PRIVATE_KEY_SEED_LEN, az);
  // s = az[0:31]
  // prefix = az[32:61]
  az[0] &= 248; // 11111000_2
  az[31] &= 63; // 00111111_2
  az[31] |= 64; // 01000000_2

  // Step: rfc8032 5.1.6.2
  // Compute r = SHA512(prefix || message).
  uint8_t r[SHA512_DIGEST_LENGTH];
  ed25519_sha512(r, az + ED25519_PRIVATE_KEY_SEED_LEN,
    ED25519_PRIVATE_KEY_SEED_LEN, message, message_len, NULL, 0);

  // Step: rfc8032 5.1.6.[3,5,6,7]
#if defined(CURVE25519_S2N_BIGNUM_CAPABLE)
  ed25519_sign_s2n_bignum(out_sig, r, az,
      private_key + ED25519_PRIVATE_KEY_SEED_LEN, message, message_len);
#else
  ed25519_sign_nohw(out_sig, r, az,
      private_key + ED25519_PRIVATE_KEY_SEED_LEN, message, message_len);
#endif

  // The signature is computed from the private key, but is public.
  CONSTTIME_DECLASSIFY(out_sig, 64);

  FIPS_service_indicator_update_state();
  return 1;
}

int ED25519_verify(const uint8_t *message, size_t message_len,
                   const uint8_t signature[ED25519_SIGNATURE_LEN],
                   const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]) {
  boringssl_ensure_eddsa_self_test();
  return ED25519_verify_no_self_test(message, message_len, signature, public_key);
}

int ED25519_verify_no_self_test(const uint8_t *message, size_t message_len,
                                const uint8_t signature[ED25519_SIGNATURE_LEN],
                                const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]) {
  // Ed25519 verify: rfc8032 5.1.7

  // Step: rfc8032 5.1.7.1 (up to decoding the public key)
  // Decode signature as:
  //  - signature[0:31]: encoded point R, aliased to R_expected.
  //  - signature[32:61]: integer S.
  uint8_t R_expected[32];
  OPENSSL_memcpy(R_expected, signature, 32);
  uint8_t S[32];
  OPENSSL_memcpy(S, signature + 32, 32);

  // Per rfc8032 5.1.6.6
  // "the three most significant bits of the final octet are always zero"
  // 224 = 11100000_2
  if ((signature[63] & 224) != 0) {
    return 0;
  }

  // S must be in the range [0, order) in order to prevent signature
  // malleability. kOrder is the order of curve25519 in little-endian form.
  static const uint64_t kOrder[4] = {
    UINT64_C(0x5812631a5cf5d3ed),
    UINT64_C(0x14def9dea2f79cd6),
    0,
    UINT64_C(0x1000000000000000),
  };
  for (size_t i = 3;; i--) {
    uint64_t word = CRYPTO_load_u64_le(S + i * 8);
    if (word > kOrder[i]) {
      return 0;
    } else if (word < kOrder[i]) {
      break;
    } else if (i == 0) {
      return 0;
    }
  }

  // Step: rfc8032 5.1.7.[1,2,3]
  // Verification works by computing [S]B - [k]A' and comparing against R_expected.
  int res = 0;
  uint8_t R_computed_encoded[32];
#if defined(CURVE25519_S2N_BIGNUM_CAPABLE)
  res = ed25519_verify_s2n_bignum(R_computed_encoded, public_key, R_expected, S,
      message, message_len);
#else
  res = ed25519_verify_nohw(R_computed_encoded, public_key, R_expected, S,
      message, message_len);
#endif

  // Comparison [S]B - [k]A' =? R_expected. Short-circuits if decoding failed.
  res = (res == 1) && CRYPTO_memcmp(R_computed_encoded, R_expected,
                                    sizeof(R_computed_encoded)) == 0;
  if(res) {
    FIPS_service_indicator_update_state();
  }
  return res;
}

int ED25519_check_public_key(const uint8_t public_key[ED25519_PUBLIC_KEY_LEN]) {
#if defined(CURVE25519_S2N_BIGNUM_CAPABLE)
  return ed25519_check_public_key_s2n_bignum(public_key);
#else
  return ed25519_check_public_key_nohw(public_key);
#endif
}

void X25519_public_from_private(
  uint8_t out_public_value[X25519_PUBLIC_VALUE_LEN],
  const uint8_t private_key[X25519_PRIVATE_KEY_LEN]) {
  SET_DIT_AUTO_RESET;

#if defined(CURVE25519_S2N_BIGNUM_CAPABLE)
  x25519_public_from_private_s2n_bignum(out_public_value, private_key);
#else
  x25519_public_from_private_nohw(out_public_value, private_key);
#endif
    // The public key is derived from the private key, but it is public.
  CONSTTIME_DECLASSIFY(out_public_value, X25519_PUBLIC_VALUE_LEN);
}

void X25519_keypair(uint8_t out_public_value[X25519_PUBLIC_VALUE_LEN],
  uint8_t out_private_key[X25519_PRIVATE_KEY_LEN]) {
  SET_DIT_AUTO_RESET;

  RAND_bytes(out_private_key, X25519_PRIVATE_KEY_LEN);

  // All X25519 implementations should decode scalars correctly (see
  // https://tools.ietf.org/html/rfc7748#section-5). However, if an
  // implementation doesn't then it might interoperate with random keys a
  // fraction of the time because they'll, randomly, happen to be correctly
  // formed.
  //
  // Thus we do the opposite of the masking here to make sure that our private
  // keys are never correctly masked and so, hopefully, any incorrect
  // implementations are deterministically broken.
  //
  // This does not affect security because, although we're throwing away
  // entropy, a valid implementation of scalarmult should throw away the exact
  // same bits anyway.
  out_private_key[0] |= ~248;
  out_private_key[31] &= ~64;
  out_private_key[31] |= ~127;

  X25519_public_from_private(out_public_value, out_private_key);
}

int X25519(uint8_t out_shared_key[X25519_SHARED_KEY_LEN],
  const uint8_t private_key[X25519_PRIVATE_KEY_LEN],
  const uint8_t peer_public_value[X25519_PUBLIC_VALUE_LEN]) {

  SET_DIT_AUTO_RESET;
  static const uint8_t kZeros[X25519_SHARED_KEY_LEN] = {0};

#if defined(CURVE25519_S2N_BIGNUM_CAPABLE)
  x25519_scalar_mult_generic_s2n_bignum(out_shared_key, private_key, peer_public_value);
#else
    x25519_scalar_mult_generic_nohw(out_shared_key, private_key, peer_public_value);
#endif

  // The all-zero output results when the input is a point of small order.
  return constant_time_declassify_int(
             CRYPTO_memcmp(kZeros, out_shared_key, X25519_SHARED_KEY_LEN)) != 0;
}