package/network/services/hostapd/patches/060-0002-EAP-pwd-Mask-timing-of-PWE-derivation.patch

   1 From 22ac3dfebf7b25a3aae02f9b4f69025bb4173137 Mon Sep 17 00:00:00 2001
   2 From: Dan Harkins <dharkins@lounge.org>
   3 Date: Fri, 25 May 2018 21:40:04 +0300
   4 Subject: [PATCH] EAP-pwd: Mask timing of PWE derivation
   5
   6 Run through the hunting-and-pecking loop 40 times to mask the time
   7 necessary to find PWE. The odds of PWE not being found in 40 loops is
   8 roughly 1 in 1 trillion.
   9
  10 Signed-off-by: Dan Harkins <dharkins@lounge.org>
  11 ---
  12  src/eap_common/eap_pwd_common.c | 171 ++++++++++++++++++++++++--------
  13  1 file changed, 130 insertions(+), 41 deletions(-)
  14
  15 --- a/src/eap_common/eap_pwd_common.c
  16 +++ b/src/eap_common/eap_pwd_common.c
  17 @@ -112,18 +112,25 @@ int compute_password_element(EAP_PWD_gro
  18                              const u8 *id_peer, size_t id_peer_len,
  19                              const u8 *token)
  20  {
  21 +       struct crypto_bignum *qr = NULL, *qnr = NULL, *one = NULL;
  22 +       struct crypto_bignum *tmp1 = NULL, *tmp2 = NULL, *pm1 = NULL;
  23         struct crypto_hash *hash;
  24         unsigned char pwe_digest[SHA256_MAC_LEN], *prfbuf = NULL, ctr;
  25 -       int is_odd, ret = 0;
  26 +       int is_odd, ret = 0, check, found = 0;
  27         size_t primebytelen, primebitlen;
  28         struct crypto_bignum *x_candidate = NULL, *rnd = NULL, *cofactor = NULL;
  29 +       const struct crypto_bignum *prime;
  30
  31         if (grp->pwe)
  32                 return -1;
  33
  34 +       prime = crypto_ec_get_prime(grp->group);
  35         cofactor = crypto_bignum_init();
  36         grp->pwe = crypto_ec_point_init(grp->group);
  37 -       if (!cofactor || !grp->pwe) {
  38 +       tmp1 = crypto_bignum_init();
  39 +       pm1 = crypto_bignum_init();
  40 +       one = crypto_bignum_init_set((const u8 *) "\x01", 1);
  41 +       if (!cofactor || !grp->pwe || !tmp1 || !pm1 || !one) {
  42                 wpa_printf(MSG_INFO, "EAP-pwd: unable to create bignums");
  43                 goto fail;
  44         }
  45 @@ -140,15 +147,36 @@ int compute_password_element(EAP_PWD_gro
  46                            "buffer");
  47                 goto fail;
  48         }
  49 +       if (crypto_bignum_sub(prime, one, pm1) < 0)
  50 +               goto fail;
  51 +
  52 +       /* get a random quadratic residue and nonresidue */
  53 +       while (!qr || !qnr) {
  54 +               int res;
  55 +
  56 +               if (crypto_bignum_rand(tmp1, prime) < 0)
  57 +                       goto fail;
  58 +               res = crypto_bignum_legendre(tmp1, prime);
  59 +               if (!qr && res == 1) {
  60 +                       qr = tmp1;
  61 +                       tmp1 = crypto_bignum_init();
  62 +               } else if (!qnr && res == -1) {
  63 +                       qnr = tmp1;
  64 +                       tmp1 = crypto_bignum_init();
  65 +               }
  66 +               if (!tmp1)
  67 +                       goto fail;
  68 +       }
  69 +
  70         os_memset(prfbuf, 0, primebytelen);
  71         ctr = 0;
  72 -       while (1) {
  73 -               if (ctr > 30) {
  74 -                       wpa_printf(MSG_INFO, "EAP-pwd: unable to find random "
  75 -                                  "point on curve for group %d, something's "
  76 -                                  "fishy", num);
  77 -                       goto fail;
  78 -               }
  79 +
  80 +       /*
  81 +        * Run through the hunting-and-pecking loop 40 times to mask the time
  82 +        * necessary to find PWE. The odds of PWE not being found in 40 loops is
  83 +        * roughly 1 in 1 trillion.
  84 +        */
  85 +       while (ctr < 40) {
  86                 ctr++;
  87
  88                 /*
  89 @@ -199,58 +227,113 @@ int compute_password_element(EAP_PWD_gro
  90                                          x_candidate) < 0)
  91                         goto fail;
  92
  93 -               if (crypto_bignum_cmp(x_candidate,
  94 -                                     crypto_ec_get_prime(grp->group)) >= 0)
  95 +               if (crypto_bignum_cmp(x_candidate, prime) >= 0)
  96                         continue;
  97
  98                 wpa_hexdump(MSG_DEBUG, "EAP-pwd: x_candidate",
  99                             prfbuf, primebytelen);
 100
 101                 /*
 102 -                * need to unambiguously identify the solution, if there is
 103 -                * one...
 104 +                * compute y^2 using the equation of the curve
 105 +                *
 106 +                *      y^2 = x^3 + ax + b
 107                  */
 108 -               is_odd = crypto_bignum_is_odd(rnd);
 109 +               tmp2 = crypto_ec_point_compute_y_sqr(grp->group, x_candidate);
 110 +               if (!tmp2)
 111 +                       goto fail;
 112
 113                 /*
 114 -                * solve the quadratic equation, if it's not solvable then we
 115 -                * don't have a point
 116 +                * mask tmp2 so doing legendre won't leak timing info
 117 +                *
 118 +                * tmp1 is a random number between 1 and p-1
 119                  */
 120 -               if (crypto_ec_point_solve_y_coord(grp->group, grp->pwe,
 121 -                                                 x_candidate, is_odd) != 0) {
 122 -                       wpa_printf(MSG_INFO, "EAP-pwd: Could not solve for y");
 123 -                       continue;
 124 -               }
 125 +               if (crypto_bignum_rand(tmp1, pm1) < 0 ||
 126 +                   crypto_bignum_mulmod(tmp2, tmp1, prime, tmp2) < 0 ||
 127 +                   crypto_bignum_mulmod(tmp2, tmp1, prime, tmp2) < 0)
 128 +                       goto fail;
 129 +
 130                 /*
 131 -                * If there's a solution to the equation then the point must be
 132 -                * on the curve so why check again explicitly? OpenSSL code
 133 -                * says this is required by X9.62. We're not X9.62 but it can't
 134 -                * hurt just to be sure.
 135 +                * Now tmp2 (y^2) is masked, all values between 1 and p-1
 136 +                * are equally probable. Multiplying by r^2 does not change
 137 +                * whether or not tmp2 is a quadratic residue, just masks it.
 138 +                *
 139 +                * Flip a coin, multiply by the random quadratic residue or the
 140 +                * random quadratic nonresidue and record heads or tails.
 141                  */
 142 -               if (!crypto_ec_point_is_on_curve(grp->group, grp->pwe)) {
 143 -                       wpa_printf(MSG_INFO, "EAP-pwd: point is not on curve");
 144 -                       continue;
 145 +               if (crypto_bignum_is_odd(tmp1)) {
 146 +                       crypto_bignum_mulmod(tmp2, qr, prime, tmp2);
 147 +                       check = 1;
 148 +               } else {
 149 +                       crypto_bignum_mulmod(tmp2, qnr, prime, tmp2);
 150 +                       check = -1;
 151                 }
 152
 153 -               if (!crypto_bignum_is_one(cofactor)) {
 154 -                       /* make sure the point is not in a small sub-group */
 155 -                       if (crypto_ec_point_mul(grp->group, grp->pwe,
 156 -                                               cofactor, grp->pwe) != 0) {
 157 -                               wpa_printf(MSG_INFO, "EAP-pwd: cannot "
 158 -                                          "multiply generator by order");
 159 +               /*
 160 +                * Now it's safe to do legendre, if check is 1 then it's
 161 +                * a straightforward test (multiplying by qr does not
 162 +                * change result), if check is -1 then it's the opposite test
 163 +                * (multiplying a qr by qnr would make a qnr).
 164 +                */
 165 +               if (crypto_bignum_legendre(tmp2, prime) == check) {
 166 +                       if (found == 1)
 167 +                               continue;
 168 +
 169 +                       /* need to unambiguously identify the solution */
 170 +                       is_odd = crypto_bignum_is_odd(rnd);
 171 +
 172 +                       /*
 173 +                        * We know x_candidate is a quadratic residue so set
 174 +                        * it here.
 175 +                        */
 176 +                       if (crypto_ec_point_solve_y_coord(grp->group, grp->pwe,
 177 +                                                         x_candidate,
 178 +                                                         is_odd) != 0) {
 179 +                               wpa_printf(MSG_INFO,
 180 +                                          "EAP-pwd: Could not solve for y");
 181                                 continue;
 182                         }
 183 -                       if (crypto_ec_point_is_at_infinity(grp->group,
 184 -                                                          grp->pwe)) {
 185 -                               wpa_printf(MSG_INFO, "EAP-pwd: point is at "
 186 -                                          "infinity");
 187 +
 188 +                       /*
 189 +                        * If there's a solution to the equation then the point
 190 +                        * must be on the curve so why check again explicitly?
 191 +                        * OpenSSL code says this is required by X9.62. We're
 192 +                        * not X9.62 but it can't hurt just to be sure.
 193 +                        */
 194 +                       if (!crypto_ec_point_is_on_curve(grp->group,
 195 +                                                        grp->pwe)) {
 196 +                               wpa_printf(MSG_INFO,
 197 +                                          "EAP-pwd: point is not on curve");
 198                                 continue;
 199                         }
 200 +
 201 +                       if (!crypto_bignum_is_one(cofactor)) {
 202 +                               /* make sure the point is not in a small
 203 +                                * sub-group */
 204 +                               if (crypto_ec_point_mul(grp->group, grp->pwe,
 205 +                                                       cofactor,
 206 +                                                       grp->pwe) != 0) {
 207 +                                       wpa_printf(MSG_INFO,
 208 +                                                  "EAP-pwd: cannot multiply generator by order");
 209 +                                       continue;
 210 +                               }
 211 +                               if (crypto_ec_point_is_at_infinity(grp->group,
 212 +                                                                  grp->pwe)) {
 213 +                                       wpa_printf(MSG_INFO,
 214 +                                                  "EAP-pwd: point is at infinity");
 215 +                                       continue;
 216 +                               }
 217 +                       }
 218 +                       wpa_printf(MSG_DEBUG,
 219 +                                  "EAP-pwd: found a PWE in %d tries", ctr);
 220 +                       found = 1;
 221                 }
 222 -               /* if we got here then we have a new generator. */
 223 -               break;
 224         }
 225 -       wpa_printf(MSG_DEBUG, "EAP-pwd: found a PWE in %d tries", ctr);
 226 +       if (found == 0) {
 227 +               wpa_printf(MSG_INFO,
 228 +                          "EAP-pwd: unable to find random point on curve for group %d, something's fishy",
 229 +                          num);
 230 +               goto fail;
 231 +       }
 232         if (0) {
 233   fail:
 234                 crypto_ec_point_deinit(grp->pwe, 1);
 235 @@ -261,6 +344,12 @@ int compute_password_element(EAP_PWD_gro
 236         crypto_bignum_deinit(cofactor, 1);
 237         crypto_bignum_deinit(x_candidate, 1);
 238         crypto_bignum_deinit(rnd, 1);
 239 +       crypto_bignum_deinit(pm1, 0);
 240 +       crypto_bignum_deinit(tmp1, 1);
 241 +       crypto_bignum_deinit(tmp2, 1);
 242 +       crypto_bignum_deinit(qr, 1);
 243 +       crypto_bignum_deinit(qnr, 1);
 244 +       crypto_bignum_deinit(one, 0);
 245         os_free(prfbuf);
 246
 247         return ret;