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

[Pavel Machek]

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
pa...@denx.de address.)

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


signature.asc
Description: Digital signature

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

[Pavel Machek]

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
pa...@denx.de address.)

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


signature.asc
Description: Digital signature

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

[Theodore Ts'o]

On Sun, Jul 23, 2017 at 02:05:38PM -0400, Sandy Harris wrote:
> Sandy Harris  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

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

[Theodore Ts'o]

On Sun, Jul 23, 2017 at 02:05:38PM -0400, Sandy Harris wrote:
> Sandy Harris  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

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

[Sandy Harris]

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

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

[Sandy Harris]

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

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

[Stephan Müller]

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  
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:6396552603886565586466057102   Local timer
> >>  interrupts
> >> 
> >> with the number of disk related interrupts:
> >>  120:  21492 139284  405131705886   PCI-MSI 376832-edge
> >> 
> >> ahci[: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

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

[Stephan Müller]

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  
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:6396552603886565586466057102   Local timer
> >>  interrupts
> >> 
> >> with the number of disk related interrupts:
> >>  120:  21492 139284  405131705886   PCI-MSI 376832-edge
> >> 
> >> ahci[: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

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

[Arnd Bergmann]

On Fri, Jul 21, 2017 at 10:57 AM, Stephan Müller  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:6396552603886565586466057102   Local timer interrupts
>>
>> with the number of disk related interrupts:
>>
>>  120:  21492 139284  405131705886   PCI-MSI 376832-edge
>> ahci[: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

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

[Arnd Bergmann]

On Fri, Jul 21, 2017 at 10:57 AM, Stephan Müller  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:6396552603886565586466057102   Local timer interrupts
>>
>> with the number of disk related interrupts:
>>
>>  120:  21492 139284  405131705886   PCI-MSI 376832-edge
>> ahci[: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

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

[Jeffrey Walton]

Hi Ted,

Snipping one comment:

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

The statement about /dev/random being deprecated is not well
documented. A quick search is not turning up the expected results.

The RANDOM(4) man page provides competing (conflicting?) information:

   When read, the /dev/random device will return random bytes only  within
   the estimated number of bits of noise in the entropy pool.  /dev/random
   should be suitable for uses that need very high quality randomness such
   as  one-time  pad  or  key generation...

We regularly test the /dev/random generator by reading 10K bytes in
non-blocking, discarding them, and then asking for 16 bytes in
blocking. We also compress as a poor man's fitness test. We are
interested in how robust the generator is, how well it performs under
stress, and how well it recovers.

After draining it often takes minutes for the generator to produce 16
bytes. On Debian based systems the experiment usually fails unless
rng-tools is installed. The failures occur even on systems with
hardware based generators like rdrand and rdseed. I've witnessed the
failure on i686, x86_64, ARM and MIPS.

We recently suggested the GCC compile farm install rng-tools because
we were witnessing the problem there on machines. Cf.,
https://lists.tetaneutral.net/pipermail/cfarm-users/2017-July/30.html
. I've even seen vendors recommend wiring /dev/random to /dev/urandom
because of the entropy depletion problems. That's a big No-No
according to https://lwn.net/Articles/525459/.

The failures have always left me with an uncomfortable feeling because
there are so many damn programs out there that do their own thing.
Distro don't perform a SecArch review before packaging, so problems
lie in wait.

If the generator is truly deprecated, then it may be prudent to remove
it completely or remove it from userland. Otherwise, improve its
robustness. At minimum, update the documentation.

Jeff

On Thu, Jul 20, 2017 at 11:08 PM, Theodore Ts'o  wrote:
> 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:6396552603886565586466057102   Local timer interrupts
>
> with the number of disk related interrupts:
>
>  120:  21492 139284  405131705886   PCI-MSI 376832-edge  
> ahci[: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 

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

[Jeffrey Walton]

Hi Ted,

Snipping one comment:

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

The statement about /dev/random being deprecated is not well
documented. A quick search is not turning up the expected results.

The RANDOM(4) man page provides competing (conflicting?) information:

   When read, the /dev/random device will return random bytes only  within
   the estimated number of bits of noise in the entropy pool.  /dev/random
   should be suitable for uses that need very high quality randomness such
   as  one-time  pad  or  key generation...

We regularly test the /dev/random generator by reading 10K bytes in
non-blocking, discarding them, and then asking for 16 bytes in
blocking. We also compress as a poor man's fitness test. We are
interested in how robust the generator is, how well it performs under
stress, and how well it recovers.

After draining it often takes minutes for the generator to produce 16
bytes. On Debian based systems the experiment usually fails unless
rng-tools is installed. The failures occur even on systems with
hardware based generators like rdrand and rdseed. I've witnessed the
failure on i686, x86_64, ARM and MIPS.

We recently suggested the GCC compile farm install rng-tools because
we were witnessing the problem there on machines. Cf.,
https://lists.tetaneutral.net/pipermail/cfarm-users/2017-July/30.html
. I've even seen vendors recommend wiring /dev/random to /dev/urandom
because of the entropy depletion problems. That's a big No-No
according to https://lwn.net/Articles/525459/.

The failures have always left me with an uncomfortable feeling because
there are so many damn programs out there that do their own thing.
Distro don't perform a SecArch review before packaging, so problems
lie in wait.

If the generator is truly deprecated, then it may be prudent to remove
it completely or remove it from userland. Otherwise, improve its
robustness. At minimum, update the documentation.

Jeff

On Thu, Jul 20, 2017 at 11:08 PM, Theodore Ts'o  wrote:
> 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:6396552603886565586466057102   Local timer interrupts
>
> with the number of disk related interrupts:
>
>  120:  21492 139284  405131705886   PCI-MSI 376832-edge  
> ahci[: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
> 

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

[Stephan Müller]

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:6396552603886565586466057102   Local timer interrupts
> 
> with the number of disk related interrupts:
> 
>  120:  21492 139284  405131705886   PCI-MSI 376832-edge 
> ahci[:00:17.0]

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

Execute the follwing SystemTap script:

global NUMSAMPLES = 1;

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 

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

[Stephan Müller]

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:6396552603886565586466057102   Local timer interrupts
> 
> with the number of disk related interrupts:
> 
>  120:  21492 139284  405131705886   PCI-MSI 376832-edge 
> ahci[:00:17.0]

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

Execute the follwing SystemTap script:

global NUMSAMPLES = 1;

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 

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

[Theodore Ts'o]

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:6396552603886565586466057102   Local timer interrupts

with the number of disk related interrupts:

 120:  21492 139284  405131705886   PCI-MSI 376832-edge  
ahci[: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 

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

[Theodore Ts'o]

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:6396552603886565586466057102   Local timer interrupts

with the number of disk related interrupts:

 120:  21492 139284  405131705886   PCI-MSI 376832-edge  
ahci[: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 

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

[Stephan Müller]

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
> 

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

[Stephan Müller]

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
> 

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

[Theodore Ts'o]

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

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

[Theodore Ts'o]

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

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

[Greg Kroah-Hartman]

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

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

[Greg Kroah-Hartman]

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

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

[Stephan Müller]

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

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

[Stephan Müller]

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

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

[Stephan Müller]

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

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

[Stephan Müller]

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

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

[Theodore Ts'o]

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

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

[Theodore Ts'o]

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

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

[Sandy Harris]

On Tue, Jul 18, 2017 at 5:08 PM, Theodore Ts'o  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.

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

[Sandy Harris]

On Tue, Jul 18, 2017 at 5:08 PM, Theodore Ts'o  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.

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

[Theodore Ts'o]

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

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

[Theodore Ts'o]

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

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

[Stephan Müller]

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

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

[Stephan Müller]

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

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

[Greg Kroah-Hartman]

On Tue, Jul 18, 2017 at 10:45:12AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 10:32:10 CEST schrieb Greg Kroah-Hartman:
> 
> Hi Greg,
> 
> > external references do not last as long as the kernel change log does :(
> 
> What would be the best way to cite a 50+ page document? I got a suggestion to 
> include the ASCII version of the document into Documentation/ -- but for the 
> first inclusion request, I was not sure whether to add such large document.

Sure, we like lots of documentation, what's 50+ more pages of it?  :)

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

[Greg Kroah-Hartman]

On Tue, Jul 18, 2017 at 10:45:12AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 10:32:10 CEST schrieb Greg Kroah-Hartman:
> 
> Hi Greg,
> 
> > external references do not last as long as the kernel change log does :(
> 
> What would be the best way to cite a 50+ page document? I got a suggestion to 
> include the ASCII version of the document into Documentation/ -- but for the 
> first inclusion request, I was not sure whether to add such large document.

Sure, we like lots of documentation, what's 50+ more pages of it?  :)

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

[Greg Kroah-Hartman]

On Tue, Jul 18, 2017 at 10:45:12AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 10:32:10 CEST schrieb Greg Kroah-Hartman:
> 
> Hi Greg,
> 
> > external references do not last as long as the kernel change log does :(
> 
> What would be the best way to cite a 50+ page document? I got a suggestion to 
> include the ASCII version of the document into Documentation/ -- but for the 
> first inclusion request, I was not sure whether to add such large document.
> > 
> > Also a "wholesale" replacement of random.c is a major thing, why not
> > just submit patches to fix it up to add the needed changes you feel are
> > necessary?  We don't like to have major changes like this, that's not
> > how kernel development is done.
> 
> I have to admit that I tried that over the last years. I sent numerous small 
> cleanup patches (not changing any logic) and larger patches (with logic 
> changes). Even after pinging, I hardly got a response to any of my patches, 
> let alone that patches were accepted.

Changing core kernel code is hard, really hard, for good reason.  I
don't recall seeing a patch series from you that addressed minor things
that you might have complaints about, why not send them again?

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

thanks,

greg k-h

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

[Greg Kroah-Hartman]

On Tue, Jul 18, 2017 at 10:45:12AM +0200, Stephan Müller wrote:
> Am Dienstag, 18. Juli 2017, 10:32:10 CEST schrieb Greg Kroah-Hartman:
> 
> Hi Greg,
> 
> > external references do not last as long as the kernel change log does :(
> 
> What would be the best way to cite a 50+ page document? I got a suggestion to 
> include the ASCII version of the document into Documentation/ -- but for the 
> first inclusion request, I was not sure whether to add such large document.
> > 
> > Also a "wholesale" replacement of random.c is a major thing, why not
> > just submit patches to fix it up to add the needed changes you feel are
> > necessary?  We don't like to have major changes like this, that's not
> > how kernel development is done.
> 
> I have to admit that I tried that over the last years. I sent numerous small 
> cleanup patches (not changing any logic) and larger patches (with logic 
> changes). Even after pinging, I hardly got a response to any of my patches, 
> let alone that patches were accepted.

Changing core kernel code is hard, really hard, for good reason.  I
don't recall seeing a patch series from you that addressed minor things
that you might have complaints about, why not send them again?

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

thanks,

greg k-h

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

[Stephan Müller]

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

Hi Greg,

> external references do not last as long as the kernel change log does :(

What would be the best way to cite a 50+ page document? I got a suggestion to 
include the ASCII version of the document into Documentation/ -- but for the 
first inclusion request, I was not sure whether to add such large document.
> 
> Also a "wholesale" replacement of random.c is a major thing, why not
> just submit patches to fix it up to add the needed changes you feel are
> necessary?  We don't like to have major changes like this, that's not
> how kernel development is done.

I have to admit that I tried that over the last years. I sent numerous small 
cleanup patches (not changing any logic) and larger patches (with logic 
changes). Even after pinging, I hardly got a response to any of my patches, 
let alone that patches were accepted.

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

Ciao
Stephan

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

[Stephan Müller]

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

Hi Greg,

> external references do not last as long as the kernel change log does :(

What would be the best way to cite a 50+ page document? I got a suggestion to 
include the ASCII version of the document into Documentation/ -- but for the 
first inclusion request, I was not sure whether to add such large document.
> 
> Also a "wholesale" replacement of random.c is a major thing, why not
> just submit patches to fix it up to add the needed changes you feel are
> necessary?  We don't like to have major changes like this, that's not
> how kernel development is done.

I have to admit that I tried that over the last years. I sent numerous small 
cleanup patches (not changing any logic) and larger patches (with logic 
changes). Even after pinging, I hardly got a response to any of my patches, 
let alone that patches were accepted.

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

Ciao
Stephan

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

[Greg Kroah-Hartman]

On Tue, Jul 18, 2017 at 09:59:09AM +0200, Stephan Müller wrote:
> The LRNG with the following properties:
> 
> * noise source: interrupts timing with fast boot time seeding
> 
> * lockless LFSR to collect raw entropy
> 
> * use of standalone ChaCha20 based RNG with the option to use a
>   different DRNG selectable at compile time
> 
> * "atomic" seeding of secondary DRBG to ensure full entropy
>   transport
> 
> * instantiate one DRNG per NUMA node
> 
> Further details including the rationale for the design choices and
> properties of the LRNG together with testing is provided at [1].
> In addition, the documentation explains the conducted regression
> tests to verify that the LRNG is API and ABI compatible with the
> legacy /dev/random implementation.
> 
> [1] http://www.chronox.de/lrng.html

external references do not last as long as the kernel change log does :(

Also a "wholesale" replacement of random.c is a major thing, why not
just submit patches to fix it up to add the needed changes you feel are
necessary?  We don't like to have major changes like this, that's not
how kernel development is done.

thanks,

greg k-h

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

[Greg Kroah-Hartman]

On Tue, Jul 18, 2017 at 09:59:09AM +0200, Stephan Müller wrote:
> The LRNG with the following properties:
> 
> * noise source: interrupts timing with fast boot time seeding
> 
> * lockless LFSR to collect raw entropy
> 
> * use of standalone ChaCha20 based RNG with the option to use a
>   different DRNG selectable at compile time
> 
> * "atomic" seeding of secondary DRBG to ensure full entropy
>   transport
> 
> * instantiate one DRNG per NUMA node
> 
> Further details including the rationale for the design choices and
> properties of the LRNG together with testing is provided at [1].
> In addition, the documentation explains the conducted regression
> tests to verify that the LRNG is API and ABI compatible with the
> legacy /dev/random implementation.
> 
> [1] http://www.chronox.de/lrng.html

external references do not last as long as the kernel change log does :(

Also a "wholesale" replacement of random.c is a major thing, why not
just submit patches to fix it up to add the needed changes you feel are
necessary?  We don't like to have major changes like this, that's not
how kernel development is done.

thanks,

greg k-h

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

[Stephan Müller]

The LRNG with the following properties:

* noise source: interrupts timing with fast boot time seeding

* lockless LFSR to collect raw entropy

* use of standalone ChaCha20 based RNG with the option to use a
  different DRNG selectable at compile time

* "atomic" seeding of secondary DRBG to ensure full entropy
  transport

* instantiate one DRNG per NUMA node

Further details including the rationale for the design choices and
properties of the LRNG together with testing is provided at [1].
In addition, the documentation explains the conducted regression
tests to verify that the LRNG is API and ABI compatible with the
legacy /dev/random implementation.

[1] http://www.chronox.de/lrng.html

CC: Greg Kroah-Hartman 
CC: Arnd Bergmann 
CC: Jason A. Donenfeld 
Signed-off-by: Stephan Mueller 
---
 drivers/char/lrng_base.c | 2297 ++
 drivers/char/lrng_chacha20.c |  291 ++
 2 files changed, 2588 insertions(+)
 create mode 100644 drivers/char/lrng_base.c
 create mode 100644 drivers/char/lrng_chacha20.c

diff --git a/drivers/char/lrng_base.c b/drivers/char/lrng_base.c
new file mode 100644
index 000..a87c3ef
--- /dev/null
+++ b/drivers/char/lrng_base.c
@@ -0,0 +1,2297 @@
+/*
+ * Linux Random Number Generator (LRNG)
+ *
+ * Documentation and test code: http://www.chronox.de/lrng.html
+ *
+ * Copyright (C) 2016 - 2017, Stephan Mueller 
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *notice, and the entire permission notice in its entirety,
+ *including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *notice, this list of conditions and the following disclaimer in the
+ *documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ *products derived from this software without specific prior
+ *written permission.
+ *
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL2
+ * are required INSTEAD OF the above restrictions.  (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+/* Security strength of LRNG -- this must match DRNG security strength */
+#define LRNG_DRNG_SECURITY_STRENGTH_BYTES 32
+#define LRNG_DRNG_SECURITY_STRENGTH_BITS (LRNG_DRNG_SECURITY_STRENGTH_BYTES * 
8)
+
+#define LRNG_DRNG_BLOCKSIZE 64 /* Maximum of DRNG block sizes */
+
+/*
+ * Alignmask which should cover all cipher implementations
+ * WARNING: If this is changed to a value larger than 8, manual
+ * alignment is necessary as older versions of GCC may not be capable
+ * of aligning stack variables at boundaries greater than 8.
+ * In this case, PTR_ALIGN must be used.
+ */
+#define LRNG_KCAPI_ALIGN 8
+
+/* Primary DRNG state handle */
+struct lrng_pdrng {
+   void *pdrng;/* DRNG handle */
+   bool pdrng_fully_seeded;/* Is DRNG fully seeded? */
+   bool pdrng_min_seeded;  /* Is DRNG minimally seeded? */
+   u32 pdrng_entropy_bits; /* DRNG entropy level */
+   struct work_struct lrng_seed_work;  /* (re)seed work queue */
+   spinlock_t lock;
+};
+
+/* Secondary DRNG state handle */
+struct lrng_sdrng {
+   void *sdrng;/* DRNG handle */
+   atomic_t requests;  /* Number of DRNG requests */
+   unsigned long last_seeded;  /* Last time it was seeded */
+   bool fully_seeded;  /* Is DRNG fully seeded? */
+   

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

[Stephan Müller]

The LRNG with the following properties:

* noise source: interrupts timing with fast boot time seeding

* lockless LFSR to collect raw entropy

* use of standalone ChaCha20 based RNG with the option to use a
  different DRNG selectable at compile time

* "atomic" seeding of secondary DRBG to ensure full entropy
  transport

* instantiate one DRNG per NUMA node

Further details including the rationale for the design choices and
properties of the LRNG together with testing is provided at [1].
In addition, the documentation explains the conducted regression
tests to verify that the LRNG is API and ABI compatible with the
legacy /dev/random implementation.

[1] http://www.chronox.de/lrng.html

CC: Greg Kroah-Hartman 
CC: Arnd Bergmann 
CC: Jason A. Donenfeld 
Signed-off-by: Stephan Mueller 
---
 drivers/char/lrng_base.c | 2297 ++
 drivers/char/lrng_chacha20.c |  291 ++
 2 files changed, 2588 insertions(+)
 create mode 100644 drivers/char/lrng_base.c
 create mode 100644 drivers/char/lrng_chacha20.c

diff --git a/drivers/char/lrng_base.c b/drivers/char/lrng_base.c
new file mode 100644
index 000..a87c3ef
--- /dev/null
+++ b/drivers/char/lrng_base.c
@@ -0,0 +1,2297 @@
+/*
+ * Linux Random Number Generator (LRNG)
+ *
+ * Documentation and test code: http://www.chronox.de/lrng.html
+ *
+ * Copyright (C) 2016 - 2017, Stephan Mueller 
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *notice, and the entire permission notice in its entirety,
+ *including the disclaimer of warranties.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *notice, this list of conditions and the following disclaimer in the
+ *documentation and/or other materials provided with the distribution.
+ * 3. The name of the author may not be used to endorse or promote
+ *products derived from this software without specific prior
+ *written permission.
+ *
+ * ALTERNATIVELY, this product may be distributed under the terms of
+ * the GNU General Public License, in which case the provisions of the GPL2
+ * are required INSTEAD OF the above restrictions.  (This clause is
+ * necessary due to a potential bad interaction between the GPL and
+ * the restrictions contained in a BSD-style copyright.)
+ *
+ * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
+ * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
+ * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
+ * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
+ * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
+ * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
+ * DAMAGE.
+ */
+
+#define pr_fmt(fmt) KBUILD_MODNAME ": " fmt
+
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+#include 
+
+/* Security strength of LRNG -- this must match DRNG security strength */
+#define LRNG_DRNG_SECURITY_STRENGTH_BYTES 32
+#define LRNG_DRNG_SECURITY_STRENGTH_BITS (LRNG_DRNG_SECURITY_STRENGTH_BYTES * 
8)
+
+#define LRNG_DRNG_BLOCKSIZE 64 /* Maximum of DRNG block sizes */
+
+/*
+ * Alignmask which should cover all cipher implementations
+ * WARNING: If this is changed to a value larger than 8, manual
+ * alignment is necessary as older versions of GCC may not be capable
+ * of aligning stack variables at boundaries greater than 8.
+ * In this case, PTR_ALIGN must be used.
+ */
+#define LRNG_KCAPI_ALIGN 8
+
+/* Primary DRNG state handle */
+struct lrng_pdrng {
+   void *pdrng;/* DRNG handle */
+   bool pdrng_fully_seeded;/* Is DRNG fully seeded? */
+   bool pdrng_min_seeded;  /* Is DRNG minimally seeded? */
+   u32 pdrng_entropy_bits; /* DRNG entropy level */
+   struct work_struct lrng_seed_work;  /* (re)seed work queue */
+   spinlock_t lock;
+};
+
+/* Secondary DRNG state handle */
+struct lrng_sdrng {
+   void *sdrng;/* DRNG handle */
+   atomic_t requests;  /* Number of DRNG requests */
+   unsigned long last_seeded;  /* Last time it was seeded */
+   bool fully_seeded;  /* Is DRNG fully seeded? */
+   bool force_reseed;  /* Force a reseed */
+   spinlock_t lock;
+};
+
+/*
+ *