mpi: introduce clamp on number of digits.

The main purpose of this patch is to prevent two cases of
numeric overflow.

One is when an arithmetic operation produces a result which
would have more digits than can be represented by mp_size. The
calculation for the digits in the result operand will simply
overflow, resulting in an undersized buffer that is then
overrun.

Another overflow is in calculations which work with bit
indexing. Even if the digits is in range of mp_size, the bit
number is eight times larger and can be out of range.

We can address both problems by clamping integers to have only
so many digits, that every bit has an offset that fits into
mp_size. If mp_size is 32 bits, that means we can still have
bignums that are half a gigabyte, which seems reasonable for
nearly any conceivable application of bignums.

After this patch, we must adjust the code in arith.c and
other places to detect errors, at least out of the functions
that can produce larger integers than their inputs.

* mpi/mpi-types.h (MP_MAX_BITS, MP_MAX_DIGITS): New macro.

* mpi/mpi.c (mp_err_string): New entry corresponding to the
new MP_TOOBIG error.
(mp_init_size, s_mp_grow): Reject, with the MP_TOOBIG error,
attemps to create or grow an mp_int mp_int such that it would
have more digits than MP_MAX_DIGITS.

* mpi/mpi.h (MP_TOOBIG): New macro code.
(MP_LAST_CODE): Redefined to MP_TOOBIG.

3 files changed, 13 insertions, 2 deletions

diff --git a/mpi/mpi-types.h b/mpi/mpi-types.h
index 5d9f21d9..a55174fb 100644
--- a/mpi/mpi-types.h
+++ b/mpi/mpi-types.h
@@ -54,4 +54,7 @@ typedef int mp_err;
 #define MP_WORD_BIT convert(mp_size, CHAR_BIT*sizeof(mp_word))
 #define MP_WORD_MAX convert(mp_word, -1)
 
+#define MP_MAX_BITS (MP_SIZE_MAX - 1)
+#define MP_MAX_DIGITS (MP_MAX_BITS / MP_DIGIT_BIT)
+
 #define RADIX (convert(mp_word, MP_DIGIT_MAX) + 1)
diff --git a/mpi/mpi.c b/mpi/mpi.c
index 46ec3ddc..eaa724b3 100644
--- a/mpi/mpi.c
+++ b/mpi/mpi.c
@@ -85,7 +85,8 @@ static const char *mp_err_string[] = {
   "out of memory", /* MP_MEM */
   "argument out of range", /* MP_RANGE */
   "invalid input parameter", /* MP_BADARG */
-  "result is undefined" /* MP_UNDEF */
+  "result is undefined", /* MP_UNDEF */
+  "result is too large" /* MP_TOOBIG */
 };
 
 static const char *s_dmap_1 =
@@ -209,6 +210,9 @@ mp_err mp_init_size(mp_int *mp, mp_size prec)
 {
   ARGCHK(mp != NULL, MP_BADARG);
 
+  if (prec > MP_MAX_DIGITS)
+    return MP_TOOBIG;
+
   if ((DIGITS(mp) = coerce(mp_digit *,
                            s_mp_alloc(prec, sizeof (mp_digit)))) == NULL)
     return MP_MEM;
@@ -2663,6 +2667,9 @@ const char *mp_strerror(mp_err ec)
 /* Make sure there are at least 'min' digits allocated to mp */
 mp_err s_mp_grow(mp_int *mp, mp_size min)
 {
+  if (min > MP_MAX_DIGITS)
+    return MP_TOOBIG;
+
   if (min > ALLOC(mp)) {
     mp_digit *tmp;
 
diff --git a/mpi/mpi.h b/mpi/mpi.h
index 5438e9a1..7bc705a4 100644
--- a/mpi/mpi.h
+++ b/mpi/mpi.h
@@ -27,7 +27,8 @@
 #define MP_RANGE -3 /* argument out of range */
 #define MP_BADARG -4 /* invalid parameter */
 #define MP_UNDEF -5 /* answer is undefined */
-#define MP_LAST_CODE MP_UNDEF
+#define MP_TOOBIG -6 /* number is too large */
+#define MP_LAST_CODE MP_TOOBIG
 
 #define MP_LT -1
 #define MP_EQ 0