random.c: LFSR polynomials are not irreducible/primitive

random.c: LFSR polynomials are not irreducible/primitive

[Stephan Mueller]

Hi Ted,

drivers/char/random.c contains the following comment:

"""
 * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
 * Videau in their paper, "The Linux Pseudorandom Number Generator
 * Revisited" (see: http://eprint.iacr.org/2012/251.pdf).  In their
 * paper, they point out that we are not using a true Twisted GFSR,
 * since Matsumoto & Kurita used a trinomial feedback polynomial (that
 * is, with only three taps, instead of the six that we are using).
 * As a result, the resulting polynomial is neither primitive nor
 * irreducible, and hence does not have a maximal period over
 * GF(2**32).  They suggest a slight change to the generator
 * polynomial which improves the resulting TGFSR polynomial to be
 * irreducible, which we have made here.
"""

This comment leads me to belief that the current polynomial is primitive (and 
irreducible).

Strangely, this is not the case as seen with the following code that can be 
used with the mathematical tool called magma. There is a free online version 
of magma available to recheck it: http://magma.maths.usyd.edu.au/calc/

Note, the polynomials used up till 3.12 were primitive and irreducible.

Could you please help me understanding why the current polynomials are better 
than the old ones?

Thanks a lot.

F:=GF(2);
F;

P<x>:=PolynomialRing(F);
P;

print "Old polynomials:";

P<x>:=x^128 + x^103 + x^76 + x^51 +x^25 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

P<x>:=x^32 + x^26 + x^20 + x^14 + x^7 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

print "New polynomials:";

P<x>:=x^128 + x^104 + x^76 + x^51 +x^25 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

P<x>:=x^32 + x^26 + x^19 + x^14 + x^7 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

And obtained:

Finite field of size 2
Univariate Polynomial Ring in x over GF(2)
Old polynomials:
x^128 + x^103 + x^76 + x^51 + x^25 + x + 1
is irreducible:
true
is primitive:
true
x^32 + x^26 + x^20 + x^14 + x^7 + x + 1
is irreducible:
true
is primitive:
true
New polynomials:
x^128 + x^104 + x^76 + x^51 + x^25 + x + 1
is irreducible:
false
is primitive:
false
x^32 + x^26 + x^19 + x^14 + x^7 + x + 1
is irreducible:
false
is primitive:
false


Ciao
Stephan

Re: random.c: LFSR polynomials are not irreducible/primitive

[Theodore Ts'o]

On Mon, Aug 14, 2017 at 10:20:18AM +0200, Stephan Mueller wrote:
> Hi Ted,
> 
> drivers/char/random.c contains the following comment:
> 
> """
>  * Our mixing functions were analyzed by Lacharme, Roeck, Strubel, and
>  * Videau in their paper, "The Linux Pseudorandom Number Generator
>  * Revisited" (see: http://eprint.iacr.org/2012/251.pdf).  In their
>  * paper, they point out that we are not using a true Twisted GFSR,
>  * since Matsumoto & Kurita used a trinomial feedback polynomial (that
>  * is, with only three taps, instead of the six that we are using).
>  * As a result, the resulting polynomial is neither primitive nor
>  * irreducible, and hence does not have a maximal period over
>  * GF(2**32).  They suggest a slight change to the generator
>  * polynomial which improves the resulting TGFSR polynomial to be
>  * irreducible, which we have made here.
> """
> 
> This comment leads me to belief that the current polynomial is primitive (and 
> irreducible).
> 
> Strangely, this is not the case as seen with the following code that can be 
> used with the mathematical tool called magma. There is a free online version 
> of magma available to recheck it: http://magma.maths.usyd.edu.au/calc/
> 
> Note, the polynomials used up till 3.12 were primitive and irreducible.
> 
> Could you please help me understanding why the current polynomials are better 
> than the old ones?

Have you looked at section 3.1.1 of the above cited paper?

	http://eprint.iacr.org/2012/251.pdf

							- Ted

Re: random.c: LFSR polynomials are not irreducible/primitive

[Stephan Mueller]

Am Dienstag, 15. August 2017, 00:21:05 CEST schrieb Theodore Ts'o:

Hi Theodore,

> Have you looked at section 3.1.1 of the above cited paper?
> 
> 	http://eprint.iacr.org/2012/251.pdf

Thanks for the hint, but that does not seem to solve the mystery either.

When I use magma with GF(2^32), I see that all polynomials are neither 
primitive nor irreducible:

F:=GF(4294967296);
F;

P<x>:=PolynomialRing(F);
P;
print "Old polynomials:";

P<x>:=x^128 + x^103 + x^76 + x^51 +x^25 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

P<x>:=x^32 + x^26 + x^20 + x^14 + x^7 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

print "New polynomials:";

P<x>:=x^128 + x^104 + x^76 + x^51 +x^25 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);

P<x>:=x^32 + x^26 + x^19 + x^14 + x^7 + x + 1;
P;
print "is irreducible: "; IsIrreducible(P);
print "is primitive: "; IsPrimitive(P);



The output is:

Finite field of size 2^32
Univariate Polynomial Ring in x over GF(2^32)
Old polynomials:
x^128 + x^103 + x^76 + x^51 + x^25 + x + 1
is irreducible:
false
is primitive:
false
x^32 + x^26 + x^20 + x^14 + x^7 + x + 1
is irreducible:
false
is primitive:
false
New polynomials:
x^128 + x^104 + x^76 + x^51 + x^25 + x + 1
is irreducible:
false
is primitive:
false
x^32 + x^26 + x^19 + x^14 + x^7 + x + 1
is irreducible:
false
is primitive:
false


Thus, I am unsure how the referenced document concludes that the new 
polynomials are irreducible over GF(2^32).

Ciao
Stephan

Re: random.c: LFSR polynomials are not irreducible/primitive

[Theodore Ts'o]

On Tue, Aug 15, 2017 at 10:45:17AM +0200, Stephan Mueller wrote:
> Am Dienstag, 15. August 2017, 00:21:05 CEST schrieb Theodore Ts'o:
> 
> Hi Theodore,
> 
> > Have you looked at section 3.1.1 of the above cited paper?
> > 
> > 	http://eprint.iacr.org/2012/251.pdf
> 
> Thanks for the hint, but that does not seem to solve the mystery either.
> 
> When I use magma with GF(2^32), I see that all polynomials are neither 
> primitive nor irreducible:

I believe that assertion being made in that section is not that
modified P(X) is primitive, but that Q(X) is primitive

	Q(X) = α**3 (P(X) − 1) + 1

Where multiplication by α**3 is done by a twist-table lookup.

Also of interest might be this paper, which I believe totally missed
when the authors made their proposal on the linux-crypto list in
September 2016 (I've added them to the cc list):

	https://eprint.iacr.org/2017/726.pdf

The date on the paper is from just 3 weeks ago or so, and it was just
luck that I found it when Googling to find some other references in
response to your question.  (Thanks for raising the question, BTW).

I don't have a huge amount invested in any of the mixing schemes,
because in practice we are *not* feeding large number of zero inputs
into mixing function.  So while it is good to make the mixing function
to have as large a cyclic length as possible, it seems unlikely that
the weaknesses of the current polynomials can be leveraged into a
practical attack.

Stephan, if you have any comments on the proposal made by David
Fontaine and Olivier Vivolo, I'd appreciate hearing them!

						- Ted

Re: random.c: LFSR polynomials are not irreducible/primitive

[Stephan Mueller]

[-- Attachment #1: Type: text/plain, Size: 1102 bytes --]

Am Dienstag, 15. August 2017, 17:12:24 CEST schrieb Theodore Ts'o:

Hi Theodore,

> 
> Stephan, if you have any comments on the proposal made by David
> Fontaine and Olivier Vivolo, I'd appreciate hearing them!

I think I have some news: The magma code I used for GF(2^32) testing was not 
correct.

The corrected magma code is attached (thanks to Dr. Peter Birkner, BSI, who 
helped me here).

That magma code shows:

- the current polynomials for Q(X) = α**3 (P(X) − 1) + 1 are irreducible but 
not primitive over GF(2^32)

- the polynomials suggested in https://eprint.iacr.org/2017/726.pdf Q(X) = 
α**4 (P(X) − 1) + 1 are both, irreducible and primitive over GF(2^32)

The use of GF(2^32) is important, because we apply the LFSR to a 32 bit word. 
Hence, we have 2^32 permutations the LFSR should evenly cover.


Bottom line, I would recommend that random.c is patched to take the 
polynomials suggested in https://eprint.iacr.org/2017/726.pdf.


If it is of any help, the attached magma code could be preserved somewhere 
useful (in random.c?)

Ciao
Stephan

[-- Attachment #2: LFSR_polynomials eprint 251.mag --]
[-- Type: application/x-wine-extension-mag, Size: 2655 bytes --]

Re: random.c: LFSR polynomials are not irreducible/primitive

[Fontaine david]

Hi,

Sorry to answer this late, but i was pretty busy, and i assume Olivier
Vivolo is on vacation.

For a polynomial, being primitive implies being irreducible, and the
polynomial which must be primitive is Q(x), as you described it
earlier, on GF(2^32).
When the polynomials will be primitive,the TGFSR (LFSR on 32 bit word)
will have his maximal period.
If i remember well, we gived inthe paper, the magma code, and the
patch for random.c.
We did several tests for the propsal, and we chose those polynomials
because they avoid a lot of changes on the source code, and they
preserve the quality of the statistic distribution.


Regards,
David.


2017-08-16 14:51 GMT+02:00 Stephan Mueller <smueller@chronox.de>:
> Am Dienstag, 15. August 2017, 17:12:24 CEST schrieb Theodore Ts'o:
>
> Hi Theodore,
>
>>
>> Stephan, if you have any comments on the proposal made by David
>> Fontaine and Olivier Vivolo, I'd appreciate hearing them!
>
> I think I have some news: The magma code I used for GF(2^32) testing was not
> correct.
>
> The corrected magma code is attached (thanks to Dr. Peter Birkner, BSI, who
> helped me here).
>
> That magma code shows:
>
> - the current polynomials for Q(X) = α**3 (P(X) − 1) + 1 are irreducible but
> not primitive over GF(2^32)
>
> - the polynomials suggested in https://eprint.iacr.org/2017/726.pdf Q(X) =
> α**4 (P(X) − 1) + 1 are both, irreducible and primitive over GF(2^32)
>
> The use of GF(2^32) is important, because we apply the LFSR to a 32 bit word.
> Hence, we have 2^32 permutations the LFSR should evenly cover.
>
>
> Bottom line, I would recommend that random.c is patched to take the
> polynomials suggested in https://eprint.iacr.org/2017/726.pdf.
>
>
> If it is of any help, the attached magma code could be preserved somewhere
> useful (in random.c?)
>
> Ciao
> Stephan

Re: random.c: LFSR polynomials are not irreducible/primitive

[Stephan Mueller]

Am Dienstag, 15. August 2017, 17:12:24 CEST schrieb Theodore Ts'o:

Hi Theodore, Jeffrey,
> 
> Stephan, if you have any comments on the proposal made by David
> Fontaine and Olivier Vivolo, I'd appreciate hearing them!

(from Jefferey):

> This may be helpful, too. I use it to look up minimal weight
> irreducibles when I need them.
> http://www.hpl.hp.com/techreports/98/HPL-98-135.pdf

Thanks for the list of polynomials. There is even another list that I used for 
my LRNG: http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf.

The problem with all of these polynomials is that their taps are very close 
together and are mostly in the high parts. As there is a chance that adjacent 
event values that shall be processed with the LFSR have some form of 
correlation, having taps close together is not good, especially when they are 
in the high parts of the polynomial.

To counter that effect, either polynomials with spaced-out taps are good (as 
sought by Ted).

There is another solution that I found which was confirmed by mathematicians 
to be of no effect regarding the polynomial behavior: instead of updating 
adjacent words in the entropy pool, update words that are more spaced apart. 
The key is that the spacing must ensure that still all words are evenly 
updated. Updating more spaced-apart words will effectively counter potential 
correlations in adjacent input data when these adjacent values are XORed due 
to polynomials with close taps.

In my LRNG I use the value 67 (a prime number), since I have taps that are 
close together in the high parts. The value 67 is somewhat in the middle of 
the smallest pool size (having 128 words) and thus should have the largest 
spacing possible for the smallest pool. The spacing does not need to be a 
prime number, it is sufficient that this value is odd to ensure that all words 
are evenly accessed by the spacing.

Translating that consideration into the code found in random.c, the following 
line is affected:

                i = (i - 1) & wordmask;

This line could be changed to something like:

                i = (i - 13) & wordmask;

Why 13? Well, it is a prime number (I like primes :-) ) and it is somewhat in 
the middle of the smallest pool size of 32 words.

Though, as we have polynomials that are spread out more evenly, we do not need 
that change. Yet, if the impact on having such large polynomials (and thus 
doing that many XORs for each byte in the event value) is considered to great 
speed-wise, we could use much smaller polynomials, even when their taps are 
not spaced apart.

Ciao
Stephan