Use a constant control flow in the derivation loop, avoiding leakage in the iteration succesfuly converting the password. Increase number of iterations (20 to 30) to avoid passwords needing more iterations. --- src/sae.c | 135 +++++++++++++++++++++++++++++++++++++---------------- src/util.h | 31 ++++++++++++ 2 files changed, 125 insertions(+), 41 deletions(-) diff --git a/src/sae.c b/src/sae.c index 97e3348e..54247c92 100644 --- a/src/sae.c +++ b/src/sae.c @@ -97,23 +97,47 @@ static bool sae_pwd_seed(const uint8_t *addr1, const uint8_t *addr2, &counter, (size_t) 1); } +/* + * Computes KDF-256(pwd_seed, "SAE Hunting and Pecking", p). If the output is + * greater than p, the output is set to qnr, a quadratic non-residue. + * Since this happens with very low probability, using the same qnr is fine. + */ static struct l_ecc_scalar *sae_pwd_value(const struct l_ecc_curve *curve, - uint8_t *pwd_seed) + uint8_t *pwd_seed, uint8_t *qnr) { uint8_t pwd_value[L_ECC_SCALAR_MAX_BYTES]; uint8_t prime[L_ECC_SCALAR_MAX_BYTES]; ssize_t len; + uint8_t is_in_range; struct l_ecc_scalar *p = l_ecc_curve_get_prime(curve); len = l_ecc_scalar_get_data(p, prime, sizeof(prime)); - l_ecc_scalar_free(p); if (!kdf_sha256(pwd_seed, 32, "SAE Hunting and Pecking", - strlen("SAE Hunting and Pecking"), prime, len, - pwd_value, len)) + strlen("SAE Hunting and Pecking"), prime, len, + pwd_value, len)) return NULL; + /* + * If pwd_value >= prime, this iteration should fail. We need a smooth + * control flow, so we need to continue anyway. + */ + is_in_range = l_secure_memcmp(pwd_value, prime, len); + /* + * We only consider is_in_range == -1 as valid, meaning the value of the + * MSB defines the mask. + */ + is_in_range = util_secure_fill_with_msb(is_in_range); + + /* + * libell has public Legendre symbol only for l_ecc_scalar, but they cannot + * be created if the coordinate is greater than the p. Hence, to avoid + * control flow dependencies, we replace pwd_value by a dummy quadratic + * non residue if we generate a value >= prime. + */ + util_secure_select(is_in_range, pwd_value, qnr, pwd_value, sizeof(pwd_value)); + return l_ecc_scalar_new(curve, pwd_value, sizeof(pwd_value)); } @@ -190,7 +214,7 @@ static struct l_ecc_scalar *sae_new_residue(const struct l_ecc_curve *curve, return s; } -static bool sae_is_quadradic_residue(const struct l_ecc_curve *curve, +static uint8_t sae_is_quadradic_residue(const struct l_ecc_curve *curve, struct l_ecc_scalar *value, struct l_ecc_scalar *qr, struct l_ecc_scalar *qnr) @@ -213,7 +237,7 @@ static bool sae_is_quadradic_residue(const struct l_ecc_curve *curve, if (bytes <= 0) { l_ecc_scalar_free(num); - return false; + return 0; } if (rbuf[bytes / 8 - 1] & 1) { @@ -221,20 +245,20 @@ static bool sae_is_quadradic_residue(const struct l_ecc_curve *curve, if (l_ecc_scalar_legendre(num) == -1) { l_ecc_scalar_free(num); - return true; + return 1; } } else { l_ecc_scalar_multiply(num, num, qnr); if (l_ecc_scalar_legendre(num) == 1) { l_ecc_scalar_free(num); - return true; + return 1; } } l_ecc_scalar_free(num); - return false; + return 0; } /* @@ -244,66 +268,95 @@ static bool sae_is_quadradic_residue(const struct l_ecc_curve *curve, static bool sae_compute_pwe(struct sae_sm *sm, char *password, const uint8_t *addr1, const uint8_t *addr2) { - bool found = false; + uint8_t found = 0; + uint8_t is_residue; + uint8_t is_odd = 0; uint8_t counter; uint8_t pwd_seed[32]; + uint8_t x[L_ECC_SCALAR_MAX_BYTES]; + uint8_t x_cand[L_ECC_SCALAR_MAX_BYTES]; struct l_ecc_scalar *pwd_value; - uint8_t random[32]; - uint8_t *base = (uint8_t *) password; - size_t base_len = strlen(password); - uint8_t save[32] = { 0 }; + uint8_t *dummy; + uint8_t *base; + size_t base_len; struct l_ecc_scalar *qr; struct l_ecc_scalar *qnr; - uint8_t x[L_ECC_SCALAR_MAX_BYTES]; + uint8_t qnr_bin[L_ECC_SCALAR_MAX_BYTES] = {0}; /* create qr/qnr prior to beginning hunting-and-pecking loop */ qr = sae_new_residue(sm->curve, true); qnr = sae_new_residue(sm->curve, false); + l_ecc_scalar_get_data(qnr, qnr_bin, sizeof(qnr_bin)); + + /* + * Allocate memory for the base, and set a random dummy to be used in + * additional iterations, once a valid value is found + */ + base_len = strlen(password); + base = l_malloc(base_len * sizeof(*base)); + dummy = l_malloc(base_len * sizeof(*dummy)); + l_getrandom(dummy, base_len); - for (counter = 1; counter <= 20; counter++) { - /* pwd-seed = H(max(addr1, addr2) || min(addr1, addr2), - * base || counter) + /* + * Loop with constant time and memory access + * We do 30 iterations instead of the 40 recommended to achieve a + * resonnable security/complexity trade-off. + */ + for (counter = 1; counter <= 30; counter++) { + /* + * Set base to either dummy or password, depending on found's value + * A non-secure version would be: + * base = (found ? dummy : password); + */ + util_secure_select(found, dummy, (uint8_t *)password, base, base_len); + + /* + * pwd-seed = H(max(addr1, addr2) || min(addr1, addr2), + * base || counter) * pwd-value = KDF-256(pwd-seed, "SAE Hunting and Pecking", p) */ sae_pwd_seed(addr1, addr2, base, base_len, counter, pwd_seed); + /* + * The case pwd_value > prime is handled inside, so that execution + * can continue whatever the result is, without changing the outcome. + */ + pwd_value = sae_pwd_value(sm->curve, pwd_seed, qnr_bin); - pwd_value = sae_pwd_value(sm->curve, pwd_seed); - if (!pwd_value) - continue; - - if (sae_is_quadradic_residue(sm->curve, pwd_value, qr, qnr)) { - if (found == false) { - l_ecc_scalar_get_data(pwd_value, x, sizeof(x)); - - memcpy(save, pwd_seed, 32); + /* + * Check if the candidate is a valid x-coordinate on our curve, and + * convert it from scalar to binary. + */ + is_residue = sae_is_quadradic_residue(sm->curve, pwd_value, qr, qnr); + l_ecc_scalar_get_data(pwd_value, x_cand, sizeof(x_cand)); - l_getrandom(random, 32); - base = random; - base_len = 32; + /* + * If we already found the point, we overwrite x with itself. + * Otherwise, we copy the new candidate into x. + */ + util_secure_select(found, x, x_cand, x, sizeof(x)); + is_odd = util_secure_select_byte(found, is_odd, pwd_seed[31] & 0x01); - found = true; - } - } + /* + * found is 0 or 0xff here and is_residue is 0 or 1. Bitwise OR of them + * (with is_residue converted to 0/0xff) handles this in constant time. + */ + found |= is_residue * 0xff; + memset(pwd_seed, 0, sizeof(pwd_seed)); l_ecc_scalar_free(pwd_value); } l_ecc_scalar_free(qr); l_ecc_scalar_free(qnr); + l_free(dummy); + l_free(base); if (!found) { l_error("max PWE iterations reached!"); return false; } + sm->pwe = l_ecc_point_from_data(sm->curve, !is_odd + 2, x, sizeof(x)); - if (!(save[31] & 1)) - sm->pwe = l_ecc_point_from_data(sm->curve, - L_ECC_POINT_TYPE_COMPRESSED_BIT1, - x, sizeof(x)); - else - sm->pwe = l_ecc_point_from_data(sm->curve, - L_ECC_POINT_TYPE_COMPRESSED_BIT0, - x, sizeof(x)); if (!sm->pwe) { l_error("computing y failed, was x quadratic residue?"); diff --git a/src/util.h b/src/util.h index edc6e777..dc0e77d0 100644 --- a/src/util.h +++ b/src/util.h @@ -71,4 +71,35 @@ static inline void util_set_bit(uint8_t *field, unsigned int bit) field[bit / 8] = 1 << (bit % 8); } +/* + * Copy either true_value or false_value (depending if mask is 0xFF or 0x00 + * respectively) into dest. All three buffers are assumed to be the same size. + * This constant time selection method allows to keep an identical memory access + * pattern. + */ +static inline uint8_t util_secure_select_byte(uint8_t mask, const uint8_t true_value, + const uint8_t false_value) +{ + return (mask & true_value) | (~mask & false_value); +} + +/* + * Copy either true_value or false_value (depending if mask is 0xFF or 0x00 + * respectively) into dest. All three buffers are assume to be the same size. + * This constant time selection method allows to choose and keeping an + * identical memory access pattern. + */ +static inline void util_secure_select(uint8_t mask, const uint8_t *true_value, + const uint8_t *false_value, uint8_t *dest, size_t size) +{ + for(int i = 0; i < size; i++) + dest[i] = util_secure_select_byte(mask, true_value[i], false_value[i]); +} + +/* Create a value filled with the MSB of the input. */ +static inline uint8_t util_secure_fill_with_msb(uint8_t val) +{ + return (uint8_t ) (val >> (sizeof(val)*8 - 1)) * 0xFF; +} + #endif /* __UTIL_H */ -- 2.25.4