xref: /freebsd/contrib/wpa/src/eap_common/eap_pwd_common.c (revision cddbc3b40812213ff00041f79174cac0be360a2a)
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