Fix infinite loop in BN_mod_sqrt()

A bug in the implementation of the Tonelli-Shanks algorithm can lead to
an infinite loop. This loop can be hit in various ways, in particular on
decompressing an elliptic curve public key via EC_POINT_oct2point() - to
do this, one must solve y^2 = x^3 + ax + b for y, given x.

If a certificate uses explicit encoding for elliptic curve parameters,
this operation needs to be done during certificate verification, leading
to a DoS. In particular, everything dealing with untrusted certificates
is affected, notably TLS servers explicitly configured to request
client certificates (httpd, smtpd, various VPN implementations, ...).
Ordinary TLS servers do not consume untrusted certificates.

The problem is that we cannot assume that x^3 + ax + b is actually a
square on untrusted input and neither can we assume that the modulus
p is a prime. Ensuring that p is a prime is too expensive (it would
likely itself lead to a DoS). To avoid the infinite loop, fix the logic
to be more resilient and explicitly limit the number of iterations that
can be done.  The bug is such that the infinite loop can also be hit for
primes = 3 (mod 4) but fortunately that case is optimized earlier.

It's also worth noting that there is a size bound on the field size
enforced via OPENSSL_ECC_MAX_FIELD_BITS (= 661), which help mitigate
further DoS vectors in presence of this fix.

Reported by Tavis Ormandy and David Benjamin, Google
Patch based on the fixes by David Benjamin and Tomas Mraz, OpenSSL

ok beck inoguchi

1 files changed, 15 insertions, 14 deletions

diff --git a/lib/libcrypto/bn/bn_sqrt.c b/lib/libcrypto/bn/bn_sqrt.c
index 8514f23a274..4b9638b6dca 100644
--- a/lib/libcrypto/bn/bn_sqrt.c
+++ b/lib/libcrypto/bn/bn_sqrt.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: bn_sqrt.c,v 1.9 2017/01/29 17:49:22 beck Exp $ */
+/* $OpenBSD: bn_sqrt.c,v 1.10 2022/03/15 15:52:39 tb Exp $ */
 /* Written by Lenka Fibikova <fibikova@exp-math.uni-essen.de>
  * and Bodo Moeller for the OpenSSL project. */
 /* ====================================================================
@@ -351,21 +351,22 @@ BN_mod_sqrt(BIGNUM *in, const BIGNUM *a, const BIGNUM *p, BN_CTX *ctx)
 			goto vrfy;
 		}
 
-
-		/* find smallest  i  such that  b^(2^i) = 1 */
-		i = 1;
-		if (!BN_mod_sqr(t, b, p, ctx))
-			goto end;
-		while (!BN_is_one(t)) {
-			i++;
-			if (i == e) {
-				BNerror(BN_R_NOT_A_SQUARE);
-				goto end;
+		/* Find the smallest i with 0 < i < e such that b^(2^i) = 1. */
+		for (i = 1; i < e; i++) {
+			if (i == 1) {
+				if (!BN_mod_sqr(t, b, p, ctx))
+					goto end;
+			} else {
+				if (!BN_mod_sqr(t, t, p, ctx))
+					goto end;
 			}
-			if (!BN_mod_mul(t, t, t, p, ctx))
-				goto end;
+			if (BN_is_one(t))
+				break;
+		}
+		if (i >= e) {
+			BNerror(BN_R_NOT_A_SQUARE);
+			goto end;
 		}
-
 
 		/* t := y^2^(e - i - 1) */
 		if (!BN_copy(t, y))