From 72fa0e445948a698471c35be00d67bf6c770dd65 Mon Sep 17 00:00:00 2001
From: tb <>
Date: Sat, 13 Apr 2019 18:42:23 +0000
Subject: Avoid quadratic behavior of decimal BIGNUM conversion

The complexity of BN_bn2dec(bn) is quadratic in the length of bn.  This
function is used for printing numbers in CRLs which are typically small.
If a BN is larger than 127 bits, dump it as hex because that's cheap and
for numbers this size not significantly harder for humans to parse.

OpenSSL commit 10a3195fcf7d04ba519651cf12e945a8fe470a3c by David Benjamin
(still under the old licence), but significantly simplified.

Ideally, we would catch excessively large numbers on deserialization, but
that is made trickier by the templated ASN1.  Erroring out is also not an
option since the relevant part of the x509v3/ directory doesn't like to
do proper error checking (looking at you v2i and i2v).

Timeout found by oss-fuzz, should fix issues #13823 and #14130.

input & ok jsing
---
 src/lib/libcrypto/x509v3/v3_utl.c | 45 +++++++++++++++++++++++++++++++--------
 1 file changed, 36 insertions(+), 9 deletions(-)

diff --git a/src/lib/libcrypto/x509v3/v3_utl.c b/src/lib/libcrypto/x509v3/v3_utl.c
index 4f8d16fd00..75f7662e7e 100644
--- a/src/lib/libcrypto/x509v3/v3_utl.c
+++ b/src/lib/libcrypto/x509v3/v3_utl.c
@@ -1,4 +1,4 @@
-/* $OpenBSD: v3_utl.c,v 1.31 2018/05/19 10:50:08 tb Exp $ */
+/* $OpenBSD: v3_utl.c,v 1.32 2019/04/13 18:42:23 tb Exp $ */
 /* Written by Dr Stephen N Henson (steve@openssl.org) for the OpenSSL
  * project.
  */
@@ -66,6 +66,7 @@
 #include <openssl/err.h>
 #include <openssl/x509v3.h>
 
+char *bnstr(const BIGNUM *bn);
 static char *strip_spaces(char *name);
 static int sk_strcmp(const char * const *a, const char * const *b);
 static STACK_OF(OPENSSL_STRING) *get_email(X509_NAME *name,
@@ -148,17 +149,43 @@ X509V3_add_value_bool_nf(const char *name, int asn1_bool,
 	return 1;
 }
 
+char *
+bn_to_string(const BIGNUM *bn)
+{
+	const char *sign = "";
+	char *bnstr, *hex;
+	char *ret = NULL;
+
+	/* Only display small numbers in decimal, as conversion is quadratic. */
+	if (BN_num_bits(bn) < 128)
+		return BN_bn2dec(bn);
+
+	if ((hex = bnstr = BN_bn2hex(bn)) == NULL)
+		goto err;
+
+	if (BN_is_negative(bn)) {
+		sign = "-";
+		hex++;
+	}
+
+	if (asprintf(&ret, "%s0x%s", sign, hex) == -1)
+		ret = NULL;
+
+ err:
+	free(bnstr);
+	return ret;
+}
 
 char *
 i2s_ASN1_ENUMERATED(X509V3_EXT_METHOD *method, const ASN1_ENUMERATED *a)
 {
-	BIGNUM *bntmp = NULL;
+	BIGNUM *bntmp;
 	char *strtmp = NULL;
 
-	if (!a)
+	if (a == NULL)
 		return NULL;
-	if (!(bntmp = ASN1_ENUMERATED_to_BN(a, NULL)) ||
-	    !(strtmp = BN_bn2dec(bntmp)))
+	if ((bntmp = ASN1_ENUMERATED_to_BN(a, NULL)) == NULL ||
+	    (strtmp = bn_to_string(bntmp)) == NULL)
 		X509V3error(ERR_R_MALLOC_FAILURE);
 	BN_free(bntmp);
 	return strtmp;
@@ -167,13 +194,13 @@ i2s_ASN1_ENUMERATED(X509V3_EXT_METHOD *method, const ASN1_ENUMERATED *a)
 char *
 i2s_ASN1_INTEGER(X509V3_EXT_METHOD *method, const ASN1_INTEGER *a)
 {
-	BIGNUM *bntmp = NULL;
+	BIGNUM *bntmp;
 	char *strtmp = NULL;
 
-	if (!a)
+	if (a == NULL)
 		return NULL;
-	if (!(bntmp = ASN1_INTEGER_to_BN(a, NULL)) ||
-	    !(strtmp = BN_bn2dec(bntmp)))
+	if ((bntmp = ASN1_INTEGER_to_BN(a, NULL)) == NULL ||
+	    (strtmp = bn_to_string(bntmp)) == NULL)
 		X509V3error(ERR_R_MALLOC_FAILURE);
 	BN_free(bntmp);
 	return strtmp;
-- 
cgit v1.2.3-55-g6feb