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

Groups > linux.kernel > #1690330 > unrolled thread

Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-18 16:40 +0200
    Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-18 23:10 +0200
      Re: [RFC PATCH v12 3/4] Linux Random Number Generator Sandy Harris <sandyinchina@gmail.com> - 2017-07-19 03:10 +0200
        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-19 04:00 +0200
          Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-19 08:30 +0200
          Re: [RFC PATCH v12 3/4] Linux Random Number Generator Pavel Machek <pavel@ucw.cz> - 2017-07-30 12:50 +0200
        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Sandy Harris <sandyinchina@gmail.com> - 2017-07-23 20:10 +0200
          Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-23 23:50 +0200
      Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-19 08:30 +0200
        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Greg Kroah-Hartman <gregkh@linuxfoundation.org> - 2017-07-19 08:40 +0200
        Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-19 19:30 +0200
          Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-20 21:10 +0200
            Re: [RFC PATCH v12 3/4] Linux Random Number Generator Theodore Ts'o <tytso@mit.edu> - 2017-07-21 05:10 +0200
              Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-21 11:00 +0200
                Re: [RFC PATCH v12 3/4] Linux Random Number Generator Stephan Müller <smueller@chronox.de> - 2017-07-21 17:20 +0200
                Re: [RFC PATCH v12 3/4] Linux Random Number Generator Arnd Bergmann <arnd@arndb.de> - 2017-07-21 17:20 +0200

#1690330 — Re: [RFC PATCH v12 3/4] Linux Random Number Generator

Am Dienstag, 18. Juli 2017, 10:52:12 CEST schrieb Greg Kroah-Hartman:

Hi Greg,

> 
> > I have stated the core concerns I have with random.c in [1]. To remedy
> > these core concerns, major changes to random.c are needed. With the past
> > experience, I would doubt that I get the changes into random.c.
> > 
> > [1] https://www.spinics.net/lists/linux-crypto/msg26316.html
> 
> Evolution is the correct way to do this, kernel development relies on
> that.  We don't do the "use this totally different and untested file
> instead!" method.

I am not sure I understand your reply. The offered patch set does not rip out 
existing code. It adds a replacement implementation which can be enabled 
during compile time. Yet it is even disabled per default (and thus the legacy 
code is compiled).

I see such a development approach in numerous different kernel core areas: 
memory allocators (SLAB, SLOB, SLUB), process schedulers, IRQ schedulers.

What is so different for the realm of RNGs?

Ciao
Stephan

[toc] | [next] | [standalone]

#1690650

On Tue, Jul 18, 2017 at 04:37:11PM +0200, Stephan Müller wrote:
> > 
> > > I have stated the core concerns I have with random.c in [1]. To remedy
> > > these core concerns, major changes to random.c are needed. With the past
> > > experience, I would doubt that I get the changes into random.c.
> > > 
> > > [1] https://www.spinics.net/lists/linux-crypto/msg26316.html
> > 
> > Evolution is the correct way to do this, kernel development relies on
> > that.  We don't do the "use this totally different and untested file
> > instead!" method.
> 
> I am not sure I understand your reply. The offered patch set does not rip out 
> existing code. It adds a replacement implementation which can be enabled 
> during compile time. Yet it is even disabled per default (and thus the legacy 
> code is compiled).

I've been trying to take the best features and suggestions from your
proposal and integrating them into /dev/random already.  Things that
I've chosen not take is basically because I disbelieve that the Jitter
RNG is valid.  And that's mostly becuase I trust Peter Anvin (who has
access to Intel chip architects, who has expressed unease) more than
you.  (No hard feelings).

So I have been trying to do the evolution thing already.  

> I see such a development approach in numerous different kernel core areas: 
> memory allocators (SLAB, SLOB, SLUB), process schedulers, IRQ schedulers.

But we don't have two VFS layers or two MM layers.  We also don't have
two implementations of printk.

I'm obviously biased, but I don't see I see the Raison d'Etre for
merging LRNG into the kernel.

						- Ted

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

#1690865

On Tue, Jul 18, 2017 at 5:08 PM, Theodore Ts'o <tytso@mit.edu> wrote:

> I've been trying to take the best features and suggestions from your
> proposal and integrating them into /dev/random already.

A good approach.

> Things that I've chosen not take is basically because I disbelieve
> that the Jitter RNG is valid. ...

The biggest problem with random(4) is that you cannot generate good
output without a good seed & just after boot, especially first boot on
a new system, you may not have enough entropy. A user space process
cannot do it soon enough and all the in-kernel solutions (unless you
have a hardware RNG) pose difficulties.

The only really good solution I know of is to find a way to provide a
chunk of randomness early in the boot process. John Denker has a good
discussion of doing this by modifying the kernel image & Ted talks of
doing it via the boot loader. Neither looks remarkably easy. Other
approaches like making the kernel read a seed file or passing a
parameter on the kernel command line have been suggested but, if I
recall right, rejected.

As I see it, the questions about Jitter, or any other in-kernel
generator based on timing, are whether it is good enough to be useful
until we have one of the above solutions or useful as a
defense-in-depth trick after we have one. I'd say yes to both.

There's been a lot of analysis. Stephan has a detailed rationale & a
lot of test data in his papers & the Havege papers also discuss
getting entropy from timer operations. I'd say the best paper is
McGuire et al:
https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf

There is enough there to convince me that grabbing some (256?) bits
from such a generator early in the initialization is worthwhile.

> So I have been trying to do the evolution thing already.
> ...

> I'm obviously biased, but I don't see I see the Raison d'Etre for
> merging LRNG into the kernel.

Nor I.

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

#1690906

On Tue, Jul 18, 2017 at 09:00:10PM -0400, Sandy Harris wrote:
> The only really good solution I know of is to find a way to provide a
> chunk of randomness early in the boot process. John Denker has a good
> discussion of doing this by modifying the kernel image & Ted talks of
> doing it via the boot loader. Neither looks remarkably easy. Other
> approaches like making the kernel read a seed file or passing a
> parameter on the kernel command line have been suggested but, if I
> recall right, rejected.

It's actually not that _hard_ to modify the boot loader.  It's not
finicky work like, say, adding support for metadata checksums or xattr
deduplication to ext4.  It's actually mostly plumbing.  It's just that
we haven't found a lot of people willing to do it as paid work, and
the hobbyists haven't been interested.

> As I see it, the questions about Jitter, or any other in-kernel
> generator based on timing, are whether it is good enough to be useful
> until we have one of the above solutions or useful as a
> defense-in-depth trick after we have one. I'd say yes to both.
> 
> There's been a lot of analysis. Stephan has a detailed rationale & a
> lot of test data in his papers & the Havege papers also discuss
> getting entropy from timer operations. I'd say the best paper is
> McGuire et al:
> https://static.lwn.net/images/conf/rtlws11/random-hardware.pdf

So here's the problem that I have with most of these analyses.  Most
of them are done using the x86 as the CPU.  This is true of the
McGuire, Okech, and Schiesser paper you've cited above.  But things
are largely irrelevant on the x86, because we have RDRAND.  And while
I like to mix in environmental noise before generating personal
long-term public keys.  I'm actually mostly OK with relying on RDRAND
for initializing the seeds for hash table to protect against network
denial of service attacks.  (Which is currently the first user of the
not-yet-initialized CRNG on my laptop during kernel boot.)

The real problem is with the non-x86 systems that don't have a
hardware RNG, and there depending timing events which don't depend on
external devices is much more dodgy.  Remember that on most embedded
devices there is only a single oscillator driving the entire system.
It's not like you even have multiple crystal oscillators beating
against one another.

So if you are only depending on CPU timing loops, you basically have a
very complex state machine, driven by a single oscillator, and you're
trying to kid yourself that you're getting entropy out the other end.
How is that any different from using AES in counter mode and claiming
because you don't know the seed, that it's "true randomness"?  It
certainly passes all of the statistical tests!

Hence, we have to rely on external events outside of the CPU and so we
need to depend on interrupt timing --- and that's what we do in
drivers/char/random.c already!  You can debate whether we are being
too conservative with when we judge that we've collective enough
unpredictability to count it as a "bit" of randomness.  So it's
trivially easy to turn the knob and make sure the CRNG gets
initialized more quickly using fewer interrupt timings, and boom!
Problem solved.

Simply turning the knob to make our entropy estimator more lax makes
people uncomfortable, and since they don't have access to the internal
microarchitecture of the CPU, they take comfort in the fact that it's
really, really complicated, and so something like the Jitter RNG
*must* be a more secure way to do things.  But that's really an illusion.

If the real unpredictability is really coming from the interrupts
changing the state of the CPU microarchitecture, the real question is
how many interrupts do you need before you consider things
"unpredictable" to an adequate level of security?  Arguing that we
should turn down the "interrupts per bit of entropy" in
drivers/char/random.c is a much more honest way of having that
discussion.

					- Ted

P.S.  In the McGuire paper you cited, it assumes that the system is
fully booted and there are multiple processes running which are
influencing the kernel scheduler.  This makes the paper **not** an
applicable at all.  So if you think that is the most compelling
analysis, I'm definitely not impressed....

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

#1691017

Am Mittwoch, 19. Juli 2017, 03:51:33 CEST schrieb Theodore Ts'o:

Hi Theodore,

> If the real unpredictability is really coming from the interrupts
> changing the state of the CPU microarchitecture, the real question is
> how many interrupts do you need before you consider things
> "unpredictable" to an adequate level of security?  Arguing that we
> should turn down the "interrupts per bit of entropy" in
> drivers/char/random.c is a much more honest way of having that
> discussion.

Please answer on the concerns given in [1] which explains that we cannot allow 
turning that knob in the current implementation.

[1] https://www.spinics.net/lists/linux-crypto/msg26316.html

Ciao
Stephan

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

#1699509

[Multipart message — attachments visible in raw view] — view raw

Hi!

On Tue 2017-07-18 21:51:33, Theodore Ts'o wrote:
> On Tue, Jul 18, 2017 at 09:00:10PM -0400, Sandy Harris wrote:
> > The only really good solution I know of is to find a way to provide a
> > chunk of randomness early in the boot process. John Denker has a good
> > discussion of doing this by modifying the kernel image & Ted talks of
> > doing it via the boot loader. Neither looks remarkably easy. Other
> > approaches like making the kernel read a seed file or passing a
> > parameter on the kernel command line have been suggested but, if I
> > recall right, rejected.
> 
> It's actually not that _hard_ to modify the boot loader.  It's not
> finicky work like, say, adding support for metadata checksums or xattr
> deduplication to ext4.  It's actually mostly plumbing.  It's just that
> we haven't found a lot of people willing to do it as paid work, and
> the hobbyists haven't been interested.

Modifying the boot loader sources is not hard, right.

Deploying the modified boot loader is another story; these are
bootloaders -- they normally don't need updating, so they are often
not easy to update, or maybe updating them is risky.

Anyway, if you want to pay for some bootloader modifications... I'm
working for a company that can help :-). (Sometimes I use
pavel@denx.de address.)

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

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

#1694347

Sandy Harris <sandyinchina@gmail.com> wrote:

> The biggest problem with random(4) is that you cannot generate good
> output without a good seed & just after boot, ...
>
> The only really good solution I know of is to find a way to provide a
> chunk of randomness early in the boot process. John Denker has a good
> discussion of doing this by modifying the kernel image & Ted talks of
> doing it via the boot loader. ...

Would it be enough to have a kernel module that does more-or-less what
the current shell scripts do, but earlier in the boot process? Throw
the stored data into the random(4) driver at module init time & update
it periodically later. This would not help much for first boot on a
new system, unless its store could be updated during install; Denker's
point that you need each system provisioned differently is important.
However it looks like it would be enough on other boots.

It also looks like it might be easier to implement & test. In
particular it is an isolated do-one-thing-well tool; the programmer
only needs to worry about his or her module, not several different
boot loaders or the procedures that distros have for CD images or
manufacturers for device setup.

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

#1694360

On Sun, Jul 23, 2017 at 02:05:38PM -0400, Sandy Harris wrote:
> Sandy Harris <sandyinchina@gmail.com> wrote:
> 
> > The biggest problem with random(4) is that you cannot generate good
> > output without a good seed & just after boot, ...
> >
> > The only really good solution I know of is to find a way to provide a
> > chunk of randomness early in the boot process. John Denker has a good
> > discussion of doing this by modifying the kernel image & Ted talks of
> > doing it via the boot loader. ...
> 
> Would it be enough to have a kernel module that does more-or-less what
> the current shell scripts do, but earlier in the boot process? Throw
> the stored data into the random(4) driver at module init time & update
> it periodically later. This would not help much for first boot on a
> new system, unless its store could be updated during install; Denker's
> point that you need each system provisioned differently is important.
> However it looks like it would be enough on other boots.

There are two things that make this hard.  The first is progamming
environment for, say, the GRUB bootloader, is very different from that
of, say, a System V init script.  The second is that it's not obvious
where you can safely store the information across boots.

For a specific architecture --- say, a PC desktop/server using a MBR
or GPT partition table, it's not that hard.  At which point, if you
want to assume that you are using a distribution kernel which is using
an initial ramdisk, you might not even need a kernel module; you could
just do it in the initrd before systemd gets a chance to run, and then
you can do it as a straight-forward shell script.  So that's actually
not hard, and not that different from what we have today.

It won't solve the problem for, say a Tails system, where you could be
booting off of a DVD (in which case you might not have any place to
store state), or a USB or SD card.  That's *also* not hard, but you
end up having to have a different solution for that case.

> It also looks like it might be easier to implement & test. In
> particular it is an isolated do-one-thing-well tool; the programmer
> only needs to worry about his or her module, not several different
> boot loaders or the procedures that distros have for CD images or
> manufacturers for device setup.

Unfortunately, you *do* still have to worry about multiple partition
tables, and potential places where the entropy could be stored.  The
solution for MBR, GPT, and Tails will all have to be slightly
different.

Again, none of this is terribly tricky work.  There are lots of fiddly
details, and if you get it right for one configuration, you will still
have to do something else for the next configuration.  So it's a lot
of grunt work, and since you can't come up for one solution that will
solve it for all systems, it won't be terribly glorious.

Note that you can also solve this problem by diddling the systemd unit
files, if you can make sure that you can fix the dependencies such
that the entropy setup is the very thing that happens after root file
system is mounted read/write, and before anything that might try to
generate keys is allowed to run.  That's going to be roughly the same
level of coverage as a kernel module and doesn't require trying to
store it in some partition-table unique place, but instead you have to
learn a lot of about systemd unit file configuration.

Cheers,

						- Ted

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

#1691010

Am Dienstag, 18. Juli 2017, 23:08:16 CEST schrieb Theodore Ts'o:

Hi Theodore,
> 
> I've been trying to take the best features and suggestions from your
> proposal and integrating them into /dev/random already.  Things that
> I've chosen not take is basically because I disbelieve that the Jitter
> RNG is valid.  And that's mostly becuase I trust Peter Anvin (who has
> access to Intel chip architects, who has expressed unease) more than
> you.  (No hard feelings).

I am unsure why you always point to the Jitter RNG. This is one noise source 
to keep or to remove -- at least it provides more data during early boot than 
any other noise source we currently have.

In the email [1] I have expressed the core concerns I see -- none of them 
address the need to keep the Jitter RNG as one noise source. To address those, 
a very deep dive into random.c needs to be made.

Such deep dive has the potential to be disruptive. Therefore, doesn't it make 
more sense to have such conceptual changes rather covered in a separate 
implementation?

[1] https://www.spinics.net/lists/linux-crypto/msg26316.html

Ciao
Stephan

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

#1691030

On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 23:08:16 CEST schrieb Theodore Ts'o:
> 
> Hi Theodore,
> > 
> > I've been trying to take the best features and suggestions from your
> > proposal and integrating them into /dev/random already.  Things that
> > I've chosen not take is basically because I disbelieve that the Jitter
> > RNG is valid.  And that's mostly becuase I trust Peter Anvin (who has
> > access to Intel chip architects, who has expressed unease) more than
> > you.  (No hard feelings).
> 
> I am unsure why you always point to the Jitter RNG. This is one noise source 
> to keep or to remove -- at least it provides more data during early boot than 
> any other noise source we currently have.
> 
> In the email [1] I have expressed the core concerns I see -- none of them 
> address the need to keep the Jitter RNG as one noise source. To address those, 
> a very deep dive into random.c needs to be made.
> 
> Such deep dive has the potential to be disruptive. Therefore, doesn't it make 
> more sense to have such conceptual changes rather covered in a separate 
> implementation?

No, it makes more sense to send individual patches addressing your
concerns to the existing random driver.  Again, that's how
kernel development has always worked.

thanks,

greg k-h

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

#1692047

On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote:
> In the email [1] I have expressed the core concerns I see -- none of them 
> address the need to keep the Jitter RNG as one noise source. To address those, 
> a very deep dive into random.c needs to be made.

That's simply not true.  The other issues besides the Jitter RNG are
really nits.

One of your complaints is the fact that we collect both interrupt
timing and HID/block timings.  First of all, we could eliminate the
HID/block timings since in practice we get the vast majority of our
entropy from the interrupt timing.  I keep it because we have a real
theoretical basis for their being unpredictability from the HID/block
timings.  For example, [1].

[1] http://world.std.com/~dtd/random/forward.pdf

The fact that there might be double count from the perspective of
entropy is not really an issue because we do a "fast mix" of 64
interrupts before we mix into the primary interrupt pool.  And when we
do mix into the primary pool we count that only as a single bit of
entropy.  The reason why I'm being super cautious here is because some
of these interrupts might be timer interrupts, or come from other
sources that might be correlated to the clock interrupt.  The
conservative assumption here is that at least one of the interrupts
out of 64, on average, will come from something that the adversary can
not anticipate, such as coming from a NIC or wireless device, and that
we will get at least one bit's worth of unpredictability.

The fact that we also mix in the jiffies plus the keyboard/mouse scan
code, is something that happens immediately.  So even if you think we
should not count the fast mix interrupt count, the fact that we mix
the timing values from 64 interrupts before we credit the entropy
counter by a single bit is sufficiently conservative; we're talking
about 1/64th of a bit here.

But if you **really** think mixing in the timing of the HID event
(gathered via a different mechanism --- jiffies vs cycle counter, and
including the the keyboard scan), a patch to disable
add_keyboard_randomness() is pretty trivial.  It doesn't justify a
complete rewrite of the random core.

(BTW, granted this is anecdata, but on my laptop, the CRNG is fully
initialized before systemd has even started and before the root file
system is mounted.  And after that point the entropy initialization
only matters for the legacy apps that use /dev/random, which doesn't
even exist in your proposed RNG, since everything just uses a
ChaCha20-based CRNG.)


Another one of your complaints is a straw-man argument ("I understand
that this pathological case is not present for the legacy
/dev/random...").  First of all, how we do entropy estimation after
the CRNG boot is far less important, because the primary recommended
interface is /dev/urandom or better yet getrandom(2).  Secondly, we
*don't* allow transfer of small quantums of entropy.  There is a
minimum transfer limit of 64 bits, and that can easily be increased to
128 bits if one really cared.  I've never really considered recovery
from state compromise to be that important, but if one did care,
increasing that limit is a two line patch.


I could go on, but the bottom line is that, quite frankly, I don't
consider your criticsms to be particular compelling or convincing.

Regards,

						- Ted

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

#1693179

Am Mittwoch, 19. Juli 2017, 19:26:03 CEST schrieb Theodore Ts'o:

Hi Theodore,

> On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote:
> > In the email [1] I have expressed the core concerns I see -- none of them
> > address the need to keep the Jitter RNG as one noise source. To address
> > those, a very deep dive into random.c needs to be made.
> 
> That's simply not true.  The other issues besides the Jitter RNG are
> really nits.
> 
> One of your complaints is the fact that we collect both interrupt
> timing and HID/block timings.  First of all, we could eliminate the
> HID/block timings since in practice we get the vast majority of our
> entropy from the interrupt timing.  I keep it because we have a real
> theoretical basis for their being unpredictability from the HID/block
> timings.  For example, [1].
> 
> [1] http://world.std.com/~dtd/random/forward.pdf
> 
> The fact that there might be double count from the perspective of
> entropy is not really an issue because we do a "fast mix" of 64
> interrupts before we mix into the primary interrupt pool.  And when we
> do mix into the primary pool we count that only as a single bit of
> entropy.  The reason why I'm being super cautious here is because some
> of these interrupts might be timer interrupts, or come from other
> sources that might be correlated to the clock interrupt.  The
> conservative assumption here is that at least one of the interrupts
> out of 64, on average, will come from something that the adversary can
> not anticipate, such as coming from a NIC or wireless device, and that
> we will get at least one bit's worth of unpredictability.
> 
> The fact that we also mix in the jiffies plus the keyboard/mouse scan
> code, is something that happens immediately.  So even if you think we
> should not count the fast mix interrupt count, the fact that we mix
> the timing values from 64 interrupts before we credit the entropy
> counter by a single bit is sufficiently conservative; we're talking
> about 1/64th of a bit here.

I concur with your rationale where de-facto the correlation is effect is 
diminished and eliminated with the fast_pool and the minimal entropy 
estimation of interrupts.

But it does not address my concern. Maybe I was not clear, please allow me to 
explain it again.

We have lots of entropy in the system which is discarded by the aforementioned 
approach (if a high-res timer is present -- without it all bets are off anyway 
and this should be covered in a separate discussion). At boot time, this issue 
is fixed by injecting 256 interrupts in the CRNG and consider it seeded.

But at runtime, were we still need entropy to reseed the CRNG and to supply /
dev/random. The accounting of entropy at runtime is much too conservative 
compared to any types of measurements that were conducted on bare metal or 
virtualized environment or on different architectures (if requested, I can 
surely share the test code and results in addition to already published 
studies -- see [1] table 1, 2 and 3 with figure 3.2 to get an idea). As long 
as a high-resolution time stamp is present, interrupts do provide much more 
than 1/64th bit of entropy per occurrence.

[1] http://www.chronox.de/lrng/doc/lrng.pdf

The implementation that was precisely outlined above present in random.c 
however does not allow revaluing the amount of entropy present in interrupts 
to a higher level simply because then the correlation issue kicks in.

Thus, when we want to re-value the interrupts with a higher level of entropy, 
we need to take out the high-resolution time stamp (and thus the more or less 
sole effective entropy provider for add_[disk|input]_randomness).

You mentioned that you are super conservative for interrupts due to timer 
interrupts. In all measurements on the different systems I conducted, I have 
not seen that the timer triggers an interrupt picked up by 
add_interrupt_randomness. For the sake of discussion, let us assume that such 
timer interrupts are present for a worst-case assessment. Such timer 
interrupts by nature should occur very periodically. Thus, it should be easy 
to detect them. IMHO the suggested stuck test in the LRNG exactly covers that 
scenario: only if the 1st, 2nd and 3rd derivative of the time stamp is non-
zero, the interrupt time stamp is considered to deliver entropy.

Thus, when revaluing the interrupt entropy, and removing the high-res timer 
from HID/block devices, the entropy heuristic in add_timer_randomness can go.

As we have no formal model about entropy to begin with, we can only assume and 
hope we underestimate entropy with the entropy heuristic. Thus, a precise 
entropy update with the asymptotic calculation in credit_entropy_bits may also 
not really be helpful and could be discarded.

> 
> But if you **really** think mixing in the timing of the HID event
> (gathered via a different mechanism --- jiffies vs cycle counter, and
> including the the keyboard scan), a patch to disable
> add_keyboard_randomness() is pretty trivial.  It doesn't justify a
> complete rewrite of the random core.
> 
> (BTW, granted this is anecdata, but on my laptop, the CRNG is fully
> initialized before systemd has even started and before the root file
> system is mounted.

Agreed, I see that too. And as mentioned above, this is how I think it is 
appropriate. This behavior is very similar to what I see on my LRNG.

> And after that point the entropy initialization
> only matters for the legacy apps that use /dev/random, which doesn't
> even exist in your proposed RNG, since everything just uses a
> ChaCha20-based CRNG.)
> 

I am not sure I understand the last statement. The blocking_pool (or the 
ChaCha20 DRNG in my LRNG) feeding /dev/random is simply a deterministic RNG 
with prediction resistance (in SP800-90A-speak). I.e. when one random bit 
shall be generated, one bit of entropy from the noise sources needs to go in.

Whether you have a blocking_pool or a normal DRNG to feed /dev/random does not 
matter as long as it only delivers as many bits as went in as entropy.
> 
> Another one of your complaints is a straw-man argument ("I understand
> that this pathological case is not present for the legacy
> /dev/random...").  First of all, how we do entropy estimation after
> the CRNG boot is far less important, because the primary recommended
> interface is /dev/urandom or better yet getrandom(2).  Secondly, we
> *don't* allow transfer of small quantums of entropy.  There is a
> minimum transfer limit of 64 bits, and that can easily be increased to
> 128 bits if one really cared.  I've never really considered recovery
> from state compromise to be that important, but if one did care,
> increasing that limit is a two line patch.

_xfer_secondary_pool says:

        /* pull at least as much as a wakeup */
        bytes = max_t(int, bytes, random_read_wakeup_bits / 8);

This determines the minimum amount. random_read_wakeup_bits can be changed by 
user space:

        {
                .procname       = "read_wakeup_threshold",
                .data           = &random_read_wakeup_bits,
                .maxlen         = sizeof(int),
                .mode           = 0644,
                .proc_handler   = proc_dointvec_minmax,
                .extra1         = &min_read_thresh,
                .extra2         = &max_read_thresh,
        },

min_read_thresh is 8.

Thus, the minimum amount of transfer is 1 byte as far as I read. I concur, 
however, that the default is 64 (bits).

This is what I would suggest to have changed to, say, the absolute minimum of 
64 or 128 bits.



Finally, I still think it is helpful to allow (not mandate) to involve the 
kernel crypto API for the DRNG maintenance (i.e. the supplier for /dev/random 
and /dev/urandom). The reason is that now more and more DRNG implementations 
in hardware pop up. Why not allowing them to be used. I.e. random.c would only 
contain the logic to manage entropy but uses the DRNG requested by a user.

In addition allowing a replacement of the DRNG component (at compile time at 
least) may get us away from having a separate DRNG solution in the kernel 
crypto API. Some users want their chosen or a standardized DRNG to deliver 
random numbers. Thus, we have several DRNGs in the kernel crypto API which are 
seeded by get_random_bytes. Or in user space, many folks need their own DRNG 
in user space in addition to the kernel. IMHO this is all a waste. If we could 
use the user-requested DRNG when producing random numbers for get_random_bytes 
or /dev/urandom or getrandom.

Ciao
Stephan

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

#1693358

On Thu, Jul 20, 2017 at 09:00:02PM +0200, Stephan Müller wrote:
> I concur with your rationale where de-facto the correlation is effect is 
> diminished and eliminated with the fast_pool and the minimal entropy 
> estimation of interrupts.
> 
> But it does not address my concern. Maybe I was not clear, please allow me to 
> explain it again.
> 
> We have lots of entropy in the system which is discarded by the aforementioned 
> approach (if a high-res timer is present -- without it all bets are off anyway 
> and this should be covered in a separate discussion). At boot time, this issue 
> is fixed by injecting 256 interrupts in the CRNG and consider it seeded.
> 
> But at runtime, were we still need entropy to reseed the CRNG and to supply /
> dev/random. The accounting of entropy at runtime is much too conservative...

Practically no one uses /dev/random.  It's essentially a deprecated
interface; the primary interfaces that have been recommended for well
over a decade is /dev/urandom, and now, getrandom(2).  We only need
384 bits of randomness every 5 minutes to reseed the CRNG, and that's
plenty even given the very conservative entropy estimation currently
being used.

This was deliberate.  I care a lot more that we get the initial
boot-time CRNG initialization right on ARM32 and MIPS embedded
devices, far, far, more than I care about making plenty of
information-theoretic entropy available at /dev/random on an x86
system.  Further, I haven't seen an argument for the use case where
this would be valuable.

If you don't think they count because ARM32 and MIPS don't have a
high-res timer, then you have very different priorities than I do.  I
will point out that numerically there are huge number of these devices
--- and very, very few users of /dev/random.

> You mentioned that you are super conservative for interrupts due to timer 
> interrupts. In all measurements on the different systems I conducted, I have 
> not seen that the timer triggers an interrupt picked up by 
> add_interrupt_randomness.

Um, the timer is the largest number of interrupts on my system.  Compare:

            CPU0       CPU1       CPU2       CPU3
 LOC:    6396552    6038865    6558646    6057102   Local timer interrupts

with the number of disk related interrupts:

 120:      21492     139284      40513    1705886   PCI-MSI 376832-edge      ahci[0000:00:17.0]

... and add_interrupt_randomness() gets called for **every**
interrupt.  On an mostly idle machine (I was in meetings most of
today) it's not surprising that time interrupts dominate.  That
doesn't matter for me as much because I don't really care about
/dev/random performance.  What's is **far** more important is that the
entropy estimations behave correctly, across all of Linux's
architectures, while the kernel is going through startup, before CRNG
is declared initialized.

> As we have no formal model about entropy to begin with, we can only assume and 
> hope we underestimate entropy with the entropy heuristic.

Yes, and that's why I use an ultra-conservative estimate.  If we start
using a more aggressive hueristic, we open ourselves up to potentially
very severe security bugs --- and for what?  What's the cost benefit
ratio here which makes this a worthwhile thing to risk?

> Finally, I still think it is helpful to allow (not mandate) to involve the 
> kernel crypto API for the DRNG maintenance (i.e. the supplier for /dev/random 
> and /dev/urandom). The reason is that now more and more DRNG implementations 
> in hardware pop up. Why not allowing them to be used. I.e. random.c would only 
> contain the logic to manage entropy but uses the DRNG requested by a user.

We *do* allow them to be used.  And we support a large number of
hardware random number generators already.  See drivers/char/hw_random.

BTW, I theorize that this is why the companies that could do the
bootloader random seen work haven't bothered.  Most of their products
have a TPM or equivalent, and with modern kernel the hw_random
interface now has a kernel thread that will automatically fill the
/dev/random entropy pool from the hw_random device.  So this all works
already, today, without needing a userspace rngd (which used to be
required).

> In addition allowing a replacement of the DRNG component (at compile time at 
> least) may get us away from having a separate DRNG solution in the kernel 
> crypto API. Some users want their chosen or a standardized DRNG to deliver 
> random numbers. Thus, we have several DRNGs in the kernel crypto API which are 
> seeded by get_random_bytes. Or in user space, many folks need their own DRNG 
> in user space in addition to the kernel. IMHO this is all a waste. If we could 
> use the user-requested DRNG when producing random numbers for get_random_bytes 
> or /dev/urandom or getrandom.

To be honest, I've never understood why that's there in the crypto API
at all.  But adding more ways to switch out the DRNG for /dev/random
doesn't solve that problem; in fact it's moving things in the wrong
direction.

Cheers,

						- Ted

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

#1693480

Am Freitag, 21. Juli 2017, 05:08:47 CEST schrieb Theodore Ts'o:

Hi Theodore,

> On Thu, Jul 20, 2017 at 09:00:02PM +0200, Stephan Müller wrote:
> > I concur with your rationale where de-facto the correlation is effect is
> > diminished and eliminated with the fast_pool and the minimal entropy
> > estimation of interrupts.
> > 
> > But it does not address my concern. Maybe I was not clear, please allow me
> > to explain it again.
> > 
> > We have lots of entropy in the system which is discarded by the
> > aforementioned approach (if a high-res timer is present -- without it all
> > bets are off anyway and this should be covered in a separate discussion).
> > At boot time, this issue is fixed by injecting 256 interrupts in the CRNG
> > and consider it seeded.
> > 
> > But at runtime, were we still need entropy to reseed the CRNG and to
> > supply / dev/random. The accounting of entropy at runtime is much too
> > conservative...
> Practically no one uses /dev/random.  It's essentially a deprecated
> interface; the primary interfaces that have been recommended for well
> over a decade is /dev/urandom, and now, getrandom(2).  We only need
> 384 bits of randomness every 5 minutes to reseed the CRNG, and that's
> plenty even given the very conservative entropy estimation currently
> being used.

On a headless system with SSDs, this is not enough based on measurements where 
entropy_avail is always low ...
> 
> This was deliberate.  I care a lot more that we get the initial
> boot-time CRNG initialization right on ARM32 and MIPS embedded
> devices, far, far, more than I care about making plenty of
> information-theoretic entropy available at /dev/random on an x86
> system.  Further, I haven't seen an argument for the use case where
> this would be valuable.

My concern covers *both* /dev/random and /dev/urandom.
> 
> If you don't think they count because ARM32 and MIPS don't have a
> high-res timer, then you have very different priorities than I do.  I
> will point out that numerically there are huge number of these devices
> --- and very, very few users of /dev/random.

With only jiffies, you will not get suitable entropy from interrupts or HID or 
block devices, as these actions can be monitored from user space with a 
suitable degree of precision.

The only real entropy provider would be HID as the entropy may come from the 
key strokes. But that is observable and should not count as entropy.
> 
> > You mentioned that you are super conservative for interrupts due to timer
> > interrupts. In all measurements on the different systems I conducted, I
> > have not seen that the timer triggers an interrupt picked up by
> > add_interrupt_randomness.
> 
> Um, the timer is the largest number of interrupts on my system.  Compare:
> 
>             CPU0       CPU1       CPU2       CPU3
>  LOC:    6396552    6038865    6558646    6057102   Local timer interrupts
> 
> with the number of disk related interrupts:
> 
>  120:      21492     139284      40513    1705886   PCI-MSI 376832-edge     
> ahci[0000:00:17.0]

They seem to be not picked up with the add_interrupt_randomness function.

Execute the follwing SystemTap script:

global NUMSAMPLES = 10000;

global num_events = 0;

probe kernel.function("add_interrupt_randomness")
{
        printf("%d\n", $irq);
        num_events++;

        if (num_events > NUMSAMPLES)
                exit();
}

The timer interrupt does not show up here.

> 
> ... and add_interrupt_randomness() gets called for **every**
> interrupt.  On an mostly idle machine (I was in meetings most of
> today) it's not surprising that time interrupts dominate.  That
> doesn't matter for me as much because I don't really care about
> /dev/random performance.  What's is **far** more important is that the
> entropy estimations behave correctly, across all of Linux's
> architectures, while the kernel is going through startup, before CRNG
> is declared initialized.
> 
> > As we have no formal model about entropy to begin with, we can only assume
> > and hope we underestimate entropy with the entropy heuristic.
> 
> Yes, and that's why I use an ultra-conservative estimate.  If we start
> using a more aggressive hueristic, we open ourselves up to potentially
> very severe security bugs --- and for what?  What's the cost benefit
> ratio here which makes this a worthwhile thing to risk?

The benefit is that in case there is an entropy hog on the system, /dev/random 
and /dev/urandom recover faster from that. Otherwise they do not get reseeded 
at all.
> 
> > Finally, I still think it is helpful to allow (not mandate) to involve the
> > kernel crypto API for the DRNG maintenance (i.e. the supplier for
> > /dev/random and /dev/urandom). The reason is that now more and more DRNG
> > implementations in hardware pop up. Why not allowing them to be used.
> > I.e. random.c would only contain the logic to manage entropy but uses the
> > DRNG requested by a user.
> We *do* allow them to be used.  And we support a large number of
> hardware random number generators already.  See drivers/char/hw_random.

These are noise sources with RNGs, they are not the pure DRNGs without noise 
source I am talking about.
> 
> BTW, I theorize that this is why the companies that could do the
> bootloader random seen work haven't bothered.  Most of their products
> have a TPM or equivalent, and with modern kernel the hw_random
> interface now has a kernel thread that will automatically fill the
> /dev/random entropy pool from the hw_random device.  So this all works
> already, today, without needing a userspace rngd (which used to be
> required).

I am not talking about the input to /dev/random or /dev/urandom. I am talking 
about the DRNG generating the output of /dev/random and /dev/urandom.
> 
> > In addition allowing a replacement of the DRNG component (at compile time
> > at least) may get us away from having a separate DRNG solution in the
> > kernel crypto API. Some users want their chosen or a standardized DRNG to
> > deliver random numbers. Thus, we have several DRNGs in the kernel crypto
> > API which are seeded by get_random_bytes. Or in user space, many folks
> > need their own DRNG in user space in addition to the kernel. IMHO this is
> > all a waste. If we could use the user-requested DRNG when producing
> > random numbers for get_random_bytes or /dev/urandom or getrandom.
> 
> To be honest, I've never understood why that's there in the crypto API
> at all.

Exactly because some folks require a DRNG that meets certain criteria. The 
DRNGs in the kernel crypto API are seeded by get_random_bytes and then produce 
output for the callers just because get_random_bytes has a DRNG for outputting 
data that is not suitable in their eyes.

If get_random_bytes (or the user space interfaces) would be more flexible in 
the output DRNG, the entire business with DRNGs in the kernel crypto API could 
go away.

> But adding more ways to switch out the DRNG for /dev/random
> doesn't solve that problem; in fact it's moving things in the wrong
> direction.

I am always talking about /dev/random and /dev/urandom (as well as 
get_random_bytes).
> 
> Cheers,
> 
> 						- Ted



Ciao
Stephan

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

#1693780

Am Freitag, 21. Juli 2017, 17:09:11 CEST schrieb Arnd Bergmann:

Hi Arnd,

> On Fri, Jul 21, 2017 at 10:57 AM, Stephan Müller <smueller@chronox.de> 
wrote:
> > Am Freitag, 21. Juli 2017, 05:08:47 CEST schrieb Theodore Ts'o:
> >> Um, the timer is the largest number of interrupts on my system.  Compare:
> >>             CPU0       CPU1       CPU2       CPU3
> >>  
> >>  LOC:    6396552    6038865    6558646    6057102   Local timer
> >>  interrupts
> >> 
> >> with the number of disk related interrupts:
> >>  120:      21492     139284      40513    1705886   PCI-MSI 376832-edge
> >> 
> >> ahci[0000:00:17.0]
> > 
> > They seem to be not picked up with the add_interrupt_randomness function.
> 
> On x86, the local APIC timer has some special handling in
> arch/x86/entry/entry_64.S that does not go through handle_irq_event().
> 
> I would assume that this is different when you boot with the "noapictimer"
> option and use the hpet clockevent instead.
> 
> On other architectures, the timer interrupt is often handled as a regular
> IRQ as well.

Thank you for the hint.

Yet, I would think that timer interrupts can be identified by 
add_interrupt_randomness, either by the IRQ or the stuck test that was is 
suggested with the LRNG patch set.

Ciao
Stephan

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

#1693786

On Fri, Jul 21, 2017 at 10:57 AM, Stephan Müller <smueller@chronox.de> wrote:
> Am Freitag, 21. Juli 2017, 05:08:47 CEST schrieb Theodore Ts'o:

>> Um, the timer is the largest number of interrupts on my system.  Compare:
>>
>>             CPU0       CPU1       CPU2       CPU3
>>  LOC:    6396552    6038865    6558646    6057102   Local timer interrupts
>>
>> with the number of disk related interrupts:
>>
>>  120:      21492     139284      40513    1705886   PCI-MSI 376832-edge
>> ahci[0000:00:17.0]
>
> They seem to be not picked up with the add_interrupt_randomness function.

On x86, the local APIC timer has some special handling in
arch/x86/entry/entry_64.S that does not go through handle_irq_event().

I would assume that this is different when you boot with the "noapictimer"
option and use the hpet clockevent instead.

On other architectures, the timer interrupt is often handled as a regular
IRQ as well.

       Arnd

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web