CVE-2020-11735 (C, published 2020-06-25T14:15Z)
Description: value: The private-key operations in ecc.c in wolfSSL before 4.4.0 do not use a constant-time modular inverse when mapping to affine coordinates, aka a "projective coordinates leak."
Severity: MEDIUM (CVSS v3 base score: 5.3)
Weakness: CWE-203 \u2014 Observable Discrepancy
The product behaves differently or sends different responses under different circumstances in a way that is observable to an unauthorized actor, which exposes security-relevant information about the state of the product, such as whether a particular operation was successful or not.
Repository: https://github.com/wolfSSL/wolfssl
Files changed:
wolfcrypt/src/ecc.c
wolfcrypt/src/tfm.c
wolfssl/wolfcrypt/ecc.h
wolfssl/wolfcrypt/tfm.h
Commit message: Constant time EC map to affine for private operations

For fast math, use a constant time modular inverse when mapping to
affine when operation involves a private key - key gen, calc shared
secret, sign.


Vulnerable code:
int ecc_map(ecc_point* P, mp_int* modulus, mp_digit mp)
   /* first map z back to normal */
   err = mp_montgomery_reduce(z, modulus, mp);

   if (err == MP_OKAY)
       err = mp_invmod(z, modulus, t1);
        err = wc_ecc_mulmod_ex(k, point, result, curve->Af, curve->prime, 1,
                                                                  1, key->heap);

Fixed code:
  ct       Operation should be constant time.
int ecc_map_ex(ecc_point* P, mp_int* modulus, mp_digit mp, int ct)
   (void)ct;

   if (err == MP_OKAY) {
#if defined(ECC_TIMING_RESISTANT) && defined(USE_FAST_MATH)
       if (ct) {
           err = mp_invmod_mont_ct(z, modulus, t1, mp);
           if (err == MP_OKAY)
               err = mp_montgomery_reduce(t1, modulus, mp);
       }
       else
#endif
       {
           /* first map z back to normal */
           err = mp_montgomery_reduce(z, modulus, mp);
           if (err == MP_OKAY)
               err = mp_invmod(z, modulus, t1);
       }
   }
int ecc_map(ecc_point* P, mp_int* modulus, mp_digit mp)
{
    return ecc_map_ex(P, modulus, mp, 0);
}
        mp_digit mp = 0;

        /* Map in a separate call as this should be constant time */
        err = wc_ecc_mulmod_ex(k, point, result, curve->Af, curve->prime, 0,
        if (err == MP_OKAY) {
            err = mp_montgomery_setup(curve->prime, &mp);
        }
        if (err == MP_OKAY) {
            /* Use constant time map if compiled in */
            err = ecc_map_ex(result, curve->prime, mp, 1);
        }
        mp_digit mp;

            /* Map in a separate call as this should be constant time */
                                                                  0, key->heap);
        if (err == MP_OKAY) {
            err = mp_montgomery_setup(curve->prime, &mp);
        }
        if (err == MP_OKAY) {
            /* Use constant time map if compiled in */
            err = ecc_map_ex(pub, curve->prime, mp, 1);
        }
#define CT_INV_MOD_PRE_CNT      8

/* modulus (b) must be greater than 2 and a prime */
int fp_invmod_mont_ct(fp_int *a, fp_int *b, fp_int *c, fp_digit mp)
{
  int i, j;
#ifndef WOLFSSL_SMALL_STACK
  fp_int t[1], e[1];
  fp_int pre[CT_INV_MOD_PRE_CNT];
#else
  fp_int* t;
  fp_int* e;
  fp_int* pre;
#endif

#ifdef WOLFSSL_SMALL_STACK
  t = (fp_int*)XMALLOC(sizeof(fp_int) * (2 + CT_INV_MOD_PRE_CNT), NULL,
                                                           DYNAMIC_TYPE_BIGINT);
  if (t == NULL)
    return FP_MEM;
  e = t + 1;
  pre = t + 2;
#endif

  fp_init(t);
  fp_init(e);

  fp_init(&pre[0]);
  fp_copy(a, &pre[0]);
  for (i = 1; i < CT_INV_MOD_PRE_CNT; i++) {
    fp_init(&pre[i]);
    fp_sqr(&pre[i-1], &pre[i]);
    fp_montgomery_reduce(&pre[i], b, mp);
    fp_mul(&pre[i], a, &pre[i]);
    fp_montgomery_reduce(&pre[i], b, mp);
  }

  fp_sub_d(b, 2, e);
  /* Highest bit is always set. */
  for (i = fp_count_bits(e)-2, j = 1; i >= 0; i--, j++) {
      if (!fp_is_bit_set(e, i) || j == CT_INV_MOD_PRE_CNT)
          break;
  }
  fp_copy(&pre[j-1], t);
  for (j = 0; i >= 0; i--) {
    int set = fp_is_bit_set(e, i);

    if ((j == CT_INV_MOD_PRE_CNT) || (!set && j > 0)) {
      fp_mul(t, &pre[j-1], t);
      fp_montgomery_reduce(t, b, mp);
      j = 0;
    }
    fp_sqr(t, t);
    fp_montgomery_reduce(t, b, mp);
    j += set;
  }
  if (j > 0) {
    fp_mul(t, &pre[j-1], c);
    fp_montgomery_reduce(c, b, mp);
  }
  else 
    fp_copy(t, c);

#ifdef WOLFSSL_SMALL_STACK
  XFREE(t, NULL, DYNAMIC_TYPE_BIGINT);
#endif
  return FP_OKAY;
}

/* hac 14.61, pp608 */
int mp_invmod_mont_ct (mp_int * a, mp_int * b, mp_int * c, mp_digit mp)
{
  return fp_invmod_mont_ct(a, b, c, mp);
}

ECC_API int ecc_map_ex(ecc_point*, mp_int*, mp_digit, int ct);
int fp_invmod_mont_ct(fp_int *a, fp_int *b, fp_int *c, fp_digit mp);
MP_API int  mp_invmod_mont_ct(mp_int *a, mp_int *b, mp_int *c, fp_digit mp);