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 -- To unsubscribe from this list: send the line "unsubscribe linux-crypto" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
