package/network/services/hostapd/patches/062-0004-EAP-pwd-Use-constant-time-and-memory-access-for-find.patch

   1 From aaf65feac67c3993935634eefe5bc76b9fce03aa Mon Sep 17 00:00:00 2001
   2 From: Jouni Malinen <jouni@codeaurora.org>
   3 Date: Tue, 26 Feb 2019 11:59:45 +0200
   4 Subject: [PATCH 04/14] EAP-pwd: Use constant time and memory access for
   5  finding the PWE
   6
   7 This algorithm could leak information to external observers in form of
   8 timing differences or memory access patterns (cache use). While the
   9 previous implementation had protection against the most visible timing
  10 differences (looping 40 rounds and masking the legendre operation), it
  11 did not protect against memory access patterns between the two possible
  12 code paths in the masking operations. That might be sufficient to allow
  13 an unprivileged process running on the same device to be able to
  14 determine which path is being executed through a cache attack and based
  15 on that, determine information about the used password.
  16
  17 Convert the PWE finding loop to use constant time functions and
  18 identical memory access path without different branches for the QR/QNR
  19 cases to minimize possible side-channel information similarly to the
  20 changes done for SAE authentication. (CVE-2019-9495)
  21
  22 Signed-off-by: Jouni Malinen <jouni@codeaurora.org>
  23 ---
  24  src/eap_common/eap_pwd_common.c | 187 +++++++++++++++++++++-------------------
  25  1 file changed, 99 insertions(+), 88 deletions(-)
  26
  27 --- a/src/eap_common/eap_pwd_common.c
  28 +++ b/src/eap_common/eap_pwd_common.c
  29 @@ -8,11 +8,15 @@
  30
  31  #include "includes.h"
  32  #include "common.h"
  33 +#include "utils/const_time.h"
  34  #include "crypto/sha256.h"
  35  #include "crypto/crypto.h"
  36  #include "eap_defs.h"
  37  #include "eap_pwd_common.h"
  38
  39 +#define MAX_ECC_PRIME_LEN 66
  40 +
  41 +
  42  /* The random function H(x) = HMAC-SHA256(0^32, x) */
  43  struct crypto_hash * eap_pwd_h_init(void)
  44  {
  45 @@ -102,6 +106,15 @@ EAP_PWD_group * get_eap_pwd_group(u16 nu
  46  }
  47
  48
  49 +static void buf_shift_right(u8 *buf, size_t len, size_t bits)
  50 +{
  51 +       size_t i;
  52 +       for (i = len - 1; i > 0; i--)
  53 +               buf[i] = (buf[i - 1] << (8 - bits)) | (buf[i] >> bits);
  54 +       buf[0] >>= bits;
  55 +}
  56 +
  57 +
  58  /*
  59   * compute a "random" secret point on an elliptic curve based
  60   * on the password and identities.
  61 @@ -113,17 +126,27 @@ int compute_password_element(EAP_PWD_gro
  62                              const u8 *token)
  63  {
  64         struct crypto_bignum *qr = NULL, *qnr = NULL, *one = NULL;
  65 +       struct crypto_bignum *qr_or_qnr = NULL;
  66 +       u8 qr_bin[MAX_ECC_PRIME_LEN];
  67 +       u8 qnr_bin[MAX_ECC_PRIME_LEN];
  68 +       u8 qr_or_qnr_bin[MAX_ECC_PRIME_LEN];
  69 +       u8 x_bin[MAX_ECC_PRIME_LEN];
  70         struct crypto_bignum *tmp1 = NULL, *tmp2 = NULL, *pm1 = NULL;
  71         struct crypto_hash *hash;
  72         unsigned char pwe_digest[SHA256_MAC_LEN], *prfbuf = NULL, ctr;
  73 -       int is_odd, ret = 0, check, found = 0;
  74 -       size_t primebytelen, primebitlen;
  75 -       struct crypto_bignum *x_candidate = NULL, *rnd = NULL, *cofactor = NULL;
  76 +       int ret = 0, check, res;
  77 +       u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
  78 +                      * mask */
  79 +       size_t primebytelen = 0, primebitlen;
  80 +       struct crypto_bignum *x_candidate = NULL, *cofactor = NULL;
  81         const struct crypto_bignum *prime;
  82 +       u8 mask, found_ctr = 0, is_odd = 0;
  83
  84         if (grp->pwe)
  85                 return -1;
  86
  87 +       os_memset(x_bin, 0, sizeof(x_bin));
  88 +
  89         prime = crypto_ec_get_prime(grp->group);
  90         cofactor = crypto_bignum_init();
  91         grp->pwe = crypto_ec_point_init(grp->group);
  92 @@ -152,8 +175,6 @@ int compute_password_element(EAP_PWD_gro
  93
  94         /* get a random quadratic residue and nonresidue */
  95         while (!qr || !qnr) {
  96 -               int res;
  97 -
  98                 if (crypto_bignum_rand(tmp1, prime) < 0)
  99                         goto fail;
 100                 res = crypto_bignum_legendre(tmp1, prime);
 101 @@ -167,6 +188,11 @@ int compute_password_element(EAP_PWD_gro
 102                 if (!tmp1)
 103                         goto fail;
 104         }
 105 +       if (crypto_bignum_to_bin(qr, qr_bin, sizeof(qr_bin),
 106 +                                primebytelen) < 0 ||
 107 +           crypto_bignum_to_bin(qnr, qnr_bin, sizeof(qnr_bin),
 108 +                                primebytelen) < 0)
 109 +               goto fail;
 110
 111         os_memset(prfbuf, 0, primebytelen);
 112         ctr = 0;
 113 @@ -194,17 +220,16 @@ int compute_password_element(EAP_PWD_gro
 114                 eap_pwd_h_update(hash, &ctr, sizeof(ctr));
 115                 eap_pwd_h_final(hash, pwe_digest);
 116
 117 -               crypto_bignum_deinit(rnd, 1);
 118 -               rnd = crypto_bignum_init_set(pwe_digest, SHA256_MAC_LEN);
 119 -               if (!rnd) {
 120 -                       wpa_printf(MSG_INFO, "EAP-pwd: unable to create rnd");
 121 -                       goto fail;
 122 -               }
 123 +               is_odd = const_time_select_u8(
 124 +                       found, is_odd, pwe_digest[SHA256_MAC_LEN - 1] & 0x01);
 125                 if (eap_pwd_kdf(pwe_digest, SHA256_MAC_LEN,
 126                                 (u8 *) "EAP-pwd Hunting And Pecking",
 127                                 os_strlen("EAP-pwd Hunting And Pecking"),
 128                                 prfbuf, primebitlen) < 0)
 129                         goto fail;
 130 +               if (primebitlen % 8)
 131 +                       buf_shift_right(prfbuf, primebytelen,
 132 +                                       8 - primebitlen % 8);
 133
 134                 crypto_bignum_deinit(x_candidate, 1);
 135                 x_candidate = crypto_bignum_init_set(prfbuf, primebytelen);
 136 @@ -214,24 +239,13 @@ int compute_password_element(EAP_PWD_gro
 137                         goto fail;
 138                 }
 139
 140 -               /*
 141 -                * eap_pwd_kdf() returns a string of bits 0..primebitlen but
 142 -                * BN_bin2bn will treat that string of bits as a big endian
 143 -                * number. If the primebitlen is not an even multiple of 8
 144 -                * then excessive bits-- those _after_ primebitlen-- so now
 145 -                * we have to shift right the amount we masked off.
 146 -                */
 147 -               if ((primebitlen % 8) &&
 148 -                   crypto_bignum_rshift(x_candidate,
 149 -                                        (8 - (primebitlen % 8)),
 150 -                                        x_candidate) < 0)
 151 -                       goto fail;
 152 -
 153                 if (crypto_bignum_cmp(x_candidate, prime) >= 0)
 154                         continue;
 155
 156 -               wpa_hexdump(MSG_DEBUG, "EAP-pwd: x_candidate",
 157 -                           prfbuf, primebytelen);
 158 +               wpa_hexdump_key(MSG_DEBUG, "EAP-pwd: x_candidate",
 159 +                               prfbuf, primebytelen);
 160 +               const_time_select_bin(found, x_bin, prfbuf, primebytelen,
 161 +                                     x_bin);
 162
 163                 /*
 164                  * compute y^2 using the equation of the curve
 165 @@ -260,13 +274,15 @@ int compute_password_element(EAP_PWD_gro
 166                  * Flip a coin, multiply by the random quadratic residue or the
 167                  * random quadratic nonresidue and record heads or tails.
 168                  */
 169 -               if (crypto_bignum_is_odd(tmp1)) {
 170 -                       crypto_bignum_mulmod(tmp2, qr, prime, tmp2);
 171 -                       check = 1;
 172 -               } else {
 173 -                       crypto_bignum_mulmod(tmp2, qnr, prime, tmp2);
 174 -                       check = -1;
 175 -               }
 176 +               mask = const_time_eq_u8(crypto_bignum_is_odd(tmp1), 1);
 177 +               check = const_time_select_s8(mask, 1, -1);
 178 +               const_time_select_bin(mask, qr_bin, qnr_bin, primebytelen,
 179 +                                     qr_or_qnr_bin);
 180 +               crypto_bignum_deinit(qr_or_qnr, 1);
 181 +               qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, primebytelen);
 182 +               if (!qr_or_qnr ||
 183 +                   crypto_bignum_mulmod(tmp2, qr_or_qnr, prime, tmp2) < 0)
 184 +                       goto fail;
 185
 186                 /*
 187                  * Now it's safe to do legendre, if check is 1 then it's
 188 @@ -274,59 +290,12 @@ int compute_password_element(EAP_PWD_gro
 189                  * change result), if check is -1 then it's the opposite test
 190                  * (multiplying a qr by qnr would make a qnr).
 191                  */
 192 -               if (crypto_bignum_legendre(tmp2, prime) == check) {
 193 -                       if (found == 1)
 194 -                               continue;
 195 -
 196 -                       /* need to unambiguously identify the solution */
 197 -                       is_odd = crypto_bignum_is_odd(rnd);
 198 -
 199 -                       /*
 200 -                        * We know x_candidate is a quadratic residue so set
 201 -                        * it here.
 202 -                        */
 203 -                       if (crypto_ec_point_solve_y_coord(grp->group, grp->pwe,
 204 -                                                         x_candidate,
 205 -                                                         is_odd) != 0) {
 206 -                               wpa_printf(MSG_INFO,
 207 -                                          "EAP-pwd: Could not solve for y");
 208 -                               continue;
 209 -                       }
 210 -
 211 -                       /*
 212 -                        * If there's a solution to the equation then the point
 213 -                        * must be on the curve so why check again explicitly?
 214 -                        * OpenSSL code says this is required by X9.62. We're
 215 -                        * not X9.62 but it can't hurt just to be sure.
 216 -                        */
 217 -                       if (!crypto_ec_point_is_on_curve(grp->group,
 218 -                                                        grp->pwe)) {
 219 -                               wpa_printf(MSG_INFO,
 220 -                                          "EAP-pwd: point is not on curve");
 221 -                               continue;
 222 -                       }
 223 -
 224 -                       if (!crypto_bignum_is_one(cofactor)) {
 225 -                               /* make sure the point is not in a small
 226 -                                * sub-group */
 227 -                               if (crypto_ec_point_mul(grp->group, grp->pwe,
 228 -                                                       cofactor,
 229 -                                                       grp->pwe) != 0) {
 230 -                                       wpa_printf(MSG_INFO,
 231 -                                                  "EAP-pwd: cannot multiply generator by order");
 232 -                                       continue;
 233 -                               }
 234 -                               if (crypto_ec_point_is_at_infinity(grp->group,
 235 -                                                                  grp->pwe)) {
 236 -                                       wpa_printf(MSG_INFO,
 237 -                                                  "EAP-pwd: point is at infinity");
 238 -                                       continue;
 239 -                               }
 240 -                       }
 241 -                       wpa_printf(MSG_DEBUG,
 242 -                                  "EAP-pwd: found a PWE in %d tries", ctr);
 243 -                       found = 1;
 244 -               }
 245 +               res = crypto_bignum_legendre(tmp2, prime);
 246 +               if (res == -2)
 247 +                       goto fail;
 248 +               mask = const_time_eq(res, check);
 249 +               found_ctr = const_time_select_u8(found, found_ctr, ctr);
 250 +               found |= mask;
 251         }
 252         if (found == 0) {
 253                 wpa_printf(MSG_INFO,
 254 @@ -334,6 +303,44 @@ int compute_password_element(EAP_PWD_gro
 255                            num);
 256                 goto fail;
 257         }
 258 +
 259 +       /*
 260 +        * We know x_candidate is a quadratic residue so set it here.
 261 +        */
 262 +       crypto_bignum_deinit(x_candidate, 1);
 263 +       x_candidate = crypto_bignum_init_set(x_bin, primebytelen);
 264 +       if (!x_candidate ||
 265 +           crypto_ec_point_solve_y_coord(grp->group, grp->pwe, x_candidate,
 266 +                                         is_odd) != 0) {
 267 +               wpa_printf(MSG_INFO, "EAP-pwd: Could not solve for y");
 268 +               goto fail;
 269 +       }
 270 +
 271 +       /*
 272 +        * If there's a solution to the equation then the point must be on the
 273 +        * curve so why check again explicitly? OpenSSL code says this is
 274 +        * required by X9.62. We're not X9.62 but it can't hurt just to be sure.
 275 +        */
 276 +       if (!crypto_ec_point_is_on_curve(grp->group, grp->pwe)) {
 277 +               wpa_printf(MSG_INFO, "EAP-pwd: point is not on curve");
 278 +               goto fail;
 279 +       }
 280 +
 281 +       if (!crypto_bignum_is_one(cofactor)) {
 282 +               /* make sure the point is not in a small sub-group */
 283 +               if (crypto_ec_point_mul(grp->group, grp->pwe, cofactor,
 284 +                                       grp->pwe) != 0) {
 285 +                       wpa_printf(MSG_INFO,
 286 +                                  "EAP-pwd: cannot multiply generator by order");
 287 +                       goto fail;
 288 +               }
 289 +               if (crypto_ec_point_is_at_infinity(grp->group, grp->pwe)) {
 290 +                       wpa_printf(MSG_INFO, "EAP-pwd: point is at infinity");
 291 +                       goto fail;
 292 +               }
 293 +       }
 294 +       wpa_printf(MSG_DEBUG, "EAP-pwd: found a PWE in %02d tries", found_ctr);
 295 +
 296         if (0) {
 297   fail:
 298                 crypto_ec_point_deinit(grp->pwe, 1);
 299 @@ -343,14 +350,18 @@ int compute_password_element(EAP_PWD_gro
 300         /* cleanliness and order.... */
 301         crypto_bignum_deinit(cofactor, 1);
 302         crypto_bignum_deinit(x_candidate, 1);
 303 -       crypto_bignum_deinit(rnd, 1);
 304         crypto_bignum_deinit(pm1, 0);
 305         crypto_bignum_deinit(tmp1, 1);
 306         crypto_bignum_deinit(tmp2, 1);
 307         crypto_bignum_deinit(qr, 1);
 308         crypto_bignum_deinit(qnr, 1);
 309 +       crypto_bignum_deinit(qr_or_qnr, 1);
 310         crypto_bignum_deinit(one, 0);
 311 -       os_free(prfbuf);
 312 +       bin_clear_free(prfbuf, primebytelen);
 313 +       os_memset(qr_bin, 0, sizeof(qr_bin));
 314 +       os_memset(qnr_bin, 0, sizeof(qnr_bin));
 315 +       os_memset(qr_or_qnr_bin, 0, sizeof(qr_or_qnr_bin));
 316 +       os_memset(pwe_digest, 0, sizeof(pwe_digest));
 317
 318         return ret;
 319  }