contrib/wpa_supplicant/src/common/dragonfly.c

   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 }