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 "crypto/sha256.h" 12 #include "crypto/crypto.h" 13 #include "eap_defs.h" 14 #include "eap_pwd_common.h" 15 16 /* The random function H(x) = HMAC-SHA256(0^32, x) */ 17 struct crypto_hash * eap_pwd_h_init(void) 18 { 19 u8 allzero[SHA256_MAC_LEN]; 20 os_memset(allzero, 0, SHA256_MAC_LEN); 21 return crypto_hash_init(CRYPTO_HASH_ALG_HMAC_SHA256, allzero, 22 SHA256_MAC_LEN); 23 } 24 25 26 void eap_pwd_h_update(struct crypto_hash *hash, const u8 *data, size_t len) 27 { 28 crypto_hash_update(hash, data, len); 29 } 30 31 32 void eap_pwd_h_final(struct crypto_hash *hash, u8 *digest) 33 { 34 size_t len = SHA256_MAC_LEN; 35 crypto_hash_finish(hash, digest, &len); 36 } 37 38 39 /* a counter-based KDF based on NIST SP800-108 */ 40 static int eap_pwd_kdf(const u8 *key, size_t keylen, const u8 *label, 41 size_t labellen, u8 *result, size_t resultbitlen) 42 { 43 struct crypto_hash *hash; 44 u8 digest[SHA256_MAC_LEN]; 45 u16 i, ctr, L; 46 size_t resultbytelen, len = 0, mdlen; 47 48 resultbytelen = (resultbitlen + 7) / 8; 49 ctr = 0; 50 L = htons(resultbitlen); 51 while (len < resultbytelen) { 52 ctr++; 53 i = htons(ctr); 54 hash = crypto_hash_init(CRYPTO_HASH_ALG_HMAC_SHA256, 55 key, keylen); 56 if (hash == NULL) 57 return -1; 58 if (ctr > 1) 59 crypto_hash_update(hash, digest, SHA256_MAC_LEN); 60 crypto_hash_update(hash, (u8 *) &i, sizeof(u16)); 61 crypto_hash_update(hash, label, labellen); 62 crypto_hash_update(hash, (u8 *) &L, sizeof(u16)); 63 mdlen = SHA256_MAC_LEN; 64 if (crypto_hash_finish(hash, digest, &mdlen) < 0) 65 return -1; 66 if ((len + mdlen) > resultbytelen) 67 os_memcpy(result + len, digest, resultbytelen - len); 68 else 69 os_memcpy(result + len, digest, mdlen); 70 len += mdlen; 71 } 72 73 /* since we're expanding to a bit length, mask off the excess */ 74 if (resultbitlen % 8) { 75 u8 mask = 0xff; 76 mask <<= (8 - (resultbitlen % 8)); 77 result[resultbytelen - 1] &= mask; 78 } 79 80 return 0; 81 } 82 83 84 EAP_PWD_group * get_eap_pwd_group(u16 num) 85 { 86 EAP_PWD_group *grp; 87 88 grp = os_zalloc(sizeof(EAP_PWD_group)); 89 if (!grp) 90 return NULL; 91 grp->group = crypto_ec_init(num); 92 if (!grp->group) { 93 wpa_printf(MSG_INFO, "EAP-pwd: unable to create EC group"); 94 os_free(grp); 95 return NULL; 96 } 97 98 grp->group_num = num; 99 wpa_printf(MSG_INFO, "EAP-pwd: provisioned group %d", num); 100 101 return grp; 102 } 103 104 105 /* 106 * compute a "random" secret point on an elliptic curve based 107 * on the password and identities. 108 */ 109 int compute_password_element(EAP_PWD_group *grp, u16 num, 110 const u8 *password, size_t password_len, 111 const u8 *id_server, size_t id_server_len, 112 const u8 *id_peer, size_t id_peer_len, 113 const u8 *token) 114 { 115 struct crypto_bignum *qr = NULL, *qnr = NULL, *one = NULL; 116 struct crypto_bignum *tmp1 = NULL, *tmp2 = NULL, *pm1 = NULL; 117 struct crypto_hash *hash; 118 unsigned char pwe_digest[SHA256_MAC_LEN], *prfbuf = NULL, ctr; 119 int is_odd, ret = 0, check, found = 0; 120 size_t primebytelen, primebitlen; 121 struct crypto_bignum *x_candidate = NULL, *rnd = NULL, *cofactor = NULL; 122 const struct crypto_bignum *prime; 123 124 if (grp->pwe) 125 return -1; 126 127 prime = crypto_ec_get_prime(grp->group); 128 cofactor = crypto_bignum_init(); 129 grp->pwe = crypto_ec_point_init(grp->group); 130 tmp1 = crypto_bignum_init(); 131 pm1 = crypto_bignum_init(); 132 one = crypto_bignum_init_set((const u8 *) "\x01", 1); 133 if (!cofactor || !grp->pwe || !tmp1 || !pm1 || !one) { 134 wpa_printf(MSG_INFO, "EAP-pwd: unable to create bignums"); 135 goto fail; 136 } 137 138 if (crypto_ec_cofactor(grp->group, cofactor) < 0) { 139 wpa_printf(MSG_INFO, "EAP-pwd: unable to get cofactor for " 140 "curve"); 141 goto fail; 142 } 143 primebitlen = crypto_ec_prime_len_bits(grp->group); 144 primebytelen = crypto_ec_prime_len(grp->group); 145 if ((prfbuf = os_malloc(primebytelen)) == NULL) { 146 wpa_printf(MSG_INFO, "EAP-pwd: unable to malloc space for prf " 147 "buffer"); 148 goto fail; 149 } 150 if (crypto_bignum_sub(prime, one, pm1) < 0) 151 goto fail; 152 153 /* get a random quadratic residue and nonresidue */ 154 while (!qr || !qnr) { 155 int res; 156 157 if (crypto_bignum_rand(tmp1, prime) < 0) 158 goto fail; 159 res = crypto_bignum_legendre(tmp1, prime); 160 if (!qr && res == 1) { 161 qr = tmp1; 162 tmp1 = crypto_bignum_init(); 163 } else if (!qnr && res == -1) { 164 qnr = tmp1; 165 tmp1 = crypto_bignum_init(); 166 } 167 if (!tmp1) 168 goto fail; 169 } 170 171 os_memset(prfbuf, 0, primebytelen); 172 ctr = 0; 173 174 /* 175 * Run through the hunting-and-pecking loop 40 times to mask the time 176 * necessary to find PWE. The odds of PWE not being found in 40 loops is 177 * roughly 1 in 1 trillion. 178 */ 179 while (ctr < 40) { 180 ctr++; 181 182 /* 183 * compute counter-mode password value and stretch to prime 184 * pwd-seed = H(token | peer-id | server-id | password | 185 * counter) 186 */ 187 hash = eap_pwd_h_init(); 188 if (hash == NULL) 189 goto fail; 190 eap_pwd_h_update(hash, token, sizeof(u32)); 191 eap_pwd_h_update(hash, id_peer, id_peer_len); 192 eap_pwd_h_update(hash, id_server, id_server_len); 193 eap_pwd_h_update(hash, password, password_len); 194 eap_pwd_h_update(hash, &ctr, sizeof(ctr)); 195 eap_pwd_h_final(hash, pwe_digest); 196 197 crypto_bignum_deinit(rnd, 1); 198 rnd = crypto_bignum_init_set(pwe_digest, SHA256_MAC_LEN); 199 if (!rnd) { 200 wpa_printf(MSG_INFO, "EAP-pwd: unable to create rnd"); 201 goto fail; 202 } 203 if (eap_pwd_kdf(pwe_digest, SHA256_MAC_LEN, 204 (u8 *) "EAP-pwd Hunting And Pecking", 205 os_strlen("EAP-pwd Hunting And Pecking"), 206 prfbuf, primebitlen) < 0) 207 goto fail; 208 209 crypto_bignum_deinit(x_candidate, 1); 210 x_candidate = crypto_bignum_init_set(prfbuf, primebytelen); 211 if (!x_candidate) { 212 wpa_printf(MSG_INFO, 213 "EAP-pwd: unable to create x_candidate"); 214 goto fail; 215 } 216 217 /* 218 * eap_pwd_kdf() returns a string of bits 0..primebitlen but 219 * BN_bin2bn will treat that string of bits as a big endian 220 * number. If the primebitlen is not an even multiple of 8 221 * then excessive bits-- those _after_ primebitlen-- so now 222 * we have to shift right the amount we masked off. 223 */ 224 if ((primebitlen % 8) && 225 crypto_bignum_rshift(x_candidate, 226 (8 - (primebitlen % 8)), 227 x_candidate) < 0) 228 goto fail; 229 230 if (crypto_bignum_cmp(x_candidate, prime) >= 0) 231 continue; 232 233 wpa_hexdump(MSG_DEBUG, "EAP-pwd: x_candidate", 234 prfbuf, primebytelen); 235 236 /* 237 * compute y^2 using the equation of the curve 238 * 239 * y^2 = x^3 + ax + b 240 */ 241 tmp2 = crypto_ec_point_compute_y_sqr(grp->group, x_candidate); 242 if (!tmp2) 243 goto fail; 244 245 /* 246 * mask tmp2 so doing legendre won't leak timing info 247 * 248 * tmp1 is a random number between 1 and p-1 249 */ 250 if (crypto_bignum_rand(tmp1, pm1) < 0 || 251 crypto_bignum_mulmod(tmp2, tmp1, prime, tmp2) < 0 || 252 crypto_bignum_mulmod(tmp2, tmp1, prime, tmp2) < 0) 253 goto fail; 254 255 /* 256 * Now tmp2 (y^2) is masked, all values between 1 and p-1 257 * are equally probable. Multiplying by r^2 does not change 258 * whether or not tmp2 is a quadratic residue, just masks it. 259 * 260 * Flip a coin, multiply by the random quadratic residue or the 261 * random quadratic nonresidue and record heads or tails. 262 */ 263 if (crypto_bignum_is_odd(tmp1)) { 264 crypto_bignum_mulmod(tmp2, qr, prime, tmp2); 265 check = 1; 266 } else { 267 crypto_bignum_mulmod(tmp2, qnr, prime, tmp2); 268 check = -1; 269 } 270 271 /* 272 * Now it's safe to do legendre, if check is 1 then it's 273 * a straightforward test (multiplying by qr does not 274 * change result), if check is -1 then it's the opposite test 275 * (multiplying a qr by qnr would make a qnr). 276 */ 277 if (crypto_bignum_legendre(tmp2, prime) == check) { 278 if (found == 1) 279 continue; 280 281 /* need to unambiguously identify the solution */ 282 is_odd = crypto_bignum_is_odd(rnd); 283 284 /* 285 * We know x_candidate is a quadratic residue so set 286 * it here. 287 */ 288 if (crypto_ec_point_solve_y_coord(grp->group, grp->pwe, 289 x_candidate, 290 is_odd) != 0) { 291 wpa_printf(MSG_INFO, 292 "EAP-pwd: Could not solve for y"); 293 continue; 294 } 295 296 /* 297 * If there's a solution to the equation then the point 298 * must be on the curve so why check again explicitly? 299 * OpenSSL code says this is required by X9.62. We're 300 * not X9.62 but it can't hurt just to be sure. 301 */ 302 if (!crypto_ec_point_is_on_curve(grp->group, 303 grp->pwe)) { 304 wpa_printf(MSG_INFO, 305 "EAP-pwd: point is not on curve"); 306 continue; 307 } 308 309 if (!crypto_bignum_is_one(cofactor)) { 310 /* make sure the point is not in a small 311 * sub-group */ 312 if (crypto_ec_point_mul(grp->group, grp->pwe, 313 cofactor, 314 grp->pwe) != 0) { 315 wpa_printf(MSG_INFO, 316 "EAP-pwd: cannot multiply generator by order"); 317 continue; 318 } 319 if (crypto_ec_point_is_at_infinity(grp->group, 320 grp->pwe)) { 321 wpa_printf(MSG_INFO, 322 "EAP-pwd: point is at infinity"); 323 continue; 324 } 325 } 326 wpa_printf(MSG_DEBUG, 327 "EAP-pwd: found a PWE in %d tries", ctr); 328 found = 1; 329 } 330 } 331 if (found == 0) { 332 wpa_printf(MSG_INFO, 333 "EAP-pwd: unable to find random point on curve for group %d, something's fishy", 334 num); 335 goto fail; 336 } 337 if (0) { 338 fail: 339 crypto_ec_point_deinit(grp->pwe, 1); 340 grp->pwe = NULL; 341 ret = 1; 342 } 343 /* cleanliness and order.... */ 344 crypto_bignum_deinit(cofactor, 1); 345 crypto_bignum_deinit(x_candidate, 1); 346 crypto_bignum_deinit(rnd, 1); 347 crypto_bignum_deinit(pm1, 0); 348 crypto_bignum_deinit(tmp1, 1); 349 crypto_bignum_deinit(tmp2, 1); 350 crypto_bignum_deinit(qr, 1); 351 crypto_bignum_deinit(qnr, 1); 352 crypto_bignum_deinit(one, 0); 353 os_free(prfbuf); 354 355 return ret; 356 } 357 358 359 int compute_keys(EAP_PWD_group *grp, const struct crypto_bignum *k, 360 const struct crypto_bignum *peer_scalar, 361 const struct crypto_bignum *server_scalar, 362 const u8 *confirm_peer, const u8 *confirm_server, 363 const u32 *ciphersuite, u8 *msk, u8 *emsk, u8 *session_id) 364 { 365 struct crypto_hash *hash; 366 u8 mk[SHA256_MAC_LEN], *cruft; 367 u8 msk_emsk[EAP_MSK_LEN + EAP_EMSK_LEN]; 368 size_t prime_len, order_len; 369 370 prime_len = crypto_ec_prime_len(grp->group); 371 order_len = crypto_ec_order_len(grp->group); 372 373 cruft = os_malloc(prime_len); 374 if (!cruft) 375 return -1; 376 377 /* 378 * first compute the session-id = TypeCode | H(ciphersuite | scal_p | 379 * scal_s) 380 */ 381 session_id[0] = EAP_TYPE_PWD; 382 hash = eap_pwd_h_init(); 383 if (hash == NULL) { 384 os_free(cruft); 385 return -1; 386 } 387 eap_pwd_h_update(hash, (const u8 *) ciphersuite, sizeof(u32)); 388 crypto_bignum_to_bin(peer_scalar, cruft, order_len, order_len); 389 eap_pwd_h_update(hash, cruft, order_len); 390 crypto_bignum_to_bin(server_scalar, cruft, order_len, order_len); 391 eap_pwd_h_update(hash, cruft, order_len); 392 eap_pwd_h_final(hash, &session_id[1]); 393 394 /* then compute MK = H(k | confirm-peer | confirm-server) */ 395 hash = eap_pwd_h_init(); 396 if (hash == NULL) { 397 os_free(cruft); 398 return -1; 399 } 400 crypto_bignum_to_bin(k, cruft, prime_len, prime_len); 401 eap_pwd_h_update(hash, cruft, prime_len); 402 os_free(cruft); 403 eap_pwd_h_update(hash, confirm_peer, SHA256_MAC_LEN); 404 eap_pwd_h_update(hash, confirm_server, SHA256_MAC_LEN); 405 eap_pwd_h_final(hash, mk); 406 407 /* stretch the mk with the session-id to get MSK | EMSK */ 408 if (eap_pwd_kdf(mk, SHA256_MAC_LEN, 409 session_id, SHA256_MAC_LEN + 1, 410 msk_emsk, (EAP_MSK_LEN + EAP_EMSK_LEN) * 8) < 0) { 411 return -1; 412 } 413 414 os_memcpy(msk, msk_emsk, EAP_MSK_LEN); 415 os_memcpy(emsk, msk_emsk + EAP_MSK_LEN, EAP_EMSK_LEN); 416 417 return 1; 418 } 419