contrib/wpa/src/eap_common/eap_pwd_common.c

   1 /*
   2  * EAP server/peer: EAP-pwd shared routines
   3  * Copyright (c) 2010, Dan Harkins <dharkins@lounge.org>
   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 #include "common.h"
  11 #include "utils/const_time.h"
  12 #include "common/dragonfly.h"
  13 #include "crypto/sha256.h"
  14 #include "crypto/crypto.h"
  15 #include "eap_defs.h"
  16 #include "eap_pwd_common.h"
  17
  18 #define MAX_ECC_PRIME_LEN 66
  19
  20
  21 /* The random function H(x) = HMAC-SHA256(0^32, x) */
  22 struct crypto_hash * eap_pwd_h_init(void)
  23 {
  24         u8 allzero[SHA256_MAC_LEN];
  25         os_memset(allzero, 0, SHA256_MAC_LEN);
  26         return crypto_hash_init(CRYPTO_HASH_ALG_HMAC_SHA256, allzero,
  27                                 SHA256_MAC_LEN);
  28 }
  29
  30
  31 void eap_pwd_h_update(struct crypto_hash *hash, const u8 *data, size_t len)
  32 {
  33         crypto_hash_update(hash, data, len);
  34 }
  35
  36
  37 void eap_pwd_h_final(struct crypto_hash *hash, u8 *digest)
  38 {
  39         size_t len = SHA256_MAC_LEN;
  40         crypto_hash_finish(hash, digest, &len);
  41 }
  42
  43
  44 /* a counter-based KDF based on NIST SP800-108 */
  45 static int eap_pwd_kdf(const u8 *key, size_t keylen, const u8 *label,
  46                        size_t labellen, u8 *result, size_t resultbitlen)
  47 {
  48         struct crypto_hash *hash;
  49         u8 digest[SHA256_MAC_LEN];
  50         u16 i, ctr, L;
  51         size_t resultbytelen, len = 0, mdlen;
  52
  53         resultbytelen = (resultbitlen + 7) / 8;
  54         ctr = 0;
  55         L = htons(resultbitlen);
  56         while (len < resultbytelen) {
  57                 ctr++;
  58                 i = htons(ctr);
  59                 hash = crypto_hash_init(CRYPTO_HASH_ALG_HMAC_SHA256,
  60                                         key, keylen);
  61                 if (hash == NULL)
  62                         return -1;
  63                 if (ctr > 1)
  64                         crypto_hash_update(hash, digest, SHA256_MAC_LEN);
  65                 crypto_hash_update(hash, (u8 *) &i, sizeof(u16));
  66                 crypto_hash_update(hash, label, labellen);
  67                 crypto_hash_update(hash, (u8 *) &L, sizeof(u16));
  68                 mdlen = SHA256_MAC_LEN;
  69                 if (crypto_hash_finish(hash, digest, &mdlen) < 0)
  70                         return -1;
  71                 if ((len + mdlen) > resultbytelen)
  72                         os_memcpy(result + len, digest, resultbytelen - len);
  73                 else
  74                         os_memcpy(result + len, digest, mdlen);
  75                 len += mdlen;
  76         }
  77
  78         /* since we're expanding to a bit length, mask off the excess */
  79         if (resultbitlen % 8) {
  80                 u8 mask = 0xff;
  81                 mask <<= (8 - (resultbitlen % 8));
  82                 result[resultbytelen - 1] &= mask;
  83         }
  84
  85         return 0;
  86 }
  87
  88
  89 EAP_PWD_group * get_eap_pwd_group(u16 num)
  90 {
  91         EAP_PWD_group *grp;
  92
  93         if (!dragonfly_suitable_group(num, 1)) {
  94                 wpa_printf(MSG_INFO, "EAP-pwd: unsuitable group %u", num);
  95                 return NULL;
  96         }
  97         grp = os_zalloc(sizeof(EAP_PWD_group));
  98         if (!grp)
  99                 return NULL;
 100         grp->group = crypto_ec_init(num);
 101         if (!grp->group) {
 102                 wpa_printf(MSG_INFO, "EAP-pwd: unable to create EC group");
 103                 os_free(grp);
 104                 return NULL;
 105         }
 106
 107         grp->group_num = num;
 108         wpa_printf(MSG_INFO, "EAP-pwd: provisioned group %d", num);
 109
 110         return grp;
 111 }
 112
 113
 114 /*
 115  * compute a "random" secret point on an elliptic curve based
 116  * on the password and identities.
 117  */
 118 int compute_password_element(EAP_PWD_group *grp, u16 num,
 119                              const u8 *password, size_t password_len,
 120                              const u8 *id_server, size_t id_server_len,
 121                              const u8 *id_peer, size_t id_peer_len,
 122                              const u8 *token)
 123 {
 124         struct crypto_bignum *qr = NULL, *qnr = NULL;
 125         u8 qr_bin[MAX_ECC_PRIME_LEN];
 126         u8 qnr_bin[MAX_ECC_PRIME_LEN];
 127         u8 qr_or_qnr_bin[MAX_ECC_PRIME_LEN];
 128         u8 x_bin[MAX_ECC_PRIME_LEN];
 129         u8 prime_bin[MAX_ECC_PRIME_LEN];
 130         struct crypto_bignum *tmp2 = NULL;
 131         struct crypto_hash *hash;
 132         unsigned char pwe_digest[SHA256_MAC_LEN], *prfbuf = NULL, ctr;
 133         int ret = 0, res;
 134         u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
 135                        * mask */
 136         size_t primebytelen = 0, primebitlen;
 137         struct crypto_bignum *x_candidate = NULL;
 138         const struct crypto_bignum *prime;
 139         u8 found_ctr = 0, is_odd = 0;
 140         int cmp_prime;
 141         unsigned int in_range;
 142
 143         if (grp->pwe)
 144                 return -1;
 145
 146         os_memset(x_bin, 0, sizeof(x_bin));
 147
 148         prime = crypto_ec_get_prime(grp->group);
 149         primebitlen = crypto_ec_prime_len_bits(grp->group);
 150         primebytelen = crypto_ec_prime_len(grp->group);
 151         if (crypto_bignum_to_bin(prime, prime_bin, sizeof(prime_bin),
 152                                  primebytelen) < 0)
 153                 return -1;
 154         grp->pwe = crypto_ec_point_init(grp->group);
 155         if (!grp->pwe) {
 156                 wpa_printf(MSG_INFO, "EAP-pwd: unable to create bignums");
 157                 goto fail;
 158         }
 159
 160         if ((prfbuf = os_malloc(primebytelen)) == NULL) {
 161                 wpa_printf(MSG_INFO, "EAP-pwd: unable to malloc space for prf "
 162                            "buffer");
 163                 goto fail;
 164         }
 165
 166         /* get a random quadratic residue and nonresidue */
 167         if (dragonfly_get_random_qr_qnr(prime, &qr, &qnr) < 0 ||
 168             crypto_bignum_to_bin(qr, qr_bin, sizeof(qr_bin),
 169                                  primebytelen) < 0 ||
 170             crypto_bignum_to_bin(qnr, qnr_bin, sizeof(qnr_bin),
 171                                  primebytelen) < 0)
 172                 goto fail;
 173
 174         os_memset(prfbuf, 0, primebytelen);
 175         ctr = 0;
 176
 177         /*
 178          * Run through the hunting-and-pecking loop 40 times to mask the time
 179          * necessary to find PWE. The odds of PWE not being found in 40 loops is
 180          * roughly 1 in 1 trillion.
 181          */
 182         while (ctr < 40) {
 183                 ctr++;
 184
 185                 /*
 186                  * compute counter-mode password value and stretch to prime
 187                  *    pwd-seed = H(token | peer-id | server-id | password |
 188                  *                 counter)
 189                  */
 190                 hash = eap_pwd_h_init();
 191                 if (hash == NULL)
 192                         goto fail;
 193                 eap_pwd_h_update(hash, token, sizeof(u32));
 194                 eap_pwd_h_update(hash, id_peer, id_peer_len);
 195                 eap_pwd_h_update(hash, id_server, id_server_len);
 196                 eap_pwd_h_update(hash, password, password_len);
 197                 eap_pwd_h_update(hash, &ctr, sizeof(ctr));
 198                 eap_pwd_h_final(hash, pwe_digest);
 199
 200                 is_odd = const_time_select_u8(
 201                         found, is_odd, pwe_digest[SHA256_MAC_LEN - 1] & 0x01);
 202                 if (eap_pwd_kdf(pwe_digest, SHA256_MAC_LEN,
 203                                 (u8 *) "EAP-pwd Hunting And Pecking",
 204                                 os_strlen("EAP-pwd Hunting And Pecking"),
 205                                 prfbuf, primebitlen) < 0)
 206                         goto fail;
 207                 if (primebitlen % 8)
 208                         buf_shift_right(prfbuf, primebytelen,
 209                                         8 - primebitlen % 8);
 210                 cmp_prime = const_time_memcmp(prfbuf, prime_bin, primebytelen);
 211                 /* Create a const_time mask for selection based on prf result
 212                  * being smaller than prime. */
 213                 in_range = const_time_fill_msb((unsigned int) cmp_prime);
 214                 /* The algorithm description would skip the next steps if
 215                  * cmp_prime >= 0, but go through them regardless to minimize
 216                  * externally observable differences in behavior. */
 217
 218                 crypto_bignum_deinit(x_candidate, 1);
 219                 x_candidate = crypto_bignum_init_set(prfbuf, primebytelen);
 220                 if (!x_candidate) {
 221                         wpa_printf(MSG_INFO,
 222                                    "EAP-pwd: unable to create x_candidate");
 223                         goto fail;
 224                 }
 225
 226                 wpa_hexdump_key(MSG_DEBUG, "EAP-pwd: x_candidate",
 227                                 prfbuf, primebytelen);
 228                 const_time_select_bin(found, x_bin, prfbuf, primebytelen,
 229                                       x_bin);
 230
 231                 /*
 232                  * compute y^2 using the equation of the curve
 233                  *
 234                  *      y^2 = x^3 + ax + b
 235                  */
 236                 crypto_bignum_deinit(tmp2, 1);
 237                 tmp2 = crypto_ec_point_compute_y_sqr(grp->group, x_candidate);
 238                 if (!tmp2)
 239                         goto fail;
 240
 241                 res = dragonfly_is_quadratic_residue_blind(grp->group, qr_bin,
 242                                                            qnr_bin, tmp2);
 243                 if (res < 0)
 244                         goto fail;
 245                 found_ctr = const_time_select_u8(found, found_ctr, ctr);
 246                 /* found is 0 or 0xff here and res is 0 or 1. Bitwise OR of them
 247                  * (with res converted to 0/0xff and masked with prf being below
 248                  * prime) handles this in constant time.
 249                  */
 250                 found |= (res & in_range) * 0xff;
 251         }
 252         if (found == 0) {
 253                 wpa_printf(MSG_INFO,
 254                            "EAP-pwd: unable to find random point on curve for group %d, something's fishy",
 255                            num);
 256                 goto fail;
 257         }
 258
 259         /*
 260          * We know x_candidate is a quadratic residue so set it here.
 261          */
 262         crypto_bignum_deinit(x_candidate, 1);
 263         x_candidate = crypto_bignum_init_set(x_bin, primebytelen);
 264         if (!x_candidate ||
 265             crypto_ec_point_solve_y_coord(grp->group, grp->pwe, x_candidate,
 266                                           is_odd) != 0) {
 267                 wpa_printf(MSG_INFO, "EAP-pwd: Could not solve for y");
 268                 goto fail;
 269         }
 270
 271         /*
 272          * If there's a solution to the equation then the point must be on the
 273          * curve so why check again explicitly? OpenSSL code says this is
 274          * required by X9.62. We're not X9.62 but it can't hurt just to be sure.
 275          */
 276         if (!crypto_ec_point_is_on_curve(grp->group, grp->pwe)) {
 277                 wpa_printf(MSG_INFO, "EAP-pwd: point is not on curve");
 278                 goto fail;
 279         }
 280
 281         wpa_printf(MSG_DEBUG, "EAP-pwd: found a PWE in %02d tries", found_ctr);
 282
 283         if (0) {
 284  fail:
 285                 crypto_ec_point_deinit(grp->pwe, 1);
 286                 grp->pwe = NULL;
 287                 ret = 1;
 288         }
 289         /* cleanliness and order.... */
 290         crypto_bignum_deinit(x_candidate, 1);
 291         crypto_bignum_deinit(tmp2, 1);
 292         crypto_bignum_deinit(qr, 1);
 293         crypto_bignum_deinit(qnr, 1);
 294         bin_clear_free(prfbuf, primebytelen);
 295         os_memset(qr_bin, 0, sizeof(qr_bin));
 296         os_memset(qnr_bin, 0, sizeof(qnr_bin));
 297         os_memset(qr_or_qnr_bin, 0, sizeof(qr_or_qnr_bin));
 298         os_memset(pwe_digest, 0, sizeof(pwe_digest));
 299
 300         return ret;
 301 }
 302
 303
 304 int compute_keys(EAP_PWD_group *grp, const struct crypto_bignum *k,
 305                  const struct crypto_bignum *peer_scalar,
 306                  const struct crypto_bignum *server_scalar,
 307                  const u8 *confirm_peer, const u8 *confirm_server,
 308                  const u32 *ciphersuite, u8 *msk, u8 *emsk, u8 *session_id)
 309 {
 310         struct crypto_hash *hash;
 311         u8 mk[SHA256_MAC_LEN], *cruft;
 312         u8 msk_emsk[EAP_MSK_LEN + EAP_EMSK_LEN];
 313         size_t prime_len, order_len;
 314
 315         prime_len = crypto_ec_prime_len(grp->group);
 316         order_len = crypto_ec_order_len(grp->group);
 317
 318         cruft = os_malloc(prime_len);
 319         if (!cruft)
 320                 return -1;
 321
 322         /*
 323          * first compute the session-id = TypeCode | H(ciphersuite | scal_p |
 324          *      scal_s)
 325          */
 326         session_id[0] = EAP_TYPE_PWD;
 327         hash = eap_pwd_h_init();
 328         if (hash == NULL) {
 329                 os_free(cruft);
 330                 return -1;
 331         }
 332         eap_pwd_h_update(hash, (const u8 *) ciphersuite, sizeof(u32));
 333         crypto_bignum_to_bin(peer_scalar, cruft, order_len, order_len);
 334         eap_pwd_h_update(hash, cruft, order_len);
 335         crypto_bignum_to_bin(server_scalar, cruft, order_len, order_len);
 336         eap_pwd_h_update(hash, cruft, order_len);
 337         eap_pwd_h_final(hash, &session_id[1]);
 338
 339         /* then compute MK = H(k | confirm-peer | confirm-server) */
 340         hash = eap_pwd_h_init();
 341         if (hash == NULL) {
 342                 os_free(cruft);
 343                 return -1;
 344         }
 345         crypto_bignum_to_bin(k, cruft, prime_len, prime_len);
 346         eap_pwd_h_update(hash, cruft, prime_len);
 347         os_free(cruft);
 348         eap_pwd_h_update(hash, confirm_peer, SHA256_MAC_LEN);
 349         eap_pwd_h_update(hash, confirm_server, SHA256_MAC_LEN);
 350         eap_pwd_h_final(hash, mk);
 351
 352         /* stretch the mk with the session-id to get MSK | EMSK */
 353         if (eap_pwd_kdf(mk, SHA256_MAC_LEN,
 354                         session_id, SHA256_MAC_LEN + 1,
 355                         msk_emsk, (EAP_MSK_LEN + EAP_EMSK_LEN) * 8) < 0) {
 356                 return -1;
 357         }
 358
 359         os_memcpy(msk, msk_emsk, EAP_MSK_LEN);
 360         os_memcpy(emsk, msk_emsk + EAP_MSK_LEN, EAP_EMSK_LEN);
 361
 362         return 1;
 363 }
 364
 365
 366 static int eap_pwd_element_coord_ok(const struct crypto_bignum *prime,
 367                                     const u8 *buf, size_t len)
 368 {
 369         struct crypto_bignum *val;
 370         int ok = 1;
 371
 372         val = crypto_bignum_init_set(buf, len);
 373         if (!val || crypto_bignum_is_zero(val) ||
 374             crypto_bignum_cmp(val, prime) >= 0)
 375                 ok = 0;
 376         crypto_bignum_deinit(val, 0);
 377         return ok;
 378 }
 379
 380
 381 struct crypto_ec_point * eap_pwd_get_element(EAP_PWD_group *group,
 382                                              const u8 *buf)
 383 {
 384         struct crypto_ec_point *element;
 385         const struct crypto_bignum *prime;
 386         size_t prime_len;
 387
 388         prime = crypto_ec_get_prime(group->group);
 389         prime_len = crypto_ec_prime_len(group->group);
 390
 391         /* RFC 5931, 2.8.5.2.2: 0 < x,y < p */
 392         if (!eap_pwd_element_coord_ok(prime, buf, prime_len) ||
 393             !eap_pwd_element_coord_ok(prime, buf + prime_len, prime_len)) {
 394                 wpa_printf(MSG_INFO, "EAP-pwd: Invalid coordinate in element");
 395                 return NULL;
 396         }
 397
 398         element = crypto_ec_point_from_bin(group->group, buf);
 399         if (!element) {
 400                 wpa_printf(MSG_INFO, "EAP-pwd: EC point from element failed");
 401                 return NULL;
 402         }
 403
 404         /* RFC 5931, 2.8.5.2.2: on curve and not the point at infinity */
 405         if (!crypto_ec_point_is_on_curve(group->group, element) ||
 406             crypto_ec_point_is_at_infinity(group->group, element)) {
 407                 wpa_printf(MSG_INFO, "EAP-pwd: Invalid element");
 408                 goto fail;
 409         }
 410
 411 out:
 412         return element;
 413 fail:
 414         crypto_ec_point_deinit(element, 0);
 415         element = NULL;
 416         goto out;
 417 }
 418
 419
 420 struct crypto_bignum * eap_pwd_get_scalar(EAP_PWD_group *group, const u8 *buf)
 421 {
 422         struct crypto_bignum *scalar;
 423         const struct crypto_bignum *order;
 424         size_t order_len;
 425
 426         order = crypto_ec_get_order(group->group);
 427         order_len = crypto_ec_order_len(group->group);
 428
 429         /* RFC 5931, 2.8.5.2: 1 < scalar < r */
 430         scalar = crypto_bignum_init_set(buf, order_len);
 431         if (!scalar || crypto_bignum_is_zero(scalar) ||
 432             crypto_bignum_is_one(scalar) ||
 433             crypto_bignum_cmp(scalar, order) >= 0) {
 434                 wpa_printf(MSG_INFO, "EAP-pwd: received scalar is invalid");
 435                 crypto_bignum_deinit(scalar, 0);
 436                 scalar = NULL;
 437         }
 438
 439         return scalar;
 440 }
 441
 442
 443 int eap_pwd_get_rand_mask(EAP_PWD_group *group, struct crypto_bignum *_rand,
 444                           struct crypto_bignum *_mask,
 445                           struct crypto_bignum *scalar)
 446 {
 447         return dragonfly_generate_scalar(crypto_ec_get_order(group->group),
 448                                          _rand, _mask, scalar);
 449 }