/*

 * Simultaneous authentication of equals

 * Copyright (c) 2012-2016, Jouni Malinen <j@w1.fi>

 *

 * This software may be distributed under the terms of the BSD license.

 * See README for more details.

 */

#include "includes.h"

#include "common.h"

#include "common/defs.h"

#include "common/wpa_common.h"

#include "utils/const_time.h"

#include "crypto/crypto.h"

#include "crypto/sha256.h"

#include "crypto/sha384.h"

#include "crypto/sha512.h"

#include "crypto/random.h"

#include "crypto/dh_groups.h"

#include "ieee802_11_defs.h"

#include "dragonfly.h"

#include "sae.h"

int sae_set_group(struct sae_data *sae, int group)

{

  struct sae_temporary_data *tmp;

#ifdef CONFIG_TESTING_OPTIONS

  /* Allow all groups for testing purposes in non-production builds. */

#else /* CONFIG_TESTING_OPTIONS */

  if (!dragonfly_suitable_group(group, 0)) {

    wpa_printf(MSG_DEBUG, "SAE: Reject unsuitable group %d", group);

    return -1;

  }

#endif /* CONFIG_TESTING_OPTIONS */

  sae_clear_data(sae);

  tmp = sae->tmp = os_zalloc(sizeof(*tmp));

  if (tmp == NULL)

    return -1;

  /* First, check if this is an ECC group */

  tmp->ec = crypto_ec_init(group);

  if (tmp->ec) {

    wpa_printf(MSG_DEBUG, "SAE: Selecting supported ECC group %d",

         group);

    sae->group = group;

    tmp->prime_len = crypto_ec_prime_len(tmp->ec);

    tmp->prime = crypto_ec_get_prime(tmp->ec);

    tmp->order_len = crypto_ec_order_len(tmp->ec);

    tmp->order = crypto_ec_get_order(tmp->ec);

    return 0;

  }

  /* Not an ECC group, check FFC */

  tmp->dh = dh_groups_get(group);

  if (tmp->dh) {

    wpa_printf(MSG_DEBUG, "SAE: Selecting supported FFC group %d",

         group);

    sae->group = group;

    tmp->prime_len = tmp->dh->prime_len;

    if (tmp->prime_len > SAE_MAX_PRIME_LEN) {

      sae_clear_data(sae);

      return -1;

    }

    tmp->prime_buf = crypto_bignum_init_set(tmp->dh->prime,

              tmp->prime_len);

    if (tmp->prime_buf == NULL) {

      sae_clear_data(sae);

      return -1;

    }

    tmp->prime = tmp->prime_buf;

    tmp->order_len = tmp->dh->order_len;

    tmp->order_buf = crypto_bignum_init_set(tmp->dh->order,

              tmp->dh->order_len);

    if (tmp->order_buf == NULL) {

      sae_clear_data(sae);

      return -1;

    }

    tmp->order = tmp->order_buf;

    return 0;

  }

  /* Unsupported group */

  wpa_printf(MSG_DEBUG,

       "SAE: Group %d not supported by the crypto library", group);

  return -1;

}

void sae_clear_temp_data(struct sae_data *sae)

{

  struct sae_temporary_data *tmp;

  if (sae == NULL || sae->tmp == NULL)

    return;

  tmp = sae->tmp;

  crypto_ec_deinit(tmp->ec);

  crypto_bignum_deinit(tmp->prime_buf, 0);

  crypto_bignum_deinit(tmp->order_buf, 0);

  crypto_bignum_deinit(tmp->sae_rand, 1);

  crypto_bignum_deinit(tmp->pwe_ffc, 1);

  crypto_bignum_deinit(tmp->own_commit_scalar, 0);

  crypto_bignum_deinit(tmp->own_commit_element_ffc, 0);

  crypto_bignum_deinit(tmp->peer_commit_element_ffc, 0);

  crypto_ec_point_deinit(tmp->pwe_ecc, 1);

  crypto_ec_point_deinit(tmp->own_commit_element_ecc, 0);

  crypto_ec_point_deinit(tmp->peer_commit_element_ecc, 0);

  wpabuf_free(tmp->anti_clogging_token);

  wpabuf_free(tmp->own_rejected_groups);

  wpabuf_free(tmp->peer_rejected_groups);

  os_free(tmp->pw_id);

  os_free(tmp->parsed_pw_id);

  os_free(tmp->dec_pw_id);

  bin_clear_free(tmp, sizeof(*tmp));

  sae->tmp = NULL;

}

void sae_clear_data(struct sae_data *sae)

{

  unsigned int no_pw_id;

  if (sae == NULL)

    return;

  sae_clear_temp_data(sae);

  crypto_bignum_deinit(sae->peer_commit_scalar, 0);

  crypto_bignum_deinit(sae->peer_commit_scalar_accepted, 0);

  no_pw_id = sae->no_pw_id;

  os_memset(sae, 0, sizeof(*sae));

  sae->no_pw_id = no_pw_id;

}

static void sae_pwd_seed_key(const u8 *addr1, const u8 *addr2, u8 *key)

{

  wpa_printf(MSG_DEBUG, "SAE: PWE derivation - addr1=" MACSTR

       " addr2=" MACSTR, MAC2STR(addr1), MAC2STR(addr2));

  if (os_memcmp(addr1, addr2, ETH_ALEN) > 0) {

    os_memcpy(key, addr1, ETH_ALEN);

    os_memcpy(key + ETH_ALEN, addr2, ETH_ALEN);

  } else {

    os_memcpy(key, addr2, ETH_ALEN);

    os_memcpy(key + ETH_ALEN, addr1, ETH_ALEN);

  }

}

static int sae_test_pwd_seed_ecc(struct sae_data *sae, const u8 *pwd_seed,

         const u8 *prime, const u8 *qr, const u8 *qnr,

         u8 *pwd_value)

{

  struct crypto_bignum *y_sqr, *x_cand;

  int res;

  size_t bits;

  int cmp_prime;

  unsigned int in_range;

  wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-seed", pwd_seed, SHA256_MAC_LEN);

  /* pwd-value = KDF-z(pwd-seed, "SAE Hunting and Pecking", p) */

  bits = crypto_ec_prime_len_bits(sae->tmp->ec);

  if (sha256_prf_bits(pwd_seed, SHA256_MAC_LEN, "SAE Hunting and Pecking",

          prime, sae->tmp->prime_len, pwd_value, bits) < 0)

    return -1;

  if (bits % 8)

    buf_shift_right(pwd_value, sae->tmp->prime_len, 8 - bits % 8);

  wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-value",

      pwd_value, sae->tmp->prime_len);

  cmp_prime = const_time_memcmp(pwd_value, prime, sae->tmp->prime_len);

  /* Create a const_time mask for selection based on prf result

   * being smaller than prime. */

  in_range = const_time_fill_msb((unsigned int) cmp_prime);

  /* The algorithm description would skip the next steps if

   * cmp_prime >= 0 (return 0 here), but go through them regardless to

   * minimize externally observable differences in behavior. */

  x_cand = crypto_bignum_init_set(pwd_value, sae->tmp->prime_len);

  if (!x_cand)

    return -1;

  y_sqr = crypto_ec_point_compute_y_sqr(sae->tmp->ec, x_cand);

  crypto_bignum_deinit(x_cand, 1);

  if (!y_sqr)

    return -1;

  res = dragonfly_is_quadratic_residue_blind(sae->tmp->ec, qr, qnr,

               y_sqr);

  crypto_bignum_deinit(y_sqr, 1);

  if (res < 0)

    return res;

  return const_time_select_int(in_range, res, 0);

}

/* Returns -1 on fatal failure, 0 if PWE cannot be derived from the provided

 * pwd-seed, or 1 if a valid PWE was derived from pwd-seed. */

static int sae_test_pwd_seed_ffc(struct sae_data *sae, const u8 *pwd_seed,

         struct crypto_bignum *pwe)

{

  u8 pwd_value[SAE_MAX_PRIME_LEN];

  size_t bits = sae->tmp->prime_len * 8;

  u8 exp[1];

  struct crypto_bignum *a, *b = NULL;

  int res, is_val;

  u8 pwd_value_valid;

  wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-seed", pwd_seed, SHA256_MAC_LEN);

  /* pwd-value = KDF-z(pwd-seed, "SAE Hunting and Pecking", p) */

  if (sha256_prf_bits(pwd_seed, SHA256_MAC_LEN, "SAE Hunting and Pecking",

          sae->tmp->dh->prime, sae->tmp->prime_len, pwd_value,

          bits) < 0)

    return -1;

  wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-value", pwd_value,

      sae->tmp->prime_len);

  /* Check whether pwd-value < p */

  res = const_time_memcmp(pwd_value, sae->tmp->dh->prime,

        sae->tmp->prime_len);

  /* pwd-value >= p is invalid, so res is < 0 for the valid cases and

   * the negative sign can be used to fill the mask for constant time

   * selection */

  pwd_value_valid = const_time_fill_msb(res);

  /* If pwd-value >= p, force pwd-value to be < p and perform the

   * calculations anyway to hide timing difference. The derived PWE will

   * be ignored in that case. */

  pwd_value[0] = const_time_select_u8(pwd_value_valid, pwd_value[0], 0);

  /* PWE = pwd-value^((p-1)/r) modulo p */

  res = -1;

  a = crypto_bignum_init_set(pwd_value, sae->tmp->prime_len);

  if (!a)

    goto fail;

  /* This is an optimization based on the used group that does not depend

   * on the password in any way, so it is fine to use separate branches

   * for this step without constant time operations. */

  if (sae->tmp->dh->safe_prime) {

    /*

     * r = (p-1)/2 for the group used here, so this becomes:

     * PWE = pwd-value^2 modulo p

     */

    exp[0] = 2;

    b = crypto_bignum_init_set(exp, sizeof(exp));

  } else {

    /* Calculate exponent: (p-1)/r */

    exp[0] = 1;

    b = crypto_bignum_init_set(exp, sizeof(exp));

    if (b == NULL ||

        crypto_bignum_sub(sae->tmp->prime, b, b) < 0 ||

        crypto_bignum_div(b, sae->tmp->order, b) < 0)

      goto fail;

  }

  if (!b)

    goto fail;

  res = crypto_bignum_exptmod(a, b, sae->tmp->prime, pwe);

  if (res < 0)

    goto fail;

  /* There were no fatal errors in calculations, so determine the return

   * value using constant time operations. We get here for number of

   * invalid cases which are cleared here after having performed all the

   * computation. PWE is valid if pwd-value was less than prime and

   * PWE > 1. Start with pwd-value check first and then use constant time

   * operations to clear res to 0 if PWE is 0 or 1.

   */

  res = const_time_select_u8(pwd_value_valid, 1, 0);

  is_val = crypto_bignum_is_zero(pwe);

  res = const_time_select_u8(const_time_is_zero(is_val), res, 0);

  is_val = crypto_bignum_is_one(pwe);

  res = const_time_select_u8(const_time_is_zero(is_val), res, 0);

fail:

  crypto_bignum_deinit(a, 1);

  crypto_bignum_deinit(b, 1);

  return res;

}

static int sae_derive_pwe_ecc(struct sae_data *sae, const u8 *addr1,

            const u8 *addr2, const u8 *password,

            size_t password_len)

{

  u8 counter, k;

  u8 addrs[2 * ETH_ALEN];

  const u8 *addr[2];

  size_t len[2];

  u8 *stub_password, *tmp_password;

  int pwd_seed_odd = 0;

  u8 prime[SAE_MAX_ECC_PRIME_LEN];

  size_t prime_len;

  struct crypto_bignum *x = NULL, *y = NULL, *qr = NULL, *qnr = NULL;

  u8 x_bin[SAE_MAX_ECC_PRIME_LEN];

  u8 x_cand_bin[SAE_MAX_ECC_PRIME_LEN];

  u8 qr_bin[SAE_MAX_ECC_PRIME_LEN];

  u8 qnr_bin[SAE_MAX_ECC_PRIME_LEN];

  u8 x_y[2 * SAE_MAX_ECC_PRIME_LEN];

  int res = -1;

  u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*

           * mask */

  unsigned int is_eq;

  os_memset(x_bin, 0, sizeof(x_bin));

  stub_password = os_malloc(password_len);

  tmp_password = os_malloc(password_len);

  if (!stub_password || !tmp_password ||

      random_get_bytes(stub_password, password_len) < 0)

    goto fail;

  prime_len = sae->tmp->prime_len;

  if (crypto_bignum_to_bin(sae->tmp->prime, prime, sizeof(prime),

         prime_len) < 0)

    goto fail;

  /*

   * Create a random quadratic residue (qr) and quadratic non-residue

   * (qnr) modulo p for blinding purposes during the loop.

   */

  if (dragonfly_get_random_qr_qnr(sae->tmp->prime, &qr, &qnr) < 0 ||

      crypto_bignum_to_bin(qr, qr_bin, sizeof(qr_bin), prime_len) < 0 ||

      crypto_bignum_to_bin(qnr, qnr_bin, sizeof(qnr_bin), prime_len) < 0)

    goto fail;

  wpa_hexdump_ascii_key(MSG_DEBUG, "SAE: password",

            password, password_len);

  /*

   * H(salt, ikm) = HMAC-SHA256(salt, ikm)

   * base = password

   * pwd-seed = H(MAX(STA-A-MAC, STA-B-MAC) || MIN(STA-A-MAC, STA-B-MAC),

   *              base || counter)

   */

  sae_pwd_seed_key(addr1, addr2, addrs);

  addr[0] = tmp_password;

  len[0] = password_len;

  addr[1] = &counter;

  len[1] = sizeof(counter);

  /*

   * Continue for at least k iterations to protect against side-channel

   * attacks that attempt to determine the number of iterations required

   * in the loop.

   */

  k = dragonfly_min_pwe_loop_iter(sae->group);

  for (counter = 1; counter <= k || !found; counter++) {

    u8 pwd_seed[SHA256_MAC_LEN];

    if (counter > 200) {

      /* This should not happen in practice */

      wpa_printf(MSG_DEBUG, "SAE: Failed to derive PWE");

      break;

    }

    wpa_printf(MSG_DEBUG, "SAE: counter = %03u", counter);

    const_time_select_bin(found, stub_password, password,

              password_len, tmp_password);

    if (hmac_sha256_vector(addrs, sizeof(addrs), 2,

               addr, len, pwd_seed) < 0) {

      wpa_printf(MSG_INFO,

           "SAE: hmac_sha256_vector() failed - cannot derive PWE");

      break;

    }

    res = sae_test_pwd_seed_ecc(sae, pwd_seed,

              prime, qr_bin, qnr_bin, x_cand_bin);

    const_time_select_bin(found, x_bin, x_cand_bin, prime_len,

              x_bin);

    pwd_seed_odd = const_time_select_u8(

      found, pwd_seed_odd,

      pwd_seed[SHA256_MAC_LEN - 1] & 0x01);

    os_memset(pwd_seed, 0, sizeof(pwd_seed));

    if (res < 0)

      goto fail;

    /* Need to minimize differences in handling res == 0 and 1 here

     * to avoid differences in timing and instruction cache access,

     * so use const_time_select_*() to make local copies of the

     * values based on whether this loop iteration was the one that

     * found the pwd-seed/x. */

    /* found is 0 or 0xff here and res is 0 or 1. Bitwise OR of them

     * (with res converted to 0/0xff) handles this in constant time.

     */

    found |= res * 0xff;

    wpa_printf(MSG_DEBUG, "SAE: pwd-seed result %d found=0x%02x",

         res, found);

  }

  if (!found) {

    wpa_printf(MSG_DEBUG, "SAE: Could not generate PWE");

    res = -1;

    goto fail;

  }

  x = crypto_bignum_init_set(x_bin, prime_len);

  if (!x) {

    res = -1;

    goto fail;

  }

  /* y = sqrt(x^3 + ax + b) mod p

   * if LSB(save) == LSB(y): PWE = (x, y)

   * else: PWE = (x, p - y)

   *

   * Calculate y and the two possible values for PWE and after that,

   * use constant time selection to copy the correct alternative.

   */

  y = crypto_ec_point_compute_y_sqr(sae->tmp->ec, x);

  if (!y ||

      dragonfly_sqrt(sae->tmp->ec, y, y) < 0 ||

      crypto_bignum_to_bin(y, x_y, SAE_MAX_ECC_PRIME_LEN,

         prime_len) < 0 ||

      crypto_bignum_sub(sae->tmp->prime, y, y) < 0 ||

      crypto_bignum_to_bin(y, x_y + SAE_MAX_ECC_PRIME_LEN,

         SAE_MAX_ECC_PRIME_LEN, prime_len) < 0) {

    wpa_printf(MSG_DEBUG, "SAE: Could not solve y");

    goto fail;

  }

  is_eq = const_time_eq(pwd_seed_odd, x_y[prime_len - 1] & 0x01);

  const_time_select_bin(is_eq, x_y, x_y + SAE_MAX_ECC_PRIME_LEN,

            prime_len, x_y + prime_len);

  os_memcpy(x_y, x_bin, prime_len);

  wpa_hexdump_key(MSG_DEBUG, "SAE: PWE", x_y, 2 * prime_len);

  crypto_ec_point_deinit(sae->tmp->pwe_ecc, 1);

  sae->tmp->pwe_ecc = crypto_ec_point_from_bin(sae->tmp->ec, x_y);

  if (!sae->tmp->pwe_ecc) {

    wpa_printf(MSG_DEBUG, "SAE: Could not generate PWE");

    res = -1;

  }

fail:

  forced_memzero(x_y, sizeof(x_y));

  crypto_bignum_deinit(qr, 0);

  crypto_bignum_deinit(qnr, 0);

  crypto_bignum_deinit(y, 1);

  os_free(stub_password);

  bin_clear_free(tmp_password, password_len);

  crypto_bignum_deinit(x, 1);

  os_memset(x_bin, 0, sizeof(x_bin));

  os_memset(x_cand_bin, 0, sizeof(x_cand_bin));

  return res;

}

static int sae_derive_pwe_ffc(struct sae_data *sae, const u8 *addr1,

            const u8 *addr2, const u8 *password,

            size_t password_len)

{

  u8 counter, k, sel_counter = 0;

  u8 addrs[2 * ETH_ALEN];

  const u8 *addr[2];

  size_t len[2];

  u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*

           * mask */

  u8 mask;

  struct crypto_bignum *pwe;

  size_t prime_len = sae->tmp->prime_len;

  u8 *pwe_buf;

  crypto_bignum_deinit(sae->tmp->pwe_ffc, 1);

  sae->tmp->pwe_ffc = NULL;

  /* Allocate a buffer to maintain selected and candidate PWE for constant

   * time selection. */

  pwe_buf = os_zalloc(prime_len * 2);

  pwe = crypto_bignum_init();

  if (!pwe_buf || !pwe)

    goto fail;

  wpa_hexdump_ascii_key(MSG_DEBUG, "SAE: password",

            password, password_len);

  /*

   * H(salt, ikm) = HMAC-SHA256(salt, ikm)

   * pwd-seed = H(MAX(STA-A-MAC, STA-B-MAC) || MIN(STA-A-MAC, STA-B-MAC),

   *              password || counter)

   */

  sae_pwd_seed_key(addr1, addr2, addrs);

  addr[0] = password;

  len[0] = password_len;

  addr[1] = &counter;

  len[1] = sizeof(counter);

  k = dragonfly_min_pwe_loop_iter(sae->group);

  for (counter = 1; counter <= k || !found; counter++) {

    u8 pwd_seed[SHA256_MAC_LEN];

    int res;

    if (counter > 200) {

      /* This should not happen in practice */

      wpa_printf(MSG_DEBUG, "SAE: Failed to derive PWE");

      break;

    }

    wpa_printf(MSG_DEBUG, "SAE: counter = %02u", counter);

    if (hmac_sha256_vector(addrs, sizeof(addrs), 2,

               addr, len, pwd_seed) < 0)

      break;

    res = sae_test_pwd_seed_ffc(sae, pwd_seed, pwe);

    /* res is -1 for fatal failure, 0 if a valid PWE was not found,

     * or 1 if a valid PWE was found. */

    if (res < 0)

      break;

    /* Store the candidate PWE into the second half of pwe_buf and

     * the selected PWE in the beginning of pwe_buf using constant

     * time selection. */

    if (crypto_bignum_to_bin(pwe, pwe_buf + prime_len, prime_len,

           prime_len) < 0)

      break;

    const_time_select_bin(found, pwe_buf, pwe_buf + prime_len,

              prime_len, pwe_buf);

    sel_counter = const_time_select_u8(found, sel_counter, counter);

    mask = const_time_eq_u8(res, 1);

    found = const_time_select_u8(found, found, mask);

  }

  if (!found)

    goto fail;

  wpa_printf(MSG_DEBUG, "SAE: Use PWE from counter = %02u", sel_counter);

  sae->tmp->pwe_ffc = crypto_bignum_init_set(pwe_buf, prime_len);

fail:

  crypto_bignum_deinit(pwe, 1);

  bin_clear_free(pwe_buf, prime_len * 2);

  return sae->tmp->pwe_ffc ? 0 : -1;

}

static int hkdf_extract(size_t hash_len, const u8 *salt, size_t salt_len,

      size_t num_elem, const u8 *addr[], const size_t len[],

      u8 *prk)

{

  if (hash_len == 32)

    return hmac_sha256_vector(salt, salt_len, num_elem, addr, len,

            prk);

#ifdef CONFIG_SHA384

  if (hash_len == 48)

    return hmac_sha384_vector(salt, salt_len, num_elem, addr, len,

            prk);

#endif /* CONFIG_SHA384 */

#ifdef CONFIG_SHA512

  if (hash_len == 64)

    return hmac_sha512_vector(salt, salt_len, num_elem, addr, len,

            prk);

#endif /* CONFIG_SHA512 */

  return -1;

}

static int hkdf_expand(size_t hash_len, const u8 *prk, size_t prk_len,

           const char *info, u8 *okm, size_t okm_len)

{

  size_t info_len = os_strlen(info);

  if (hash_len == 32)

    return hmac_sha256_kdf(prk, prk_len, NULL,

               (const u8 *) info, info_len,

               okm, okm_len);

#ifdef CONFIG_SHA384

  if (hash_len == 48)

    return hmac_sha384_kdf(prk, prk_len, NULL,

               (const u8 *) info, info_len,

               okm, okm_len);

#endif /* CONFIG_SHA384 */

#ifdef CONFIG_SHA512

  if (hash_len == 64)

    return hmac_sha512_kdf(prk, prk_len, NULL,

               (const u8 *) info, info_len,

               okm, okm_len);

#endif /* CONFIG_SHA512 */

  return -1;

}

static int sswu_curve_param(int group, int *z)

{

  switch (group) {

  case 19:

    *z = -10;

    return 0;

  case 20:

    *z = -12;

    return 0;

  case 21:

    *z = -4;

    return 0;

  case 25:

  case 29:

    *z = -5;

    return 0;

  case 26:

    *z = 31;

    return 0;

  case 28:

    *z = -2;

    return 0;

  case 30:

    *z = 7;

    return 0;

  default:

    return -1;

  }

}

static void debug_print_bignum(const char *title, const struct crypto_bignum *a,

             size_t prime_len)

{

  u8 *bin;

  bin = os_malloc(prime_len);

  if (bin && crypto_bignum_to_bin(a, bin, prime_len, prime_len) >= 0)

    wpa_hexdump_key(MSG_DEBUG, title, bin, prime_len);

  else

    wpa_printf(MSG_DEBUG, "Could not print bignum (%s)", title);

  bin_clear_free(bin, prime_len);

}

static struct crypto_ec_point * sswu(struct crypto_ec *ec, int group,

             const struct crypto_bignum *u)

{

  int z_int;

  const struct crypto_bignum *a, *b, *prime;

  struct crypto_bignum *u2, *t1, *t2, *z, *t, *zero, *one, *two, *three,

    *x1a, *x1b, *y = NULL;

  struct crypto_bignum *x1 = NULL, *x2, *gx1, *gx2, *v = NULL;

  unsigned int m_is_zero, is_qr, is_eq;

  size_t prime_len;

  u8 bin[SAE_MAX_ECC_PRIME_LEN];

  u8 bin1[SAE_MAX_ECC_PRIME_LEN];

  u8 bin2[SAE_MAX_ECC_PRIME_LEN];

  u8 x_y[2 * SAE_MAX_ECC_PRIME_LEN];

  struct crypto_ec_point *p = NULL;

  if (sswu_curve_param(group, &z_int) < 0)

    return NULL;

  prime = crypto_ec_get_prime(ec);

  prime_len = crypto_ec_prime_len(ec);

  a = crypto_ec_get_a(ec);

  b = crypto_ec_get_b(ec);

  u2 = crypto_bignum_init();

  t1 = crypto_bignum_init();

  t2 = crypto_bignum_init();

  z = crypto_bignum_init_uint(abs(z_int));

  t = crypto_bignum_init();

  zero = crypto_bignum_init_uint(0);

  one = crypto_bignum_init_uint(1);

  two = crypto_bignum_init_uint(2);

  three = crypto_bignum_init_uint(3);

  x1a = crypto_bignum_init();

  x1b = crypto_bignum_init();

  x2 = crypto_bignum_init();

  gx1 = crypto_bignum_init();

  gx2 = crypto_bignum_init();

  if (!u2 || !t1 || !t2 || !z || !t || !zero || !one || !two || !three ||

      !x1a || !x1b || !x2 || !gx1 || !gx2)

    goto fail;

  if (z_int < 0 && crypto_bignum_sub(prime, z, z) < 0)

    goto fail;

  /* m = z^2 * u^4 + z * u^2 */

  /* --> tmp = z * u^2, m = tmp^2 + tmp */

  /* u2 = u^2

   * t1 = z * u2

   * t2 = t1^2

   * m = t1 = t1 + t2 */

  if (crypto_bignum_sqrmod(u, prime, u2) < 0 ||

      crypto_bignum_mulmod(z, u2, prime, t1) < 0 ||

      crypto_bignum_sqrmod(t1, prime, t2) < 0 ||

      crypto_bignum_addmod(t1, t2, prime, t1) < 0)

    goto fail;

  debug_print_bignum("SSWU: m", t1, prime_len);

  /* l = CEQ(m, 0)

   * t = CSEL(l, 0, inverse(m); where inverse(x) is calculated as

   * x^(p-2) modulo p which will handle m == 0 case correctly */

  /* TODO: Make sure crypto_bignum_is_zero() is constant time */

  m_is_zero = const_time_eq(crypto_bignum_is_zero(t1), 1);

  /* t = m^(p-2) modulo p */

  if (crypto_bignum_sub(prime, two, t2) < 0 ||

      crypto_bignum_exptmod(t1, t2, prime, t) < 0)

    goto fail;

  debug_print_bignum("SSWU: t", t, prime_len);

  /* b / (z * a) */

  if (crypto_bignum_mulmod(z, a, prime, t1) < 0 ||

      crypto_bignum_inverse(t1, prime, t1) < 0 ||

      crypto_bignum_mulmod(b, t1, prime, x1a) < 0)

    goto fail;

  debug_print_bignum("SSWU: x1a = b / (z * a)", x1a, prime_len);

  /* (-b/a) * (1 + t) */

  if (crypto_bignum_sub(prime, b, t1) < 0 ||

      crypto_bignum_inverse(a, prime, t2) < 0 ||

      crypto_bignum_mulmod(t1, t2, prime, t1) < 0 ||

      crypto_bignum_addmod(one, t, prime, t2) < 0 ||

      crypto_bignum_mulmod(t1, t2, prime, x1b) < 0)

    goto fail;

  debug_print_bignum("SSWU: x1b = (-b/a) * (1 + t)", x1b, prime_len);

  /* x1 = CSEL(CEQ(m, 0), x1a, x1b) */

  if (crypto_bignum_to_bin(x1a, bin1, sizeof(bin1), prime_len) < 0 ||

      crypto_bignum_to_bin(x1b, bin2, sizeof(bin2), prime_len) < 0)

    goto fail;

  const_time_select_bin(m_is_zero, bin1, bin2, prime_len, bin);

  x1 = crypto_bignum_init_set(bin, prime_len);

  if (!x1)

    goto fail;

  debug_print_bignum("SSWU: x1 = CSEL(l, x1a, x1b)", x1, prime_len);

  /* gx1 = x1^3 + a * x1 + b */

  if (crypto_bignum_exptmod(x1, three, prime, t1) < 0 ||

      crypto_bignum_mulmod(a, x1, prime, t2) < 0 ||

      crypto_bignum_addmod(t1, t2, prime, t1) < 0 ||

      crypto_bignum_addmod(t1, b, prime, gx1) < 0)

    goto fail;

  debug_print_bignum("SSWU: gx1 = x1^3 + a * x1 + b", gx1, prime_len);

  /* x2 = z * u^2 * x1 */

  if (crypto_bignum_mulmod(z, u2, prime, t1) < 0 ||

      crypto_bignum_mulmod(t1, x1, prime, x2) < 0)

    goto fail;

  debug_print_bignum("SSWU: x2 = z * u^2 * x1", x2, prime_len);

  /* gx2 = x2^3 + a * x2 + b */

  if (crypto_bignum_exptmod(x2, three, prime, t1) < 0 ||

      crypto_bignum_mulmod(a, x2, prime, t2) < 0 ||

      crypto_bignum_addmod(t1, t2, prime, t1) < 0 ||

      crypto_bignum_addmod(t1, b, prime, gx2) < 0)

    goto fail;

  debug_print_bignum("SSWU: gx2 = x2^3 + a * x2 + b", gx2, prime_len);

  /* l = gx1 is a quadratic residue modulo p

   * --> gx1^((p-1)/2) modulo p is zero or one */

  if (crypto_bignum_sub(prime, one, t1) < 0 ||

      crypto_bignum_rshift(t1, 1, t1) < 0 ||

      crypto_bignum_exptmod(gx1, t1, prime, t1) < 0)

    goto fail;

  debug_print_bignum("SSWU: gx1^((p-1)/2) modulo p", t1, prime_len);

  is_qr = const_time_eq(crypto_bignum_is_zero(t1) |

            crypto_bignum_is_one(t1), 1);

  /* v = CSEL(l, gx1, gx2) */

  if (crypto_bignum_to_bin(gx1, bin1, sizeof(bin1), prime_len) < 0 ||

      crypto_bignum_to_bin(gx2, bin2, sizeof(bin2), prime_len) < 0)

    goto fail;

  const_time_select_bin(is_qr, bin1, bin2, prime_len, bin);

  v = crypto_bignum_init_set(bin, prime_len);

  if (!v)

    goto fail;

  debug_print_bignum("SSWU: v = CSEL(l, gx1, gx2)", v, prime_len);

  /* x = CSEL(l, x1, x2) */

  if (crypto_bignum_to_bin(x1, bin1, sizeof(bin1), prime_len) < 0 ||

      crypto_bignum_to_bin(x2, bin2, sizeof(bin2), prime_len) < 0)

    goto fail;

  const_time_select_bin(is_qr, bin1, bin2, prime_len, x_y);

  wpa_hexdump_key(MSG_DEBUG, "SSWU: x = CSEL(l, x1, x2)", x_y, prime_len);

  /* y = sqrt(v) */

  y = crypto_bignum_init();

  if (!y || dragonfly_sqrt(ec, v, y) < 0)

    goto fail;

  debug_print_bignum("SSWU: y = sqrt(v)", y, prime_len);

  /* l = CEQ(LSB(u), LSB(y)) */

  if (crypto_bignum_to_bin(u, bin1, sizeof(bin1), prime_len) < 0 ||

      crypto_bignum_to_bin(y, bin2, sizeof(bin2), prime_len) < 0)

    goto fail;

  is_eq = const_time_eq(bin1[prime_len - 1] & 0x01,

            bin2[prime_len - 1] & 0x01);

  /* P = CSEL(l, (x,y), (x, p-y)) */

  if (crypto_bignum_sub(prime, y, t1) < 0)

    goto fail;

  debug_print_bignum("SSWU: p - y", t1, prime_len);

  if (crypto_bignum_to_bin(y, bin1, sizeof(bin1), prime_len) < 0 ||

      crypto_bignum_to_bin(t1, bin2, sizeof(bin2), prime_len) < 0)

    goto fail;

  const_time_select_bin(is_eq, bin1, bin2, prime_len, &x_y[prime_len]);

  /* output P */

  wpa_hexdump_key(MSG_DEBUG, "SSWU: P.x", x_y, prime_len);

  wpa_hexdump_key(MSG_DEBUG, "SSWU: P.y", &x_y[prime_len], prime_len);

  p = crypto_ec_point_from_bin(ec, x_y);

fail:

  crypto_bignum_deinit(u2, 1);

  crypto_bignum_deinit(t1, 1);

  crypto_bignum_deinit(t2, 1);

  crypto_bignum_deinit(z, 0);

  crypto_bignum_deinit(t, 1);

  crypto_bignum_deinit(x1a, 1);

  crypto_bignum_deinit(x1b, 1);

  crypto_bignum_deinit(x1, 1);

  crypto_bignum_deinit(x2, 1);

  crypto_bignum_deinit(gx1, 1);

  crypto_bignum_deinit(gx2, 1);

  crypto_bignum_deinit(y, 1);

  crypto_bignum_deinit(v, 1);

  crypto_bignum_deinit(zero, 0);

  crypto_bignum_deinit(one, 0);

  crypto_bignum_deinit(two, 0);

  crypto_bignum_deinit(three, 0);

  forced_memzero(bin, sizeof(bin));

  forced_memzero(bin1, sizeof(bin1));

  forced_memzero(bin2, sizeof(bin2));

  forced_memzero(x_y, sizeof(x_y));

  return p;

}

static int sae_pwd_seed(size_t hash_len, const u8 *ssid, size_t ssid_len,

      const u8 *password, size_t password_len,

      const u8 *identifier, size_t identifier_len,

      u8 *pwd_seed)

{

  const u8 *addr[2];

  size_t len[2];

  size_t num_elem;

  /* pwd-seed = HKDF-Extract(ssid, password [ || identifier ]) */

  addr[0] = password;

  len[0] = password_len;

  num_elem = 1;

  wpa_hexdump_ascii(MSG_DEBUG, "SAE: SSID", ssid, ssid_len);

  wpa_hexdump_ascii_key(MSG_DEBUG, "SAE: password",

            password, password_len);

  if (identifier) {

    wpa_hexdump_ascii(MSG_DEBUG, "SAE: password identifier",

          identifier, identifier_len);

    addr[num_elem] = (const u8 *) identifier;

    len[num_elem] = identifier_len;

    num_elem++;

  }

  if (hkdf_extract(hash_len, ssid, ssid_len, num_elem, addr, len,

       pwd_seed) < 0)

    return -1;

  wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-seed", pwd_seed, hash_len);

  return 0;

}

size_t sae_ecc_prime_len_2_hash_len(size_t prime_len)

{

  if (prime_len <= 256 / 8)

    return 32;

  if (prime_len <= 384 / 8)

    return 48;

  return 64;

}

static struct crypto_ec_point *

sae_derive_pt_ecc(struct crypto_ec *ec, int group,

      const u8 *ssid, size_t ssid_len,

      const u8 *password, size_t password_len,

      const u8 *identifier, size_t identifier_len)

{

  u8 pwd_seed[64];

  u8 pwd_value[SAE_MAX_ECC_PRIME_LEN * 2];

  size_t pwd_value_len, hash_len, prime_len;

  const struct crypto_bignum *prime;

  struct crypto_bignum *bn = NULL;

  struct crypto_ec_point *p1 = NULL, *p2 = NULL, *pt = NULL;

  prime = crypto_ec_get_prime(ec);

  prime_len = crypto_ec_prime_len(ec);

  if (prime_len > SAE_MAX_ECC_PRIME_LEN)

    goto fail;

  hash_len = sae_ecc_prime_len_2_hash_len(prime_len);

  /* len = olen(p) + ceil(olen(p)/2) */

  pwd_value_len = prime_len + (prime_len + 1) / 2;

  if (sae_pwd_seed(hash_len, ssid, ssid_len, password, password_len,

       identifier, identifier_len, pwd_seed) < 0)

    goto fail;