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

+ Reply to Thread
Results 1 to 2 of 2

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


+ Reply to Thread