[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
32bit machines) or 64 (on 64bit machines).
A simple example which illustrates this (in the ...

[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
32bit machines) or 64 (on 64bit 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

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.mailarchive.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
> 32bit machines) or 64 (on 64bit 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 openssldev@openssl.org
Automated List Manager majordomo@openssl.org