From fe534b0baaa8c0e6ddeb24cf529d6e50e33dc501 Mon Sep 17 00:00:00 2001
From: Jouni Malinen <j@w1.fi>
Date: Fri, 7 Jan 2022 13:47:16 +0200
Subject: [PATCH 3/4] SAE: Derive the y coordinate for PWE with own
 implementation

The crypto_ec_point_solve_y_coord() wrapper function might not use
constant time operations in the crypto library and as such, could leak
side channel information about the password that is used to generate the
PWE in the hunting and pecking loop. As such, calculate the two possible
y coordinate values and pick the correct one to use with constant time
selection.

Signed-off-by: Jouni Malinen <j@w1.fi>
---
 src/common/sae.c | 47 +++++++++++++++++++++++++++++++++--------------
 1 file changed, 33 insertions(+), 14 deletions(-)

diff --git a/src/common/sae.c b/src/common/sae.c
index 08fdbfd18173..8d79ed962768 100644
--- a/src/common/sae.c
+++ b/src/common/sae.c
@@ -286,14 +286,16 @@ static int sae_derive_pwe_ecc(struct sae_data *sae, const u8 *addr1,
 	int pwd_seed_odd = 0;
 	u8 prime[SAE_MAX_ECC_PRIME_LEN];
 	size_t prime_len;
-	struct crypto_bignum *x = NULL, *qr = NULL, *qnr = NULL;
+	struct crypto_bignum *x = NULL, *y = NULL, *qr = NULL, *qnr = NULL;
 	u8 x_bin[SAE_MAX_ECC_PRIME_LEN];
 	u8 x_cand_bin[SAE_MAX_ECC_PRIME_LEN];
 	u8 qr_bin[SAE_MAX_ECC_PRIME_LEN];
 	u8 qnr_bin[SAE_MAX_ECC_PRIME_LEN];
+	u8 x_y[2 * SAE_MAX_ECC_PRIME_LEN];
 	int res = -1;
 	u8 found = 0; /* 0 (false) or 0xff (true) to be used as const_time_*
 		       * mask */
+	unsigned int is_eq;
 
 	os_memset(x_bin, 0, sizeof(x_bin));
 
@@ -402,25 +404,42 @@ static int sae_derive_pwe_ecc(struct sae_data *sae, const u8 *addr1,
 		goto fail;
 	}
 
-	if (!sae->tmp->pwe_ecc)
-		sae->tmp->pwe_ecc = crypto_ec_point_init(sae->tmp->ec);
-	if (!sae->tmp->pwe_ecc)
-		res = -1;
-	else
-		res = crypto_ec_point_solve_y_coord(sae->tmp->ec,
-						    sae->tmp->pwe_ecc, x,
-						    pwd_seed_odd);
-	if (res < 0) {
-		/*
-		 * This should not happen since we already checked that there
-		 * is a result.
-		 */
+	/* y = sqrt(x^3 + ax + b) mod p
+	 * if LSB(save) == LSB(y): PWE = (x, y)
+	 * else: PWE = (x, p - y)
+	 *
+	 * Calculate y and the two possible values for PWE and after that,
+	 * use constant time selection to copy the correct alternative.
+	 */
+	y = crypto_ec_point_compute_y_sqr(sae->tmp->ec, x);
+	if (!y ||
+	    dragonfly_sqrt(sae->tmp->ec, y, y) < 0 ||
+	    crypto_bignum_to_bin(y, x_y, SAE_MAX_ECC_PRIME_LEN,
+				 prime_len) < 0 ||
+	    crypto_bignum_sub(sae->tmp->prime, y, y) < 0 ||
+	    crypto_bignum_to_bin(y, x_y + SAE_MAX_ECC_PRIME_LEN,
+				 SAE_MAX_ECC_PRIME_LEN, prime_len) < 0) {
 		wpa_printf(MSG_DEBUG, "SAE: Could not solve y");
+		goto fail;
+	}
+
+	is_eq = const_time_eq(pwd_seed_odd, x_y[prime_len - 1] & 0x01);
+	const_time_select_bin(is_eq, x_y, x_y + SAE_MAX_ECC_PRIME_LEN,
+			      prime_len, x_y + prime_len);
+	os_memcpy(x_y, x_bin, prime_len);
+	wpa_hexdump_key(MSG_DEBUG, "SAE: PWE", x_y, 2 * prime_len);
+	crypto_ec_point_deinit(sae->tmp->pwe_ecc, 1);
+	sae->tmp->pwe_ecc = crypto_ec_point_from_bin(sae->tmp->ec, x_y);
+	if (!sae->tmp->pwe_ecc) {
+		wpa_printf(MSG_DEBUG, "SAE: Could not generate PWE");
+		res = -1;
 	}
 
 fail:
+	forced_memzero(x_y, sizeof(x_y));
 	crypto_bignum_deinit(qr, 0);
 	crypto_bignum_deinit(qnr, 0);
+	crypto_bignum_deinit(y, 1);
 	os_free(dummy_password);
 	bin_clear_free(tmp_password, password_len);
 	crypto_bignum_deinit(x, 1);
-- 
2.25.1

