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

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

[George Spelvin]

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.

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

[Theodore Ts'o]

On Sat, Dec 14, 2013 at 04:06:07AM -0500, George Spelvin wrote:
> 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.
> 
> 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.


The mixing function doesn't have to be a good quality PRNG, since
that's not its function.  One of the things that is highly desirable,
though, is that it "smears" recently mixed in data across the entire
pool as quickly as possible.  The above algorithm is more efficient
because it only needs to touch two memory locations --- but for our
use case, we want to be able to read from multiple memory locations.

In particular, it's important that when we mix the hash back into pool
to prevent backtracking attacks, and extract from the pool again and
re-hash (see extract_entropy), it's important that when we mix in the
hash, it affects the portion of the pool that we rehash.  We could
work around this if we changed the mixing function, true, but I'm not
sure I see the benefit of making this change.

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.

Regards,

						- Ted

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

[George Spelvin]

> The mixing function doesn't have to be a good quality PRNG, since
> that's not its function.  One of the things that is highly desirable,
> though, is that it "smears" recently mixed in data across the entire
> pool as quickly as possible.  The above algorithm is more efficient
> because it only needs to touch two memory locations --- but for our
> use case, we want to be able to read from multiple memory locations.

Actually, there is one aspect in which it is desirable that it is a
good-quality PRNG, but it's something of an inversion of the usual
PRNG goal.

It doesn't actually matter how large an effect input entropy has on
the pool.  Just toggling one bit is the same as affecting many bits;
achieving avalanche is the *output* hash's job.

What's critical for the input hash is that seed additions don't cancel
each other.  That is, XORing in some new seed material doesn't hit
the same bits as older seed material.  What's key is not exactly that
additions affect lots of bits as that *different* additions affect
*different* groups of bits.  In other words, differentials rather than
single-bit avalanches,

A "good-quality PRNG" is a way of expressing this property.  Good
distribution and avoidance of correlation of outputs turns into good
distribution of *inputs* and avoidance of cancellation.

I agree that *maximal* period is not particularly important; all that's
needed is "long enough".  But it's not exactly an *undesirable* property,
either.

> In particular, it's important that when we mix the hash back into pool
> to prevent backtracking attacks, and extract from the pool again and
> re-hash (see extract_entropy), it's important that when we mix in the
> hash, it affects the portion of the pool that we rehash.  We could
> work around this if we changed the mixing function, true, but I'm not
> sure I see the benefit of making this change.

Er, yes, I wasn't planning on breaking that...
(Although I do have some code cleanup patches in that area that have
been sitting in my tree for a long time that I should submit,)

> 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.

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.

I've also ported the Skein rotate function finding program to 32 bits
(it's not as simple as changing the BITS_PER_WORD define at the top
of the file!) and have been finding 32-bit threefish rotate values.

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

[Theodore Ts'o]

On Sat, Dec 14, 2013 at 04:55:59PM -0500, George Spelvin wrote:
> 
> What's critical for the input hash is that seed additions don't cancel
> each other.  That is, XORing in some new seed material doesn't hit
> the same bits as older seed material.  What's key is not exactly that
> additions affect lots of bits as that *different* additions affect
> *different* groups of bits.  In other words, differentials rather than
> single-bit avalanches,

Agreed, but that's we have the input_rotate.  Do you have analysis or
arguments why we Richard Brent's construction would do a better job?

BTW, one other design requirement I had when desining the mixing
function was if you fix in all zero's, the result was a reversible
mixing of the bits; in other words, "dd if=/dev/zero of=/dev/random"
is guaranteed to not lose any entropy caused by self-cancellation.

> 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.

I'm not convinced we need to worry about cache timing attacks, since
they typically involve a chosen plaintext attack and a fixed key ---
and the attacker isn't going to know what we are going to be
encrypting, let alone be able to chose the plaintext.  Even if that
were not the case, see the paper, "Are AES x86 Cache Timing Attacks
Still Feasible?":

	http://cseweb.ucsd.edu/~hovav/dist/aes_cache.pdf

Regards,

						- Ted

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

[George Spelvin]

> Agreed, but that's we have the input_rotate.  Do you have analysis or
> arguments why we Richard Brent's construction would do a better job?
> 
> BTW, one other design requirement I had when desining the mixing
> function was if you fix in all zero's, the result was a reversible
> mixing of the bits; in other words, "dd if=/dev/zero of=/dev/random"
> is guaranteed to not lose any entropy caused by self-cancellation.

To address your second paragraph first: both the existing and Brent's
construction are linear feedback shift registers.  The only difference
is the polynomial.

Becuase it's a bijective function (a permutation), the input of any
fixed string to the pool is an invertible operation, and therefore cannot
lose entropy.  I agree that this property is essential, and it remains.

The difference is that currently the mxing is done using a word-wise
polynomial, followed by some ad-hoc bit mixing within the word using
the twist table.  Brent's design is more integrated and mixes all the
bits in a uniform manner.

It is, however, a relatively minor tweak, nothing fundamental.

> I'm not convinced we need to worry about cache timing attacks, since
> they typically involve a chosen plaintext attack and a fixed key ---
> and the attacker isn't going to know what we are going to be
> encrypting, let alone be able to chose the plaintext.

You're describing standard key-recovery attacks.  For /dev/random,
just knowing the *ciphertext* constitutes a successful attack.

In fact, even partial (a few bits of) knowledge about the ciphertext is
a violation of the intended security guarantee.

I haven't gone through a full analysis, but there are plenty of functions
available with fixed access patterns and timing, where the issue simply
Goes Away.  Why not use one?

> Even if that were not the case, see the paper, "Are AES x86 Cache Timing
> Attacks Still Feasible?":
>
>	http://cseweb.ucsd.edu/~hovav/dist/aes_cache.pdf

The paper's first point, that hardware support makes all this moot, is
of course true, and I agree it's difficult, but the rest is addressing
x86 running a web browser!

What about all the all the small routers, Raspberry Pis and the like
generating lots of session keys without a lot of UI code bloat?
And with simpler cache structures without hardware prefetchers and
other confounding factors.

And it seems to be making the point that a per-core L1 means that you
have to probe the L2.  But hyperthreading means that you can have
an attacking thread sharing L1 with the encryption.


The exact hash function is not critical, but it seems that there are
secure alternatives that are faster (Rijndael's key schedule is simple,
but when used as a hash, rekeying per block needs to be included), don't
need lookup tables (smaller minimum kernel!), and have fixed timing so I
don't need to even think about whether a cache timing attack is practical.

If hardware AES support changes those factors, then by all means use AES.
I just think the combination of all three factors militate against AES for
the standard software fallback.

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

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

[George Spelvin]

> 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.

Well, /dev/urandom is documented as being *deliberately* slow.  It's meant
only to produce 128 to 256 bits of seed material for CPRNG.  I don't
know if Ted considers speeding it up to be goal or an antigoal. :-)

One thing i've thought about is adding a /dev/frandom, which is seeded
once at open time and then produces a "reasonably strong" large block of
cryptographic output, very quickly.  (Key size between 128 and 192 bits.)

I understand why Ted didn't do this in the first place, but the number
of people I see doing something like "cat /dev/urandom > /dev/sdx"
to test incompressible data is remarkable.

If the additional code is small, perhaps it's worth doing.


BTW, if it helps on 32-bit platforms I can get you rotate constats for
a 32-bit version of threefish.  I haven't generated a key scheduling
constant, though.

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

[Theodore Ts'o]

On Sun, Dec 15, 2013 at 03:34:59AM -0500, George Spelvin wrote:
> > I'm not convinced we need to worry about cache timing attacks, since
> > they typically involve a chosen plaintext attack and a fixed key ---
> > and the attacker isn't going to know what we are going to be
> > encrypting, let alone be able to chose the plaintext.
> 
> You're describing standard key-recovery attacks.  For /dev/random,
> just knowing the *ciphertext* constitutes a successful attack.

Um, no.  The *ciphertext* is the output.  The attacker can get all of
the ciphertext he or she wants by reading /dev/random (although we'd
probably do some folding as we currently do so the attacker won't even
get all of the ciphertext).  What the attacker has to be able to do is
given some of the ciphertext bits, be able to predict future
ciphertext bits given some construction which uses AES as the basis.

For example, using something simple (we'd probably using something
more complicated, such as Davies-Meyer), show me a cache timing attack
where the attacker can get to see arbitrary values of:

      R_X = AES(KEY, I+X)

But where the attacker does not know KEY, *or* I, but can get to see
R_X for values 0 < X < N.  The attacker has to be able to predict
R_(N+1).

Show me a cache timing attack given this scenario, and I'll be
convinced.  I believe this is **harder** than a standard key-recovery
attack, since the attacker doesn't get to choose the plaintext.  And
if you can't choose the plaintext in order try to recover the key,
please tell me how use can use cache timings in order to predict
R_(N+1), or even some bits of R_(N+1)?  Especially given that any good
crypto algorithm is designed so that even one or two bits change in
the key or the plaintext will result in massive changes in the
ciphertext....

					- Ted

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

[Greg Price]

On Sun, Dec 15, 2013 at 05:09:10PM -0500, George Spelvin wrote:
> Well, /dev/urandom is documented as being *deliberately* slow.  It's meant
> only to produce 128 to 256 bits of seed material for CPRNG.  I don't
> know if Ted considers speeding it up to be goal or an antigoal. :-)

Hmm, I don't think I've seen that documentation.  I don't see anything
about that point in the comments of drivers/char/random.c.  The
urandom(4) man page says /dev/urandom "is designed for security, not
speed, and is poorly suited to generating large amounts of random
data."  Which is quite different from being designed for slowness!

The great thing about the state of cryptography in 2013 is that we
don't have the kind of tradeoff between speed and security that we had
in the past.  Skein and Salsa20 and some other hashes and ciphers from
within the past decade are all very fast, and they've also been
attacked hard by cryptanalysts (motivated by competitions), and held
up very well.  From my understanding of the literature, moving to
either one from our current SHA-1-based scheme would only increase the
level of confidence one should have in the security of the random driver.

I think it would be great to be able to change the documentation to
"is designed for security and is also very fast and well suited to
generating large amounts of random data".  Users are always tempted by
speed, and if we can reduce that temptation by making our CSPRNG
faster (and still secure), it will be good for security.


> BTW, if it helps on 32-bit platforms I can get you rotate constats for
> a 32-bit version of threefish.  I haven't generated a key scheduling
> constant, though.

Interesting.  So, the generic Skein implementations in the SUPERCOP
testing/benchmarking suite are about four times slower on x86_32 than
x86_64.  Which means Skein should still be about 6x faster than the
current /dev/urandom implementation, but it'd be nice to be faster
still.  I imagine the same rough comparisons will hold on other 64-bit
and 32-bit architectures, though the gap between x86_32 and x86_64 is
probably wider because of the scarcity of registers on x86_32.

I wouldn't want to compromise on security to do it, though.  My
confidence in Skein/Threefish's security comes mostly from the SHA-3
competition, where many expert cryptanalysts attacked it and didn't
get very far except in understanding why it seems to be hard to break.
To make, or even evaluate, a 32-bit variant of Threefish seems like
it'd require much deeper understanding of the design of Threefish and
its cryptanalysis than I've tried to develop.  How do you plan to
evaluate the security of your 32-bit Threefish?

Regards,
Greg

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

[George Spelvin]

On Sun, Dec 15, 2013 at 03:34:59AM -0500, George Spelvin wrote:
>> You're describing standard key-recovery attacks.  For /dev/random,
>> just knowing the *ciphertext* constitutes a successful attack.

> Um, no.  The *ciphertext* is the output.  The attacker can get all of
> the ciphertext he or she wants by reading /dev/random (although we'd
> probably do some folding as we currently do so the attacker won't even
> get all of the ciphertext).  What the attacker has to be able to do is
> given some of the ciphertext bits, be able to predict future
> ciphertext bits given some construction which uses AES as the basis.

The attack I was thinking of was figuring out (without breaking root and
using ptrace) what some *other* process on the same machine is reading
from /dev/random.

In other words, reading someone else's output.

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

[Theodore Ts'o]

On Sun, Dec 15, 2013 at 11:22:47PM -0500, George Spelvin wrote:
> 
> > Um, no.  The *ciphertext* is the output.  The attacker can get all of
> > the ciphertext he or she wants by reading /dev/random (although we'd
> > probably do some folding as we currently do so the attacker won't even
> > get all of the ciphertext).  What the attacker has to be able to do is
> > given some of the ciphertext bits, be able to predict future
> > ciphertext bits given some construction which uses AES as the basis.
> 
> The attack I was thinking of was figuring out (without breaking root and
> using ptrace) what some *other* process on the same machine is reading
> from /dev/random.
> 
> In other words, reading someone else's output.

I understand that; and as I wrote in my last e-mail, I think that is a
substantially harder attack than the currently published cache timing
attacks, which are known plaintext attacks --- that is the attacker
doesn't know the key, but can choose the plaintext, and view the
resulting ciphertext.

In this case, the attacker doen't know the key *and* the plaintext; it
can view its own attempt to read from /dev/random, but from that, it
needs to be able to figure out the the key and the plaintext (i.e.,
the entropy pool) in order to be able to predict someone else's output
of /dev/random.

If you think this is easier than the currently published cache timing
attacks, please provide details why you think this is the case,
preferably in the form of a demonstration....

						- Ted

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

[Theodore Ts'o]

On Mon, Dec 16, 2013 at 01:43:59AM -0500, Theodore Ts'o wrote:
> I understand that; and as I wrote in my last e-mail, I think that is a
> substantially harder attack than the currently published cache timing
> attacks, which are known plaintext attacks --- that is the attacker
> doesn't know the key, but can choose the plaintext, and view the
> resulting ciphertext.

s/known plaintext attacks/chosen plaintext attacks/

> 
> In this case, the attacker doen't know the key *and* the plaintext; it
> can view its own attempt to read from /dev/random, but from that, it
> needs to be able to figure out the the key and the plaintext (i.e.,
> the entropy pool) in order to be able to predict someone else's output
> of /dev/random.
> 
> If you think this is easier than the currently published cache timing
> attacks, please provide details why you think this is the case,
> preferably in the form of a demonstration....
> 
> 						- Ted
> 

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

[George Spelvin]

>> Well, /dev/urandom is documented as being *deliberately* slow.

> Hmm, I don't think I've seen that documentation.  I don't see anything
> about that point in the comments of drivers/char/random.c.  The
> urandom(4) man page says /dev/urandom "is designed for security, not
> speed, and is poorly suited to generating large amounts of random
> data."  Which is quite different from being designed for slowness!

I guess the comment has evaporated.  I know it used to be there,
either in the source or old mailing list discussion.  However,
it's almost 20 years old now and I'm having a hard time tracking
down a source.

The comment wasn't, as the trailing :-) indicated, entirely serious.
There's no actual *problem* with making it faster, but I remember Ted
being very clear that he actually wanted to *discourage* people from
reading lots of data from it.

That's what I was alluding to.

> The great thing about the state of cryptography in 2013 is that we
> don't have the kind of tradeoff between speed and security that we had
> in the past.

Absolutely.  No argument.

>> BTW, if it helps on 32-bit platforms I can get you rotate constats for
>> a 32-bit version of threefish.  I haven't generated a key scheduling
>> constant, though.

> I wouldn't want to compromise on security to do it, though.  My
> confidence in Skein/Threefish's security comes mostly from the SHA-3
> competition, where many expert cryptanalysts attacked it and didn't
> get very far except in understanding why it seems to be hard to break.
> To make, or even evaluate, a 32-bit variant of Threefish seems like
> it'd require much deeper understanding of the design of Threefish and
> its cryptanalysis than I've tried to develop.  How do you plan to
> evaluate the security of your 32-bit Threefish?

The designers posted the search program they used to generate the rotation
constants, as part of proving there are no back doors.  They say in the
paper that a 32-bit version is possible, although they didn't generate
rotation constants.

Porting the program to 32 bits is a bit of a pain, as 64-bit assumptions
crept in all over, but it's not that hard.

As was pointed out in the competition, an attack on *any* fairly-random
set of threefish rotation constants would be alarming.  The set that was
chosen uses general principles for making a good choice, but if there
is some non-obvious criterion that can create a significant weakness,
that would be a major problem for the entire ARX structure.

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

[George Spelvin]

> I understand that; and as I wrote in my last e-mail, I think that is a
> substantially harder attack than the currently published cache timing
> attacks, which are chosen plaintext attacks --- that is the attacker
> doesn't know the key, but can choose the plaintext, and view the
> resulting ciphertext.

Okay, sorry for the misunderstanding.  I *thought* we were talking past
each other.

First of all, you might want to look at this paper:
http://www.ieee-security.org/TC/SP2011/PAPERS/2011/paper031.pdf
"Cache Games -- Bringing Access-Based Cache Attacks on AES to Practice"

It describes a practical implementation of a timing-based key-recovery
attack *without any access to plain- or ciphertext at all* after watching
~100 block encryptions in OpenSSL.

Key recovery is the target usually studied, so recovering the text
(in the absence of the key or other text) is not as well documented,
but it certainly shouldn't be any harder.

The major complicating factor is that most attacks assume a constant key,
while hashing uses a varying key per encryption.  But there are strong
dependencies (the output of one encryption is the input to the next)
that can perhaps be handled with improved analysis.

No, I don't have example code, but I hope you can see how I think
concerns are realistic.  (And remember: attacks only ever get better.)

(I should also mention that the paper above exploits the Linux scheduler
to collect high-resolution timing information, so could be greatly
hampered by disabling preemption in /dev/random.  But there is probably
an equivalent attack via hyperthreading.)


As I've said before, the point I want to stress is not even that the
attack is necessarily practical, but it's a PITA to prove that it's *not*,
and the SHA-3 competition has given us several excellent cryptographic
cores explicitly designed to avoid the issue entirely.

If the alternatives to AES had serious disadvantages, I'd be getting busy
with a detailed comparison.  But is that even necessary?