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 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 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 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 * 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 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 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 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) */ 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