Char.c

Hi Linus:

This push fixes a weakness in random number generation of file random.c.

The two polynomials of LFSR used in Linux/drivers/char/random.c are
P1(X) = x^128 + x^104 + x^76 + x^51 +x^25 + x + 1, for input pool
P2(X) = x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 , for output pool

These polynomials Q1(X) = alpha ^3 *(P1(X)-1)+1 and Q2(X) = alpha ^3
*(P2(X)-1)+1 are not primitive over GF(2^32) where alpha is an
primitive element of GF(2^32).
It turns out that periods of LFSR corresponding to these polynomials
are not optimal, it means that the space of numbers generated by these
LFSR is not  GF(2^(32*deg(Pi))-1), i=1,2.

As mentioned in the random.c file, these polynomials come from an
article http://eprint.iacr.org/2012/251.pdf. It is stated in the
article that these polynomials have periods (2^(32*deg(Pi))-1)/3,
i=1,2, so not optimal.

We can improve these LFSR choosing these polynomials as primitive and
therefore increase the space of numbers generated by 3.

The polynomials used in the current implementation of the PRNG and the
point presented here, do not conclude a practical attack on the PRNG.

After several calculations, we propose here the following polynomials:
R1(x) = x^128 + x^106 +x^79 + x^51 +x^25 + x+ 1, as new polynomial of input pool
R2(x) = x^32 + x^27 + x^21 + x^14 + x^7 + x +1, as new polynomial of
the output pool

So polynomials S1(X) = alpha^4*(R1(X)-1)+1 and S2(X) =
alpha^4*(R2(X)-1)+1 are primitive on GF(2^32).
It is very easy to check their primitive with magma. Use the online
tool (http://magma.maths.usyd.edu.au/calc/) and the following code:

K0:=GF(2);
P<X> := PolynomialRing(K0);
K1<a> := ext<K0|X^32+X^26+X^23+X^22+X^16+X^12+X^11+X^10+X^8+X^7+X^5+X^4+X^2+X^1+1>;K1;
P<t> := PolynomialRing(K1);

R1 :=  t^128 + t^106 + t^79 + t^51 + t^25 + t + 1;
S1 := a^4*(R1-1)+1;

R2 := t^32 + t^27 + t^21 + t^14 + t^7 + t + 1;
S2 := a^4*(R2-1)+1;

S1test := Evaluate((1/(t^128))*S1,1/t);S1test;

t^128 + a*t^127 + a*t^100 + a*t^74 + a*t^53 + a*t^25 + a

S1test := t^128 + a^4*t^127 + a^4*t^103 + a^4*t^77 + a^4*t^49 + a^4*t^22 + a^4;
IsPrimitive(S1test);

true

S2test := Evaluate((1/(t^32))*S2,1/t);S2test;

t^32 + a*t^31 + a*t^24 + a*t^16 + a*t^12 + a*t^6 + a

S2test := t^32 + a^4*t^31 + a^4*t^25 + a^4*t^18 + a^4*t^11 + a^4*t^5 + a^4;
IsPrimitive(S2test);

true

To use these polynomials, the following changes in the random.c file
should be applied:

olivier@Zebulon:~/Documents/linux-4.7.4/drivers/char$ diff random.c random-new.c
371,372c371,373
<        /* x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
<        { S(128),         104,     76,       51,       25,       1 },
---

       /* was: x^128 + x^104 + x^76 + x^51 +x^25 + x + 1 */
       /* x^128 + x^106 + x^79 + x^51 +x^25 + x + 1 */
       { S(128),         106,     79,       51,       25,       1 },

374,375c375,377
<        /* x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */
<        { S(32),           26,       19,       14,       7,         1 },
---

       /* was: x^32 + x^26 + x^19 + x^14 + x^7 + x + 1 */
       /* x^32 + x^27 + x^21 + x^14 + x^7 + x + 1 */
       { S(32),           27,       21,       14,       7,         1 },

478a481

/* was:

481a485,490

*/
static __u32 const twist_table[16] = {
       0x00000000, 0x1db71064, 0x3b6e20c8, 0x26d930ac,
        0x76dc4190, 0x6b6b51f4, 0x4db26158, 0x5005713c,
        0xedb88320, 0xf00f9344, 0xd6d6a3e8, 0xcb61b38c,
        0x9b64c2b0, 0x86d3d2d4, 0xa00ae278, 0xbdbdf21c };

525c534,536
<                    r->pool[i] = (w >> 3) ^ twist_table[w & 7];
---

                   /*
                  was: r->pool[i] = (w >> 3) ^ twist_table[w & 7];*/
                   r->pool[i] = (w >> 4) ^ twist_table[w & 15];

Regards,
David Fontaine & Olivier Vivolo