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

1 files changed, 36 insertions, 9 deletions

diff --git a/lib/libcrypto/x509v3/v3_utl.c b/lib/libcrypto/x509v3/v3_utl.c
index 4f8d16fd00c..75f7662e7ef 100644
--- a/lib/libcrypto/x509v3/v3_utl.c
+++ b/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;