aboutsummaryrefslogtreecommitdiffstats
path: root/src/common/dragonfly.c
diff options
context:
space:
mode:
authorJouni Malinen <jouni@codeaurora.org>2019-04-25 19:35:14 (GMT)
committerJouni Malinen <j@w1.fi>2019-04-25 20:49:49 (GMT)
commit17749e948acb85570de6b809e7e84bc5472a2e3c (patch)
tree61734fe9ada3265de8d185ce0b13264a309594ba /src/common/dragonfly.c
parenta9615b1b889680dea7fe39d55a59e8a7e8b03b6d (diff)
downloadhostap-17749e948acb85570de6b809e7e84bc5472a2e3c.zip
hostap-17749e948acb85570de6b809e7e84bc5472a2e3c.tar.gz
hostap-17749e948acb85570de6b809e7e84bc5472a2e3c.tar.bz2
Share common SAE and EAP-pwd functionality: is_quadratic_residue
Use a shared helper function for the blinded mechanism of determining the Legendre symbol. Signed-off-by: Jouni Malinen <jouni@codeaurora.org>
Diffstat (limited to 'src/common/dragonfly.c')
-rw-r--r--src/common/dragonfly.c76
1 files changed, 75 insertions, 1 deletions
diff --git a/src/common/dragonfly.c b/src/common/dragonfly.c
index d4c3561..f6ecf43 100644
--- a/src/common/dragonfly.c
+++ b/src/common/dragonfly.c
@@ -10,6 +10,7 @@
#include "utils/includes.h"
#include "utils/common.h"
+#include "utils/const_time.h"
#include "crypto/crypto.h"
#include "dragonfly.h"
@@ -60,7 +61,7 @@ int dragonfly_get_random_qr_qnr(const struct crypto_bignum *prime,
}
-struct crypto_bignum *
+static struct crypto_bignum *
dragonfly_get_rand_1_to_p_1(const struct crypto_bignum *prime)
{
struct crypto_bignum *tmp, *pm1, *one;
@@ -80,3 +81,76 @@ dragonfly_get_rand_1_to_p_1(const struct crypto_bignum *prime)
crypto_bignum_deinit(one, 0);
return tmp;
}
+
+
+int dragonfly_is_quadratic_residue_blind(struct crypto_ec *ec,
+ const u8 *qr, const u8 *qnr,
+ const struct crypto_bignum *val)
+{
+ struct crypto_bignum *r, *num, *qr_or_qnr = NULL;
+ int check, res = -1;
+ u8 qr_or_qnr_bin[DRAGONFLY_MAX_ECC_PRIME_LEN];
+ const struct crypto_bignum *prime;
+ size_t prime_len;
+ unsigned int mask;
+
+ prime = crypto_ec_get_prime(ec);
+ prime_len = crypto_ec_prime_len(ec);
+
+ /*
+ * Use a blinding technique to mask val while determining whether it is
+ * a quadratic residue modulo p to avoid leaking timing information
+ * while determining the Legendre symbol.
+ *
+ * v = val
+ * r = a random number between 1 and p-1, inclusive
+ * num = (v * r * r) modulo p
+ */
+ r = dragonfly_get_rand_1_to_p_1(prime);
+ if (!r)
+ return -1;
+
+ num = crypto_bignum_init();
+ if (!num ||
+ crypto_bignum_mulmod(val, r, prime, num) < 0 ||
+ crypto_bignum_mulmod(num, r, prime, num) < 0)
+ goto fail;
+
+ /*
+ * Need to minimize differences in handling different cases, so try to
+ * avoid branches and timing differences.
+ *
+ * If r is odd:
+ * num = (num * qr) module p
+ * LGR(num, p) = 1 ==> quadratic residue
+ * else:
+ * num = (num * qnr) module p
+ * LGR(num, p) = -1 ==> quadratic residue
+ *
+ * mask is set to !odd(r)
+ */
+ mask = const_time_is_zero(crypto_bignum_is_odd(r));
+ const_time_select_bin(mask, qnr, qr, prime_len, qr_or_qnr_bin);
+ qr_or_qnr = crypto_bignum_init_set(qr_or_qnr_bin, prime_len);
+ if (!qr_or_qnr ||
+ crypto_bignum_mulmod(num, qr_or_qnr, prime, num) < 0)
+ goto fail;
+ /* branchless version of check = odd(r) ? 1 : -1, */
+ check = const_time_select_int(mask, -1, 1);
+
+ /* Determine the Legendre symbol on the masked value */
+ res = crypto_bignum_legendre(num, prime);
+ if (res == -2) {
+ res = -1;
+ goto fail;
+ }
+ /* branchless version of res = res == check
+ * (res is -1, 0, or 1; check is -1 or 1) */
+ mask = const_time_eq(res, check);
+ res = const_time_select_int(mask, 1, 0);
+fail:
+ crypto_bignum_deinit(num, 1);
+ crypto_bignum_deinit(r, 1);
+ crypto_bignum_deinit(qr_or_qnr, 1);
+ return res;
+}