PolynomialMod2::operator<<= Bug

[apatryda]

When using PolynomialMod2 shift left operator, the most significant word
is lost when shifting by more than WORD_BITS bits.

In "gf2n.c" the line 349 states:

 reg[reg.size()-1] = carry;

it should be:

 reg[reg.size()-shiftWords-1] = carry;

[noloader]

Confirmed there's some wonkiness going on. Crossing the boundary from 64-bits to 65-bits produces:

...
63:
  1111111,11111111,11111111,11111111,11111111,11111111,11111111,11111111,10000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000b
64:
  11111111,11111111,11111111,11111111,11111111,11111111,11111111,11111111,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000b
65:
  1010000,00000000,00000000,00000000,00000000,00000000,00000000,00000000,11111111,11111111,11111111,11111111,11111111,11111111,11111111,11111110,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000b
66:
  11111111,11111111,11111111,11111111,11111111,11111111,11111111,11111100,00000000,00000000,00000000,00000000,00000000,00000000,00000000,00000000b
...

---

$ cat mod2.cxx 
#include <iostream>
#include "gf2n.h"

int main()
{
    cout << "WORD_BITS: " << WORD_BITS << endl;
    const word v(SIZE_MAX);  // String of 1's

    const PolynomialMod2 mod(v);
    unsigned int i = 0;

    for (i=WORD_BITS - 8; i <= 2*WORD_BITS + 8; i++)
    {
        cout << i << ":" << endl;
        cout << "  " << (mod << i)  << endl;
    }

    return 0;
}

[noloader]

@apatryda - Here you go. Thanks for reporting.

Have you checked the other mod arithmetic classes? If you have not, then we'll audit them. It appears there is nothing to audit.

Maybe we need a few test cases added.... Done...

@@ -320,6 +325,11 @@

 PolynomialMod2& PolynomialMod2::operator<<=(unsigned int n)
 {
+#if !defined(NDEBUG)
+   int x; CRYPTOPP_UNUSED(x);
+   assert(SafeConvert(n,x));
+#endif
+
    if (!reg.size())
        return *this;

@@ -348,8 +358,8 @@
        return *this;
    }

-   int shiftWords = n / WORD_BITS;
-   int shiftBits = n % WORD_BITS;
+   const int shiftWords = n / WORD_BITS;
+   const int shiftBits = n % WORD_BITS;

    if (shiftBits)
    {
@@ -365,8 +375,9 @@

    if (carry)
    {
-       reg.Grow(reg.size()+shiftWords+1);
-       reg[reg.size()-1] = carry;
+       const size_t carryIndex = reg.size();
+       reg.Grow(reg.size()+shiftWords+!!shiftBits);
+       reg[carryIndex] = carry;
    }
    else
        reg.Grow(reg.size()+shiftWords);

[noloader]

@apatryda - I wanted to give you a heads up here... I was testing under Debian's X32 Port, and here's the result:

Testing PolynomialMod2 bit operations...

passed    1 shifted over range [0,129]
FAILED    0xffffffff shifted over range [0,129]
passed    random values shifted over range [0,129]

I'm getting ready to put it under the debugger. I _think_ I may have crafted the test case incorrectly, and it only shows up under X32.

False alarm... It was the test case.