diff options
Diffstat (limited to 'src/common/dragonfly.c')
| -rw-r--r-- | src/common/dragonfly.c | 215 |
1 files changed, 215 insertions, 0 deletions
diff --git a/src/common/dragonfly.c b/src/common/dragonfly.c new file mode 100644 index 000000000000..547be66f1561 --- /dev/null +++ b/src/common/dragonfly.c @@ -0,0 +1,215 @@ +/* + * 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. Disable + * groups that use Brainpool curves as well for now since they leak more + * timing information due to the prime not being close to a power of + * two. */ + return group == 19 || group == 20 || group == 21 || + (!ecc_only && + (group == 15 || group == 16 || group == 17 || group == 18)); +} + + +unsigned int dragonfly_min_pwe_loop_iter(int group) +{ + if (group == 22 || group == 23 || group == 24) { + /* FFC groups for which pwd-value is likely to be >= p + * frequently */ + return 40; + } + + if (group == 1 || group == 2 || group == 5 || group == 14 || + group == 15 || group == 16 || group == 17 || group == 18) { + /* FFC groups that have prime that is close to a power of two */ + return 1; + } + + /* Default to 40 (this covers most ECC groups) */ + return 40; +} + + +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; +} |