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 for Android: free password hash cracker in your pocket

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

Message-ID: <1801152.Iu9ZVUxv1v@tauon.chronox.de>
Date:   Wed, 16 Aug 2017 14:51:42 +0200
From:   Stephan Mueller <smueller@...onox.de>
To:     Theodore Ts'o <tytso@....edu>
Cc:     LKML <linux-kernel@...r.kernel.org>, linux-crypto@...r.kernel.org,
        david.fontaine@...gemini.com, olivier.vivolo@...nge.com
Subject: 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
Download attachment "LFSR_polynomials eprint 251.mag" of type "application/x-wine-extension-mag" (2655 bytes)