linux-kernel - Replace /dev/random input mix polynomial with Brent's xorgen?

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-next>] [day] [month] [year] [list]

Message-ID: <20131214090607.30797.qmail@science.horizon.com>
Date:	14 Dec 2013 04:06:07 -0500
From:	"George Spelvin" <linux@...izon.com>
To:	tytso@....edu
Cc:	linux@...izon.com, linux-kernel@...r.kernel.org
Subject: Replace /dev/random input mix polynomial with Brent's xorgen?

Richard Brent extended some efficient XOR-based PRNGs designed by George
Marsaglia into a family of "xorgen" generators which are efficent,
non-sparse, maximal-period polynomials of length 64, 128, 256,... 4096
bits.

(It ends there because proving period 2^n-1 requires knowing the
factorization of 2^n-1, and 2^8192-1 = (2^4096+1)*(2^2048+1)*...*(2^1+1).
The factorization of 2^4096+1 = F_12 is currently stuck on an 1133-digit
composite residue; see http://caramel.loria.fr/f12.txt)

http://maths-people.anu.edu.au/~brent/pub/pub224.html
"Some long-period random number generators using shifts and xors",

Related background papers:
http://www.jstatsoft.org/v08/i14/paper
"Xorshift RNGs"
http://maths-people.anu.edu.au/~brent/pub/pub218.html
"Note on Marsaglia's xorshift RNGs"

Anyway, the algorithm boils down to

t1 = x[i-r];	t2 = x[i-s];
t1 ^= t1 << a;	t2 ^= t2 << c;
t1 ^= t1 >> b;	t2 ^= t2 >> d;
x[i] = t1 ^ t2;

For various constants r = 2..128, s < r, and shifts a, b, c and d.
Both 32- and 64-bit versions are included.

This is both more efficient and (especually using 64-bit words) more
thorough than the current code, for sizes up to 4096 bits.  Although the
current code has tables for larger pools, everything larger than 32x128 =
4096 bits is currenty commented out and not used.

Would you be interested in a patch to revise _mix_pool_bytes()?

I'm also thinking of revising the input rotate-by-7 to use
Marsaglia's original xorshift as a whitener.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/