projects / openwrt / staging / yousong.git / blob
? search:


1870c497c416d9e3441ffdcefc411e2a878855c3
[openwrt/staging/yousong.git] /
1 From aaf65feac67c3993935634eefe5bc76b9fce03aa Mon Sep 17 00:00:00 2001
2 From: Jouni Malinen <jouni@codeaurora.org>
3 Date: Tue, 26 Feb 2019 11:59:45 +0200
4 Subject: [PATCH 04/14] EAP-pwd: Use constant time and memory access for
5 finding the PWE
6
7 This algorithm could leak information to external observers in form of
8 timing differences or memory access patterns (cache use). While the
9 previous implementation had protection against the most visible timing
10 differences (looping 40 rounds and masking the legendre operation), it
11 did not protect against memory access patterns between the two possible
12 code paths in the masking operations. That might be sufficient to allow
13 an unprivileged process running on the same device to be able to
14 determine which path is being executed through a cache attack and based
15 on that, determine information about the used password.
16
17 Convert the PWE finding loop to use constant time functions and
18 identical memory access path without different branches for the QR/QNR
19 cases to minimize possible side-channel information similarly to the
20 changes done for SAE authentication. (CVE-2019-9495)
21
22 Signed-off-by: Jouni Malinen <jouni@codeaurora.org>
23 ---
24 src/eap_common/eap_pwd_common.c | 187 +++++++++++++++++++++-------------------
25 1 file changed, 99 insertions(+), 88 deletions(-)
26
27 --- a/src/eap_common/eap_pwd_common.c
28 +++ b/src/eap_common/eap_pwd_common.c
29 @@ -8,11 +8,15 @@
30
31 #include "includes.h"
32 #include "common.h"
33 +#include "utils/const_time.h"
34 #include "crypto/sha256.h"
35 #include "crypto/crypto.h"
36 #include "eap_defs.h"
37 #include "eap_pwd_common.h"
38
39 +#define MAX_ECC_PRIME_LEN 66
40 +
41 +
42 /* The random function H(x) = HMAC-SHA256(0^32, x) */
43 struct crypto_hash * eap_pwd_h_init(void)
44 {
45 @@ -102,6 +106,15 @@ EAP_PWD_group * get_eap_pwd_group(u16 nu
46 }
47
48
49 +static void buf_shift_right(u8 *buf, size_t len, size_t bits)
50 +{
51 + size_t i;
52 + for (i = len - 1; i > 0; i--)
53 + buf[i] = (buf[i - 1] << (8 - bits)) | (buf[i] >> bits);
54 + buf[0] >>= bits;
55 +}
56 +
57 +
58 /*
59 * compute a "random" secret point on an elliptic curve based
60 * on the password and identities.
61 @@ -113,17 +126,27 @@ int compute_password_element(EAP_PWD_gro
62 const u8 *token)
63 {
64 struct crypto_bignum *qr = NULL, *qnr = NULL, *one = NULL;
65 + struct crypto_bignum *qr_or_qnr = NULL;
66 + u8 qr_bin[MAX_ECC_PRIME_LEN];
67 + u8 qnr_bin[MAX_ECC_PRIME_LEN];
68 + u8 qr_or_qnr_bin[MAX_ECC_PRIME_LEN];
69 + u8 x_bin[MAX_ECC_PRIME_LEN];
70 struct crypto_bignum *tmp1 = NULL, *tmp2 = NULL, *pm1 = NULL;
71 struct crypto_hash *hash;
72 unsigned char pwe_digest[SHA256_MAC_LEN], *prfbuf = NULL, ctr;
73 - int is_odd, ret = 0, check, found = 0;
74 - size_t primebytelen, primebitlen;
75 - struct crypto_bignum *x_candidate = NULL, *rnd = NULL, *cofactor = NULL;
76 + int ret = 0, check, res;
77 + u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
78 + * mask */
79 + size_t primebytelen = 0, primebitlen;
80 + struct crypto_bignum *x_candidate = NULL, *cofactor = NULL;
81 const struct crypto_bignum *prime;
82 + u8 mask, found_ctr = 0, is_odd = 0;
83
84 if (grp->pwe)
85 return -1;
86
87 + os_memset(x_bin, 0, sizeof(x_bin));
88 +
89 prime = crypto_ec_get_prime(grp->group);
90 cofactor = crypto_bignum_init();
91 grp->pwe = crypto_ec_point_init(grp->group);
92 @@ -152,8 +175,6 @@ int compute_password_element(EAP_PWD_gro
93
94 /* get a random quadratic residue and nonresidue */
95 while (!qr || !qnr) {
96 - int res;
97 -
98 if (crypto_bignum_rand(tmp1, prime) < 0)
99 goto fail;
100 res = crypto_bignum_legendre(tmp1, prime);
101 @@ -167,6 +188,11 @@ int compute_password_element(EAP_PWD_gro
102 if (!tmp1)
103 goto fail;
104 }
105 + if (crypto_bignum_to_bin(qr, qr_bin, sizeof(qr_bin),
106 + primebytelen) < 0 ||
107 + crypto_bignum_to_bin(qnr, qnr_bin, sizeof(qnr_bin),
108 + primebytelen) < 0)
109 + goto fail;
110
111 os_memset(prfbuf, 0, primebytelen);
112 ctr = 0;
113 @@ -194,17 +220,16 @@ int compute_password_element(EAP_PWD_gro
114 eap_pwd_h_update(hash, &ctr, sizeof(ctr));
115 eap_pwd_h_final(hash, pwe_digest);
116
117 - crypto_bignum_deinit(rnd, 1);
118 - rnd = crypto_bignum_init_set(pwe_digest, SHA256_MAC_LEN);
119 - if (!rnd) {
120 - wpa_printf(MSG_INFO, "EAP-pwd: unable to create rnd");
121 - goto fail;
122 - }
123 + is_odd = const_time_select_u8(
124 + found, is_odd, pwe_digest[SHA256_MAC_LEN - 1] & 0x01);
125 if (eap_pwd_kdf(pwe_digest, SHA256_MAC_LEN,
126 (u8 *) "EAP-pwd Hunting And Pecking",
127 os_strlen("EAP-pwd Hunting And Pecking"),
128 prfbuf, primebitlen) < 0)
129 goto fail;
130 + if (primebitlen % 8)
131 + buf_shift_right(prfbuf, primebytelen,
132 + 8 - primebitlen % 8);
133
134 crypto_bignum_deinit(x_candidate, 1);
135 x_candidate = crypto_bignum_init_set(prfbuf, primebytelen);
136 @@ -214,24 +239,13 @@ int compute_password_element(EAP_PWD_gro
137 goto fail;
138 }
139
140 - /*
141 - * eap_pwd_kdf() returns a string of bits 0..primebitlen but
142 - * BN_bin2bn will treat that string of bits as a big endian
143 - * number. If the primebitlen is not an even multiple of 8
144 - * then excessive bits-- those _after_ primebitlen-- so now
145 - * we have to shift right the amount we masked off.
146 - */
147 - if ((primebitlen % 8) &&
148 - crypto_bignum_rshift(x_candidate,
149 - (8 - (primebitlen % 8)),
150 - x_candidate) < 0)
151 - goto fail;
152 -
153 if (crypto_bignum_cmp(x_candidate, prime) >= 0)
154 continue;
155
156 - wpa_hexdump(MSG_DEBUG, "EAP-pwd: x_candidate",
157 - prfbuf, primebytelen);
158 + wpa_hexdump_key(MSG_DEBUG, "EAP-pwd: x_candidate",
159 + prfbuf, primebytelen);
160 + const_time_select_bin(found, x_bin, prfbuf, primebytelen,
161 + x_bin);
162
163 /*
164 * compute y^2 using the equation of the curve
165 @@ -260,13 +274,15 @@ int compute_password_element(EAP_PWD_gro
166 * Flip a coin, multiply by the random quadratic residue or the
167 * random quadratic nonresidue and record heads or tails.
168 */
169 - if (crypto_bignum_is_odd(tmp1)) {
170 - crypto_bignum_mulmod(tmp2, qr, prime, tmp2);
171 - check = 1;
172 - } else {
173 - crypto_bignum_mulmod(tmp2, qnr, prime, tmp2);
174 - check = -1;
175 - }
176 + mask = const_time_eq_u8(crypto_bignum_is_odd(tmp1), 1);
177 + check = const_time_select_s8(mask, 1, -1);
178 + const_time_select_bin(mask, qr_bin, qnr_bin, primebytelen,
179 + qr_or_qnr_bin);
180 + crypto_bignum_deinit(qr_or_qnr, 1);
181 + qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, primebytelen);
182 + if (!qr_or_qnr ||
183 + crypto_bignum_mulmod(tmp2, qr_or_qnr, prime, tmp2) < 0)
184 + goto fail;
185
186 /*
187 * Now it's safe to do legendre, if check is 1 then it's
188 @@ -274,59 +290,12 @@ int compute_password_element(EAP_PWD_gro
189 * change result), if check is -1 then it's the opposite test
190 * (multiplying a qr by qnr would make a qnr).
191 */
192 - if (crypto_bignum_legendre(tmp2, prime) == check) {
193 - if (found == 1)
194 - continue;
195 -
196 - /* need to unambiguously identify the solution */
197 - is_odd = crypto_bignum_is_odd(rnd);
198 -
199 - /*
200 - * We know x_candidate is a quadratic residue so set
201 - * it here.
202 - */
203 - if (crypto_ec_point_solve_y_coord(grp->group, grp->pwe,
204 - x_candidate,
205 - is_odd) != 0) {
206 - wpa_printf(MSG_INFO,
207 - "EAP-pwd: Could not solve for y");
208 - continue;
209 - }
210 -
211 - /*
212 - * If there's a solution to the equation then the point
213 - * must be on the curve so why check again explicitly?
214 - * OpenSSL code says this is required by X9.62. We're
215 - * not X9.62 but it can't hurt just to be sure.
216 - */
217 - if (!crypto_ec_point_is_on_curve(grp->group,
218 - grp->pwe)) {
219 - wpa_printf(MSG_INFO,
220 - "EAP-pwd: point is not on curve");
221 - continue;
222 - }
223 -
224 - if (!crypto_bignum_is_one(cofactor)) {
225 - /* make sure the point is not in a small
226 - * sub-group */
227 - if (crypto_ec_point_mul(grp->group, grp->pwe,
228 - cofactor,
229 - grp->pwe) != 0) {
230 - wpa_printf(MSG_INFO,
231 - "EAP-pwd: cannot multiply generator by order");
232 - continue;
233 - }
234 - if (crypto_ec_point_is_at_infinity(grp->group,
235 - grp->pwe)) {
236 - wpa_printf(MSG_INFO,
237 - "EAP-pwd: point is at infinity");
238 - continue;
239 - }
240 - }
241 - wpa_printf(MSG_DEBUG,
242 - "EAP-pwd: found a PWE in %d tries", ctr);
243 - found = 1;
244 - }
245 + res = crypto_bignum_legendre(tmp2, prime);
246 + if (res == -2)
247 + goto fail;
248 + mask = const_time_eq(res, check);
249 + found_ctr = const_time_select_u8(found, found_ctr, ctr);
250 + found |= mask;
251 }
252 if (found == 0) {
253 wpa_printf(MSG_INFO,
254 @@ -334,6 +303,44 @@ int compute_password_element(EAP_PWD_gro
255 num);
256 goto fail;
257 }
258 +
259 + /*
260 + * We know x_candidate is a quadratic residue so set it here.
261 + */
262 + crypto_bignum_deinit(x_candidate, 1);
263 + x_candidate = crypto_bignum_init_set(x_bin, primebytelen);
264 + if (!x_candidate ||
265 + crypto_ec_point_solve_y_coord(grp->group, grp->pwe, x_candidate,
266 + is_odd) != 0) {
267 + wpa_printf(MSG_INFO, "EAP-pwd: Could not solve for y");
268 + goto fail;
269 + }
270 +
271 + /*
272 + * If there's a solution to the equation then the point must be on the
273 + * curve so why check again explicitly? OpenSSL code says this is
274 + * required by X9.62. We're not X9.62 but it can't hurt just to be sure.
275 + */
276 + if (!crypto_ec_point_is_on_curve(grp->group, grp->pwe)) {
277 + wpa_printf(MSG_INFO, "EAP-pwd: point is not on curve");
278 + goto fail;
279 + }
280 +
281 + if (!crypto_bignum_is_one(cofactor)) {
282 + /* make sure the point is not in a small sub-group */
283 + if (crypto_ec_point_mul(grp->group, grp->pwe, cofactor,
284 + grp->pwe) != 0) {
285 + wpa_printf(MSG_INFO,
286 + "EAP-pwd: cannot multiply generator by order");
287 + goto fail;
288 + }
289 + if (crypto_ec_point_is_at_infinity(grp->group, grp->pwe)) {
290 + wpa_printf(MSG_INFO, "EAP-pwd: point is at infinity");
291 + goto fail;
292 + }
293 + }
294 + wpa_printf(MSG_DEBUG, "EAP-pwd: found a PWE in %02d tries", found_ctr);
295 +
296 if (0) {
297 fail:
298 crypto_ec_point_deinit(grp->pwe, 1);
299 @@ -343,14 +350,18 @@ int compute_password_element(EAP_PWD_gro
300 /* cleanliness and order.... */
301 crypto_bignum_deinit(cofactor, 1);
302 crypto_bignum_deinit(x_candidate, 1);
303 - crypto_bignum_deinit(rnd, 1);
304 crypto_bignum_deinit(pm1, 0);
305 crypto_bignum_deinit(tmp1, 1);
306 crypto_bignum_deinit(tmp2, 1);
307 crypto_bignum_deinit(qr, 1);
308 crypto_bignum_deinit(qnr, 1);
309 + crypto_bignum_deinit(qr_or_qnr, 1);
310 crypto_bignum_deinit(one, 0);
311 - os_free(prfbuf);
312 + bin_clear_free(prfbuf, primebytelen);
313 + os_memset(qr_bin, 0, sizeof(qr_bin));
314 + os_memset(qnr_bin, 0, sizeof(qnr_bin));
315 + os_memset(qr_or_qnr_bin, 0, sizeof(qr_or_qnr_bin));
316 + os_memset(pwe_digest, 0, sizeof(pwe_digest));
317
318 return ret;
319 }
Yousong Zhou staging tree