Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1385516 > unrolled thread

random(4) changes

Back to article view | Back to linux.kernel

Contents

  random(4) changes Sandy Harris <sandyinchina@gmail.com> - 2016-04-23 00:30 +0200
    Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-23 10:00 +0200
    Re: random(4) changes Theodore Ts'o <tytso@mit.edu> - 2016-04-24 04:10 +0200
      Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-24 10:10 +0200
        Re: random(4) changes Theodore Ts'o <tytso@mit.edu> - 2016-04-26 05:10 +0200
          Re: random(4) changes Herbert Xu <herbert@gondor.apana.org.au> - 2016-04-26 13:10 +0200
            Re: random(4) changes Andi Kleen <andi@firstfloor.org> - 2016-04-26 22:50 +0200
              Re: random(4) changes Herbert Xu <herbert@gondor.apana.org.au> - 2016-04-27 06:30 +0200
          Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-26 20:30 +0200
          Re: random(4) changes Pavel Machek <pavel@ucw.cz> - 2016-04-26 20:50 +0200
            Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-26 21:00 +0200
              Re: random(4) changes Pavel Machek <pavel@ucw.cz> - 2016-04-26 21:50 +0200
    Re: random(4) changes Andi Kleen <andi@firstfloor.org> - 2016-04-25 18:10 +0200
      Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-25 19:30 +0200
        Re: random(4) changes Andi Kleen <andi@firstfloor.org> - 2016-04-25 19:40 +0200
          Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-25 20:00 +0200
            Re: random(4) changes Andi Kleen <andi@firstfloor.org> - 2016-04-25 21:40 +0200
              Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-26 14:10 +0200
              Re: random(4) changes Stephan Mueller <smueller@chronox.de> - 2016-04-27 19:50 +0200
      Re: random(4) changes Theodore Ts'o <tytso@mit.edu> - 2016-04-26 03:10 +0200
      Re: random(4) changes Sandy Harris <sandyinchina@gmail.com> - 2016-04-26 14:50 +0200

Page 1 of 2  [1] 2  Next page →

#1385516 — random(4) changes

Stephan has recently proposed some extensive changes to this driver,
and I proposed a quite different set earlier. My set can be found at:
https://github.com/sandy-harris

This post tries to find the bits of both proposals that seem clearly
worth doing and entail neither large implementation problems nor large
risk of throwing out any babies with the bathwater.

Unfortunately, nothing here deals with the elephant in the room -- the
distinctly hard problem of making sure the driver is initialised well
enough & early enough. That needs a separate post, probably a separate
thread. I do not find Stepan's solution to this problem plausible and
my stuff does not claim to deal with it, though it includes some
things that might help.

I really like Stephan's idea of simplifying the interrupt handling,
replacing the multiple entropy-gathering calls in the current driver
with one routine called for all interrupts. See section 1.2 of his
doc. That seems to me a much cleaner design, easier both to analyse
and to optimise as a fast interrupt handler. I also find Stephan's
arguments that this will work better on modern  systems -- VMs,
machines with SSDs, etc. -- quite plausible.

Note, though, that I am only talking about the actual interrupt
handling, not the rest of Stephan's input handling code: the parity
calculation and XORing the resulting single bit into the entropy pool.
I'd be happier, at least initially, with a patch that only implemented
a single-source interrupt handler that gave 32 or 64 bits to existing
input-handling code.

Stephan: would you want to provide such a patch?
Ted: would you be inclined to accept it?

I also quite like Stephan's idea of replacing the two output pools
with a NIST-approved DBRG, mainly because this would probably make
getting various certifications easier. I also like the idea of using
crypto lib code for that since it makes both testing & maintenance
easier. This strikes me, though, as a do-when-convenient sort of
cleanup task, not at all urgent unless there are specific
certifications we need soon.

As for my proposals, I of course think they are full of good ideas,
but there's only one I think is really important.

In the current driver -- and I think in Stephan's, though I have not
looked at his code in any detail, only his paper -- heavy use of
/dev/urandom or the kernel get_random_bytes() call can deplete the
entropy available to /dev/random. That can be a serious problem in
some circumstances, but I think I have a fix.

You have an input pool (I) plus a blocking pool (B) & a non-blocking
pool (NB). The problem is what to do when NB must produce a lot of
output but you do not want to deplete I too much. B & NB might be
replaced by DBRGs and the problem would not change.

B must be reseeded before very /dev/random output, NB after some
number of output blocks. I used #define SAFE_OUT 503 but some other
number might be better depending how NB is implemented & how
paranoid/conservative one feels.

B can only produce one full-entropy output, suitable for /dev/random,
per reseed but B and NB are basically the same design so B can also
produce SAFE_OUT reasonably good random numbers per reseed. Use those
to reseed NB.and you reduce the load on I for reseeding NB from
SAFE_OUT (use I every time NB is reseeded) to SAFE_OUT*SAFE_OUT (use I
only to reseed B).

This does need analysis by cryptographers, but at a minimum it is
basically plausible and, even with some fairly small value for
SAFE_OUT, it greatly alleviates the problem.

[toc] | [next] | [standalone]

#1385589

Am Freitag, 22. April 2016, 18:27:48 schrieb Sandy Harris:

Hi Sandy,

> Stephan has recently proposed some extensive changes to this driver,
> and I proposed a quite different set earlier. My set can be found at:
> https://github.com/sandy-harris
> 
> This post tries to find the bits of both proposals that seem clearly
> worth doing and entail neither large implementation problems nor large
> risk of throwing out any babies with the bathwater.
> 
> Unfortunately, nothing here deals with the elephant in the room -- the
> distinctly hard problem of making sure the driver is initialised well
> enough & early enough. That needs a separate post, probably a separate
> thread. I do not find Stepan's solution to this problem plausible and
> my stuff does not claim to deal with it, though it includes some
> things that might help.

Interesting, I thought I solved the issue. But if you think it is not solved, 
let us cover that in a separate thread.
> 
> I really like Stephan's idea of simplifying the interrupt handling,
> replacing the multiple entropy-gathering calls in the current driver
> with one routine called for all interrupts. See section 1.2 of his
> doc. That seems to me a much cleaner design, easier both to analyse
> and to optimise as a fast interrupt handler. I also find Stephan's
> arguments that this will work better on modern  systems -- VMs,
> machines with SSDs, etc. -- quite plausible.
> 
> Note, though, that I am only talking about the actual interrupt
> handling, not the rest of Stephan's input handling code: the parity
> calculation and XORing the resulting single bit into the entropy pool.
> I'd be happier, at least initially, with a patch that only implemented
> a single-source interrupt handler that gave 32 or 64 bits to existing
> input-handling code.
> 
> Stephan: would you want to provide such a patch?

Sure, if this is the will if the council, I will see it done.

> Ted: would you be inclined to accept it?
> 
> I also quite like Stephan's idea of replacing the two output pools
> with a NIST-approved DBRG, mainly because this would probably make
> getting various certifications easier. I also like the idea of using
> crypto lib code for that since it makes both testing & maintenance
> easier. This strikes me, though, as a do-when-convenient sort of
> cleanup task, not at all urgent unless there are specific
> certifications we need soon.
> 
> As for my proposals, I of course think they are full of good ideas,
> but there's only one I think is really important.
> 
> In the current driver -- and I think in Stephan's, though I have not
> looked at his code in any detail, only his paper -- heavy use of
> /dev/urandom or the kernel get_random_bytes() call can deplete the
> entropy available to /dev/random. That can be a serious problem in
> some circumstances, but I think I have a fix.

To quote from my paper:

"""
When the secondary DRBG requests a reseeding from the primary DRBG and
the primary DRBG pulls from the entropy pool, an emergency entropy level
of 512 bits of entropy is left in the entropy pool. This emergency entropy is
provided to serve /dev/random even while /dev/urandom is stressed.
"""

Note, the 512 bits are chosen arbitrarily and can be set at compile time to 
any other value with LRNG_EMERG_POOLSIZE. If needed, we can even make this 
runtime-configurable.
> 
> You have an input pool (I) plus a blocking pool (B) & a non-blocking
> pool (NB). The problem is what to do when NB must produce a lot of
> output but you do not want to deplete I too much. B & NB might be
> replaced by DBRGs and the problem would not change.
> 
> B must be reseeded before very /dev/random output, NB after some
> number of output blocks. I used #define SAFE_OUT 503 but some other
> number might be better depending how NB is implemented & how
> paranoid/conservative one feels.
> 
> B can only produce one full-entropy output, suitable for /dev/random,
> per reseed but B and NB are basically the same design so B can also
> produce SAFE_OUT reasonably good random numbers per reseed. Use those
> to reseed NB.and you reduce the load on I for reseeding NB from
> SAFE_OUT (use I every time NB is reseeded) to SAFE_OUT*SAFE_OUT (use I
> only to reseed B).
> 
> This does need analysis by cryptographers, but at a minimum it is
> basically plausible and, even with some fairly small value for
> SAFE_OUT, it greatly alleviates the problem.


Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1385761

On Fri, Apr 22, 2016 at 06:27:48PM -0400, Sandy Harris wrote:
> 
> I really like Stephan's idea of simplifying the interrupt handling,
> replacing the multiple entropy-gathering calls in the current driver
> with one routine called for all interrupts. See section 1.2 of his
> doc. That seems to me a much cleaner design, easier both to analyse
> and to optimise as a fast interrupt handler.

The current /dev/random driver *already* has a fast interrupt handler,
and it was designed specifically to be very fast and very lightweight.

It's a fair argument that getting rid of add_disk_randomness()
probably makes sense.  However, add_input_randomness() is useful
because it is also mixing in the HID input (e.g., the characters typed
or the mouse movements), and that is extremely valuable and I wouldn't
want to get rid of this.

> In the current driver -- and I think in Stephan's, though I have not
> looked at his code in any detail, only his paper -- heavy use of
> /dev/urandom or the kernel get_random_bytes() call can deplete the
> entropy available to /dev/random. That can be a serious problem in
> some circumstances, but I think I have a fix.

So /dev/urandom, or preferentially, the getrandom(2) system call,
which will block until the entropy pool is initialized, is designed to
be a CRNG.  We use the entropy accounting for the urandom pool as a
hueristic to know how aggressively to pull the random pool and/or
things like hwrandom (since pulling entropy from the TPM does have
costs, for example power utilization for battery-powered devices).

We already throttle back how much we pull from the input pool if it is
being used heavily, specifically to avoid this problem.

Cheers,

					- Ted

[toc] | [prev] | [next] | [standalone]

#1385783

Am Samstag, 23. April 2016, 22:03:23 schrieb Theodore Ts'o:

Hi Theodore,

> On Fri, Apr 22, 2016 at 06:27:48PM -0400, Sandy Harris wrote:
> > I really like Stephan's idea of simplifying the interrupt handling,
> > replacing the multiple entropy-gathering calls in the current driver
> > with one routine called for all interrupts. See section 1.2 of his
> > doc. That seems to me a much cleaner design, easier both to analyse
> > and to optimise as a fast interrupt handler.
> 
> The current /dev/random driver *already* has a fast interrupt handler,
> and it was designed specifically to be very fast and very lightweight.

I agree here. The only challenge with the current implementation is the time 
the fast_pool is to be mixed into an entropy pool. This requires a lock and 
quite some code afterwards.

I tried hard to avoid such additional code paths in my LRNG.
> 
> It's a fair argument that getting rid of add_disk_randomness()
> probably makes sense.  However, add_input_randomness() is useful
> because it is also mixing in the HID input (e.g., the characters typed
> or the mouse movements), and that is extremely valuable and I wouldn't
> want to get rid of this.

In addition to the request to remove the Jitter RNG, I also have added support 
for the add_input_randomness function into the LRNG. I will release the code 
shortly.

When dropping the add_disk_randomness function in the legacy /dev/random, I 
would assume that without changes to add_input_randomness and 
add_interrupt_randomness, we become even more entropy-starved. The entropy 
heuristic for add_interrupt_randomness cannot be re-valued to a higher level 
because the time stamp for the HID is still processed as part of 
add_input_randomness -- i.e. there is still a high correlation between the 
processed values of add_interrupt_randomness and add_input_randomness. Thus, 
all events received for block devices are now valued at most with 1/64th bits 
of entropy when dropping add_disk_randomness (which partially used to be 
valued higher).

Thus, I tried with the LRNG to implement add_input_randomness as follows: it 
only picks up the key numbers or mouse coordinates but no timestamp. Those are 
mixed into the entropy pool without crediting any entropy. The reason for not 
crediting any entropy is that an unprivileged user knows the keys he pressed. 
Thus the user is an observer and a potential attacker that has full knowledge 
of an input value into the entropy pool. As each HID event is also processed 
as an interrupt, the interrupt processing of the LRNG will credit close to one 
bit of entropy for each HID event due to the interrupt timing nonetheless.
> 
> > In the current driver -- and I think in Stephan's, though I have not
> > looked at his code in any detail, only his paper -- heavy use of
> > /dev/urandom or the kernel get_random_bytes() call can deplete the
> > entropy available to /dev/random. That can be a serious problem in
> > some circumstances, but I think I have a fix.
> 
> So /dev/urandom, or preferentially, the getrandom(2) system call,
> which will block until the entropy pool is initialized, is designed to
> be a CRNG.  We use the entropy accounting for the urandom pool as a
> hueristic to know how aggressively to pull the random pool and/or
> things like hwrandom (since pulling entropy from the TPM does have
> costs, for example power utilization for battery-powered devices).
> 
> We already throttle back how much we pull from the input pool if it is
> being used heavily, specifically to avoid this problem.

Agreed. And this exact behavior I tried to replicate into the LRNG (the 
blocking of getrandom and the emergency entropy for /dev/random). The 
processing leaves an "emergency" level of entropy in the pool that is 
inaccessible to /dev/urandom. Furthermore, when a call to /dev/random drains 
the entropy pool completely, the emergency entropy is replenished first before 
/dev/urandom gets new entropy from the entropy pool.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1387110

On Sun, Apr 24, 2016 at 10:03:45AM +0200, Stephan Mueller wrote:
> 
> I agree here. The only challenge with the current implementation is the time 
> the fast_pool is to be mixed into an entropy pool. This requires a lock and 
> quite some code afterwards.

This only happens no more than once every 64 interrupts, and we don't
actually block waiting for the lock (we use a spin_trylock, and we
skip mixing to the next interrupt if it is locked).  I've done a lot
of careful benchmarking of the cycles used.

> When dropping the add_disk_randomness function in the legacy /dev/random, I 
> would assume that without changes to add_input_randomness and 
> add_interrupt_randomness, we become even more entropy-starved.

Sure, but your system isn't doing anything magical here.  The main
difference is that you assume you can get almost a full bit of entropy
out of each interrupt timing, where I'm much more conservative and
assume we can only get 1/64th of a bit out of each interrupt timing.
(e.g., that each interrupt event may have some complex correlation
that is more sophisticated than what a "stuck bit" detector might be
able to detect.)

Part of the reason why I've been very conservative here is because not
all ARM CPU's provide access to a high speed counter.  Using the IP
and other CPU registers as a stop-gap is not great, but it is better
than just using jiffies (which you seem to assume the /dev/random
driver is doing; this is not true, and this is one of the ways in
which the current system is better than your proposed LRNG, and why
I'm not really fond of major "rip and replace" patches --- it's likely
such a approach will end up making things worse for some systems, and
I don't true the ARM SOC or embedded/mobile vendors to chose the
kernel configuration sanely in terms of "should I use random number
generator 'A' or 'B' for my system?).


The other big difference is you aren't allowing anyone to extract from
the primary entropy pool (/dev/random) until it is has a chance to
fully initialize the /dev/urandom pool, which is a good thing to do,
and something that's not hard to do without doing a complete rip and
replace of the RNG.  So I'll look at adding that to the /dev/random driver.

Yet another difference which I've noticed as I've been going over the
patches is that that since it relies on CRYPTO_DRBG, it drags in a
fairly large portion of the crypto subsystem, and requires it to be
compiled into the kernel (instead of being loaded as needed as a
module).  So the people who are worrying about keeping the kernel on a
diet aren't going to be particularly happy about this.

I've thought about using a CRNG for the secondary pool, which would be
a lot smaller and faster as far as random number extraction.  But the
concern I have is that I don't want to drag in the whole generalized
crypto subsystem just for /dev/random.  If we make it too heavyweight,
then there will be pressure to make /dev/random optional, which would
mean that application programs can't depend on it and some device
manufacturers might be tempted to make it disappear for their kernels.

So my preference if we want to go down this path is to use a CRNG
based on something like Twofish, which is modern, still unbroken, and
is designed to be implemented efficiently in software in a small
amount (both in terms of text and data segments).  This would then
make it realtively efficient to use per-CPU CRNG's, in order to to
satisfy Andi Kleen's concern about making /dev/urandom efficient for
crazy programs that are trying to extract a huge amounts of data out
of /dev/urandom on a big multi-socket system.  And I would do this
with a hard-wired system that avoids dragging in the crypto system to
to keep the Linux tinification folks happy.

Cheers,

					- Ted

[toc] | [prev] | [next] | [standalone]

#1387378

Theodore Ts'o <tytso@mit.edu> wrote:
>
> Yet another difference which I've noticed as I've been going over the
> patches is that that since it relies on CRYPTO_DRBG, it drags in a
> fairly large portion of the crypto subsystem, and requires it to be
> compiled into the kernel (instead of being loaded as needed as a
> module).  So the people who are worrying about keeping the kernel on a
> diet aren't going to be particularly happy about this.

As the IPv4 stack now selects CRYPTO_AES, the crypto system will
be pulled into your kernel anyway unless you can live without IPv4.

Cheers,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[toc] | [prev] | [next] | [standalone]

#1388070

On Tue, Apr 26, 2016 at 07:04:15PM +0800, Herbert Xu wrote:
> Theodore Ts'o <tytso@mit.edu> wrote:
> >
> > Yet another difference which I've noticed as I've been going over the
> > patches is that that since it relies on CRYPTO_DRBG, it drags in a
> > fairly large portion of the crypto subsystem, and requires it to be
> > compiled into the kernel (instead of being loaded as needed as a
> > module).  So the people who are worrying about keeping the kernel on a
> > diet aren't going to be particularly happy about this.
> 
> As the IPv4 stack now selects CRYPTO_AES, the crypto system will
> be pulled into your kernel anyway unless you can live without IPv4.

I posted patches to fix this. At some point it definitely has to be.

-Andi

[toc] | [prev] | [next] | [standalone]

#1388659

On Tue, Apr 26, 2016 at 01:47:09PM -0700, Andi Kleen wrote:
>
> I posted patches to fix this. At some point it definitely has to be.

Can you point me to the patch submission?

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

[toc] | [prev] | [next] | [standalone]

#1387812

Am Montag, 25. April 2016, 23:07:35 schrieb Theodore Ts'o:

Hi Theodore,
> 
> > When dropping the add_disk_randomness function in the legacy /dev/random,
> > I
> > would assume that without changes to add_input_randomness and
> > add_interrupt_randomness, we become even more entropy-starved.
> 
> Sure, but your system isn't doing anything magical here.  The main
> difference is that you assume you can get almost a full bit of entropy
> out of each interrupt timing, where I'm much more conservative and
> assume we can only get 1/64th of a bit out of each interrupt timing.
> (e.g., that each interrupt event may have some complex correlation
> that is more sophisticated than what a "stuck bit" detector might be
> able to detect.)

The stuck test is only for identifying small patterns.

With the measurements I have done on a number of different systems trying to 
find a worst case attack and applying it, I still found that the timing of 
interrupt events show variations of 11 bits and more. It is good to be 
conservative for entropy estimations. But being too conservative is like 
killing yourself just because you are afraid of dying.

I tried to find an entropy estimate that is reasonable. And by moving from 11 
bits to 0.9 bits, I thought I am good here.

However, if a more conservative approach is requested, the LRNG only requires 
the change of LRNG_IRQ_ENTROPY_BYTES.

> 
> Part of the reason why I've been very conservative here is because not
> all ARM CPU's provide access to a high speed counter.  Using the IP
> and other CPU registers as a stop-gap is not great, but it is better
> than just using jiffies (which you seem to assume the /dev/random
> driver is doing; this is not true, and this is one of the ways in
> which the current system is better than your proposed LRNG, and why

I have neither said that the legacy /dev/random rests only on jiffies in 
absence of a high-res timer nor did I try to imply that. What I am saying is 
that even the combination of Jiffies and registers is not great either as they 
seem to be predictable with a reasonable degree of precision by an external 
entity.

In fact, Pavel's comments made me add exactly this kind of logic to cover 
systems without high-res timers. I will release the new code shortly. But they 
are only invoked if a high-res timer is not available.

> I'm not really fond of major "rip and replace" patches --- it's likely
> such a approach will end up making things worse for some systems, and
> I don't true the ARM SOC or embedded/mobile vendors to chose the
> kernel configuration sanely in terms of "should I use random number
> generator 'A' or 'B' for my system?).

I am sorry, but I cannot understand this statement: I am neither ripping 
things out, nor do I favor an outright replacement. I am offering a new option 
which may even be marked experimental for the time being.

I am asking to consider a new approach to collect entropy. And I am offering a 
patch that currently is intended for research and evaluation. It is a full API 
and ABI compatible version of the legacy /dev/random which allows such 
research and evaluation.

I do not see any way to use small steps in changing the legacy /dev/random 
with the challenges it faces. Besides, even small changes to the legacy 
/dev/random are rarely accepted, let alone the big items covering its 
challenges.

[..]
> 
> Yet another difference which I've noticed as I've been going over the
> patches is that that since it relies on CRYPTO_DRBG, it drags in a
> fairly large portion of the crypto subsystem, and requires it to be
> compiled into the kernel (instead of being loaded as needed as a
> module).  So the people who are worrying about keeping the kernel on a
> diet aren't going to be particularly happy about this.

If this is really a concern to people, I think there is no blocker to us here: 
I deliberately implemented the DRBG in the kernel crypto API such that it acts 
as a mere "block chaining mode" which is independent from the API it is called 
with and independent from the API of the underlying cipher suites. For a proof 
of this claim, you may want to compare the code from the crypto/drbg.c with 
the random/random-drbg.c code in upstream libgcrypt -- they are identical when 
it comes to the DRBG logic (I implemented the DRBG code on libgcrypt at the 
beginning with the goal to provide such cryptolib-agnostic implementation so 
that I can easily apply it to the kernel crypto API).

The LRNG uses only the DRBG core without using the kernel crypto API itself. 
Thus, it is not too hard to extract the DRBG core into a library code like 
lib/sha1.c and combine both if one does not want to compile the kernel crypto 
API.

> 
> I've thought about using a CRNG for the secondary pool, which would be
> a lot smaller and faster as far as random number extraction.  But the
> concern I have is that I don't want to drag in the whole generalized
> crypto subsystem just for /dev/random.  If we make it too heavyweight,
> then there will be pressure to make /dev/random optional, which would
> mean that application programs can't depend on it and some device
> manufacturers might be tempted to make it disappear for their kernels.
> 
> So my preference if we want to go down this path is to use a CRNG
> based on something like Twofish, which is modern, still unbroken, and
> is designed to be implemented efficiently in software in a small
> amount (both in terms of text and data segments).  This would then
> make it realtively efficient to use per-CPU CRNG's, in order to to
> satisfy Andi Kleen's concern about making /dev/urandom efficient for
> crazy programs that are trying to extract a huge amounts of data out
> of /dev/urandom on a big multi-socket system.  And I would do this
> with a hard-wired system that avoids dragging in the crypto system to
> to keep the Linux tinification folks happy.

I think with my answer above it is clear that the LRNG does not rely on having 
the kernel crypto API -- it is merely a convenience as of now. But we should 
not block ourselves from using it when it is there. It provides huge 
advantages.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1387886

Hi1

> > When dropping the add_disk_randomness function in the legacy /dev/random, I 
> > would assume that without changes to add_input_randomness and 
> > add_interrupt_randomness, we become even more entropy-starved.
> 
> Sure, but your system isn't doing anything magical here.  The main
> difference is that you assume you can get almost a full bit of entropy
> out of each interrupt timing, where I'm much more conservative and
> assume we can only get 1/64th of a bit out of each interrupt timing.

Maybe 1/64th of a bit is a bit too conservative? I guess we really
have more than one bit of entropy on any system with timestamp
counter....

Making it 1/2 of bit (or something) should be very easy way to improve
entropy early during boot...

Best regards,
									Pavel
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

[toc] | [prev] | [next] | [standalone]

#1387906

Am Dienstag, 26. April 2016, 20:44:39 schrieb Pavel Machek:

Hi Pavel,

> Hi1
> 
> > > When dropping the add_disk_randomness function in the legacy
> > > /dev/random, I
> > > would assume that without changes to add_input_randomness and
> > > add_interrupt_randomness, we become even more entropy-starved.
> > 
> > Sure, but your system isn't doing anything magical here.  The main
> > difference is that you assume you can get almost a full bit of entropy
> > out of each interrupt timing, where I'm much more conservative and
> > assume we can only get 1/64th of a bit out of each interrupt timing.
> 
> Maybe 1/64th of a bit is a bit too conservative? I guess we really
> have more than one bit of entropy on any system with timestamp
> counter....
> 
> Making it 1/2 of bit (or something) should be very easy way to improve
> entropy early during boot...

I can easily settle on 1/2 bit here. The LRNG currently uses 0.9 bits which 
are based on measurements plus a safety margin. But I see no issue to even 
lower it further to, say, 1/2.

But simply enlarging the heuristic for the interrupt processing of the legacy 
/dev/random is a challenge IMHO. The key issue is the following:

When the legacy /dev/random receives one [block|HID] event, the following 
happens:

- add_[disk|input]_randomness assigns a time stamp containing majority of the 
entropy plus jiffies plus the event value and mix that triplet into the input 
pool

- for the very same event add_interrupt_randomness is also triggered and 
records the time stamp (plus jiffies, the instruction pointer and one 
register). Again, the majority of the entropy comes from the time stamp.

Both invocations are applied to the same event where the majority of entropy 
for each invocation is derived from a time stamp. It is clear that the 
invocation of both are highly correlated. So is the time stamp both 
invocations obtain. Thus, the time stamp of either one must not be credited 
with high entropy content.

If the credited entropy for an interrupt raises, the credited entropy for 
add_[disk|block]_randomness must be decreased. That is the core issue why I 
came up with a separate way of recording these events.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1387970

Hi!

> > > > When dropping the add_disk_randomness function in the legacy
> > > > /dev/random, I
> > > > would assume that without changes to add_input_randomness and
> > > > add_interrupt_randomness, we become even more entropy-starved.
> > > 
> > > Sure, but your system isn't doing anything magical here.  The main
> > > difference is that you assume you can get almost a full bit of entropy
> > > out of each interrupt timing, where I'm much more conservative and
> > > assume we can only get 1/64th of a bit out of each interrupt timing.
> > 
> > Maybe 1/64th of a bit is a bit too conservative? I guess we really
> > have more than one bit of entropy on any system with timestamp
> > counter....
> > 
> > Making it 1/2 of bit (or something) should be very easy way to improve
> > entropy early during boot...
> 
> I can easily settle on 1/2 bit here. The LRNG currently uses 0.9 bits which 
> are based on measurements plus a safety margin. But I see no issue to even 
> lower it further to, say, 1/2.

No, you don't need to change anything. But maybe mainline rng should
change.

									Pavel
									
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

[toc] | [prev] | [next] | [standalone]

#1386618

Sandy Harris <sandyinchina@gmail.com> writes:

There is also the third problem of horrible scalability of /dev/random
output on larger systems, for which patches are getting ignored.

https://lkml.org/lkml/2016/2/10/716

Ignoring problems does not make them go away.

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only

[toc] | [prev] | [next] | [standalone]

#1386689

Am Montag, 25. April 2016, 09:06:03 schrieb Andi Kleen:

Hi Andi,

> Sandy Harris <sandyinchina@gmail.com> writes:
> 
> There is also the third problem of horrible scalability of /dev/random
> output on larger systems, for which patches are getting ignored.
> 
> https://lkml.org/lkml/2016/2/10/716
> 
> Ignoring problems does not make them go away.

I have seen your patches, but I am not fully sure I understand the root cause. 
is the noise source handling the issue or the random number generation the 
issue?

If it is the latter, can you explain where the scalability issue comes in?
> 
> -Andi


Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1386692

On Mon, Apr 25, 2016 at 07:25:55PM +0200, Stephan Mueller wrote:
> Am Montag, 25. April 2016, 09:06:03 schrieb Andi Kleen:
> 
> Hi Andi,
> 
> > Sandy Harris <sandyinchina@gmail.com> writes:
> > 
> > There is also the third problem of horrible scalability of /dev/random
> > output on larger systems, for which patches are getting ignored.
> > 
> > https://lkml.org/lkml/2016/2/10/716
> > 
> > Ignoring problems does not make them go away.
> 
> I have seen your patches, but I am not fully sure I understand the root cause. 
> is the noise source handling the issue or the random number generation the 
> issue?

Noise source handling is fine, the problem is the global locking on the
entropy pools when generating random numbers.

> If it is the latter, can you explain where the scalability issue comes in?

A single pool which is locked/written to does not scale. Larger systems
need multiple pools

-Andi

-- 
ak@linux.intel.com -- Speaking for myself only.

[toc] | [prev] | [next] | [standalone]

#1386711

Am Montag, 25. April 2016, 10:38:25 schrieb Andi Kleen:

Hi Andi,

> On Mon, Apr 25, 2016 at 07:25:55PM +0200, Stephan Mueller wrote:
> > Am Montag, 25. April 2016, 09:06:03 schrieb Andi Kleen:
> > 
> > Hi Andi,
> > 
> > > Sandy Harris <sandyinchina@gmail.com> writes:
> > > 
> > > There is also the third problem of horrible scalability of /dev/random
> > > output on larger systems, for which patches are getting ignored.
> > > 
> > > https://lkml.org/lkml/2016/2/10/716
> > > 
> > > Ignoring problems does not make them go away.
> > 
> > I have seen your patches, but I am not fully sure I understand the root
> > cause. is the noise source handling the issue or the random number
> > generation the issue?
> 
> Noise source handling is fine, the problem is the global locking on the
> entropy pools when generating random numbers.
> 
> > If it is the latter, can you explain where the scalability issue comes in?
> 
> A single pool which is locked/written to does not scale. Larger systems
> need multiple pools

That would imply that even when you have a system with 1000 CPUs, you want to 
have a large amount of random numbers. Is this the use case?

Or is simply the presence of 1000 CPUs an issue for "normal" loads on 
/dev/urandom?
> 
> -Andi


Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1386794

> > > If it is the latter, can you explain where the scalability issue comes in?
> > 
> > A single pool which is locked/written to does not scale. Larger systems
> > need multiple pools
> 
> That would imply that even when you have a system with 1000 CPUs, you want to 
> have a large amount of random numbers. Is this the use case?

That is right. Large systems do more work than small systems.
If the system is for example handling SSL connections it needs
more random numbers to handle more connections.

BTW the problems happen long before 1000 CPUs, more like 12-18 cores
competing.

Also today's large system is tomorrow's small systems. The
systems affected are actually not that large anymore.

The original numbers

Without patchkit:

1 node:  1x
2 nodes: 0.75x
3 nodes: 0.55x
4 nodes: 0.42x

-Andi
-- 
ak@linux.intel.com -- Speaking for myself only.

[toc] | [prev] | [next] | [standalone]

#1387416

Am Montag, 25. April 2016, 12:35:32 schrieb Andi Kleen:

Hi Andi,

> > > > If it is the latter, can you explain where the scalability issue comes
> > > > in?
> > > 
> > > A single pool which is locked/written to does not scale. Larger systems
> > > need multiple pools
> > 
> > That would imply that even when you have a system with 1000 CPUs, you want
> > to have a large amount of random numbers. Is this the use case?
> 
> That is right. Large systems do more work than small systems.
> If the system is for example handling SSL connections it needs
> more random numbers to handle more connections.
> 
> BTW the problems happen long before 1000 CPUs, more like 12-18 cores
> competing.
> 
> Also today's large system is tomorrow's small systems. The
> systems affected are actually not that large anymore.
> 
> The original numbers
> 
> Without patchkit:
> 
> 1 node:  1x
> 2 nodes: 0.75x
> 3 nodes: 0.55x
> 4 nodes: 0.42x

I have changed the LRNG now such that a multiple instantiation of the 
secondary DRBG can be implemented with very limited amount of code.

Thus, the proposal you have for the nonblocking_pool can be adapted.

Yet I have not implemented such duplication as I first would like to see 
whether the initial proposal of my LRNG is considered acceptable.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1389410

Am Montag, 25. April 2016, 12:35:32 schrieb Andi Kleen:

Hi Andi,

> > > > If it is the latter, can you explain where the scalability issue comes
> > > > in?
> > > 
> > > A single pool which is locked/written to does not scale. Larger systems
> > > need multiple pools
> > 
> > That would imply that even when you have a system with 1000 CPUs, you want
> > to have a large amount of random numbers. Is this the use case?
> 
> That is right. Large systems do more work than small systems.
> If the system is for example handling SSL connections it needs
> more random numbers to handle more connections.

I have ported the NUMA logic to the LRNG. It instantiates the secondary DRBG 
once for each NUMA node just like your patch.

Though, the initialization of the instances of the secondary DRBGs is 
different. I serialize the initialization such that one DRBG instance is 
seeded at a time from the primary DRBG.

I tested the code by using the per-CPU logic instead of per-NUMA node. This 
test shows that all works fine.

I then changed it to use a per NUMA node instance. It works on my test systems 
which instantiate the DRBG only once as I only have one node.

May I ask you to test that code on your system as I do not have access to a 
NUMA system? I will release a new version shortly.

Ciao
Stephan

[toc] | [prev] | [next] | [standalone]

#1387046

On Mon, Apr 25, 2016 at 09:06:03AM -0700, Andi Kleen wrote:
> Sandy Harris <sandyinchina@gmail.com> writes:
> 
> There is also the third problem of horrible scalability of /dev/random
> output on larger systems, for which patches are getting ignored.
> 
> https://lkml.org/lkml/2016/2/10/716
> 
> Ignoring problems does not make them go away.

Sorry, too much travel, deadlines and conference this spring.  I
haven't forgot them.

						- Ted

[toc] | [prev] | [next] | [standalone]

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | linux.kernel

csiph-web