contrib/wpa/src/common/sae.c

   1 /*
   2  * Simultaneous authentication of equals
   3  * Copyright (c) 2012-2016, Jouni Malinen <j@w1.fi>
   4  *
   5  * This software may be distributed under the terms of the BSD license.
   6  * See README for more details.
   7  */
   8
   9 #include "includes.h"
  10
  11 #include "common.h"
  12 #include "utils/const_time.h"
  13 #include "crypto/crypto.h"
  14 #include "crypto/sha256.h"
  15 #include "crypto/random.h"
  16 #include "crypto/dh_groups.h"
  17 #include "ieee802_11_defs.h"
  18 #include "sae.h"
  19
  20
  21 static int sae_suitable_group(int group)
  22 {
  23 #ifdef CONFIG_TESTING_OPTIONS
  24         /* Allow all groups for testing purposes in non-production builds. */
  25         return 1;
  26 #else /* CONFIG_TESTING_OPTIONS */
  27         /* Enforce REVmd rules on which SAE groups are suitable for production
  28          * purposes: FFC groups whose prime is >= 3072 bits and ECC groups
  29          * defined over a prime field whose prime is >= 256 bits. Furthermore,
  30          * ECC groups defined over a characteristic 2 finite field and ECC
  31          * groups with a co-factor greater than 1 are not suitable. */
  32         return group == 19 || group == 20 || group == 21 ||
  33                 group == 28 || group == 29 || group == 30 ||
  34                 group == 15 || group == 16 || group == 17 || group == 18;
  35 #endif /* CONFIG_TESTING_OPTIONS */
  36 }
  37
  38
  39 int sae_set_group(struct sae_data *sae, int group)
  40 {
  41         struct sae_temporary_data *tmp;
  42
  43         if (!sae_suitable_group(group)) {
  44                 wpa_printf(MSG_DEBUG, "SAE: Reject unsuitable group %d", group);
  45                 return -1;
  46         }
  47
  48         sae_clear_data(sae);
  49         tmp = sae->tmp = os_zalloc(sizeof(*tmp));
  50         if (tmp == NULL)
  51                 return -1;
  52
  53         /* First, check if this is an ECC group */
  54         tmp->ec = crypto_ec_init(group);
  55         if (tmp->ec) {
  56                 wpa_printf(MSG_DEBUG, "SAE: Selecting supported ECC group %d",
  57                            group);
  58                 sae->group = group;
  59                 tmp->prime_len = crypto_ec_prime_len(tmp->ec);
  60                 tmp->prime = crypto_ec_get_prime(tmp->ec);
  61                 tmp->order = crypto_ec_get_order(tmp->ec);
  62                 return 0;
  63         }
  64
  65         /* Not an ECC group, check FFC */
  66         tmp->dh = dh_groups_get(group);
  67         if (tmp->dh) {
  68                 wpa_printf(MSG_DEBUG, "SAE: Selecting supported FFC group %d",
  69                            group);
  70                 sae->group = group;
  71                 tmp->prime_len = tmp->dh->prime_len;
  72                 if (tmp->prime_len > SAE_MAX_PRIME_LEN) {
  73                         sae_clear_data(sae);
  74                         return -1;
  75                 }
  76
  77                 tmp->prime_buf = crypto_bignum_init_set(tmp->dh->prime,
  78                                                         tmp->prime_len);
  79                 if (tmp->prime_buf == NULL) {
  80                         sae_clear_data(sae);
  81                         return -1;
  82                 }
  83                 tmp->prime = tmp->prime_buf;
  84
  85                 tmp->order_buf = crypto_bignum_init_set(tmp->dh->order,
  86                                                         tmp->dh->order_len);
  87                 if (tmp->order_buf == NULL) {
  88                         sae_clear_data(sae);
  89                         return -1;
  90                 }
  91                 tmp->order = tmp->order_buf;
  92
  93                 return 0;
  94         }
  95
  96         /* Unsupported group */
  97         wpa_printf(MSG_DEBUG,
  98                    "SAE: Group %d not supported by the crypto library", group);
  99         return -1;
 100 }
 101
 102
 103 void sae_clear_temp_data(struct sae_data *sae)
 104 {
 105         struct sae_temporary_data *tmp;
 106         if (sae == NULL || sae->tmp == NULL)
 107                 return;
 108         tmp = sae->tmp;
 109         crypto_ec_deinit(tmp->ec);
 110         crypto_bignum_deinit(tmp->prime_buf, 0);
 111         crypto_bignum_deinit(tmp->order_buf, 0);
 112         crypto_bignum_deinit(tmp->sae_rand, 1);
 113         crypto_bignum_deinit(tmp->pwe_ffc, 1);
 114         crypto_bignum_deinit(tmp->own_commit_scalar, 0);
 115         crypto_bignum_deinit(tmp->own_commit_element_ffc, 0);
 116         crypto_bignum_deinit(tmp->peer_commit_element_ffc, 0);
 117         crypto_ec_point_deinit(tmp->pwe_ecc, 1);
 118         crypto_ec_point_deinit(tmp->own_commit_element_ecc, 0);
 119         crypto_ec_point_deinit(tmp->peer_commit_element_ecc, 0);
 120         wpabuf_free(tmp->anti_clogging_token);
 121         os_free(tmp->pw_id);
 122         bin_clear_free(tmp, sizeof(*tmp));
 123         sae->tmp = NULL;
 124 }
 125
 126
 127 void sae_clear_data(struct sae_data *sae)
 128 {
 129         if (sae == NULL)
 130                 return;
 131         sae_clear_temp_data(sae);
 132         crypto_bignum_deinit(sae->peer_commit_scalar, 0);
 133         os_memset(sae, 0, sizeof(*sae));
 134 }
 135
 136
 137 static void buf_shift_right(u8 *buf, size_t len, size_t bits)
 138 {
 139         size_t i;
 140         for (i = len - 1; i > 0; i--)
 141                 buf[i] = (buf[i - 1] << (8 - bits)) | (buf[i] >> bits);
 142         buf[0] >>= bits;
 143 }
 144
 145
 146 static struct crypto_bignum * sae_get_rand(struct sae_data *sae)
 147 {
 148         u8 val[SAE_MAX_PRIME_LEN];
 149         int iter = 0;
 150         struct crypto_bignum *bn = NULL;
 151         int order_len_bits = crypto_bignum_bits(sae->tmp->order);
 152         size_t order_len = (order_len_bits + 7) / 8;
 153
 154         if (order_len > sizeof(val))
 155                 return NULL;
 156
 157         for (;;) {
 158                 if (iter++ > 100 || random_get_bytes(val, order_len) < 0)
 159                         return NULL;
 160                 if (order_len_bits % 8)
 161                         buf_shift_right(val, order_len, 8 - order_len_bits % 8);
 162                 bn = crypto_bignum_init_set(val, order_len);
 163                 if (bn == NULL)
 164                         return NULL;
 165                 if (crypto_bignum_is_zero(bn) ||
 166                     crypto_bignum_is_one(bn) ||
 167                     crypto_bignum_cmp(bn, sae->tmp->order) >= 0) {
 168                         crypto_bignum_deinit(bn, 0);
 169                         continue;
 170                 }
 171                 break;
 172         }
 173
 174         os_memset(val, 0, order_len);
 175         return bn;
 176 }
 177
 178
 179 static struct crypto_bignum * sae_get_rand_and_mask(struct sae_data *sae)
 180 {
 181         crypto_bignum_deinit(sae->tmp->sae_rand, 1);
 182         sae->tmp->sae_rand = sae_get_rand(sae);
 183         if (sae->tmp->sae_rand == NULL)
 184                 return NULL;
 185         return sae_get_rand(sae);
 186 }
 187
 188
 189 static void sae_pwd_seed_key(const u8 *addr1, const u8 *addr2, u8 *key)
 190 {
 191         wpa_printf(MSG_DEBUG, "SAE: PWE derivation - addr1=" MACSTR
 192                    " addr2=" MACSTR, MAC2STR(addr1), MAC2STR(addr2));
 193         if (os_memcmp(addr1, addr2, ETH_ALEN) > 0) {
 194                 os_memcpy(key, addr1, ETH_ALEN);
 195                 os_memcpy(key + ETH_ALEN, addr2, ETH_ALEN);
 196         } else {
 197                 os_memcpy(key, addr2, ETH_ALEN);
 198                 os_memcpy(key + ETH_ALEN, addr1, ETH_ALEN);
 199         }
 200 }
 201
 202
 203 static struct crypto_bignum *
 204 get_rand_1_to_p_1(const u8 *prime, size_t prime_len, size_t prime_bits,
 205                   int *r_odd)
 206 {
 207         for (;;) {
 208                 struct crypto_bignum *r;
 209                 u8 tmp[SAE_MAX_ECC_PRIME_LEN];
 210
 211                 if (random_get_bytes(tmp, prime_len) < 0)
 212                         break;
 213                 if (prime_bits % 8)
 214                         buf_shift_right(tmp, prime_len, 8 - prime_bits % 8);
 215                 if (os_memcmp(tmp, prime, prime_len) >= 0)
 216                         continue;
 217                 r = crypto_bignum_init_set(tmp, prime_len);
 218                 if (!r)
 219                         break;
 220                 if (crypto_bignum_is_zero(r)) {
 221                         crypto_bignum_deinit(r, 0);
 222                         continue;
 223                 }
 224
 225                 *r_odd = tmp[prime_len - 1] & 0x01;
 226                 return r;
 227         }
 228
 229         return NULL;
 230 }
 231
 232
 233 static int is_quadratic_residue_blind(struct sae_data *sae,
 234                                       const u8 *prime, size_t bits,
 235                                       const u8 *qr, const u8 *qnr,
 236                                       const struct crypto_bignum *y_sqr)
 237 {
 238         struct crypto_bignum *r, *num, *qr_or_qnr = NULL;
 239         int r_odd, check, res = -1;
 240         u8 qr_or_qnr_bin[SAE_MAX_ECC_PRIME_LEN];
 241         size_t prime_len = sae->tmp->prime_len;
 242         unsigned int mask;
 243
 244         /*
 245          * Use the blinding technique to mask y_sqr while determining
 246          * whether it is a quadratic residue modulo p to avoid leaking
 247          * timing information while determining the Legendre symbol.
 248          *
 249          * v = y_sqr
 250          * r = a random number between 1 and p-1, inclusive
 251          * num = (v * r * r) modulo p
 252          */
 253         r = get_rand_1_to_p_1(prime, prime_len, bits, &r_odd);
 254         if (!r)
 255                 return -1;
 256
 257         num = crypto_bignum_init();
 258         if (!num ||
 259             crypto_bignum_mulmod(y_sqr, r, sae->tmp->prime, num) < 0 ||
 260             crypto_bignum_mulmod(num, r, sae->tmp->prime, num) < 0)
 261                 goto fail;
 262
 263         /*
 264          * Need to minimize differences in handling different cases, so try to
 265          * avoid branches and timing differences.
 266          *
 267          * If r_odd:
 268          * num = (num * qr) module p
 269          * LGR(num, p) = 1 ==> quadratic residue
 270          * else:
 271          * num = (num * qnr) module p
 272          * LGR(num, p) = -1 ==> quadratic residue
 273          */
 274         mask = const_time_is_zero(r_odd);
 275         const_time_select_bin(mask, qnr, qr, prime_len, qr_or_qnr_bin);
 276         qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, prime_len);
 277         if (!qr_or_qnr ||
 278             crypto_bignum_mulmod(num, qr_or_qnr, sae->tmp->prime, num) < 0)
 279                 goto fail;
 280         /* r_odd is 0 or 1; branchless version of check = r_odd ? 1 : -1, */
 281         check = const_time_select_int(mask, -1, 1);
 282
 283         res = crypto_bignum_legendre(num, sae->tmp->prime);
 284         if (res == -2) {
 285                 res = -1;
 286                 goto fail;
 287         }
 288         /* branchless version of res = res == check
 289          * (res is -1, 0, or 1; check is -1 or 1) */
 290         mask = const_time_eq(res, check);
 291         res = const_time_select_int(mask, 1, 0);
 292 fail:
 293         crypto_bignum_deinit(num, 1);
 294         crypto_bignum_deinit(r, 1);
 295         crypto_bignum_deinit(qr_or_qnr, 1);
 296         return res;
 297 }
 298
 299
 300 static int sae_test_pwd_seed_ecc(struct sae_data *sae, const u8 *pwd_seed,
 301                                  const u8 *prime, const u8 *qr, const u8 *qnr,
 302                                  u8 *pwd_value)
 303 {
 304         struct crypto_bignum *y_sqr, *x_cand;
 305         int res;
 306         size_t bits;
 307
 308         wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-seed", pwd_seed, SHA256_MAC_LEN);
 309
 310         /* pwd-value = KDF-z(pwd-seed, "SAE Hunting and Pecking", p) */
 311         bits = crypto_ec_prime_len_bits(sae->tmp->ec);
 312         if (sha256_prf_bits(pwd_seed, SHA256_MAC_LEN, "SAE Hunting and Pecking",
 313                             prime, sae->tmp->prime_len, pwd_value, bits) < 0)
 314                 return -1;
 315         if (bits % 8)
 316                 buf_shift_right(pwd_value, sae->tmp->prime_len, 8 - bits % 8);
 317         wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-value",
 318                         pwd_value, sae->tmp->prime_len);
 319
 320         if (os_memcmp(pwd_value, prime, sae->tmp->prime_len) >= 0)
 321                 return 0;
 322
 323         x_cand = crypto_bignum_init_set(pwd_value, sae->tmp->prime_len);
 324         if (!x_cand)
 325                 return -1;
 326         y_sqr = crypto_ec_point_compute_y_sqr(sae->tmp->ec, x_cand);
 327         crypto_bignum_deinit(x_cand, 1);
 328         if (!y_sqr)
 329                 return -1;
 330
 331         res = is_quadratic_residue_blind(sae, prime, bits, qr, qnr, y_sqr);
 332         crypto_bignum_deinit(y_sqr, 1);
 333         return res;
 334 }
 335
 336
 337 /* Returns -1 on fatal failure, 0 if PWE cannot be derived from the provided
 338  * pwd-seed, or 1 if a valid PWE was derived from pwd-seed. */
 339 static int sae_test_pwd_seed_ffc(struct sae_data *sae, const u8 *pwd_seed,
 340                                  struct crypto_bignum *pwe)
 341 {
 342         u8 pwd_value[SAE_MAX_PRIME_LEN];
 343         size_t bits = sae->tmp->prime_len * 8;
 344         u8 exp[1];
 345         struct crypto_bignum *a, *b = NULL;
 346         int res, is_val;
 347         u8 pwd_value_valid;
 348
 349         wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-seed", pwd_seed, SHA256_MAC_LEN);
 350
 351         /* pwd-value = KDF-z(pwd-seed, "SAE Hunting and Pecking", p) */
 352         if (sha256_prf_bits(pwd_seed, SHA256_MAC_LEN, "SAE Hunting and Pecking",
 353                             sae->tmp->dh->prime, sae->tmp->prime_len, pwd_value,
 354                             bits) < 0)
 355                 return -1;
 356         wpa_hexdump_key(MSG_DEBUG, "SAE: pwd-value", pwd_value,
 357                         sae->tmp->prime_len);
 358
 359         /* Check whether pwd-value < p */
 360         res = const_time_memcmp(pwd_value, sae->tmp->dh->prime,
 361                                 sae->tmp->prime_len);
 362         /* pwd-value >= p is invalid, so res is < 0 for the valid cases and
 363          * the negative sign can be used to fill the mask for constant time
 364          * selection */
 365         pwd_value_valid = const_time_fill_msb(res);
 366
 367         /* If pwd-value >= p, force pwd-value to be < p and perform the
 368          * calculations anyway to hide timing difference. The derived PWE will
 369          * be ignored in that case. */
 370         pwd_value[0] = const_time_select_u8(pwd_value_valid, pwd_value[0], 0);
 371
 372         /* PWE = pwd-value^((p-1)/r) modulo p */
 373
 374         res = -1;
 375         a = crypto_bignum_init_set(pwd_value, sae->tmp->prime_len);
 376         if (!a)
 377                 goto fail;
 378
 379         /* This is an optimization based on the used group that does not depend
 380          * on the password in any way, so it is fine to use separate branches
 381          * for this step without constant time operations. */
 382         if (sae->tmp->dh->safe_prime) {
 383                 /*
 384                  * r = (p-1)/2 for the group used here, so this becomes:
 385                  * PWE = pwd-value^2 modulo p
 386                  */
 387                 exp[0] = 2;
 388                 b = crypto_bignum_init_set(exp, sizeof(exp));
 389         } else {
 390                 /* Calculate exponent: (p-1)/r */
 391                 exp[0] = 1;
 392                 b = crypto_bignum_init_set(exp, sizeof(exp));
 393                 if (b == NULL ||
 394                     crypto_bignum_sub(sae->tmp->prime, b, b) < 0 ||
 395                     crypto_bignum_div(b, sae->tmp->order, b) < 0)
 396                         goto fail;
 397         }
 398
 399         if (!b)
 400                 goto fail;
 401
 402         res = crypto_bignum_exptmod(a, b, sae->tmp->prime, pwe);
 403         if (res < 0)
 404                 goto fail;
 405
 406         /* There were no fatal errors in calculations, so determine the return
 407          * value using constant time operations. We get here for number of
 408          * invalid cases which are cleared here after having performed all the
 409          * computation. PWE is valid if pwd-value was less than prime and
 410          * PWE > 1. Start with pwd-value check first and then use constant time
 411          * operations to clear res to 0 if PWE is 0 or 1.
 412          */
 413         res = const_time_select_u8(pwd_value_valid, 1, 0);
 414         is_val = crypto_bignum_is_zero(pwe);
 415         res = const_time_select_u8(const_time_is_zero(is_val), res, 0);
 416         is_val = crypto_bignum_is_one(pwe);
 417         res = const_time_select_u8(const_time_is_zero(is_val), res, 0);
 418
 419 fail:
 420         crypto_bignum_deinit(a, 1);
 421         crypto_bignum_deinit(b, 1);
 422         return res;
 423 }
 424
 425
 426 static int get_random_qr_qnr(const u8 *prime, size_t prime_len,
 427                              const struct crypto_bignum *prime_bn,
 428                              size_t prime_bits, struct crypto_bignum **qr,
 429                              struct crypto_bignum **qnr)
 430 {
 431         *qr = NULL;
 432         *qnr = NULL;
 433
 434         while (!(*qr) || !(*qnr)) {
 435                 u8 tmp[SAE_MAX_ECC_PRIME_LEN];
 436                 struct crypto_bignum *q;
 437                 int res;
 438
 439                 if (random_get_bytes(tmp, prime_len) < 0)
 440                         break;
 441                 if (prime_bits % 8)
 442                         buf_shift_right(tmp, prime_len, 8 - prime_bits % 8);
 443                 if (os_memcmp(tmp, prime, prime_len) >= 0)
 444                         continue;
 445                 q = crypto_bignum_init_set(tmp, prime_len);
 446                 if (!q)
 447                         break;
 448                 res = crypto_bignum_legendre(q, prime_bn);
 449
 450                 if (res == 1 && !(*qr))
 451                         *qr = q;
 452                 else if (res == -1 && !(*qnr))
 453                         *qnr = q;
 454                 else
 455                         crypto_bignum_deinit(q, 0);
 456         }
 457
 458         return (*qr && *qnr) ? 0 : -1;
 459 }
 460
 461
 462 static int sae_derive_pwe_ecc(struct sae_data *sae, const u8 *addr1,
 463                               const u8 *addr2, const u8 *password,
 464                               size_t password_len, const char *identifier)
 465 {
 466         u8 counter, k = 40;
 467         u8 addrs[2 * ETH_ALEN];
 468         const u8 *addr[3];
 469         size_t len[3];
 470         size_t num_elem;
 471         u8 *dummy_password, *tmp_password;
 472         int pwd_seed_odd = 0;
 473         u8 prime[SAE_MAX_ECC_PRIME_LEN];
 474         size_t prime_len;
 475         struct crypto_bignum *x = NULL, *qr = NULL, *qnr = NULL;
 476         u8 x_bin[SAE_MAX_ECC_PRIME_LEN];
 477         u8 x_cand_bin[SAE_MAX_ECC_PRIME_LEN];
 478         u8 qr_bin[SAE_MAX_ECC_PRIME_LEN];
 479         u8 qnr_bin[SAE_MAX_ECC_PRIME_LEN];
 480         size_t bits;
 481         int res = -1;
 482         u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
 483                        * mask */
 484
 485         os_memset(x_bin, 0, sizeof(x_bin));
 486
 487         dummy_password = os_malloc(password_len);
 488         tmp_password = os_malloc(password_len);
 489         if (!dummy_password || !tmp_password ||
 490             random_get_bytes(dummy_password, password_len) < 0)
 491                 goto fail;
 492
 493         prime_len = sae->tmp->prime_len;
 494         if (crypto_bignum_to_bin(sae->tmp->prime, prime, sizeof(prime),
 495                                  prime_len) < 0)
 496                 goto fail;
 497         bits = crypto_ec_prime_len_bits(sae->tmp->ec);
 498
 499         /*
 500          * Create a random quadratic residue (qr) and quadratic non-residue
 501          * (qnr) modulo p for blinding purposes during the loop.
 502          */
 503         if (get_random_qr_qnr(prime, prime_len, sae->tmp->prime, bits,
 504                               &qr, &qnr) < 0 ||
 505             crypto_bignum_to_bin(qr, qr_bin, sizeof(qr_bin), prime_len) < 0 ||
 506             crypto_bignum_to_bin(qnr, qnr_bin, sizeof(qnr_bin), prime_len) < 0)
 507                 goto fail;
 508
 509         wpa_hexdump_ascii_key(MSG_DEBUG, "SAE: password",
 510                               password, password_len);
 511         if (identifier)
 512                 wpa_printf(MSG_DEBUG, "SAE: password identifier: %s",
 513                            identifier);
 514
 515         /*
 516          * H(salt, ikm) = HMAC-SHA256(salt, ikm)
 517          * base = password [|| identifier]
 518          * pwd-seed = H(MAX(STA-A-MAC, STA-B-MAC) || MIN(STA-A-MAC, STA-B-MAC),
 519          *              base || counter)
 520          */
 521         sae_pwd_seed_key(addr1, addr2, addrs);
 522
 523         addr[0] = tmp_password;
 524         len[0] = password_len;
 525         num_elem = 1;
 526         if (identifier) {
 527                 addr[num_elem] = (const u8 *) identifier;
 528                 len[num_elem] = os_strlen(identifier);
 529                 num_elem++;
 530         }
 531         addr[num_elem] = &counter;
 532         len[num_elem] = sizeof(counter);
 533         num_elem++;
 534
 535         /*
 536          * Continue for at least k iterations to protect against side-channel
 537          * attacks that attempt to determine the number of iterations required
 538          * in the loop.
 539          */
 540         for (counter = 1; counter <= k || !found; counter++) {
 541                 u8 pwd_seed[SHA256_MAC_LEN];
 542
 543                 if (counter > 200) {
 544                         /* This should not happen in practice */
 545                         wpa_printf(MSG_DEBUG, "SAE: Failed to derive PWE");
 546                         break;
 547                 }
 548
 549                 wpa_printf(MSG_DEBUG, "SAE: counter = %03u", counter);
 550                 const_time_select_bin(found, dummy_password, password,
 551                                       password_len, tmp_password);
 552                 if (hmac_sha256_vector(addrs, sizeof(addrs), num_elem,
 553                                        addr, len, pwd_seed) < 0)
 554                         break;
 555
 556                 res = sae_test_pwd_seed_ecc(sae, pwd_seed,
 557                                             prime, qr_bin, qnr_bin, x_cand_bin);
 558                 const_time_select_bin(found, x_bin, x_cand_bin, prime_len,
 559                                       x_bin);
 560                 pwd_seed_odd = const_time_select_u8(
 561                         found, pwd_seed_odd,
 562                         pwd_seed[SHA256_MAC_LEN - 1] & 0x01);
 563                 os_memset(pwd_seed, 0, sizeof(pwd_seed));
 564                 if (res < 0)
 565                         goto fail;
 566                 /* Need to minimize differences in handling res == 0 and 1 here
 567                  * to avoid differences in timing and instruction cache access,
 568                  * so use const_time_select_*() to make local copies of the
 569                  * values based on whether this loop iteration was the one that
 570                  * found the pwd-seed/x. */
 571
 572                 /* found is 0 or 0xff here and res is 0 or 1. Bitwise OR of them
 573                  * (with res converted to 0/0xff) handles this in constant time.
 574                  */
 575                 found |= res * 0xff;
 576                 wpa_printf(MSG_DEBUG, "SAE: pwd-seed result %d found=0x%02x",
 577                            res, found);
 578         }
 579
 580         if (!found) {
 581                 wpa_printf(MSG_DEBUG, "SAE: Could not generate PWE");
 582                 res = -1;
 583                 goto fail;
 584         }
 585
 586         x = crypto_bignum_init_set(x_bin, prime_len);
 587         if (!x) {
 588                 res = -1;
 589                 goto fail;
 590         }
 591
 592         if (!sae->tmp->pwe_ecc)
 593                 sae->tmp->pwe_ecc = crypto_ec_point_init(sae->tmp->ec);
 594         if (!sae->tmp->pwe_ecc)
 595                 res = -1;
 596         else
 597                 res = crypto_ec_point_solve_y_coord(sae->tmp->ec,
 598                                                     sae->tmp->pwe_ecc, x,
 599                                                     pwd_seed_odd);
 600         if (res < 0) {
 601                 /*
 602                  * This should not happen since we already checked that there
 603                  * is a result.
 604                  */
 605                 wpa_printf(MSG_DEBUG, "SAE: Could not solve y");
 606         }
 607
 608 fail:
 609         crypto_bignum_deinit(qr, 0);
 610         crypto_bignum_deinit(qnr, 0);
 611         os_free(dummy_password);
 612         bin_clear_free(tmp_password, password_len);
 613         crypto_bignum_deinit(x, 1);
 614         os_memset(x_bin, 0, sizeof(x_bin));
 615         os_memset(x_cand_bin, 0, sizeof(x_cand_bin));
 616
 617         return res;
 618 }
 619
 620
 621 static int sae_modp_group_require_masking(int group)
 622 {
 623         /* Groups for which pwd-value is likely to be >= p frequently */
 624         return group == 22 || group == 23 || group == 24;
 625 }
 626
 627
 628 static int sae_derive_pwe_ffc(struct sae_data *sae, const u8 *addr1,
 629                               const u8 *addr2, const u8 *password,
 630                               size_t password_len, const char *identifier)
 631 {
 632         u8 counter, k, sel_counter = 0;
 633         u8 addrs[2 * ETH_ALEN];
 634         const u8 *addr[3];
 635         size_t len[3];
 636         size_t num_elem;
 637         u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
 638                        * mask */
 639         u8 mask;
 640         struct crypto_bignum *pwe;
 641         size_t prime_len = sae->tmp->prime_len * 8;
 642         u8 *pwe_buf;
 643
 644         crypto_bignum_deinit(sae->tmp->pwe_ffc, 1);
 645         sae->tmp->pwe_ffc = NULL;
 646
 647         /* Allocate a buffer to maintain selected and candidate PWE for constant
 648          * time selection. */
 649         pwe_buf = os_zalloc(prime_len * 2);
 650         pwe = crypto_bignum_init();
 651         if (!pwe_buf || !pwe)
 652                 goto fail;
 653
 654         wpa_hexdump_ascii_key(MSG_DEBUG, "SAE: password",
 655                               password, password_len);
 656
 657         /*
 658          * H(salt, ikm) = HMAC-SHA256(salt, ikm)
 659          * pwd-seed = H(MAX(STA-A-MAC, STA-B-MAC) || MIN(STA-A-MAC, STA-B-MAC),
 660          *              password [|| identifier] || counter)
 661          */
 662         sae_pwd_seed_key(addr1, addr2, addrs);
 663
 664         addr[0] = password;
 665         len[0] = password_len;
 666         num_elem = 1;
 667         if (identifier) {
 668                 addr[num_elem] = (const u8 *) identifier;
 669                 len[num_elem] = os_strlen(identifier);
 670                 num_elem++;
 671         }
 672         addr[num_elem] = &counter;
 673         len[num_elem] = sizeof(counter);
 674         num_elem++;
 675
 676         k = sae_modp_group_require_masking(sae->group) ? 40 : 1;
 677
 678         for (counter = 1; counter <= k || !found; counter++) {
 679                 u8 pwd_seed[SHA256_MAC_LEN];
 680                 int res;
 681
 682                 if (counter > 200) {
 683                         /* This should not happen in practice */
 684                         wpa_printf(MSG_DEBUG, "SAE: Failed to derive PWE");
 685                         break;
 686                 }
 687
 688                 wpa_printf(MSG_DEBUG, "SAE: counter = %02u", counter);
 689                 if (hmac_sha256_vector(addrs, sizeof(addrs), num_elem,
 690                                        addr, len, pwd_seed) < 0)
 691                         break;
 692                 res = sae_test_pwd_seed_ffc(sae, pwd_seed, pwe);
 693                 /* res is -1 for fatal failure, 0 if a valid PWE was not found,
 694                  * or 1 if a valid PWE was found. */
 695                 if (res < 0)
 696                         break;
 697                 /* Store the candidate PWE into the second half of pwe_buf and
 698                  * the selected PWE in the beginning of pwe_buf using constant
 699                  * time selection. */
 700                 if (crypto_bignum_to_bin(pwe, pwe_buf + prime_len, prime_len,
 701                                          prime_len) < 0)
 702                         break;
 703                 const_time_select_bin(found, pwe_buf, pwe_buf + prime_len,
 704                                       prime_len, pwe_buf);
 705                 sel_counter = const_time_select_u8(found, sel_counter, counter);
 706                 mask = const_time_eq_u8(res, 1);
 707                 found = const_time_select_u8(found, found, mask);
 708         }
 709
 710         if (!found)
 711                 goto fail;
 712
 713         wpa_printf(MSG_DEBUG, "SAE: Use PWE from counter = %02u", sel_counter);
 714         sae->tmp->pwe_ffc = crypto_bignum_init_set(pwe_buf, prime_len);
 715 fail:
 716         crypto_bignum_deinit(pwe, 1);
 717         bin_clear_free(pwe_buf, prime_len * 2);
 718         return sae->tmp->pwe_ffc ? 0 : -1;
 719 }
 720
 721
 722 static int sae_derive_commit_element_ecc(struct sae_data *sae,
 723                                          struct crypto_bignum *mask)
 724 {
 725         /* COMMIT-ELEMENT = inverse(scalar-op(mask, PWE)) */
 726         if (!sae->tmp->own_commit_element_ecc) {
 727                 sae->tmp->own_commit_element_ecc =
 728                         crypto_ec_point_init(sae->tmp->ec);
 729                 if (!sae->tmp->own_commit_element_ecc)
 730                         return -1;
 731         }
 732
 733         if (crypto_ec_point_mul(sae->tmp->ec, sae->tmp->pwe_ecc, mask,
 734                                 sae->tmp->own_commit_element_ecc) < 0 ||
 735             crypto_ec_point_invert(sae->tmp->ec,
 736                                    sae->tmp->own_commit_element_ecc) < 0) {
 737                 wpa_printf(MSG_DEBUG, "SAE: Could not compute commit-element");
 738                 return -1;
 739         }
 740
 741         return 0;
 742 }
 743
 744
 745 static int sae_derive_commit_element_ffc(struct sae_data *sae,
 746                                          struct crypto_bignum *mask)
 747 {
 748         /* COMMIT-ELEMENT = inverse(scalar-op(mask, PWE)) */
 749         if (!sae->tmp->own_commit_element_ffc) {
 750                 sae->tmp->own_commit_element_ffc = crypto_bignum_init();
 751                 if (!sae->tmp->own_commit_element_ffc)
 752                         return -1;
 753         }
 754
 755         if (crypto_bignum_exptmod(sae->tmp->pwe_ffc, mask, sae->tmp->prime,
 756                                   sae->tmp->own_commit_element_ffc) < 0 ||
 757             crypto_bignum_inverse(sae->tmp->own_commit_element_ffc,
 758                                   sae->tmp->prime,
 759                                   sae->tmp->own_commit_element_ffc) < 0) {
 760                 wpa_printf(MSG_DEBUG, "SAE: Could not compute commit-element");
 761                 return -1;
 762         }
 763
 764         return 0;
 765 }
 766
 767
 768 static int sae_derive_commit(struct sae_data *sae)
 769 {
 770         struct crypto_bignum *mask;
 771         int ret = -1;
 772         unsigned int counter = 0;
 773
 774         do {
 775                 counter++;
 776                 if (counter > 100) {
 777                         /*
 778                          * This cannot really happen in practice if the random
 779                          * number generator is working. Anyway, to avoid even a
 780                          * theoretical infinite loop, break out after 100
 781                          * attemps.
 782                          */
 783                         return -1;
 784                 }
 785
 786                 mask = sae_get_rand_and_mask(sae);
 787                 if (mask == NULL) {
 788                         wpa_printf(MSG_DEBUG, "SAE: Could not get rand/mask");
 789                         return -1;
 790                 }
 791
 792                 /* commit-scalar = (rand + mask) modulo r */
 793                 if (!sae->tmp->own_commit_scalar) {
 794                         sae->tmp->own_commit_scalar = crypto_bignum_init();
 795                         if (!sae->tmp->own_commit_scalar)
 796                                 goto fail;
 797                 }
 798                 crypto_bignum_add(sae->tmp->sae_rand, mask,
 799                                   sae->tmp->own_commit_scalar);
 800                 crypto_bignum_mod(sae->tmp->own_commit_scalar, sae->tmp->order,
 801                                   sae->tmp->own_commit_scalar);
 802         } while (crypto_bignum_is_zero(sae->tmp->own_commit_scalar) ||
 803                  crypto_bignum_is_one(sae->tmp->own_commit_scalar));
 804
 805         if ((sae->tmp->ec && sae_derive_commit_element_ecc(sae, mask) < 0) ||
 806             (sae->tmp->dh && sae_derive_commit_element_ffc(sae, mask) < 0))
 807                 goto fail;
 808
 809         ret = 0;
 810 fail:
 811         crypto_bignum_deinit(mask, 1);
 812         return ret;
 813 }
 814
 815
 816 int sae_prepare_commit(const u8 *addr1, const u8 *addr2,
 817                        const u8 *password, size_t password_len,
 818                        const char *identifier, struct sae_data *sae)
 819 {
 820         if (sae->tmp == NULL ||
 821             (sae->tmp->ec && sae_derive_pwe_ecc(sae, addr1, addr2, password,
 822                                                 password_len,
 823                                                 identifier) < 0) ||
 824             (sae->tmp->dh && sae_derive_pwe_ffc(sae, addr1, addr2, password,
 825                                                 password_len,
 826                                                 identifier) < 0) ||
 827             sae_derive_commit(sae) < 0)
 828                 return -1;
 829         return 0;
 830 }
 831
 832
 833 static int sae_derive_k_ecc(struct sae_data *sae, u8 *k)
 834 {
 835         struct crypto_ec_point *K;
 836         int ret = -1;
 837
 838         K = crypto_ec_point_init(sae->tmp->ec);
 839         if (K == NULL)
 840                 goto fail;
 841
 842         /*
 843          * K = scalar-op(rand, (elem-op(scalar-op(peer-commit-scalar, PWE),
 844          *                                        PEER-COMMIT-ELEMENT)))
 845          * If K is identity element (point-at-infinity), reject
 846          * k = F(K) (= x coordinate)
 847          */
 848
 849         if (crypto_ec_point_mul(sae->tmp->ec, sae->tmp->pwe_ecc,
 850                                 sae->peer_commit_scalar, K) < 0 ||
 851             crypto_ec_point_add(sae->tmp->ec, K,
 852                                 sae->tmp->peer_commit_element_ecc, K) < 0 ||
 853             crypto_ec_point_mul(sae->tmp->ec, K, sae->tmp->sae_rand, K) < 0 ||
 854             crypto_ec_point_is_at_infinity(sae->tmp->ec, K) ||
 855             crypto_ec_point_to_bin(sae->tmp->ec, K, k, NULL) < 0) {
 856                 wpa_printf(MSG_DEBUG, "SAE: Failed to calculate K and k");
 857                 goto fail;
 858         }
 859
 860         wpa_hexdump_key(MSG_DEBUG, "SAE: k", k, sae->tmp->prime_len);
 861
 862         ret = 0;
 863 fail:
 864         crypto_ec_point_deinit(K, 1);
 865         return ret;
 866 }
 867
 868
 869 static int sae_derive_k_ffc(struct sae_data *sae, u8 *k)
 870 {
 871         struct crypto_bignum *K;
 872         int ret = -1;
 873
 874         K = crypto_bignum_init();
 875         if (K == NULL)
 876                 goto fail;
 877
 878         /*
 879          * K = scalar-op(rand, (elem-op(scalar-op(peer-commit-scalar, PWE),
 880          *                                        PEER-COMMIT-ELEMENT)))
 881          * If K is identity element (one), reject.
 882          * k = F(K) (= x coordinate)
 883          */
 884
 885         if (crypto_bignum_exptmod(sae->tmp->pwe_ffc, sae->peer_commit_scalar,
 886                                   sae->tmp->prime, K) < 0 ||
 887             crypto_bignum_mulmod(K, sae->tmp->peer_commit_element_ffc,
 888                                  sae->tmp->prime, K) < 0 ||
 889             crypto_bignum_exptmod(K, sae->tmp->sae_rand, sae->tmp->prime, K) < 0
 890             ||
 891             crypto_bignum_is_one(K) ||
 892             crypto_bignum_to_bin(K, k, SAE_MAX_PRIME_LEN, sae->tmp->prime_len) <
 893             0) {
 894                 wpa_printf(MSG_DEBUG, "SAE: Failed to calculate K and k");
 895                 goto fail;
 896         }
 897
 898         wpa_hexdump_key(MSG_DEBUG, "SAE: k", k, sae->tmp->prime_len);
 899
 900         ret = 0;
 901 fail:
 902         crypto_bignum_deinit(K, 1);
 903         return ret;
 904 }
 905
 906
 907 static int sae_derive_keys(struct sae_data *sae, const u8 *k)
 908 {
 909         u8 null_key[SAE_KEYSEED_KEY_LEN], val[SAE_MAX_PRIME_LEN];
 910         u8 keyseed[SHA256_MAC_LEN];
 911         u8 keys[SAE_KCK_LEN + SAE_PMK_LEN];
 912         struct crypto_bignum *tmp;
 913         int ret = -1;
 914
 915         tmp = crypto_bignum_init();
 916         if (tmp == NULL)
 917                 goto fail;
 918
 919         /* keyseed = H(<0>32, k)
 920          * KCK || PMK = KDF-512(keyseed, "SAE KCK and PMK",
 921          *                      (commit-scalar + peer-commit-scalar) modulo r)
 922          * PMKID = L((commit-scalar + peer-commit-scalar) modulo r, 0, 128)
 923          */
 924
 925         os_memset(null_key, 0, sizeof(null_key));
 926         hmac_sha256(null_key, sizeof(null_key), k, sae->tmp->prime_len,
 927                     keyseed);
 928         wpa_hexdump_key(MSG_DEBUG, "SAE: keyseed", keyseed, sizeof(keyseed));
 929
 930         crypto_bignum_add(sae->tmp->own_commit_scalar, sae->peer_commit_scalar,
 931                           tmp);
 932         crypto_bignum_mod(tmp, sae->tmp->order, tmp);
 933         crypto_bignum_to_bin(tmp, val, sizeof(val), sae->tmp->prime_len);
 934         wpa_hexdump(MSG_DEBUG, "SAE: PMKID", val, SAE_PMKID_LEN);
 935         if (sha256_prf(keyseed, sizeof(keyseed), "SAE KCK and PMK",
 936                        val, sae->tmp->prime_len, keys, sizeof(keys)) < 0)
 937                 goto fail;
 938         os_memset(keyseed, 0, sizeof(keyseed));
 939         os_memcpy(sae->tmp->kck, keys, SAE_KCK_LEN);
 940         os_memcpy(sae->pmk, keys + SAE_KCK_LEN, SAE_PMK_LEN);
 941         os_memcpy(sae->pmkid, val, SAE_PMKID_LEN);
 942         os_memset(keys, 0, sizeof(keys));
 943         wpa_hexdump_key(MSG_DEBUG, "SAE: KCK", sae->tmp->kck, SAE_KCK_LEN);
 944         wpa_hexdump_key(MSG_DEBUG, "SAE: PMK", sae->pmk, SAE_PMK_LEN);
 945
 946         ret = 0;
 947 fail:
 948         crypto_bignum_deinit(tmp, 0);
 949         return ret;
 950 }
 951
 952
 953 int sae_process_commit(struct sae_data *sae)
 954 {
 955         u8 k[SAE_MAX_PRIME_LEN];
 956         if (sae->tmp == NULL ||
 957             (sae->tmp->ec && sae_derive_k_ecc(sae, k) < 0) ||
 958             (sae->tmp->dh && sae_derive_k_ffc(sae, k) < 0) ||
 959             sae_derive_keys(sae, k) < 0)
 960                 return -1;
 961         return 0;
 962 }
 963
 964
 965 void sae_write_commit(struct sae_data *sae, struct wpabuf *buf,
 966                       const struct wpabuf *token, const char *identifier)
 967 {
 968         u8 *pos;
 969
 970         if (sae->tmp == NULL)
 971                 return;
 972
 973         wpabuf_put_le16(buf, sae->group); /* Finite Cyclic Group */
 974         if (token) {
 975                 wpabuf_put_buf(buf, token);
 976                 wpa_hexdump(MSG_DEBUG, "SAE: Anti-clogging token",
 977                             wpabuf_head(token), wpabuf_len(token));
 978         }
 979         pos = wpabuf_put(buf, sae->tmp->prime_len);
 980         crypto_bignum_to_bin(sae->tmp->own_commit_scalar, pos,
 981                              sae->tmp->prime_len, sae->tmp->prime_len);
 982         wpa_hexdump(MSG_DEBUG, "SAE: own commit-scalar",
 983                     pos, sae->tmp->prime_len);
 984         if (sae->tmp->ec) {
 985                 pos = wpabuf_put(buf, 2 * sae->tmp->prime_len);
 986                 crypto_ec_point_to_bin(sae->tmp->ec,
 987                                        sae->tmp->own_commit_element_ecc,
 988                                        pos, pos + sae->tmp->prime_len);
 989                 wpa_hexdump(MSG_DEBUG, "SAE: own commit-element(x)",
 990                             pos, sae->tmp->prime_len);
 991                 wpa_hexdump(MSG_DEBUG, "SAE: own commit-element(y)",
 992                             pos + sae->tmp->prime_len, sae->tmp->prime_len);
 993         } else {
 994                 pos = wpabuf_put(buf, sae->tmp->prime_len);
 995                 crypto_bignum_to_bin(sae->tmp->own_commit_element_ffc, pos,
 996                                      sae->tmp->prime_len, sae->tmp->prime_len);
 997                 wpa_hexdump(MSG_DEBUG, "SAE: own commit-element",
 998                             pos, sae->tmp->prime_len);
 999         }
1000
1001         if (identifier) {
1002                 /* Password Identifier element */
1003                 wpabuf_put_u8(buf, WLAN_EID_EXTENSION);
1004                 wpabuf_put_u8(buf, 1 + os_strlen(identifier));
1005                 wpabuf_put_u8(buf, WLAN_EID_EXT_PASSWORD_IDENTIFIER);
1006                 wpabuf_put_str(buf, identifier);
1007                 wpa_printf(MSG_DEBUG, "SAE: own Password Identifier: %s",
1008                            identifier);
1009         }
1010 }
1011
1012
1013 u16 sae_group_allowed(struct sae_data *sae, int *allowed_groups, u16 group)
1014 {
1015         if (allowed_groups) {
1016                 int i;
1017                 for (i = 0; allowed_groups[i] > 0; i++) {
1018                         if (allowed_groups[i] == group)
1019                                 break;
1020                 }
1021                 if (allowed_groups[i] != group) {
1022                         wpa_printf(MSG_DEBUG, "SAE: Proposed group %u not "
1023                                    "enabled in the current configuration",
1024                                    group);
1025                         return WLAN_STATUS_FINITE_CYCLIC_GROUP_NOT_SUPPORTED;
1026                 }
1027         }
1028
1029         if (sae->state == SAE_COMMITTED && group != sae->group) {
1030                 wpa_printf(MSG_DEBUG, "SAE: Do not allow group to be changed");
1031                 return WLAN_STATUS_FINITE_CYCLIC_GROUP_NOT_SUPPORTED;
1032         }
1033
1034         if (group != sae->group && sae_set_group(sae, group) < 0) {
1035                 wpa_printf(MSG_DEBUG, "SAE: Unsupported Finite Cyclic Group %u",
1036                            group);
1037                 return WLAN_STATUS_FINITE_CYCLIC_GROUP_NOT_SUPPORTED;
1038         }
1039
1040         if (sae->tmp == NULL) {
1041                 wpa_printf(MSG_DEBUG, "SAE: Group information not yet initialized");
1042                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1043         }
1044
1045         if (sae->tmp->dh && !allowed_groups) {
1046                 wpa_printf(MSG_DEBUG, "SAE: Do not allow FFC group %u without "
1047                            "explicit configuration enabling it", group);
1048                 return WLAN_STATUS_FINITE_CYCLIC_GROUP_NOT_SUPPORTED;
1049         }
1050
1051         return WLAN_STATUS_SUCCESS;
1052 }
1053
1054
1055 static int sae_is_password_id_elem(const u8 *pos, const u8 *end)
1056 {
1057         return end - pos >= 3 &&
1058                 pos[0] == WLAN_EID_EXTENSION &&
1059                 pos[1] >= 1 &&
1060                 end - pos - 2 >= pos[1] &&
1061                 pos[2] == WLAN_EID_EXT_PASSWORD_IDENTIFIER;
1062 }
1063
1064
1065 static void sae_parse_commit_token(struct sae_data *sae, const u8 **pos,
1066                                    const u8 *end, const u8 **token,
1067                                    size_t *token_len)
1068 {
1069         size_t scalar_elem_len, tlen;
1070         const u8 *elem;
1071
1072         if (token)
1073                 *token = NULL;
1074         if (token_len)
1075                 *token_len = 0;
1076
1077         scalar_elem_len = (sae->tmp->ec ? 3 : 2) * sae->tmp->prime_len;
1078         if (scalar_elem_len >= (size_t) (end - *pos))
1079                 return; /* No extra data beyond peer scalar and element */
1080
1081         /* It is a bit difficult to parse this now that there is an
1082          * optional variable length Anti-Clogging Token field and
1083          * optional variable length Password Identifier element in the
1084          * frame. We are sending out fixed length Anti-Clogging Token
1085          * fields, so use that length as a requirement for the received
1086          * token and check for the presence of possible Password
1087          * Identifier element based on the element header information.
1088          */
1089         tlen = end - (*pos + scalar_elem_len);
1090
1091         if (tlen < SHA256_MAC_LEN) {
1092                 wpa_printf(MSG_DEBUG,
1093                            "SAE: Too short optional data (%u octets) to include our Anti-Clogging Token",
1094                            (unsigned int) tlen);
1095                 return;
1096         }
1097
1098         elem = *pos + scalar_elem_len;
1099         if (sae_is_password_id_elem(elem, end)) {
1100                  /* Password Identifier element takes out all available
1101                   * extra octets, so there can be no Anti-Clogging token in
1102                   * this frame. */
1103                 return;
1104         }
1105
1106         elem += SHA256_MAC_LEN;
1107         if (sae_is_password_id_elem(elem, end)) {
1108                  /* Password Identifier element is included in the end, so
1109                   * remove its length from the Anti-Clogging token field. */
1110                 tlen -= 2 + elem[1];
1111         }
1112
1113         wpa_hexdump(MSG_DEBUG, "SAE: Anti-Clogging Token", *pos, tlen);
1114         if (token)
1115                 *token = *pos;
1116         if (token_len)
1117                 *token_len = tlen;
1118         *pos += tlen;
1119 }
1120
1121
1122 static u16 sae_parse_commit_scalar(struct sae_data *sae, const u8 **pos,
1123                                    const u8 *end)
1124 {
1125         struct crypto_bignum *peer_scalar;
1126
1127         if (sae->tmp->prime_len > end - *pos) {
1128                 wpa_printf(MSG_DEBUG, "SAE: Not enough data for scalar");
1129                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1130         }
1131
1132         peer_scalar = crypto_bignum_init_set(*pos, sae->tmp->prime_len);
1133         if (peer_scalar == NULL)
1134                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1135
1136         /*
1137          * IEEE Std 802.11-2012, 11.3.8.6.1: If there is a protocol instance for
1138          * the peer and it is in Authenticated state, the new Commit Message
1139          * shall be dropped if the peer-scalar is identical to the one used in
1140          * the existing protocol instance.
1141          */
1142         if (sae->state == SAE_ACCEPTED && sae->peer_commit_scalar &&
1143             crypto_bignum_cmp(sae->peer_commit_scalar, peer_scalar) == 0) {
1144                 wpa_printf(MSG_DEBUG, "SAE: Do not accept re-use of previous "
1145                            "peer-commit-scalar");
1146                 crypto_bignum_deinit(peer_scalar, 0);
1147                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1148         }
1149
1150         /* 1 < scalar < r */
1151         if (crypto_bignum_is_zero(peer_scalar) ||
1152             crypto_bignum_is_one(peer_scalar) ||
1153             crypto_bignum_cmp(peer_scalar, sae->tmp->order) >= 0) {
1154                 wpa_printf(MSG_DEBUG, "SAE: Invalid peer scalar");
1155                 crypto_bignum_deinit(peer_scalar, 0);
1156                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1157         }
1158
1159
1160         crypto_bignum_deinit(sae->peer_commit_scalar, 0);
1161         sae->peer_commit_scalar = peer_scalar;
1162         wpa_hexdump(MSG_DEBUG, "SAE: Peer commit-scalar",
1163                     *pos, sae->tmp->prime_len);
1164         *pos += sae->tmp->prime_len;
1165
1166         return WLAN_STATUS_SUCCESS;
1167 }
1168
1169
1170 static u16 sae_parse_commit_element_ecc(struct sae_data *sae, const u8 **pos,
1171                                         const u8 *end)
1172 {
1173         u8 prime[SAE_MAX_ECC_PRIME_LEN];
1174
1175         if (2 * sae->tmp->prime_len > end - *pos) {
1176                 wpa_printf(MSG_DEBUG, "SAE: Not enough data for "
1177                            "commit-element");
1178                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1179         }
1180
1181         if (crypto_bignum_to_bin(sae->tmp->prime, prime, sizeof(prime),
1182                                  sae->tmp->prime_len) < 0)
1183                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1184
1185         /* element x and y coordinates < p */
1186         if (os_memcmp(*pos, prime, sae->tmp->prime_len) >= 0 ||
1187             os_memcmp(*pos + sae->tmp->prime_len, prime,
1188                       sae->tmp->prime_len) >= 0) {
1189                 wpa_printf(MSG_DEBUG, "SAE: Invalid coordinates in peer "
1190                            "element");
1191                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1192         }
1193
1194         wpa_hexdump(MSG_DEBUG, "SAE: Peer commit-element(x)",
1195                     *pos, sae->tmp->prime_len);
1196         wpa_hexdump(MSG_DEBUG, "SAE: Peer commit-element(y)",
1197                     *pos + sae->tmp->prime_len, sae->tmp->prime_len);
1198
1199         crypto_ec_point_deinit(sae->tmp->peer_commit_element_ecc, 0);
1200         sae->tmp->peer_commit_element_ecc =
1201                 crypto_ec_point_from_bin(sae->tmp->ec, *pos);
1202         if (sae->tmp->peer_commit_element_ecc == NULL)
1203                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1204
1205         if (!crypto_ec_point_is_on_curve(sae->tmp->ec,
1206                                          sae->tmp->peer_commit_element_ecc)) {
1207                 wpa_printf(MSG_DEBUG, "SAE: Peer element is not on curve");
1208                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1209         }
1210
1211         *pos += 2 * sae->tmp->prime_len;
1212
1213         return WLAN_STATUS_SUCCESS;
1214 }
1215
1216
1217 static u16 sae_parse_commit_element_ffc(struct sae_data *sae, const u8 **pos,
1218                                         const u8 *end)
1219 {
1220         struct crypto_bignum *res, *one;
1221         const u8 one_bin[1] = { 0x01 };
1222
1223         if (sae->tmp->prime_len > end - *pos) {
1224                 wpa_printf(MSG_DEBUG, "SAE: Not enough data for "
1225                            "commit-element");
1226                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1227         }
1228         wpa_hexdump(MSG_DEBUG, "SAE: Peer commit-element", *pos,
1229                     sae->tmp->prime_len);
1230
1231         crypto_bignum_deinit(sae->tmp->peer_commit_element_ffc, 0);
1232         sae->tmp->peer_commit_element_ffc =
1233                 crypto_bignum_init_set(*pos, sae->tmp->prime_len);
1234         if (sae->tmp->peer_commit_element_ffc == NULL)
1235                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1236         /* 1 < element < p - 1 */
1237         res = crypto_bignum_init();
1238         one = crypto_bignum_init_set(one_bin, sizeof(one_bin));
1239         if (!res || !one ||
1240             crypto_bignum_sub(sae->tmp->prime, one, res) ||
1241             crypto_bignum_is_zero(sae->tmp->peer_commit_element_ffc) ||
1242             crypto_bignum_is_one(sae->tmp->peer_commit_element_ffc) ||
1243             crypto_bignum_cmp(sae->tmp->peer_commit_element_ffc, res) >= 0) {
1244                 crypto_bignum_deinit(res, 0);
1245                 crypto_bignum_deinit(one, 0);
1246                 wpa_printf(MSG_DEBUG, "SAE: Invalid peer element");
1247                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1248         }
1249         crypto_bignum_deinit(one, 0);
1250
1251         /* scalar-op(r, ELEMENT) = 1 modulo p */
1252         if (crypto_bignum_exptmod(sae->tmp->peer_commit_element_ffc,
1253                                   sae->tmp->order, sae->tmp->prime, res) < 0 ||
1254             !crypto_bignum_is_one(res)) {
1255                 wpa_printf(MSG_DEBUG, "SAE: Invalid peer element (scalar-op)");
1256                 crypto_bignum_deinit(res, 0);
1257                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1258         }
1259         crypto_bignum_deinit(res, 0);
1260
1261         *pos += sae->tmp->prime_len;
1262
1263         return WLAN_STATUS_SUCCESS;
1264 }
1265
1266
1267 static u16 sae_parse_commit_element(struct sae_data *sae, const u8 **pos,
1268                                     const u8 *end)
1269 {
1270         if (sae->tmp->dh)
1271                 return sae_parse_commit_element_ffc(sae, pos, end);
1272         return sae_parse_commit_element_ecc(sae, pos, end);
1273 }
1274
1275
1276 static int sae_parse_password_identifier(struct sae_data *sae,
1277                                          const u8 *pos, const u8 *end)
1278 {
1279         wpa_hexdump(MSG_DEBUG, "SAE: Possible elements at the end of the frame",
1280                     pos, end - pos);
1281         if (!sae_is_password_id_elem(pos, end)) {
1282                 if (sae->tmp->pw_id) {
1283                         wpa_printf(MSG_DEBUG,
1284                                    "SAE: No Password Identifier included, but expected one (%s)",
1285                                    sae->tmp->pw_id);
1286                         return WLAN_STATUS_UNKNOWN_PASSWORD_IDENTIFIER;
1287                 }
1288                 os_free(sae->tmp->pw_id);
1289                 sae->tmp->pw_id = NULL;
1290                 return WLAN_STATUS_SUCCESS; /* No Password Identifier */
1291         }
1292
1293         if (sae->tmp->pw_id &&
1294             (pos[1] - 1 != (int) os_strlen(sae->tmp->pw_id) ||
1295              os_memcmp(sae->tmp->pw_id, pos + 3, pos[1] - 1) != 0)) {
1296                 wpa_printf(MSG_DEBUG,
1297                            "SAE: The included Password Identifier does not match the expected one (%s)",
1298                            sae->tmp->pw_id);
1299                 return WLAN_STATUS_UNKNOWN_PASSWORD_IDENTIFIER;
1300         }
1301
1302         os_free(sae->tmp->pw_id);
1303         sae->tmp->pw_id = os_malloc(pos[1]);
1304         if (!sae->tmp->pw_id)
1305                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1306         os_memcpy(sae->tmp->pw_id, pos + 3, pos[1] - 1);
1307         sae->tmp->pw_id[pos[1] - 1] = '\0';
1308         wpa_hexdump_ascii(MSG_DEBUG, "SAE: Received Password Identifier",
1309                           sae->tmp->pw_id, pos[1] -  1);
1310         return WLAN_STATUS_SUCCESS;
1311 }
1312
1313
1314 u16 sae_parse_commit(struct sae_data *sae, const u8 *data, size_t len,
1315                      const u8 **token, size_t *token_len, int *allowed_groups)
1316 {
1317         const u8 *pos = data, *end = data + len;
1318         u16 res;
1319
1320         /* Check Finite Cyclic Group */
1321         if (end - pos < 2)
1322                 return WLAN_STATUS_UNSPECIFIED_FAILURE;
1323         res = sae_group_allowed(sae, allowed_groups, WPA_GET_LE16(pos));
1324         if (res != WLAN_STATUS_SUCCESS)
1325                 return res;
1326         pos += 2;
1327
1328         /* Optional Anti-Clogging Token */
1329         sae_parse_commit_token(sae, &pos, end, token, token_len);
1330
1331         /* commit-scalar */
1332         res = sae_parse_commit_scalar(sae, &pos, end);
1333         if (res != WLAN_STATUS_SUCCESS)
1334                 return res;
1335
1336         /* commit-element */
1337         res = sae_parse_commit_element(sae, &pos, end);
1338         if (res != WLAN_STATUS_SUCCESS)
1339                 return res;
1340
1341         /* Optional Password Identifier element */
1342         res = sae_parse_password_identifier(sae, pos, end);
1343         if (res != WLAN_STATUS_SUCCESS)
1344                 return res;
1345
1346         /*
1347          * Check whether peer-commit-scalar and PEER-COMMIT-ELEMENT are same as
1348          * the values we sent which would be evidence of a reflection attack.
1349          */
1350         if (!sae->tmp->own_commit_scalar ||
1351             crypto_bignum_cmp(sae->tmp->own_commit_scalar,
1352                               sae->peer_commit_scalar) != 0 ||
1353             (sae->tmp->dh &&
1354              (!sae->tmp->own_commit_element_ffc ||
1355               crypto_bignum_cmp(sae->tmp->own_commit_element_ffc,
1356                                 sae->tmp->peer_commit_element_ffc) != 0)) ||
1357             (sae->tmp->ec &&
1358              (!sae->tmp->own_commit_element_ecc ||
1359               crypto_ec_point_cmp(sae->tmp->ec,
1360                                   sae->tmp->own_commit_element_ecc,
1361                                   sae->tmp->peer_commit_element_ecc) != 0)))
1362                 return WLAN_STATUS_SUCCESS; /* scalars/elements are different */
1363
1364         /*
1365          * This is a reflection attack - return special value to trigger caller
1366          * to silently discard the frame instead of replying with a specific
1367          * status code.
1368          */
1369         return SAE_SILENTLY_DISCARD;
1370 }
1371
1372
1373 static void sae_cn_confirm(struct sae_data *sae, const u8 *sc,
1374                            const struct crypto_bignum *scalar1,
1375                            const u8 *element1, size_t element1_len,
1376                            const struct crypto_bignum *scalar2,
1377                            const u8 *element2, size_t element2_len,
1378                            u8 *confirm)
1379 {
1380         const u8 *addr[5];
1381         size_t len[5];
1382         u8 scalar_b1[SAE_MAX_PRIME_LEN], scalar_b2[SAE_MAX_PRIME_LEN];
1383
1384         /* Confirm
1385          * CN(key, X, Y, Z, ...) =
1386          *    HMAC-SHA256(key, D2OS(X) || D2OS(Y) || D2OS(Z) | ...)
1387          * confirm = CN(KCK, send-confirm, commit-scalar, COMMIT-ELEMENT,
1388          *              peer-commit-scalar, PEER-COMMIT-ELEMENT)
1389          * verifier = CN(KCK, peer-send-confirm, peer-commit-scalar,
1390          *               PEER-COMMIT-ELEMENT, commit-scalar, COMMIT-ELEMENT)
1391          */
1392         addr[0] = sc;
1393         len[0] = 2;
1394         crypto_bignum_to_bin(scalar1, scalar_b1, sizeof(scalar_b1),
1395                              sae->tmp->prime_len);
1396         addr[1] = scalar_b1;
1397         len[1] = sae->tmp->prime_len;
1398         addr[2] = element1;
1399         len[2] = element1_len;
1400         crypto_bignum_to_bin(scalar2, scalar_b2, sizeof(scalar_b2),
1401                              sae->tmp->prime_len);
1402         addr[3] = scalar_b2;
1403         len[3] = sae->tmp->prime_len;
1404         addr[4] = element2;
1405         len[4] = element2_len;
1406         hmac_sha256_vector(sae->tmp->kck, sizeof(sae->tmp->kck), 5, addr, len,
1407                            confirm);
1408 }
1409
1410
1411 static void sae_cn_confirm_ecc(struct sae_data *sae, const u8 *sc,
1412                                const struct crypto_bignum *scalar1,
1413                                const struct crypto_ec_point *element1,
1414                                const struct crypto_bignum *scalar2,
1415                                const struct crypto_ec_point *element2,
1416                                u8 *confirm)
1417 {
1418         u8 element_b1[2 * SAE_MAX_ECC_PRIME_LEN];
1419         u8 element_b2[2 * SAE_MAX_ECC_PRIME_LEN];
1420
1421         crypto_ec_point_to_bin(sae->tmp->ec, element1, element_b1,
1422                                element_b1 + sae->tmp->prime_len);
1423         crypto_ec_point_to_bin(sae->tmp->ec, element2, element_b2,
1424                                element_b2 + sae->tmp->prime_len);
1425
1426         sae_cn_confirm(sae, sc, scalar1, element_b1, 2 * sae->tmp->prime_len,
1427                        scalar2, element_b2, 2 * sae->tmp->prime_len, confirm);
1428 }
1429
1430
1431 static void sae_cn_confirm_ffc(struct sae_data *sae, const u8 *sc,
1432                                const struct crypto_bignum *scalar1,
1433                                const struct crypto_bignum *element1,
1434                                const struct crypto_bignum *scalar2,
1435                                const struct crypto_bignum *element2,
1436                                u8 *confirm)
1437 {
1438         u8 element_b1[SAE_MAX_PRIME_LEN];
1439         u8 element_b2[SAE_MAX_PRIME_LEN];
1440
1441         crypto_bignum_to_bin(element1, element_b1, sizeof(element_b1),
1442                              sae->tmp->prime_len);
1443         crypto_bignum_to_bin(element2, element_b2, sizeof(element_b2),
1444                              sae->tmp->prime_len);
1445
1446         sae_cn_confirm(sae, sc, scalar1, element_b1, sae->tmp->prime_len,
1447                        scalar2, element_b2, sae->tmp->prime_len, confirm);
1448 }
1449
1450
1451 void sae_write_confirm(struct sae_data *sae, struct wpabuf *buf)
1452 {
1453         const u8 *sc;
1454
1455         if (sae->tmp == NULL)
1456                 return;
1457
1458         /* Send-Confirm */
1459         sc = wpabuf_put(buf, 0);
1460         wpabuf_put_le16(buf, sae->send_confirm);
1461         if (sae->send_confirm < 0xffff)
1462                 sae->send_confirm++;
1463
1464         if (sae->tmp->ec)
1465                 sae_cn_confirm_ecc(sae, sc, sae->tmp->own_commit_scalar,
1466                                    sae->tmp->own_commit_element_ecc,
1467                                    sae->peer_commit_scalar,
1468                                    sae->tmp->peer_commit_element_ecc,
1469                                    wpabuf_put(buf, SHA256_MAC_LEN));
1470         else
1471                 sae_cn_confirm_ffc(sae, sc, sae->tmp->own_commit_scalar,
1472                                    sae->tmp->own_commit_element_ffc,
1473                                    sae->peer_commit_scalar,
1474                                    sae->tmp->peer_commit_element_ffc,
1475                                    wpabuf_put(buf, SHA256_MAC_LEN));
1476 }
1477
1478
1479 int sae_check_confirm(struct sae_data *sae, const u8 *data, size_t len)
1480 {
1481         u8 verifier[SHA256_MAC_LEN];
1482
1483         if (len < 2 + SHA256_MAC_LEN) {
1484                 wpa_printf(MSG_DEBUG, "SAE: Too short confirm message");
1485                 return -1;
1486         }
1487
1488         wpa_printf(MSG_DEBUG, "SAE: peer-send-confirm %u", WPA_GET_LE16(data));
1489
1490         if (!sae->tmp || !sae->peer_commit_scalar ||
1491             !sae->tmp->own_commit_scalar) {
1492                 wpa_printf(MSG_DEBUG, "SAE: Temporary data not yet available");
1493                 return -1;
1494         }
1495
1496         if (sae->tmp->ec) {
1497                 if (!sae->tmp->peer_commit_element_ecc ||
1498                     !sae->tmp->own_commit_element_ecc)
1499                         return -1;
1500                 sae_cn_confirm_ecc(sae, data, sae->peer_commit_scalar,
1501                                    sae->tmp->peer_commit_element_ecc,
1502                                    sae->tmp->own_commit_scalar,
1503                                    sae->tmp->own_commit_element_ecc,
1504                                    verifier);
1505         } else {
1506                 if (!sae->tmp->peer_commit_element_ffc ||
1507                     !sae->tmp->own_commit_element_ffc)
1508                         return -1;
1509                 sae_cn_confirm_ffc(sae, data, sae->peer_commit_scalar,
1510                                    sae->tmp->peer_commit_element_ffc,
1511                                    sae->tmp->own_commit_scalar,
1512                                    sae->tmp->own_commit_element_ffc,
1513                                    verifier);
1514         }
1515
1516         if (os_memcmp_const(verifier, data + 2, SHA256_MAC_LEN) != 0) {
1517                 wpa_printf(MSG_DEBUG, "SAE: Confirm mismatch");
1518                 wpa_hexdump(MSG_DEBUG, "SAE: Received confirm",
1519                             data + 2, SHA256_MAC_LEN);
1520                 wpa_hexdump(MSG_DEBUG, "SAE: Calculated verifier",
1521                             verifier, SHA256_MAC_LEN);
1522                 return -1;
1523         }
1524
1525         return 0;
1526 }
1527
1528
1529 const char * sae_state_txt(enum sae_state state)
1530 {
1531         switch (state) {
1532         case SAE_NOTHING:
1533                 return "Nothing";
1534         case SAE_COMMITTED:
1535                 return "Committed";
1536         case SAE_CONFIRMED:
1537                 return "Confirmed";
1538         case SAE_ACCEPTED:
1539                 return "Accepted";
1540         }
1541         return "?";
1542 }