mpi: hardening; bug found.

The flaw in the rand function caused by mp_count_ones is
serious. For instance calls to (rand 3000000000) are expected
to produce evenly distributed values in the range zero
to one less than 3 billion. Due to this flaw, only values
in the range [0, 2147483648) are produced. The function is
wrongly informed that 3000000000 is a power of two, and
so it subtracts one from the number of bits needed for the
clamping bit mask, causing raw random values to be clamped
to 31 bits instead of 32.

* arith.c (logcount): Use mp_err to capture return value from
mp_count_ones, rather than mp_size. If the result is less than
zero, throw an internal error. (The only non-internal error
indication that could come from this function is a memory
allocation, and we already use chk_malloc under MPI).

* mpi/mpi.c (mp_count_ones): Switch return type to mp_err,
because this function returns error codes, which are negative.
(mp_is_pow_two): Fix broken test that is always true.
This affects our random number module; it's used in the random
function for bignum moduli.
(mp_toradix_case): Use unsigned char temporary for exchanging
two unsigned chars, rather than a char temporary.
(s_mp_div_d): Assert that the partial quotient t  and
remainder w, of mp_word_type, have values that fit into the
mp_digit variables to which they are being assigned.
(s_mp_ispow2d): The result of s_highest_bit(d) is unsigned,
so if we subtract 1 from 0, we create a large value which
likely converts to -1. Let's ensure that clearly with a cast
to (int) of the return value.

* mpi/mpi.h (mp_count_ones): Declaration updated.

* mpi/mplogic.c (mpl_rsh, mpl_lsh): Fix two places where we
shift the constant 1 (of type int) left by a number of bits
that can exceed the type int. Note, that these functions are
currently not called anywhere in TXR.

3 files changed, 12 insertions, 9 deletions

diff --git a/mpi/mpi.c b/mpi/mpi.c
index d3e4cb05..673c29a1 100644
--- a/mpi/mpi.c
+++ b/mpi/mpi.c
@@ -2541,11 +2541,11 @@ static mp_size s_mp_count_ones(mp_int *mp)
   return c;
 }
 
-mp_size mp_count_ones(mp_int *mp)
+mp_err mp_count_ones(mp_int *mp)
 {
   if (SIGN(mp) == MP_NEG) {
     mp_int tmp;
-    mp_size res;
+    mp_err res;
     if ((res = mp_init_copy(&tmp, mp)) != MP_OKAY)
       return res;
     if ((res = s_mp_sub_d(&tmp, 1) != MP_OKAY))
@@ -2560,7 +2560,7 @@ mp_size mp_count_ones(mp_int *mp)
 
 mp_size mp_is_pow_two(mp_int *mp)
 {
-  return s_mp_ispow2(mp) >= 0;
+  return s_mp_ispow2(mp) < MP_SIZE_MAX;
 }
 
 /* Read an integer from the given string, and set mp to the resulting
@@ -2681,7 +2681,7 @@ mp_err mp_toradix_case(mp_int *mp, unsigned char *str, int radix, int low)
     /* Reverse the digits and sign indicator */
     ix = 0;
     while (ix < pos) {
-      char tmp2 = str[ix];
+      unsigned char tmp2 = str[ix];
 
       str[ix] = str[pos];
       str[pos] = tmp2;
@@ -3418,12 +3418,15 @@ mp_err s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r)
       t = 0;
     }
 
+    assert (t <= MP_DIGIT_MAX);
     qp[ix] = t;
   }
 
   /* Deliver the remainder, if desired */
-  if (r)
+  if (r) {
+    assert (w <= MP_DIGIT_MAX);
     *r = w;
+  }
 
   s_mp_clamp(&quot);
   mp_exch(&quot, mp);
@@ -3950,7 +3953,7 @@ int s_mp_ispow2d(mp_digit d)
     return -1; /* not a power of two */
 
   /* If d == 0, s_highest_bit returns 0, thus we return -1. */
-  return s_highest_bit(d) - 1;
+  return (int) s_highest_bit(d) - 1;
 }
 
 /* Convert the given character to its digit value, in the given radix.
diff --git a/mpi/mpi.h b/mpi/mpi.h
index 1106abde..c1b50296 100644
--- a/mpi/mpi.h
+++ b/mpi/mpi.h
@@ -177,7 +177,7 @@ mp_err mp_to_unsigned_bin(mp_int *mp, unsigned char *str);
 mp_err mp_to_unsigned_buf(mp_int *mp, unsigned char *str, size_t size);
 
 mp_size mp_count_bits(mp_int *mp);
-mp_size mp_count_ones(mp_int *mp);
+mp_err mp_count_ones(mp_int *mp);
 mp_size mp_is_pow_two(mp_int *mp);
 
 #if MP_COMPAT_MACROS
diff --git a/mpi/mplogic.c b/mpi/mplogic.c
index eae1ea47..5defba73 100644
--- a/mpi/mplogic.c
+++ b/mpi/mplogic.c
@@ -185,7 +185,7 @@ mp_err mpl_rsh(mp_int *a, mp_int *b, mp_digit d)
   /* Now handle any remaining bit shifting */
   if (bshift)
   {
-    mp_digit prev = 0, next, mask = (1 << bshift) - 1;
+    mp_digit prev = 0, next, mask = (convert(mp_digit, 1) << bshift) - 1;
     mp_size ix;
 
     /* 'mask' is a digit with the lower bshift bits set, the rest
@@ -229,7 +229,7 @@ mp_err mpl_lsh(mp_int *a, mp_int *b, mp_digit d)
 
   if (bshift) {
     mp_size ix;
-    mp_digit prev = 0, next, mask = (1 << bshift) - 1;
+    mp_digit prev = 0, next, mask = (convert(mp_digit, 1) << bshift) - 1;
 
     for (ix = 0; ix < USED(b); ix++) {
       next = (DIGIT(b, ix) >> (DIGIT_BIT - bshift)) & mask;