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

This is a discussion on [openssl.org #1705] Infinite loop in BN_GF2m_mod_arr - Openssl ; 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 ...

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

1. ## [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 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

2. ## 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 :

http://www.mail-archive.com/openssl-.../msg24090.html

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

On Wed, June 18, 2008 9:28 pm, Robert Jackson via RT wrote:
> 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 > 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
>
>

__________________________________________________ ____________________
OpenSSL Project http://www.openssl.org
Development Mailing List openssl-dev@openssl.org
Automated List Manager majordomo@openssl.org