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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Mon, 14 Aug 2017 18:21:05 -0400
From:   Theodore Ts'o <tytso@....edu>
To:     Stephan Mueller <smueller@...onox.de>
Cc:     LKML <linux-kernel@...r.kernel.org>, linux-crypto@...r.kernel.org
Subject: 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