aboutsummaryrefslogtreecommitdiffstats
path: root/src/common/dragonfly.c
blob: e98bce68233a164a1317e300a00955c944b81d33 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
/*
 * Shared Dragonfly functionality
 * Copyright (c) 2012-2016, Jouni Malinen <j@w1.fi>
 * Copyright (c) 2019, The Linux Foundation
 *
 * This software may be distributed under the terms of the BSD license.
 * See README for more details.
 */

#include "utils/includes.h"

#include "utils/common.h"
#include "utils/const_time.h"
#include "crypto/crypto.h"
#include "dragonfly.h"


int dragonfly_suitable_group(int group, int ecc_only)
{
	/* Enforce REVmd rules on which SAE groups are suitable for production
	 * purposes: FFC groups whose prime is >= 3072 bits and ECC groups
	 * defined over a prime field whose prime is >= 256 bits. Furthermore,
	 * ECC groups defined over a characteristic 2 finite field and ECC
	 * groups with a co-factor greater than 1 are not suitable. */
	return group == 19 || group == 20 || group == 21 ||
		group == 28 || group == 29 || group == 30 ||
		(!ecc_only &&
		 (group == 15 || group == 16 || group == 17 || group == 18));
}


int dragonfly_get_random_qr_qnr(const struct crypto_bignum *prime,
				struct crypto_bignum **qr,
				struct crypto_bignum **qnr)
{
	*qr = *qnr = NULL;

	while (!(*qr) || !(*qnr)) {
		struct crypto_bignum *tmp;
		int res;

		tmp = crypto_bignum_init();
		if (!tmp || crypto_bignum_rand(tmp, prime) < 0) {
			crypto_bignum_deinit(tmp, 0);
			break;
		}

		res = crypto_bignum_legendre(tmp, prime);
		if (res == 1 && !(*qr))
			*qr = tmp;
		else if (res == -1 && !(*qnr))
			*qnr = tmp;
		else
			crypto_bignum_deinit(tmp, 0);
	}

	if (*qr && *qnr)
		return 0;
	crypto_bignum_deinit(*qr, 0);
	crypto_bignum_deinit(*qnr, 0);
	*qr = *qnr = NULL;
	return -1;
}


static struct crypto_bignum *
dragonfly_get_rand_1_to_p_1(const struct crypto_bignum *prime)
{
	struct crypto_bignum *tmp, *pm1, *one;

	tmp = crypto_bignum_init();
	pm1 = crypto_bignum_init();
	one = crypto_bignum_init_set((const u8 *) "\x01", 1);
	if (!tmp || !pm1 || !one ||
	    crypto_bignum_sub(prime, one, pm1) < 0 ||
	    crypto_bignum_rand(tmp, pm1) < 0 ||
	    crypto_bignum_add(tmp, one, tmp) < 0) {
		crypto_bignum_deinit(tmp, 0);
		tmp = NULL;
	}

	crypto_bignum_deinit(pm1, 0);
	crypto_bignum_deinit(one, 0);
	return tmp;
}


int dragonfly_is_quadratic_residue_blind(struct crypto_ec *ec,
					 const u8 *qr, const u8 *qnr,
					 const struct crypto_bignum *val)
{
	struct crypto_bignum *r, *num, *qr_or_qnr = NULL;
	int check, res = -1;
	u8 qr_or_qnr_bin[DRAGONFLY_MAX_ECC_PRIME_LEN];
	const struct crypto_bignum *prime;
	size_t prime_len;
	unsigned int mask;

	prime = crypto_ec_get_prime(ec);
	prime_len = crypto_ec_prime_len(ec);

	/*
	 * Use a blinding technique to mask val while determining whether it is
	 * a quadratic residue modulo p to avoid leaking timing information
	 * while determining the Legendre symbol.
	 *
	 * v = val
	 * r = a random number between 1 and p-1, inclusive
	 * num = (v * r * r) modulo p
	 */
	r = dragonfly_get_rand_1_to_p_1(prime);
	if (!r)
		return -1;

	num = crypto_bignum_init();
	if (!num ||
	    crypto_bignum_mulmod(val, r, prime, num) < 0 ||
	    crypto_bignum_mulmod(num, r, prime, num) < 0)
		goto fail;

	/*
	 * Need to minimize differences in handling different cases, so try to
	 * avoid branches and timing differences.
	 *
	 * If r is odd:
	 * num = (num * qr) module p
	 * LGR(num, p) = 1 ==> quadratic residue
	 * else:
	 * num = (num * qnr) module p
	 * LGR(num, p) = -1 ==> quadratic residue
	 *
	 * mask is set to !odd(r)
	 */
	mask = const_time_is_zero(crypto_bignum_is_odd(r));
	const_time_select_bin(mask, qnr, qr, prime_len, qr_or_qnr_bin);
	qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, prime_len);
	if (!qr_or_qnr ||
	    crypto_bignum_mulmod(num, qr_or_qnr, prime, num) < 0)
		goto fail;
	/* branchless version of check = odd(r) ? 1 : -1, */
	check = const_time_select_int(mask, -1, 1);

	/* Determine the Legendre symbol on the masked value */
	res = crypto_bignum_legendre(num, prime);
	if (res == -2) {
		res = -1;
		goto fail;
	}
	/* branchless version of res = res == check
	 * (res is -1, 0, or 1; check is -1 or 1) */
	mask = const_time_eq(res, check);
	res = const_time_select_int(mask, 1, 0);
fail:
	crypto_bignum_deinit(num, 1);
	crypto_bignum_deinit(r, 1);
	crypto_bignum_deinit(qr_or_qnr, 1);
	return res;
}


static int dragonfly_get_rand_2_to_r_1(struct crypto_bignum *val,
				       const struct crypto_bignum *order)
{
	return crypto_bignum_rand(val, order) == 0 &&
		!crypto_bignum_is_zero(val) &&
		!crypto_bignum_is_one(val);
}


int dragonfly_generate_scalar(const struct crypto_bignum *order,
			      struct crypto_bignum *_rand,
			      struct crypto_bignum *_mask,
			      struct crypto_bignum *scalar)
{
	int count;

	/* Select two random values rand,mask such that 1 < rand,mask < r and
	 * rand + mask mod r > 1. */
	for (count = 0; count < 100; count++) {
		if (dragonfly_get_rand_2_to_r_1(_rand, order) &&
		    dragonfly_get_rand_2_to_r_1(_mask, order) &&
		    crypto_bignum_add(_rand, _mask, scalar) == 0 &&
		    crypto_bignum_mod(scalar, order, scalar) == 0 &&
		    !crypto_bignum_is_zero(scalar) &&
		    !crypto_bignum_is_one(scalar))
			return 0;
	}

	/* This should not be reachable in practice if the random number
	 * generation is working. */
	wpa_printf(MSG_INFO,
		   "dragonfly: Unable to get randomness for own scalar");
	return -1;
}