Re: Replace /dev/random input mix polynomial with Brent's xorgen?

[Greg Price]

On Sat, Dec 14, 2013 at 02:23:07PM -0500, Theodore Ts'o wrote:
> I'm much more inclined to think about changing how we generate random
> numbers from the output pool by switching from using SHA to AES in
> some one-way random function mode (i.e., such as the Davies-Meyer
> construction), since that is where we are spending most of our CPU
> time in the random driver at the moment.

I have a draft of a patch series to do something like this.  There's a
good bit of refactoring to make the output pools have a different type
from input_pool.  Then a new cryptographic engine can be swapped in
for the output pools, in place of the current SHA-1-based algorithm.

The refactoring should be basically the same for any change of
algorithm, if the new algorithm is to be used for the output pools and
not the input pool.  Which I think is the right approach -- generally
the state-of-the-art PRNG algorithms aren't optimized for taking input
quickly, as we want to do in an interrupt, so we'll want the current
mix_pool_bytes or something similar for the input pool.  Perhaps the
Brent-Marsaglia algorithms George mentioned, which I haven't yet read
about in detail.

A side benefit of the reseeding rework I sent yesterday is that it
lays the groundwork for that refactoring, by directing all routine
input through the input pool.


On Sat, Dec 14, 2013 at 04:55:59PM -0500, George Spelvin wrote:
> The SHA-3 competition has given us lots of random permutations and
> random functions.  Keccak, Salsa20/ChaCha, Skein/Threefish and SipHash
> are all interesting looking.  AES/Rijndael is actually less so, unless
> you're planning on using hardware support, because of cache timing
> attacks on the lookup tables it needs for software implementation.

My draft patch series uses Skein/Threefish.  The authors conveniently
specified a way to use it as a PRNG, and it's very fast without
special hardware support (consequently, for all kinds of hardware.)
On my laptop, reading from /dev/urandom becomes about 25 times faster
for large reads, and about 40% faster for small reads where the
syscall overhead is more important.

ChaCha or Salsa20 would be a good choice too.  The author didn't
specify a PRNG mode, but they can be plugged into standard
constructions, and they're also very fast.


Regards,
Greg
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/