chromium/third_party/boringssl/src/crypto/curve25519/curve25519.c

/* 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 <assert.h>
#include <string.h>

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

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

// Various pre-computed constants.
#include "./curve25519_tables.h"

#if defined(BORINGSSL_HAS_UINT128)
#include "../../third_party/fiat/curve25519_64.h"
#elif defined(OPENSSL_64_BIT)
#include "../../third_party/fiat/curve25519_64_msvc.h"
#else
#include "../../third_party/fiat/curve25519_32.h"
#endif


// Low-level intrinsic operations

static uint64_t load_3(const uint8_t *in) { … }

static uint64_t load_4(const uint8_t *in) { … }


// Field operations.

#if defined(OPENSSL_64_BIT)

fe_limb_t;
#define FE_NUM_LIMBS …

// assert_fe asserts that |f| satisfies bounds:
//
//  [[0x0 ~> 0x8cccccccccccc],
//   [0x0 ~> 0x8cccccccccccc],
//   [0x0 ~> 0x8cccccccccccc],
//   [0x0 ~> 0x8cccccccccccc],
//   [0x0 ~> 0x8cccccccccccc]]
//
// See comments in curve25519_64.h for which functions use these bounds for
// inputs or outputs.
#define assert_fe(f) …

// assert_fe_loose asserts that |f| satisfies bounds:
//
//  [[0x0 ~> 0x1a666666666664],
//   [0x0 ~> 0x1a666666666664],
//   [0x0 ~> 0x1a666666666664],
//   [0x0 ~> 0x1a666666666664],
//   [0x0 ~> 0x1a666666666664]]
//
// See comments in curve25519_64.h for which functions use these bounds for
// inputs or outputs.
#define assert_fe_loose(f) …

#else

typedef uint32_t fe_limb_t;
#define FE_NUM_LIMBS …

// assert_fe asserts that |f| satisfies bounds:
//
//  [[0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333],
//   [0x0 ~> 0x4666666], [0x0 ~> 0x2333333]]
//
// See comments in curve25519_32.h for which functions use these bounds for
// inputs or outputs.
#define assert_fe …

// assert_fe_loose asserts that |f| satisfies bounds:
//
//  [[0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999],
//   [0x0 ~> 0xd333332], [0x0 ~> 0x6999999]]
//
// See comments in curve25519_32.h for which functions use these bounds for
// inputs or outputs.
#define assert_fe_loose …

#endif  // OPENSSL_64_BIT

static_assert;

static void fe_frombytes_strict(fe *h, const uint8_t s[32]) { … }

static void fe_frombytes(fe *h, const uint8_t s[32]) { … }

static void fe_tobytes(uint8_t s[32], const fe *f) { … }

// h = 0
static void fe_0(fe *h) { … }

static void fe_loose_0(fe_loose *h) { … }

// h = 1
static void fe_1(fe *h) { … }

static void fe_loose_1(fe_loose *h) { … }

// h = f + g
// Can overlap h with f or g.
static void fe_add(fe_loose *h, const fe *f, const fe *g) { … }

// h = f - g
// Can overlap h with f or g.
static void fe_sub(fe_loose *h, const fe *f, const fe *g) { … }

static void fe_carry(fe *h, const fe_loose* f) { … }

static void fe_mul_impl(fe_limb_t out[FE_NUM_LIMBS],
                        const fe_limb_t in1[FE_NUM_LIMBS],
                        const fe_limb_t in2[FE_NUM_LIMBS]) { … }

static void fe_mul_ltt(fe_loose *h, const fe *f, const fe *g) { … }

static void fe_mul_llt(fe_loose *h, const fe_loose *f, const fe *g) { … }

static void fe_mul_ttt(fe *h, const fe *f, const fe *g) { … }

static void fe_mul_tlt(fe *h, const fe_loose *f, const fe *g) { … }

static void fe_mul_ttl(fe *h, const fe *f, const fe_loose *g) { … }

static void fe_mul_tll(fe *h, const fe_loose *f, const fe_loose *g) { … }

static void fe_sq_tl(fe *h, const fe_loose *f) { … }

static void fe_sq_tt(fe *h, const fe *f) { … }

// Replace (f,g) with (g,f) if b == 1;
// replace (f,g) with (f,g) if b == 0.
//
// Preconditions: b in {0,1}.
static void fe_cswap(fe *f, fe *g, fe_limb_t b) { … }

static void fe_mul121666(fe *h, const fe_loose *f) { … }

// h = -f
static void fe_neg(fe_loose *h, const fe *f) { … }

// Replace (f,g) with (g,g) if b == 1;
// replace (f,g) with (f,g) if b == 0.
//
// Preconditions: b in {0,1}.
static void fe_cmov(fe_loose *f, const fe_loose *g, fe_limb_t b) { … }

// h = f
static void fe_copy(fe *h, const fe *f) { … }

static void fe_copy_lt(fe_loose *h, const fe *f) { … }

static void fe_loose_invert(fe *out, const fe_loose *z) { … }

static void fe_invert(fe *out, const fe *z) { … }

// return 0 if f == 0
// return 1 if f != 0
static int fe_isnonzero(const fe_loose *f) { … }

// return 1 if f is in {1,3,5,...,q-2}
// return 0 if f is in {0,2,4,...,q-1}
static int fe_isnegative(const fe *f) { … }

static void fe_sq2_tt(fe *h, const fe *f) { … }

static void fe_pow22523(fe *out, const fe *z) { … }


// Group operations.

void x25519_ge_tobytes(uint8_t s[32], const ge_p2 *h) { … }

static void ge_p3_tobytes(uint8_t s[32], const ge_p3 *h) { … }

int x25519_ge_frombytes_vartime(ge_p3 *h, const uint8_t s[32]) { … }

static void ge_p2_0(ge_p2 *h) { … }

static void ge_p3_0(ge_p3 *h) { … }

static void ge_cached_0(ge_cached *h) { … }

static void ge_precomp_0(ge_precomp *h) { … }

// r = p
static void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) { … }

// r = p
void x25519_ge_p3_to_cached(ge_cached *r, const ge_p3 *p) { … }

// r = p
void x25519_ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) { … }

// r = p
void x25519_ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) { … }

// r = p
static void ge_p1p1_to_cached(ge_cached *r, const ge_p1p1 *p) { … }

// r = 2 * p
static void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) { … }

// r = 2 * p
static void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) { … }

// r = p + q
static void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) { … }

// r = p - q
static void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) { … }

// r = p + q
void x25519_ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) { … }

// r = p - q
void x25519_ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) { … }

static void cmov(ge_precomp *t, const ge_precomp *u, uint8_t b) { … }

void x25519_ge_scalarmult_small_precomp(
    ge_p3 *h, const uint8_t a[32], const uint8_t precomp_table[15 * 2 * 32]) { … }

#if defined(OPENSSL_SMALL)

void x25519_ge_scalarmult_base(ge_p3 *h, const uint8_t a[32]) { … }

#else

static void table_select(ge_precomp *t, const int pos, const signed char b) {
  uint8_t bnegative = constant_time_msb_w(b);
  uint8_t babs = b - ((bnegative & b) << 1);

  uint8_t t_bytes[3][32] = {
      {constant_time_is_zero_w(b) & 1}, {constant_time_is_zero_w(b) & 1}, {0}};
#if defined(__clang__) // materialize for vectorization, 6% speedup
  __asm__("" : "+m" (t_bytes) : /*no inputs*/);
#endif
  static_assert(sizeof(t_bytes) == sizeof(k25519Precomp[pos][0]), "");
  for (int i = 0; i < 8; i++) {
    constant_time_conditional_memxor(t_bytes, k25519Precomp[pos][i],
                                     sizeof(t_bytes),
                                     constant_time_eq_w(babs, 1 + i));
  }

  fe yplusx, yminusx, xy2d;
  fe_frombytes_strict(&yplusx, t_bytes[0]);
  fe_frombytes_strict(&yminusx, t_bytes[1]);
  fe_frombytes_strict(&xy2d, t_bytes[2]);

  fe_copy_lt(&t->yplusx, &yplusx);
  fe_copy_lt(&t->yminusx, &yminusx);
  fe_copy_lt(&t->xy2d, &xy2d);

  ge_precomp minust;
  fe_copy_lt(&minust.yplusx, &yminusx);
  fe_copy_lt(&minust.yminusx, &yplusx);
  fe_neg(&minust.xy2d, &xy2d);
  cmov(t, &minust, bnegative>>7);
}

// h = a * B
// where a = a[0]+256*a[1]+...+256^31 a[31]
// B is the Ed25519 base point (x,4/5) with x positive.
//
// Preconditions:
//   a[31] <= 127
void x25519_ge_scalarmult_base(ge_p3 *h, const uint8_t a[32]) {
#if defined(BORINGSSL_FE25519_ADX)
  if (CRYPTO_is_BMI1_capable() && CRYPTO_is_BMI2_capable() &&
      CRYPTO_is_ADX_capable()) {
    uint8_t t[4][32];
    x25519_ge_scalarmult_base_adx(t, a);
    fiat_25519_from_bytes(h->X.v, t[0]);
    fiat_25519_from_bytes(h->Y.v, t[1]);
    fiat_25519_from_bytes(h->Z.v, t[2]);
    fiat_25519_from_bytes(h->T.v, t[3]);
    return;
  }
#endif
  signed char e[64];
  signed char carry;
  ge_p1p1 r;
  ge_p2 s;
  ge_precomp t;
  int i;

  for (i = 0; i < 32; ++i) {
    e[2 * i + 0] = (a[i] >> 0) & 15;
    e[2 * i + 1] = (a[i] >> 4) & 15;
  }
  // each e[i] is between 0 and 15
  // e[63] is between 0 and 7

  carry = 0;
  for (i = 0; i < 63; ++i) {
    e[i] += carry;
    carry = e[i] + 8;
    carry >>= 4;
    e[i] -= carry << 4;
  }
  e[63] += carry;
  // each e[i] is between -8 and 8

  ge_p3_0(h);
  for (i = 1; i < 64; i += 2) {
    table_select(&t, i / 2, e[i]);
    ge_madd(&r, h, &t);
    x25519_ge_p1p1_to_p3(h, &r);
  }

  ge_p3_dbl(&r, h);
  x25519_ge_p1p1_to_p2(&s, &r);
  ge_p2_dbl(&r, &s);
  x25519_ge_p1p1_to_p2(&s, &r);
  ge_p2_dbl(&r, &s);
  x25519_ge_p1p1_to_p2(&s, &r);
  ge_p2_dbl(&r, &s);
  x25519_ge_p1p1_to_p3(h, &r);

  for (i = 0; i < 64; i += 2) {
    table_select(&t, i / 2, e[i]);
    ge_madd(&r, h, &t);
    x25519_ge_p1p1_to_p3(h, &r);
  }
}

#endif

static void cmov_cached(ge_cached *t, ge_cached *u, uint8_t b) { … }

// r = scalar * A.
// where a = a[0]+256*a[1]+...+256^31 a[31].
void x25519_ge_scalarmult(ge_p2 *r, const uint8_t *scalar, const ge_p3 *A) { … }

static void slide(signed char *r, const uint8_t *a) { … }

// r = a * A + b * B
// where a = a[0]+256*a[1]+...+256^31 a[31].
// and b = b[0]+256*b[1]+...+256^31 b[31].
// B is the Ed25519 base point (x,4/5) with x positive.
static void ge_double_scalarmult_vartime(ge_p2 *r, const uint8_t *a,
                                         const ge_p3 *A, const uint8_t *b) { … }

// int64_lshift21 returns |a << 21| but is defined when shifting bits into the
// sign bit. This works around a language flaw in C.
static inline int64_t int64_lshift21(int64_t a) { … }

// The set of scalars is \Z/l
// where l = 2^252 + 27742317777372353535851937790883648493.

// Input:
//   s[0]+256*s[1]+...+256^63*s[63] = s
//
// Output:
//   s[0]+256*s[1]+...+256^31*s[31] = s mod l
//   where l = 2^252 + 27742317777372353535851937790883648493.
//   Overwrites s in place.
void x25519_sc_reduce(uint8_t s[64]) { … }

// Input:
//   a[0]+256*a[1]+...+256^31*a[31] = a
//   b[0]+256*b[1]+...+256^31*b[31] = b
//   c[0]+256*c[1]+...+256^31*c[31] = c
//
// Output:
//   s[0]+256*s[1]+...+256^31*s[31] = (ab+c) mod l
//   where l = 2^252 + 27742317777372353535851937790883648493.
static void sc_muladd(uint8_t *s, const uint8_t *a, const uint8_t *b,
                      const uint8_t *c) { … }

void ED25519_keypair(uint8_t out_public_key[32], uint8_t out_private_key[64]) { … }

int ED25519_sign(uint8_t out_sig[64], const uint8_t *message,
                 size_t message_len, const uint8_t private_key[64]) { … }

int ED25519_verify(const uint8_t *message, size_t message_len,
                   const uint8_t signature[64], const uint8_t public_key[32]) { … }

void ED25519_keypair_from_seed(uint8_t out_public_key[32],
                               uint8_t out_private_key[64],
                               const uint8_t seed[32]) { … }


static void x25519_scalar_mult_generic(uint8_t out[32],
                                       const uint8_t scalar[32],
                                       const uint8_t point[32]) { … }

static void x25519_scalar_mult(uint8_t out[32], const uint8_t scalar[32],
                               const uint8_t point[32]) { … }

void X25519_keypair(uint8_t out_public_value[32], uint8_t out_private_key[32]) { … }

int X25519(uint8_t out_shared_key[32], const uint8_t private_key[32],
           const uint8_t peer_public_value[32]) { … }

void X25519_public_from_private(uint8_t out_public_value[32],
                                const uint8_t private_key[32]) { … }