package/network/services/hostapd/patches/061-0006-SAE-Avoid-branches-in-is_quadratic_residue_blind.patch

   1 From 362704dda04507e7ebb8035122e83d9f0ae7c320 Mon Sep 17 00:00:00 2001
   2 From: Jouni Malinen <jouni@codeaurora.org>
   3 Date: Tue, 26 Feb 2019 19:34:38 +0200
   4 Subject: [PATCH 06/14] SAE: Avoid branches in is_quadratic_residue_blind()
   5
   6 Make the non-failure path in the function proceed without branches based
   7 on r_odd and in constant time to minimize risk of observable differences
   8 in timing or cache use. (CVE-2019-9494)
   9
  10 Signed-off-by: Jouni Malinen <jouni@codeaurora.org>
  11 ---
  12  src/common/sae.c | 64 ++++++++++++++++++++++++++++++++------------------------
  13  1 file changed, 37 insertions(+), 27 deletions(-)
  14
  15 --- a/src/common/sae.c
  16 +++ b/src/common/sae.c
  17 @@ -209,12 +209,14 @@ get_rand_1_to_p_1(const u8 *prime, size_
  18
  19  static int is_quadratic_residue_blind(struct sae_data *sae,
  20                                       const u8 *prime, size_t bits,
  21 -                                     const struct crypto_bignum *qr,
  22 -                                     const struct crypto_bignum *qnr,
  23 +                                     const u8 *qr, const u8 *qnr,
  24                                       const struct crypto_bignum *y_sqr)
  25  {
  26 -       struct crypto_bignum *r, *num;
  27 +       struct crypto_bignum *r, *num, *qr_or_qnr = NULL;
  28         int r_odd, check, res = -1;
  29 +       u8 qr_or_qnr_bin[SAE_MAX_ECC_PRIME_LEN];
  30 +       size_t prime_len = sae->tmp->prime_len;
  31 +       unsigned int mask;
  32
  33         /*
  34          * Use the blinding technique to mask y_sqr while determining
  35 @@ -225,7 +227,7 @@ static int is_quadratic_residue_blind(st
  36          * r = a random number between 1 and p-1, inclusive
  37          * num = (v * r * r) modulo p
  38          */
  39 -       r = get_rand_1_to_p_1(prime, sae->tmp->prime_len, bits, &r_odd);
  40 +       r = get_rand_1_to_p_1(prime, prime_len, bits, &r_odd);
  41         if (!r)
  42                 return -1;
  43
  44 @@ -235,41 +237,45 @@ static int is_quadratic_residue_blind(st
  45             crypto_bignum_mulmod(num, r, sae->tmp->prime, num) < 0)
  46                 goto fail;
  47
  48 -       if (r_odd) {
  49 -               /*
  50 -                * num = (num * qr) module p
  51 -                * LGR(num, p) = 1 ==> quadratic residue
  52 -                */
  53 -               if (crypto_bignum_mulmod(num, qr, sae->tmp->prime, num) < 0)
  54 -                       goto fail;
  55 -               check = 1;
  56 -       } else {
  57 -               /*
  58 -                * num = (num * qnr) module p
  59 -                * LGR(num, p) = -1 ==> quadratic residue
  60 -                */
  61 -               if (crypto_bignum_mulmod(num, qnr, sae->tmp->prime, num) < 0)
  62 -                       goto fail;
  63 -               check = -1;
  64 -       }
  65 +       /*
  66 +        * Need to minimize differences in handling different cases, so try to
  67 +        * avoid branches and timing differences.
  68 +        *
  69 +        * If r_odd:
  70 +        * num = (num * qr) module p
  71 +        * LGR(num, p) = 1 ==> quadratic residue
  72 +        * else:
  73 +        * num = (num * qnr) module p
  74 +        * LGR(num, p) = -1 ==> quadratic residue
  75 +        */
  76 +       mask = const_time_is_zero(r_odd);
  77 +       const_time_select_bin(mask, qnr, qr, prime_len, qr_or_qnr_bin);
  78 +       qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, prime_len);
  79 +       if (!qr_or_qnr ||
  80 +           crypto_bignum_mulmod(num, qr_or_qnr, sae->tmp->prime, num) < 0)
  81 +               goto fail;
  82 +       /* r_odd is 0 or 1; branchless version of check = r_odd ? 1 : -1, */
  83 +       check = const_time_select_int(mask, -1, 1);
  84
  85         res = crypto_bignum_legendre(num, sae->tmp->prime);
  86         if (res == -2) {
  87                 res = -1;
  88                 goto fail;
  89         }
  90 -       res = res == check;
  91 +       /* branchless version of res = res == check
  92 +        * (res is -1, 0, or 1; check is -1 or 1) */
  93 +       mask = const_time_eq(res, check);
  94 +       res = const_time_select_int(mask, 1, 0);
  95  fail:
  96         crypto_bignum_deinit(num, 1);
  97         crypto_bignum_deinit(r, 1);
  98 +       crypto_bignum_deinit(qr_or_qnr, 1);
  99         return res;
 100  }
 101
 102
 103  static int sae_test_pwd_seed_ecc(struct sae_data *sae, const u8 *pwd_seed,
 104 -                                const u8 *prime,
 105 -                                const struct crypto_bignum *qr,
 106 -                                const struct crypto_bignum *qnr,
 107 +                                const u8 *prime, const u8 *qr, const u8 *qnr,
 108                                  u8 *pwd_value)
 109  {
 110         struct crypto_bignum *y_sqr, *x_cand;
 111 @@ -429,6 +435,8 @@ static int sae_derive_pwe_ecc(struct sae
 112         struct crypto_bignum *x = NULL, *qr = NULL, *qnr = NULL;
 113         u8 x_bin[SAE_MAX_ECC_PRIME_LEN];
 114         u8 x_cand_bin[SAE_MAX_ECC_PRIME_LEN];
 115 +       u8 qr_bin[SAE_MAX_ECC_PRIME_LEN];
 116 +       u8 qnr_bin[SAE_MAX_ECC_PRIME_LEN];
 117         size_t bits;
 118         int res = -1;
 119         u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
 120 @@ -453,7 +461,9 @@ static int sae_derive_pwe_ecc(struct sae
 121          * (qnr) modulo p for blinding purposes during the loop.
 122          */
 123         if (get_random_qr_qnr(prime, prime_len, sae->tmp->prime, bits,
 124 -                             &qr, &qnr) < 0)
 125 +                             &qr, &qnr) < 0 ||
 126 +           crypto_bignum_to_bin(qr, qr_bin, sizeof(qr_bin), prime_len) < 0 ||
 127 +           crypto_bignum_to_bin(qnr, qnr_bin, sizeof(qnr_bin), prime_len) < 0)
 128                 goto fail;
 129
 130         wpa_hexdump_ascii_key(MSG_DEBUG, "SAE: password",
 131 @@ -504,7 +514,7 @@ static int sae_derive_pwe_ecc(struct sae
 132                         break;
 133
 134                 res = sae_test_pwd_seed_ecc(sae, pwd_seed,
 135 -                                           prime, qr, qnr, x_cand_bin);
 136 +                                           prime, qr_bin, qnr_bin, x_cand_bin);
 137                 const_time_select_bin(found, x_bin, x_cand_bin, prime_len,
 138                                       x_bin);
 139                 pwd_seed_odd = const_time_select_u8(