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 } 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 87 static struct crypto_bignum * 88 dragonfly_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 109 int 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); 174 fail: 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 182 static 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 191 int 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) */ 219 int 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