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
dragonfly_suitable_group(int group,int ecc_only)18 int 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
dragonfly_min_pwe_loop_iter(int group)34 unsigned 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
dragonfly_get_random_qr_qnr(const struct crypto_bignum * prime,struct crypto_bignum ** qr,struct crypto_bignum ** qnr)53 int 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 if (res == -2)
77 break;
78 }
79 }
80
81 if (*qr && *qnr)
82 return 0;
83 crypto_bignum_deinit(*qr, 0);
84 crypto_bignum_deinit(*qnr, 0);
85 *qr = *qnr = NULL;
86 return -1;
87 }
88
89
90 static struct crypto_bignum *
dragonfly_get_rand_1_to_p_1(const struct crypto_bignum * prime)91 dragonfly_get_rand_1_to_p_1(const struct crypto_bignum *prime)
92 {
93 struct crypto_bignum *tmp, *pm1, *one;
94
95 tmp = crypto_bignum_init();
96 pm1 = crypto_bignum_init();
97 one = crypto_bignum_init_set((const u8 *) "\x01", 1);
98 if (!tmp || !pm1 || !one ||
99 crypto_bignum_sub(prime, one, pm1) < 0 ||
100 crypto_bignum_rand(tmp, pm1) < 0 ||
101 crypto_bignum_add(tmp, one, tmp) < 0) {
102 crypto_bignum_deinit(tmp, 0);
103 tmp = NULL;
104 }
105
106 crypto_bignum_deinit(pm1, 0);
107 crypto_bignum_deinit(one, 0);
108 return tmp;
109 }
110
111
dragonfly_is_quadratic_residue_blind(struct crypto_ec * ec,const u8 * qr,const u8 * qnr,const struct crypto_bignum * val)112 int dragonfly_is_quadratic_residue_blind(struct crypto_ec *ec,
113 const u8 *qr, const u8 *qnr,
114 const struct crypto_bignum *val)
115 {
116 struct crypto_bignum *r, *num, *qr_or_qnr = NULL;
117 int check, res = -1;
118 u8 qr_or_qnr_bin[DRAGONFLY_MAX_ECC_PRIME_LEN];
119 const struct crypto_bignum *prime;
120 size_t prime_len;
121 unsigned int mask;
122
123 prime = crypto_ec_get_prime(ec);
124 prime_len = crypto_ec_prime_len(ec);
125
126 /*
127 * Use a blinding technique to mask val while determining whether it is
128 * a quadratic residue modulo p to avoid leaking timing information
129 * while determining the Legendre symbol.
130 *
131 * v = val
132 * r = a random number between 1 and p-1, inclusive
133 * num = (v * r * r) modulo p
134 */
135 r = dragonfly_get_rand_1_to_p_1(prime);
136 if (!r)
137 return -1;
138
139 num = crypto_bignum_init();
140 if (!num ||
141 crypto_bignum_mulmod(val, r, prime, num) < 0 ||
142 crypto_bignum_mulmod(num, r, prime, num) < 0)
143 goto fail;
144
145 /*
146 * Need to minimize differences in handling different cases, so try to
147 * avoid branches and timing differences.
148 *
149 * If r is odd:
150 * num = (num * qr) module p
151 * LGR(num, p) = 1 ==> quadratic residue
152 * else:
153 * num = (num * qnr) module p
154 * LGR(num, p) = -1 ==> quadratic residue
155 *
156 * mask is set to !odd(r)
157 */
158 mask = const_time_is_zero(crypto_bignum_is_odd(r));
159 const_time_select_bin(mask, qnr, qr, prime_len, qr_or_qnr_bin);
160 qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, prime_len);
161 if (!qr_or_qnr ||
162 crypto_bignum_mulmod(num, qr_or_qnr, prime, num) < 0)
163 goto fail;
164 /* branchless version of check = odd(r) ? 1 : -1, */
165 check = const_time_select_int(mask, -1, 1);
166
167 /* Determine the Legendre symbol on the masked value */
168 res = crypto_bignum_legendre(num, prime);
169 if (res == -2) {
170 res = -1;
171 goto fail;
172 }
173 /* branchless version of res = res == check
174 * (res is -1, 0, or 1; check is -1 or 1) */
175 mask = const_time_eq(res, check);
176 res = const_time_select_int(mask, 1, 0);
177 fail:
178 crypto_bignum_deinit(num, 1);
179 crypto_bignum_deinit(r, 1);
180 crypto_bignum_deinit(qr_or_qnr, 1);
181 return res;
182 }
183
184
dragonfly_get_rand_2_to_r_1(struct crypto_bignum * val,const struct crypto_bignum * order)185 static int dragonfly_get_rand_2_to_r_1(struct crypto_bignum *val,
186 const struct crypto_bignum *order)
187 {
188 return crypto_bignum_rand(val, order) == 0 &&
189 !crypto_bignum_is_zero(val) &&
190 !crypto_bignum_is_one(val);
191 }
192
193
dragonfly_generate_scalar(const struct crypto_bignum * order,struct crypto_bignum * _rand,struct crypto_bignum * _mask,struct crypto_bignum * scalar)194 int dragonfly_generate_scalar(const struct crypto_bignum *order,
195 struct crypto_bignum *_rand,
196 struct crypto_bignum *_mask,
197 struct crypto_bignum *scalar)
198 {
199 int count;
200
201 /* Select two random values rand,mask such that 1 < rand,mask < r and
202 * rand + mask mod r > 1. */
203 for (count = 0; count < 100; count++) {
204 if (dragonfly_get_rand_2_to_r_1(_rand, order) &&
205 dragonfly_get_rand_2_to_r_1(_mask, order) &&
206 crypto_bignum_add(_rand, _mask, scalar) == 0 &&
207 crypto_bignum_mod(scalar, order, scalar) == 0 &&
208 !crypto_bignum_is_zero(scalar) &&
209 !crypto_bignum_is_one(scalar))
210 return 0;
211 }
212
213 /* This should not be reachable in practice if the random number
214 * generation is working. */
215 wpa_printf(MSG_INFO,
216 "dragonfly: Unable to get randomness for own scalar");
217 return -1;
218 }
219
220
221 /* res = sqrt(val) */
dragonfly_sqrt(struct crypto_ec * ec,const struct crypto_bignum * val,struct crypto_bignum * res)222 int dragonfly_sqrt(struct crypto_ec *ec, const struct crypto_bignum *val,
223 struct crypto_bignum *res)
224 {
225 const struct crypto_bignum *prime;
226 struct crypto_bignum *tmp, *one;
227 int ret = 0;
228 u8 prime_bin[DRAGONFLY_MAX_ECC_PRIME_LEN];
229 size_t prime_len;
230
231 /* For prime p such that p = 3 mod 4, sqrt(w) = w^((p+1)/4) mod p */
232
233 prime = crypto_ec_get_prime(ec);
234 prime_len = crypto_ec_prime_len(ec);
235 tmp = crypto_bignum_init();
236 one = crypto_bignum_init_uint(1);
237
238 if (crypto_bignum_to_bin(prime, prime_bin, sizeof(prime_bin),
239 prime_len) < 0 ||
240 (prime_bin[prime_len - 1] & 0x03) != 3 ||
241 !tmp || !one ||
242 /* tmp = (p+1)/4 */
243 crypto_bignum_add(prime, one, tmp) < 0 ||
244 crypto_bignum_rshift(tmp, 2, tmp) < 0 ||
245 /* res = sqrt(val) */
246 crypto_bignum_exptmod(val, tmp, prime, res) < 0)
247 ret = -1;
248
249 crypto_bignum_deinit(tmp, 0);
250 crypto_bignum_deinit(one, 0);
251 return ret;
252 }
253