# [openssl.org #1705] Infinite loop in BN_GF2m_mod_arr

• 06-18-2008, 07:28 PM
unix
[openssl.org #1705] Infinite loop in BN_GF2m_mod_arr
Hi

I've come across an infinite loop in the polynomial modulus function
BN_GF2m_mod_arr when the degree of the modulus is a multiple of 32 (on
32-bit machines) or 64 (on 64-bit machines).

A simple example which illustrates this (in the attached test case) is:

(z^65 + z^5 + z^4 + z^2 + z + 1) mod (z^64 + z^4 + z^3 + z + 1) = 1

But this will hang indefinitely.

The problem occurs when the degree is a multiple of BN_BITS2. I believe
that the top d1 bits are never being cleared in the following line:

d0 = n % BN_BITS2;
d1 = BN_BITS2 - d0;

if (d0) z[dN] = (z[dN] << d1) >> d1; /* clear up the top d1 bits */

Note when n=32, that d0=0 and d1=32. Changing the above to (see
attached patch):

if (d0) z[dN] = (z[dN] << d1) >> d1; else z[dN] = 0; /* clear up the top
d1 bits */

fixes the problem.

The above seems intuitively correct since the above would be equivalent to:

z[dN] = (z[dN] << d1) >> d1;

if shifts greater than BN_BITS2 didn't wrap around (since 0<=d0<BN_BITS2
and 1<=d1<=BN_BITS2).

Attached are the following files:

test_BN_GF2m_mod_arr.cpp : My test case
BN_GF2m_mod_arr.patch : Patch to fix the bug

Regards

Robert

• 06-18-2008, 09:40 PM
unix
Re: [openssl.org #1705] Infinite loop in BN_GF2m_mod_arr
Hi,

This bug has been already reported (bug #1690) and corrected.

[url]http://www.mail-archive.com/openssl-dev@openssl.org/msg24090.html[/url]

Cheers,
--
Mounir IDRASSI
IDRIX
[url]http://www.idrix.fr[/url]

On Wed, June 18, 2008 9:28 pm, Robert Jackson via RT wrote:[color=blue]
> Hi
>
> I've come across an infinite loop in the polynomial modulus function
> BN_GF2m_mod_arr when the degree of the modulus is a multiple of 32 (on
> 32-bit machines) or 64 (on 64-bit machines).
>
> A simple example which illustrates this (in the attached test case) is:
>
> (z^65 + z^5 + z^4 + z^2 + z + 1) mod (z^64 + z^4 + z^3 + z + 1) = 1
>
> But this will hang indefinitely.
>
> The problem occurs when the degree is a multiple of BN_BITS2. I believe
> that the top d1 bits are never being cleared in the following line:
>
> d0 = n % BN_BITS2;
> d1 = BN_BITS2 - d0;
>
> if (d0) z[dN] = (z[dN] << d1) >> d1; /* clear up the top d1 bits */
>
> Note when n=32, that d0=0 and d1=32. Changing the above to (see
> attached patch):
>
> if (d0) z[dN] = (z[dN] << d1) >> d1; else z[dN] = 0; /* clear up the top
> d1 bits */
>
> fixes the problem.
>
> The above seems intuitively correct since the above would be equivalent
> to:
>
> z[dN] = (z[dN] << d1) >> d1;
>
> if shifts greater than BN_BITS2 didn't wrap around (since 0<=d0<BN_BITS2
> and 1<=d1<=BN_BITS2).
>
> Attached are the following files:
>
> test_BN_GF2m_mod_arr.cpp : My test case
> BN_GF2m_mod_arr.patch : Patch to fix the bug
>
> Regards
>
> Robert
>
>[/color]

______________________________________________________________________
OpenSSL Project [url]http://www.openssl.org[/url]
Development Mailing List [email]openssl-dev@openssl.org[/email]
Automated List Manager [email]majordomo@openssl.org[/email]