[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

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

Hi,

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

See the following link :

[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]