2 * EAP server/peer: EAP-pwd shared routines
3 * Copyright (c) 2010, Dan Harkins <dharkins@lounge.org>
5 * This software may be distributed under the terms of the BSD license.
6 * See README for more details.
11 #include "crypto/sha256.h"
12 #include "crypto/crypto.h"
14 #include "eap_pwd_common.h"
16 /* The random function H(x) = HMAC-SHA256(0^32, x) */
17 struct crypto_hash * eap_pwd_h_init(void)
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,
26 void eap_pwd_h_update(struct crypto_hash *hash, const u8 *data, size_t len)
28 crypto_hash_update(hash, data, len);
32 void eap_pwd_h_final(struct crypto_hash *hash, u8 *digest)
34 size_t len = SHA256_MAC_LEN;
35 crypto_hash_finish(hash, digest, &len);
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)
43 struct crypto_hash *hash;
44 u8 digest[SHA256_MAC_LEN];
46 size_t resultbytelen, len = 0, mdlen;
48 resultbytelen = (resultbitlen + 7) / 8;
50 L = htons(resultbitlen);
51 while (len < resultbytelen) {
54 hash = crypto_hash_init(CRYPTO_HASH_ALG_HMAC_SHA256,
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)
66 if ((len + mdlen) > resultbytelen)
67 os_memcpy(result + len, digest, resultbytelen - len);
69 os_memcpy(result + len, digest, mdlen);
73 /* since we're expanding to a bit length, mask off the excess */
74 if (resultbitlen % 8) {
76 mask <<= (8 - (resultbitlen % 8));
77 result[resultbytelen - 1] &= mask;
84 EAP_PWD_group * get_eap_pwd_group(u16 num)
88 grp = os_zalloc(sizeof(EAP_PWD_group));
91 grp->group = crypto_ec_init(num);
93 wpa_printf(MSG_INFO, "EAP-pwd: unable to create EC group");
99 wpa_printf(MSG_INFO, "EAP-pwd: provisioned group %d", num);
106 * compute a "random" secret point on an elliptic curve based
107 * on the password and identities.
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,
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;
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");
138 if (crypto_ec_cofactor(grp->group, cofactor) < 0) {
139 wpa_printf(MSG_INFO, "EAP-pwd: unable to get cofactor for "
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 "
150 if (crypto_bignum_sub(prime, one, pm1) < 0)
153 /* get a random quadratic residue and nonresidue */
154 while (!qr || !qnr) {
157 if (crypto_bignum_rand(tmp1, prime) < 0)
159 res = crypto_bignum_legendre(tmp1, prime);
160 if (!qr && res == 1) {
162 tmp1 = crypto_bignum_init();
163 } else if (!qnr && res == -1) {
165 tmp1 = crypto_bignum_init();
171 os_memset(prfbuf, 0, primebytelen);
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.
183 * compute counter-mode password value and stretch to prime
184 * pwd-seed = H(token | peer-id | server-id | password |
187 hash = eap_pwd_h_init();
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);
197 crypto_bignum_deinit(rnd, 1);
198 rnd = crypto_bignum_init_set(pwe_digest, SHA256_MAC_LEN);
200 wpa_printf(MSG_INFO, "EAP-pwd: unable to create rnd");
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)
209 crypto_bignum_deinit(x_candidate, 1);
210 x_candidate = crypto_bignum_init_set(prfbuf, primebytelen);
213 "EAP-pwd: unable to create x_candidate");
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.
224 if ((primebitlen % 8) &&
225 crypto_bignum_rshift(x_candidate,
226 (8 - (primebitlen % 8)),
230 if (crypto_bignum_cmp(x_candidate, prime) >= 0)
233 wpa_hexdump(MSG_DEBUG, "EAP-pwd: x_candidate",
234 prfbuf, primebytelen);
237 * compute y^2 using the equation of the curve
241 tmp2 = crypto_ec_point_compute_y_sqr(grp->group, x_candidate);
246 * mask tmp2 so doing legendre won't leak timing info
248 * tmp1 is a random number between 1 and p-1
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)
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.
260 * Flip a coin, multiply by the random quadratic residue or the
261 * random quadratic nonresidue and record heads or tails.
263 if (crypto_bignum_is_odd(tmp1)) {
264 crypto_bignum_mulmod(tmp2, qr, prime, tmp2);
267 crypto_bignum_mulmod(tmp2, qnr, prime, tmp2);
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).
277 if (crypto_bignum_legendre(tmp2, prime) == check) {
281 /* need to unambiguously identify the solution */
282 is_odd = crypto_bignum_is_odd(rnd);
285 * We know x_candidate is a quadratic residue so set
288 if (crypto_ec_point_solve_y_coord(grp->group, grp->pwe,
292 "EAP-pwd: Could not solve for y");
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.
302 if (!crypto_ec_point_is_on_curve(grp->group,
305 "EAP-pwd: point is not on curve");
309 if (!crypto_bignum_is_one(cofactor)) {
310 /* make sure the point is not in a small
312 if (crypto_ec_point_mul(grp->group, grp->pwe,
316 "EAP-pwd: cannot multiply generator by order");
319 if (crypto_ec_point_is_at_infinity(grp->group,
322 "EAP-pwd: point is at infinity");
326 wpa_printf(MSG_DEBUG,
327 "EAP-pwd: found a PWE in %d tries", ctr);
333 "EAP-pwd: unable to find random point on curve for group %d, something's fishy",
339 crypto_ec_point_deinit(grp->pwe, 1);
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);
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)
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;
370 prime_len = crypto_ec_prime_len(grp->group);
371 order_len = crypto_ec_order_len(grp->group);
373 cruft = os_malloc(prime_len);
378 * first compute the session-id = TypeCode | H(ciphersuite | scal_p |
381 session_id[0] = EAP_TYPE_PWD;
382 hash = eap_pwd_h_init();
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]);
394 /* then compute MK = H(k | confirm-peer | confirm-server) */
395 hash = eap_pwd_h_init();
400 crypto_bignum_to_bin(k, cruft, prime_len, prime_len);
401 eap_pwd_h_update(hash, cruft, prime_len);
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);
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) {
414 os_memcpy(msk, msk_emsk, EAP_MSK_LEN);
415 os_memcpy(emsk, msk_emsk + EAP_MSK_LEN, EAP_EMSK_LEN);