1/*
2 * Shared Dragonfly functionality
3 * Copyright (c) 2012-2016, Jouni Malinen <j@w1.fi>
4 * Copyright (c) 2019, The Linux Foundation
5 *
6 * This software may be distributed under the terms of the BSD license.
7 * See README for more details.
8 */
9
10#include "utils/includes.h"
11
12#include "utils/common.h"
13#include "utils/const_time.h"
14#include "crypto/crypto.h"
15#include "dragonfly.h"
16
17
18int dragonfly_suitable_group(int group, int ecc_only)
19{
20	/* Enforce REVmd rules on which SAE groups are suitable for production
21	 * purposes: FFC groups whose prime is >= 3072 bits and ECC groups
22	 * defined over a prime field whose prime is >= 256 bits. Furthermore,
23	 * ECC groups defined over a characteristic 2 finite field and ECC
24	 * groups with a co-factor greater than 1 are not suitable. Disable
25	 * groups that use Brainpool curves as well for now since they leak more
26	 * timing information due to the prime not being close to a power of
27	 * two. */
28	return group == 19 || group == 20 || group == 21 ||
29		(!ecc_only &&
30		 (group == 15 || group == 16 || group == 17 || group == 18));
31}
32
33
34unsigned int dragonfly_min_pwe_loop_iter(int group)
35{
36	if (group == 22 || group == 23 || group == 24) {
37		/* FFC groups for which pwd-value is likely to be >= p
38		 * frequently */
39		return 40;
40	}
41
42	if (group == 1 || group == 2 || group == 5 || group == 14 ||
43	    group == 15 || group == 16 || group == 17 || group == 18) {
44		/* FFC groups that have prime that is close to a power of two */
45		return 1;
46	}
47
48	/* Default to 40 (this covers most ECC groups) */
49	return 40;
50}
51
52
53int dragonfly_get_random_qr_qnr(const struct crypto_bignum *prime,
54				struct crypto_bignum **qr,
55				struct crypto_bignum **qnr)
56{
57	*qr = *qnr = NULL;
58
59	while (!(*qr) || !(*qnr)) {
60		struct crypto_bignum *tmp;
61		int res;
62
63		tmp = crypto_bignum_init();
64		if (!tmp || crypto_bignum_rand(tmp, prime) < 0) {
65			crypto_bignum_deinit(tmp, 0);
66			break;
67		}
68
69		res = crypto_bignum_legendre(tmp, prime);
70		if (res == 1 && !(*qr))
71			*qr = tmp;
72		else if (res == -1 && !(*qnr))
73			*qnr = tmp;
74		else
75			crypto_bignum_deinit(tmp, 0);
76	}
77
78	if (*qr && *qnr)
79		return 0;
80	crypto_bignum_deinit(*qr, 0);
81	crypto_bignum_deinit(*qnr, 0);
82	*qr = *qnr = NULL;
83	return -1;
84}
85
86
87static struct crypto_bignum *
88dragonfly_get_rand_1_to_p_1(const struct crypto_bignum *prime)
89{
90	struct crypto_bignum *tmp, *pm1, *one;
91
92	tmp = crypto_bignum_init();
93	pm1 = crypto_bignum_init();
94	one = crypto_bignum_init_set((const u8 *) "\x01", 1);
95	if (!tmp || !pm1 || !one ||
96	    crypto_bignum_sub(prime, one, pm1) < 0 ||
97	    crypto_bignum_rand(tmp, pm1) < 0 ||
98	    crypto_bignum_add(tmp, one, tmp) < 0) {
99		crypto_bignum_deinit(tmp, 0);
100		tmp = NULL;
101	}
102
103	crypto_bignum_deinit(pm1, 0);
104	crypto_bignum_deinit(one, 0);
105	return tmp;
106}
107
108
109int dragonfly_is_quadratic_residue_blind(struct crypto_ec *ec,
110					 const u8 *qr, const u8 *qnr,
111					 const struct crypto_bignum *val)
112{
113	struct crypto_bignum *r, *num, *qr_or_qnr = NULL;
114	int check, res = -1;
115	u8 qr_or_qnr_bin[DRAGONFLY_MAX_ECC_PRIME_LEN];
116	const struct crypto_bignum *prime;
117	size_t prime_len;
118	unsigned int mask;
119
120	prime = crypto_ec_get_prime(ec);
121	prime_len = crypto_ec_prime_len(ec);
122
123	/*
124	 * Use a blinding technique to mask val while determining whether it is
125	 * a quadratic residue modulo p to avoid leaking timing information
126	 * while determining the Legendre symbol.
127	 *
128	 * v = val
129	 * r = a random number between 1 and p-1, inclusive
130	 * num = (v * r * r) modulo p
131	 */
132	r = dragonfly_get_rand_1_to_p_1(prime);
133	if (!r)
134		return -1;
135
136	num = crypto_bignum_init();
137	if (!num ||
138	    crypto_bignum_mulmod(val, r, prime, num) < 0 ||
139	    crypto_bignum_mulmod(num, r, prime, num) < 0)
140		goto fail;
141
142	/*
143	 * Need to minimize differences in handling different cases, so try to
144	 * avoid branches and timing differences.
145	 *
146	 * If r is odd:
147	 * num = (num * qr) module p
148	 * LGR(num, p) = 1 ==> quadratic residue
149	 * else:
150	 * num = (num * qnr) module p
151	 * LGR(num, p) = -1 ==> quadratic residue
152	 *
153	 * mask is set to !odd(r)
154	 */
155	mask = const_time_is_zero(crypto_bignum_is_odd(r));
156	const_time_select_bin(mask, qnr, qr, prime_len, qr_or_qnr_bin);
157	qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, prime_len);
158	if (!qr_or_qnr ||
159	    crypto_bignum_mulmod(num, qr_or_qnr, prime, num) < 0)
160		goto fail;
161	/* branchless version of check = odd(r) ? 1 : -1, */
162	check = const_time_select_int(mask, -1, 1);
163
164	/* Determine the Legendre symbol on the masked value */
165	res = crypto_bignum_legendre(num, prime);
166	if (res == -2) {
167		res = -1;
168		goto fail;
169	}
170	/* branchless version of res = res == check
171	 * (res is -1, 0, or 1; check is -1 or 1) */
172	mask = const_time_eq(res, check);
173	res = const_time_select_int(mask, 1, 0);
174fail:
175	crypto_bignum_deinit(num, 1);
176	crypto_bignum_deinit(r, 1);
177	crypto_bignum_deinit(qr_or_qnr, 1);
178	return res;
179}
180
181
182static int dragonfly_get_rand_2_to_r_1(struct crypto_bignum *val,
183				       const struct crypto_bignum *order)
184{
185	return crypto_bignum_rand(val, order) == 0 &&
186		!crypto_bignum_is_zero(val) &&
187		!crypto_bignum_is_one(val);
188}
189
190
191int dragonfly_generate_scalar(const struct crypto_bignum *order,
192			      struct crypto_bignum *_rand,
193			      struct crypto_bignum *_mask,
194			      struct crypto_bignum *scalar)
195{
196	int count;
197
198	/* Select two random values rand,mask such that 1 < rand,mask < r and
199	 * rand + mask mod r > 1. */
200	for (count = 0; count < 100; count++) {
201		if (dragonfly_get_rand_2_to_r_1(_rand, order) &&
202		    dragonfly_get_rand_2_to_r_1(_mask, order) &&
203		    crypto_bignum_add(_rand, _mask, scalar) == 0 &&
204		    crypto_bignum_mod(scalar, order, scalar) == 0 &&
205		    !crypto_bignum_is_zero(scalar) &&
206		    !crypto_bignum_is_one(scalar))
207			return 0;
208	}
209
210	/* This should not be reachable in practice if the random number
211	 * generation is working. */
212	wpa_printf(MSG_INFO,
213		   "dragonfly: Unable to get randomness for own scalar");
214	return -1;
215}
216
217
218/* res = sqrt(val) */
219int dragonfly_sqrt(struct crypto_ec *ec, const struct crypto_bignum *val,
220		   struct crypto_bignum *res)
221{
222	const struct crypto_bignum *prime;
223	struct crypto_bignum *tmp, *one;
224	int ret = 0;
225	u8 prime_bin[DRAGONFLY_MAX_ECC_PRIME_LEN];
226	size_t prime_len;
227
228	/* For prime p such that p = 3 mod 4, sqrt(w) = w^((p+1)/4) mod p */
229
230	prime = crypto_ec_get_prime(ec);
231	prime_len = crypto_ec_prime_len(ec);
232	tmp = crypto_bignum_init();
233	one = crypto_bignum_init_uint(1);
234
235	if (crypto_bignum_to_bin(prime, prime_bin, sizeof(prime_bin),
236				 prime_len) < 0 ||
237	    (prime_bin[prime_len - 1] & 0x03) != 3 ||
238	    !tmp || !one ||
239	    /* tmp = (p+1)/4 */
240	    crypto_bignum_add(prime, one, tmp) < 0 ||
241	    crypto_bignum_rshift(tmp, 2, tmp) < 0 ||
242	    /* res = sqrt(val) */
243	    crypto_bignum_exptmod(val, tmp, prime, res) < 0)
244		ret = -1;
245
246	crypto_bignum_deinit(tmp, 0);
247	crypto_bignum_deinit(one, 0);
248	return ret;
249}
250