[PATCHv2] Fix a side channel leak on the password in SAE

[PATCHv2] Fix a side channel leak on the password in SAE

[Daniel DE ALMEIDA BRAGA]

[-- Attachment #1: Type: text/plain, Size: 9037 bytes --]

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 issues with
passwords needing more iterations.
Updated to take account of ELL's patch modifications.
---
 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..c3bb6515 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;
+	int 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((uint8_t) 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..93c7d619 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);
 }
 
+/*
+ * Returns either true_value or false_value (depending if mask is 0xFF or 0x00
+ * respectively).
+ * 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);
+}
+
+/*
+ * Copies 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 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 uint32_t util_secure_fill_with_msb(uint32_t val)
+{
+	return (uint32_t) (val >> (sizeof(val)*8 - 1)) * 0xFFFFFFFF;
+}
+
 #endif /* __UTIL_H */
-- 
2.25.4

Re: [PATCHv2] Fix a side channel leak on the password in SAE

[Denis Kenzior]

[-- Attachment #1: Type: text/plain, Size: 650 bytes --]

Hi Daniel,

On 8/3/20 4:08 AM, Daniel DE ALMEIDA BRAGA wrote:
> 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 issues with
> passwords needing more iterations.
> Updated to take account of ELL's patch modifications.
> ---
>   src/sae.c  | 135 +++++++++++++++++++++++++++++++++++++----------------
>   src/util.h |  31 ++++++++++++
>   2 files changed, 125 insertions(+), 41 deletions(-)
> 

I re-formatted some of the comments to fit on 80 char lines and applied this 
patch.  Thanks!

Regards,
-Denis