From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752666AbdHNWVK (ORCPT ); Mon, 14 Aug 2017 18:21:10 -0400 Received: from imap.thunk.org ([74.207.234.97]:43206 "EHLO imap.thunk.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752408AbdHNWVI (ORCPT ); Mon, 14 Aug 2017 18:21:08 -0400 Date: Mon, 14 Aug 2017 18:21:05 -0400 From: "Theodore Ts'o" To: Stephan Mueller Cc: LKML , linux-crypto@vger.kernel.org Subject: Re: random.c: LFSR polynomials are not irreducible/primitive Message-ID: <20170814222105.oyswoj3xjyd5qu3c@thunk.org> Mail-Followup-To: Theodore Ts'o , Stephan Mueller , LKML , linux-crypto@vger.kernel.org References: <10436695.bPChAg2egJ@tauon.chronox.de> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <10436695.bPChAg2egJ@tauon.chronox.de> User-Agent: NeoMutt/20170609 (1.8.3) X-SA-Exim-Connect-IP: X-SA-Exim-Mail-From: tytso@thunk.org X-SA-Exim-Scanned: No (on imap.thunk.org); SAEximRunCond expanded to false Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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