[PATCH 1/1] mpi: check for shift exponent greater than 31.

[PATCH 1/1] mpi: check for shift exponent greater than 31.

[Ayush Mittal]

This patch check for shift exponent greater than 31,
detected by UBSAN.

1)UBSAN: Undefined behaviour in lib/mpi/generic_mpih-lshift.c:57:22
 shift exponent 32 is too large for 32-bit type 'long unsigned int'

2)UBSAN: Undefined behaviour in lib/mpi/generic_mpih-lshift.c:60:20
shift exponent 32 is too large for 32-bit type 'long unsigned int'

3)UBSAN: Undefined behaviour in lib/mpi/generic_mpih-rshift.c:57:21
shift exponent 32 is too large for 32-bit type 'long unsigned int'

4) UBSAN: Undefined behaviour in lib/mpi/generic_mpih-rshift.c:60:19
shift exponent 32 is too large for 32-bit type 'long unsigned int'

So instead of undefined behaviour defining behaviour when shift exponent 
is greater than 31 then value will be Zero .

Signed-off-by: Ayush Mittal <ayush.m@samsung.com>
Signed-off-by: Vaneet Narang <v.narang@samsung.com>
---
 lib/mpi/generic_mpih-lshift.c | 6 +++---
 lib/mpi/generic_mpih-rshift.c | 6 +++---
 lib/mpi/mpi-internal.h        | 3 +++
 3 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/lib/mpi/generic_mpih-lshift.c b/lib/mpi/generic_mpih-lshift.c
index 8631892..1c8277e 100644
--- a/lib/mpi/generic_mpih-lshift.c
+++ b/lib/mpi/generic_mpih-lshift.c
@@ -50,14 +50,14 @@
 	sh_2 = BITS_PER_MPI_LIMB - sh_1;
 	i = usize - 1;
 	low_limb = up[i];
-	retval = low_limb >> sh_2;
+	retval = MPI_RSHIFT(low_limb, sh_2);
 	high_limb = low_limb;
 	while (--i >= 0) {
 		low_limb = up[i];
-		wp[i] = (high_limb << sh_1) | (low_limb >> sh_2);
+		wp[i] = MPI_LSHIFT(high_limb, sh_1) | MPI_RSHIFT(low_limb, sh_2);
 		high_limb = low_limb;
 	}
-	wp[i] = high_limb << sh_1;
+	wp[i] = MPI_LSHIFT(high_limb, sh_1);
 
 	return retval;
 }
diff --git a/lib/mpi/generic_mpih-rshift.c b/lib/mpi/generic_mpih-rshift.c
index ffa3288..3a28bdd 100644
--- a/lib/mpi/generic_mpih-rshift.c
+++ b/lib/mpi/generic_mpih-rshift.c
@@ -50,14 +50,14 @@
 	wp -= 1;
 	sh_2 = BITS_PER_MPI_LIMB - sh_1;
 	high_limb = up[0];
-	retval = high_limb << sh_2;
+	retval = MPI_LSHIFT(high_limb, sh_2);
 	low_limb = high_limb;
 	for (i = 1; i < usize; i++) {
 		high_limb = up[i];
-		wp[i] = (low_limb >> sh_1) | (high_limb << sh_2);
+		wp[i] = MPI_RSHIFT(low_limb, sh_1) | MPI_LSHIFT(high_limb, sh_2);
 		low_limb = high_limb;
 	}
-	wp[i] = low_limb >> sh_1;
+	wp[i] = MPI_RSHIFT(low_limb, sh_1);
 
 	return retval;
 }
diff --git a/lib/mpi/mpi-internal.h b/lib/mpi/mpi-internal.h
index 7eceedd..9c94a98 100644
--- a/lib/mpi/mpi-internal.h
+++ b/lib/mpi/mpi-internal.h
@@ -37,6 +37,9 @@
 #include <linux/mpi.h>
 #include <linux/errno.h>
 
+#define MPI_LSHIFT(val, shift) (shift >= BITS_PER_MPI_LIMB ? 0 : (val << shift))
+#define MPI_RSHIFT(val, shift) (shift >= BITS_PER_MPI_LIMB ? 0 : (val >> shift))
+
 #define log_debug printk
 #define log_bug printk
 
-- 
1.9.1

RE: Re: [PATCH 1/1] mpi: check for shift exponent greater than 31.

[Vaneet Narang]

 
Hi,

>> This patch check for shift exponent greater than 31,

Yes, This should be "check for shift exponent greater than BITS_PER_LONG"

>Firstly, isn't it 63 on 64-bit machines?

Description of patch is specific to 32bit machine but patch is made considering 64bit in mind also. 
and this is the precisly the reason we have been comparing with BITS_PER_MPI_LIMB 
as BITS_PER_MPI_LIMB is BITS_PER_LONG.

>Secondly, this is the wrong way to do things.  The banner comment on
>mpihelp_lshift(), for example, says that the function has the following
>argument constraints:

>	0 < CNT < BITS_PER_MP_LIMB

>so sh1 and sh2 must both be in the range 1-31 or 1-63, assuming cnt is
>within its constraints.

You are right, there is already a comment for the range but in our case caller was mpi_powm() itself
so to fix UBSAN warning we prefferd handling in mpihelp_lshift/mpihelp_rshift.

Call Sequence:
[0-1.1677] [<c03ba190>] (ubsan_epilogue) from [<c03ba754>] (__ubsan_handle_shift_out_of_bounds+0xf4/0x13c)
[0-1.1677] [<c03ba660>] (__ubsan_handle_shift_out_of_bounds) from [<c03b5a44>] (mpihelp_lshift+0xf0/0x160)
[0-1.1677] [<c03b5954>] (mpihelp_lshift) from [<c03b8920>] (mpi_powm+0x308/0xc7c)

Scenario: MPI mod passed to mpi_powm has 0 last valid limb. 

count_leading_zeros() returns 32/64 when last valid limb of mod is 0.

* If @x is 0 then the result is COUNT_LEADING_ZEROS_0.
*/
static inline int count_leading_zeros(unsigned long x)
#define COUNT_LEADING_ZEROS_0 BITS_PER_LONG

int mpi_powm(MPI res, MPI base, MPI exp, MPI mod)
{
....
        mod_shift_cnt = count_leading_zeros(mod->d[msize - 1]);  --> count_leading_zeros can return 32/64
        if (mod_shift_cnt)
                mpihelp_lshift(mp, mod->d, msize, mod_shift_cnt); --> 32/64 can be passed to mpihelp_lshift
....
                /* Remove any leading zero words from the result.  */
                if (mod_shift_cnt)
                        mpihelp_rshift(rp, rp, rsize, mod_shift_cnt); --> Similarly 32/64 can be passed to mpihelp_rshift
....						
}						


>Therefore if it needs a checking, you only need to check cnt on entry to the
>function, rather than checking sh1 and sh2 inside the loop.  Further, you
>should use pr_err() so that we know that this has gone wrong and return an
>error to the caller (there are security implications).

Since we were not sure about checking cnt and returning some error value. we thought it may break mpi_powm().
We preferred doing a clean handling of invalid input without changing any behaviour of mpihelp_lshift/rshift . 
Please suggest how overflow can handled without breaking mpi_powm().

>Further, have you checked the caller to see if they do ever violate the
>constraints?

>From caller side, only issue which i can think is passing 0 in as last valid limb of mod. Is this any
constraint ?

Regards,
Vaneet Narang

Re: [PATCH 1/1] mpi: check for shift exponent greater than 31.

[David Howells]

Ayush Mittal <ayush.m@samsung.com> wrote:

> This patch check for shift exponent greater than 31,

Firstly, isn't it 63 on 64-bit machines?

Secondly, this is the wrong way to do things.  The banner comment on
mpihelp_lshift(), for example, says that the function has the following
argument constraints:

	0 < CNT < BITS_PER_MP_LIMB

so sh1 and sh2 must both be in the range 1-31 or 1-63, assuming cnt is
within its constraints.

Therefore if it needs a checking, you only need to check cnt on entry to the
function, rather than checking sh1 and sh2 inside the loop.  Further, you
should use pr_err() so that we know that this has gone wrong and return an
error to the caller (there are security implications).

Further, have you checked the caller to see if they do ever violate the
constraints?

It looks like you're adding fixes for your test, not for the code.

David

[PATCH 1/1] mpi: check for shift exponent greater than 31.

[Ayush Mittal]

This patch check for shift exponent greater than 31,
detected by UBSAN.

1)UBSAN: Undefined behaviour in lib/mpi/generic_mpih-lshift.c:57:22
 shift exponent 32 is too large for 32-bit type 'long unsigned int'

2)UBSAN: Undefined behaviour in lib/mpi/generic_mpih-lshift.c:60:20
shift exponent 32 is too large for 32-bit type 'long unsigned int'

3)UBSAN: Undefined behaviour in lib/mpi/generic_mpih-rshift.c:57:21
shift exponent 32 is too large for 32-bit type 'long unsigned int'

4) UBSAN: Undefined behaviour in lib/mpi/generic_mpih-rshift.c:60:19
shift exponent 32 is too large for 32-bit type 'long unsigned int'

So instead of undefined behaviour defining behaviour when shift exponent 
is greater than 31 then value will be Zero .

Signed-off-by: Ayush Mittal <ayush.m@samsung.com>
Signed-off-by: Vaneet Narang <v.narang@samsung.com>
---
 lib/mpi/generic_mpih-lshift.c | 6 +++---
 lib/mpi/generic_mpih-rshift.c | 6 +++---
 lib/mpi/mpi-internal.h        | 3 +++
 3 files changed, 9 insertions(+), 6 deletions(-)

diff --git a/lib/mpi/generic_mpih-lshift.c b/lib/mpi/generic_mpih-lshift.c
index 8631892..1c8277e 100644
--- a/lib/mpi/generic_mpih-lshift.c
+++ b/lib/mpi/generic_mpih-lshift.c
@@ -50,14 +50,14 @@
 	sh_2 = BITS_PER_MPI_LIMB - sh_1;
 	i = usize - 1;
 	low_limb = up[i];
-	retval = low_limb >> sh_2;
+	retval = MPI_RSHIFT(low_limb, sh_2);
 	high_limb = low_limb;
 	while (--i >= 0) {
 		low_limb = up[i];
-		wp[i] = (high_limb << sh_1) | (low_limb >> sh_2);
+		wp[i] = MPI_LSHIFT(high_limb, sh_1) | MPI_RSHIFT(low_limb, sh_2);
 		high_limb = low_limb;
 	}
-	wp[i] = high_limb << sh_1;
+	wp[i] = MPI_LSHIFT(high_limb, sh_1);
 
 	return retval;
 }
diff --git a/lib/mpi/generic_mpih-rshift.c b/lib/mpi/generic_mpih-rshift.c
index ffa3288..3a28bdd 100644
--- a/lib/mpi/generic_mpih-rshift.c
+++ b/lib/mpi/generic_mpih-rshift.c
@@ -50,14 +50,14 @@
 	wp -= 1;
 	sh_2 = BITS_PER_MPI_LIMB - sh_1;
 	high_limb = up[0];
-	retval = high_limb << sh_2;
+	retval = MPI_LSHIFT(high_limb, sh_2);
 	low_limb = high_limb;
 	for (i = 1; i < usize; i++) {
 		high_limb = up[i];
-		wp[i] = (low_limb >> sh_1) | (high_limb << sh_2);
+		wp[i] = MPI_RSHIFT(low_limb, sh_1) | MPI_LSHIFT(high_limb, sh_2);
 		low_limb = high_limb;
 	}
-	wp[i] = low_limb >> sh_1;
+	wp[i] = MPI_RSHIFT(low_limb, sh_1);
 
 	return retval;
 }
diff --git a/lib/mpi/mpi-internal.h b/lib/mpi/mpi-internal.h
index 7eceedd..9c94a98 100644
--- a/lib/mpi/mpi-internal.h
+++ b/lib/mpi/mpi-internal.h
@@ -37,6 +37,9 @@
 #include <linux/mpi.h>
 #include <linux/errno.h>
 
+#define MPI_LSHIFT(val, shift) (shift >= BITS_PER_MPI_LIMB ? 0 : (val << shift))
+#define MPI_RSHIFT(val, shift) (shift >= BITS_PER_MPI_LIMB ? 0 : (val >> shift))
+
 #define log_debug printk
 #define log_bug printk
 
-- 
1.9.1