random.c: LFSR polynomials are not irreducible/primitive
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:=PolynomialRing(F); P; print "Old polynomials:"; P:=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^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^128 + x^104 + x^76 + x^51 +x^25 + x + 1; P; print "is irreducible: "; IsIrreducible(P); print "is primitive: "; IsPrimitive(P); P:=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
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
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:=PolynomialRing(F); P; print "Old polynomials:"; P:=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^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^128 + x^104 + x^76 + x^51 +x^25 + x + 1; P; print "is irreducible: "; IsIrreducible(P); print "is primitive: "; IsPrimitive(P); P:=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
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
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 LFSR_polynomials eprint 251.mag Description: application/wine-extension-mag
Re: random.c: LFSR polynomials are not irreducible/primitive
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 : > 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
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
