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

Groups > linux.kernel > #1460468 > unrolled thread

[PATCH v6 0/5] /dev/random - a new approach

Back to article view | Back to linux.kernel

Contents

  [PATCH v6 0/5] /dev/random - a new approach Stephan Mueller <smueller@chronox.de> - 2016-08-11 14:30 +0200
    Re: [PATCH v6 0/5] /dev/random - a new approach Theodore Ts'o <tytso@mit.edu> - 2016-08-11 23:40 +0200
      Re: [PATCH v6 0/5] /dev/random - a new approach Stephan Mueller <smueller@chronox.de> - 2016-08-12 11:40 +0200
        Re: [PATCH v6 0/5] /dev/random - a new approach Theodore Ts'o <tytso@mit.edu> - 2016-08-12 21:30 +0200
          Re: [PATCH v6 0/5] /dev/random - a new approach Stephan Mueller <smueller@chronox.de> - 2016-08-15 08:20 +0200
            Re: [PATCH v6 0/5] /dev/random - a new approach Theodore Ts'o <tytso@mit.edu> - 2016-08-15 17:10 +0200
      Re: [PATCH v6 0/5] /dev/random - a new approach Pavel Machek <pavel@ucw.cz> - 2016-08-17 23:50 +0200
        Re: [PATCH v6 0/5] /dev/random - a new approach Theodore Ts'o <tytso@mit.edu> - 2016-08-19 03:20 +0200
          Re: [PATCH v6 0/5] /dev/random - a new approach Pavel Machek <pavel@ucw.cz> - 2016-08-19 03:30 +0200
            Re: [PATCH v6 0/5] /dev/random - a new approach Theodore Ts'o <tytso@mit.edu> - 2016-08-19 05:20 +0200
              Re: [PATCH v6 0/5] /dev/random - a new approach Herbert Xu <herbert@gondor.apana.org.au> - 2016-08-19 08:00 +0200
                Re: [PATCH v6 0/5] /dev/random - a new approach "H. Peter Anvin" <hpa@linux.intel.com> - 2016-08-19 19:30 +0200
                  Re: [PATCH v6 0/5] /dev/random - a new approach Herbert Xu <herbert@gondor.apana.org.au> - 2016-08-21 05:20 +0200
              Re: [PATCH v6 0/5] /dev/random - a new approach Pavel Machek <pavel@ucw.cz> - 2016-08-19 09:50 +0200
    Re: [PATCH v6 0/5] /dev/random - a new approach "H. Peter Anvin" <hpa@linux.intel.com> - 2016-08-15 22:50 +0200
      Re: [PATCH v6 0/5] /dev/random - a new approach Stephan Mueller <smueller@chronox.de> - 2016-08-16 07:50 +0200
        Re: [PATCH v6 0/5] /dev/random - a new approach "H. Peter Anvin" <hpa@linux.intel.com> - 2016-08-17 00:30 +0200
          Re: [PATCH v6 0/5] /dev/random - a new approach "H. Peter Anvin" <hpa@linux.intel.com> - 2016-08-17 00:50 +0200
          Re: [PATCH v6 0/5] /dev/random - a new approach Stephan Mueller <smueller@chronox.de> - 2016-08-17 07:30 +0200

#1460468 — [PATCH v6 0/5] /dev/random - a new approach

Hi Herbert, Ted,

The following patch set provides a different approach to /dev/random which
I call Linux Random Number Generator (LRNG) to collect entropy within the Linux
kernel. The main improvements compared to the legacy /dev/random is to provide
sufficient entropy during boot time as well as in virtual environments and when
using SSDs. A secondary design goal is to limit the impact of the entropy
collection on massive parallel systems and also allow the use accelerated
cryptographic primitives. Also, all steps of the entropic data processing are
testable. Finally massive performance improvements are visible at /dev/urandom
and get_random_bytes.

The design and implementation is driven by a set of goals described in [1]
that the LRNG completely implements. Furthermore, [1] includes a
comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
AIS20/31.

Changes v6:
* port to 4.8-rc1
* add missing memzero_explicit to ChaCha20 DRNG
* use kernel-doc documentation style
* use of min3 in lrng_get_pool to beautify code
* prevent fast noise sources from dominating slow noise sources
  in case of /dev/random
* set read wakeup threshold to 64 bits to comply with legacy /dev/random
* simplify the interrupt to entropy amount conversion code
* move wakeup call of entropy-providers to a code location where /dev/urandom
  will benefit from the wake up as well (i.e. when the primary DRBG entropy
  runs low because of /dev/urandom reseeds, the entropy provider is woken up)
* inject current time into primary DRBG at the time of seeding from noise
  sources (suggested by Sandy Harris)

Changes v5:
* fix treating LRNG_POOL_SIZE_BITS as entropy value in lrng_get_pool
* use CTR DRBG with AES256 as default due to its superior speed -- on X86_64
  executing within a KVM I get read speeds of up to 850 MB/s now. When using a
  fake NUMA system with 4 nodes on 4 CPUs, I still get up to 430 MB/s read speed
  with four parallel reads. Note, this patch applies to the current
  cryptodev-2.6 tree.
* simplify lrng_get_arch
* use DRBG security strengths as defined in SP800-57 section 5.6.1
* add security strength to /proc/sys/kernel/random/lrng_type
* add ChaCha20 DRNG: in case the kernel crypto API is not compiled, the ChaCha20
  DRNG with the SHA-1 C implementations are used to drive the cryptographic part
  of the LRNG.The ChaCha20 RNG is described in [1]. I analyzed it with a user
  space version of it.
* Editorial changes requested by checkpatch.pl

Changes v4:
* port to 4.7-rc1
* Use classical twisted LFSR approach to collect entropic data as requested by
  George Spelvin. The LFSR is based on a primitive and irreducible polynomial
  whose taps are not too close to the location the current byte is mixed in.
  Primitive polynomials for other entropy pool sizes are offered in the code.
* The reading of the entropy pool is performed with a hash. The hash can be
  specified at compile time. The pre-defined hashes are the same as used for
  the DRBG type (e.g. a SHA256 Hash DRBG implies the use of SHA-256, an AES256
  CTR DRBG implies the use of CMAC-AES).
* Addition of the example defines for a CTR DRBG with AES128 which can be
  enabled during compile time.
* Entropy estimate: one bit of entropy per interrupt. In case a system does
  not have a high-resolution timer, apply 1/10th bit of entropy per interrupt.
  The interrupt estimates can be changed arbitrarily at compile time.
* Use kmalloc_node for the per-NUMA node secondary DRBGs.
* Add boot time entropy tests discussed in section 3.4.3 [1].
* Align all buffers that are processed by the kernel crypto API to an 8 byte
  boundary. This boundary covers all currently existing cipher implementations.

Changes v3:
* Convert debug printk to pr_debug as suggested by Joe Perches
* Add missing \n as suggested by Joe Perches
* Do not mix in struck IRQ measurements as requested by Pavel Machek
* Add handling logic for systems without high-res timer as suggested by Pavel
  Machek -- it uses ideas from the add_interrupt_randomness of the legacy
  /dev/random implementation
* add per NUMA node secondary DRBGs as suggested by Andi Kleen -- the
  explanation of how the logic works is given in section 2.1.1 of my
  documentation [1], especially how the initial seeding is performed.

Changes v2:
* Removal of the Jitter RNG fast noise source as requested by Ted
* Addition of processing of add_input_randomness as suggested by Ted
* Update documentation and testing in [1] to cover the updates
* Addition of a SystemTap script to test add_input_randomness
* To clarify the question whether sufficient entropy is present during boot
  I added one more test in 3.3.1 [1] which demonstrates the providing of
  sufficient entropy during initialization. In the worst case of no fast noise
  sources, in the worst case of a virtual machine with only very few hardware
  devices, the testing shows that the secondary DRBG is fully seeded with 256
  bits of entropy before user space injects the random data obtained
  during shutdown of the previous boot (i.e. the requirement phrased by the
  legacy /dev/random implementation). As the writing of the random data into
  /dev/random by user space will happen before any cryptographic service
  is initialized in user space, this test demonstrates that sufficient
  entropy is already present in the LRNG at the time user space requires it
  for seeding cryptographic daemons. Note, this test result was obtained
  for different architectures, such as x86 64 bit, x86 32 bit, ARM 32 bit and
  MIPS 32 bit.

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

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

Stephan Mueller (5):
  crypto: DRBG - externalize DRBG functions for LRNG
  random: conditionally compile code depending on LRNG
  crypto: Linux Random Number Generator
  crypto: LRNG - enable compile
  crypto: LRNG - add ChaCha20 support

 crypto/Kconfig           |   10 +
 crypto/Makefile          |    7 +
 crypto/drbg.c            |   11 +-
 crypto/lrng_base.c       | 1960 ++++++++++++++++++++++++++++++++++++++++++++++
 crypto/lrng_kcapi.c      |  167 ++++
 crypto/lrng_standalone.c |  220 ++++++
 drivers/char/random.c    |    8 +
 include/crypto/drbg.h    |    7 +
 include/linux/genhd.h    |    5 +
 include/linux/random.h   |    7 +-
 10 files changed, 2395 insertions(+), 7 deletions(-)
 create mode 100644 crypto/lrng_base.c
 create mode 100644 crypto/lrng_kcapi.c
 create mode 100644 crypto/lrng_standalone.c

-- 
2.7.4

[toc] | [next] | [standalone]

#1460815

On Thu, Aug 11, 2016 at 02:24:21PM +0200, Stephan Mueller wrote:
> 
> The following patch set provides a different approach to /dev/random which
> I call Linux Random Number Generator (LRNG) to collect entropy within the Linux
> kernel. The main improvements compared to the legacy /dev/random is to provide
> sufficient entropy during boot time as well as in virtual environments and when
> using SSDs. A secondary design goal is to limit the impact of the entropy
> collection on massive parallel systems and also allow the use accelerated
> cryptographic primitives. Also, all steps of the entropic data processing are
> testable. Finally massive performance improvements are visible at /dev/urandom
> and get_random_bytes.
> 
> The design and implementation is driven by a set of goals described in [1]
> that the LRNG completely implements. Furthermore, [1] includes a
> comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
> AIS20/31.

Given the changes that have landed in Linus's tree for 4.8, how many
of the design goals for your LRNG are still left not yet achieved?

Reading the paper, you are still claiming huge performance
improvements over getrandomm and /dev/urandom.  With the use of the
ChaCha20 (and given that you added a ChaCha20 DRBG as well), it's not
clear this is still an advantage over what we currently have.

As far as whether or not you can gather enough entropy at boot time,
what we're really talking about how how much entropy we want to assume
can be gathered from interrupt timings, since what you do in your code
is not all that different from what the current random driver is
doing.  So it's pretty easy to turn a knob and say, "hey presto, we
can get all of the entropy we need before userspace starts!"  But
justifying this is much harder, and using statistical tests isn't
really sufficient as far as I'm concerned.

Cheers,

						- Ted

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

#1461040

Am Donnerstag, 11. August 2016, 17:36:32 CEST schrieb Theodore Ts'o:

Hi Theodore,

> On Thu, Aug 11, 2016 at 02:24:21PM +0200, Stephan Mueller wrote:
> > The following patch set provides a different approach to /dev/random 
which
> > I call Linux Random Number Generator (LRNG) to collect entropy within the
> > Linux kernel. The main improvements compared to the legacy /dev/random is
> > to provide sufficient entropy during boot time as well as in virtual
> > environments and when using SSDs. A secondary design goal is to limit the
> > impact of the entropy collection on massive parallel systems and also
> > allow the use accelerated cryptographic primitives. Also, all steps of
> > the entropic data processing are testable. Finally massive performance
> > improvements are visible at /dev/urandom and get_random_bytes.
> > 
> > The design and implementation is driven by a set of goals described in 
[1]
> > that the LRNG completely implements. Furthermore, [1] includes a
> > comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
> > AIS20/31.
> 
> Given the changes that have landed in Linus's tree for 4.8, how many
> of the design goals for your LRNG are still left not yet achieved?

The core concerns I have at this point are the following:

- correlation: the interrupt noise source is closely correlated to the HID/
block noise sources. I see that the fast_pool somehow "smears" that 
correlation. However, I have not seen a full assessment that the correlation 
is gone away. Given that I do not believe that the HID event values (key 
codes, mouse coordinates) have any entropy -- the user sitting at the console 
exactly knows what he pressed and which mouse coordinates are created, and 
given that for block devices, only the high-resolution time stamp gives any 
entropy, I am suggesting to remove the HID/block device noise sources and 
leave the IRQ noise source. Maybe we could record the HID event values to 
further stir the pool but do not credit it any entropy. Of course, that would 
imply that the assumed entropy in an IRQ event is revalued. I am currently 
finishing up an assessment of how entropy behaves in a VM (where I hope that 
the report is released). Please note that contrary to my initial 
expectations, the IRQ events are the only noise sources which are almost 
unaffected by a VMM operation. Hence, IRQs are much better in a VM 
environment than block or HID noise sources.

- entropy estimate: the current entropy heuristics IMHO have nothing to do 
with the entropy of the data coming in. Currently, the min of first/second/
third derivative of the Jiffies time stamp is used and capped at 11. That 
value is the entropy value credited to the event. Given that the entropy 
rests with the high-res time stamp and not with jiffies or the event value, I 
think that the heuristic is not helpful. I understand that it underestimates 
on average the available entropy, but that is the only relationship I see. In 
my mentioned entropy in VM assessment (plus the BSI report on /dev/random 
which is unfortunately written in German, but available in the Internet) I 
did a min entropy calculation based on different min entropy formulas 
(SP800-90B). That calculation shows that we get from the noise sources is 
about 5 to 6 bits. On average the entropy heuristic credits between 0.5 and 1 
bit for events, so it underestimates the entropy. Yet, the entropy heuristic 
can credit up to 11 bits. Here I think it becomes clear that the current 
entropy heuristic is not helpful. In addition, on systems where no high-res 
timer is available, I assume (I have not measured it yet), the entropy 
heuristic even overestimates the entropy.

- albeit I like the current injection of twice the fast_pool into the 
ChaCha20 (which means that the pathological case where the collection of 128 
bits of entropy would result in an attack resistance of 2 * 128 bits and 
*not* 2^128 bits is now increased to an attack strength of 2^64 * 2 bits), /
dev/urandom has *no* entropy until that injection happens. The injection 
happens early in the boot cycle, but in my test system still after user space 
starts. I tried to inject "atomically" (to not fall into the aforementioned 
pathological case trap) of 32 / 112 / 256 bits of entropy into the /dev/
urandom RNG to have /dev/urandom at least seeded with a few bits before user 
space starts followed by the atomic injection of the subsequent bits.


A minor issue that may not be of too much importance: if there is a user 
space entropy provider waiting with select(2) or poll(2) on /dev/random (like 
rngd or my jitterentropy-rngd), this provider is only woken up when somebody 
pulls on /dev/random. If /dev/urandom is pulled (and the system does not 
receive entropy from the add*randomness noise sources), the user space 
provider is *not* woken up. So, /dev/urandom spins as a DRNG even though it 
could use a topping off of its entropy once in a while. In my jitterentropy-
rngd I have handled the situation that in addition to a select(2), the daemon 
is woken up every 5 seconds to read the entropy_avail file and starts 
injecting data into the kernel if it falls below a threshold. Yet, this is a 
hack. The wakeup function in the kernel should be placed at a different 
location to also have /dev/urandom benefit from the wakeup.
> 
> Reading the paper, you are still claiming huge performance
> improvements over getrandomm and /dev/urandom.  With the use of the
> ChaCha20 (and given that you added a ChaCha20 DRBG as well), it's not
> clear this is still an advantage over what we currently have.

I agree that with your latest changes, the performance of /dev/urandom is 
comparatively to my implementation, considering the tables 6 and 7 in my 
report. Although the speed of my ChaCha20 DRNG is faster for large block 
sizes (470 vs 210 MB/s for 4096 byte blocks), you rightfully state that the 
large block sizes do not really matter and hence I am not really using it for 
comparison. 

The table 6 and 7 reference the old /dev/urandom using still the SHA-1.
> 
> As far as whether or not you can gather enough entropy at boot time,
> what we're really talking about how how much entropy we want to assume
> can be gathered from interrupt timings, since what you do in your code
> is not all that different from what the current random driver is

Correct. I think I am doing exactly what you do regarding the entropy 
collection minus the caveats mentioned above.

> doing.  So it's pretty easy to turn a knob and say, "hey presto, we
> can get all of the entropy we need before userspace starts!"  But
> justifying this is much harder, and using statistical tests isn't
> really sufficient as far as I'm concerned.

I agree that statistics is one hint only. But as of now I have not seen any 
real explanation why an IRQ event measured with a high-res timer should not 
have 1 bit or 0.5 bits of entropy on average. All my statistical measurements 
(see my LRNG paper, see with my hopefully released VM assessment paper) show 
that the statistical measurement indicates that each high-res time stamp of 
an IRQ has more 4 bits of entropy at least when the system is under attack. 
Both one bit or 0.5 bits is more than enough to have a properly working /dev/
random even in virtual environments, embedded systems, headless systems, 
systems with SSDs, systems using a device mapper, etc. All those type of 
systems are currently subject to heavy penalties because of the collision 
problem I mentioned in the first bullet above.

Finally, one remark which I know you could not care less: :-) 

I try to use a known DRNG design that a lot of folks have already assessed -- 
SP800-90A (and please, do not hint to the Dual EC DRBG as this issue was 
pointed out already by researcher shortly after the first SP800-90A came out 
in 2007). This way I do not need to re-invent the wheel and potentially 
forget about things that may be helpful in a DRNG. To allow researchers to 
assess my ChaCha20 DRNG. that used when no kernel crypto API is compiled. 
independently from the kernel, I extracted the ChaCha20 DRNG code into a 
standalone DRNG accessible at [1]. This standalone implementation can be 
debugged and studied in user space. Moreover it is a simple copy of the 
kernel code to allow researchers an easy comparison.

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

Ciao
Stephan

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

#1461433

On Fri, Aug 12, 2016 at 11:34:55AM +0200, Stephan Mueller wrote:
> 
> - correlation: the interrupt noise source is closely correlated to the HID/
> block noise sources. I see that the fast_pool somehow "smears" that 
> correlation. However, I have not seen a full assessment that the correlation 
> is gone away. Given that I do not believe that the HID event values (key 
> codes, mouse coordinates) have any entropy -- the user sitting at the console 
> exactly knows what he pressed and which mouse coordinates are created, and 
> given that for block devices, only the high-resolution time stamp gives any 
> entropy, I am suggesting to remove the HID/block device noise sources and 
> leave the IRQ noise source. Maybe we could record the HID event values to 
> further stir the pool but do not credit it any entropy. Of course, that would 
> imply that the assumed entropy in an IRQ event is revalued. I am currently 
> finishing up an assessment of how entropy behaves in a VM (where I hope that 
> the report is released). Please note that contrary to my initial 
> expectations, the IRQ events are the only noise sources which are almost 
> unaffected by a VMM operation. Hence, IRQs are much better in a VM 
> environment than block or HID noise sources.

The reason why I'm untroubled with leaving them in is because I beieve
the quality of the timing information from the HID and block devices
is better than most of the other interrupt sources.  For example, most
network interfaces these days use NAPI, which means interrupts get
coalesced and sent in batch, which means the time of the interrupt is
latched off of some kind of timer --- and on many embeded devices
there is a single oscillator for the entire mainboard.  We only call
add_disk_randomness for rotational devices (e.g., only HDD's, not
SSD's), after the interrupt has been recorded.  Yes, most of the
entropy is probably going to be found in the high entropy time stamp
rather than the jiffies-based timestamp, especially for the hard drive
completion time.

I also tend to take a much more pragmatic viewpoint towards
measurability.  Sure, the human may know what she is typing, and
something about when she typed it (although probably not accurately
enough on a millisecond basis, so even the jiffies number is going to
be not easily predicted), but the analyst sitting behind the desk at
the NSA or the BND or the MSS is probably not going to have access to
that information.

(Whereas the NSA or the BND probably *can* get low-level information
about the Intel x86 CPU's internal implementation, which is why I'm
extremely amused by the arugment --- "the internals of the Intel CPU
are **so** complex we can't reverse engineer what's going on inside,
so the jitter RNG *must* be good!"  Note BTW that the NSA has only
said they won't do industrial espionage for economic for economic
gain, not that they won't engage in espionage against industrial
entities at all.  This is why the NSA spying on Petrobras is
considered completely fair game, even if it does enrage the
Brazillians.  :-)

> - entropy estimate: the current entropy heuristics IMHO have nothing to do 
> with the entropy of the data coming in. Currently, the min of first/second/
> third derivative of the Jiffies time stamp is used and capped at 11. That 
> value is the entropy value credited to the event. Given that the entropy 
> rests with the high-res time stamp and not with jiffies or the event value, I 
> think that the heuristic is not helpful. I understand that it underestimates 
> on average the available entropy, but that is the only relationship I see. In 
> my mentioned entropy in VM assessment (plus the BSI report on /dev/random 
> which is unfortunately written in German, but available in the Internet) I 
> did a min entropy calculation based on different min entropy formulas 
> (SP800-90B). That calculation shows that we get from the noise sources is 
> about 5 to 6 bits. On average the entropy heuristic credits between 0.5 and 1 
> bit for events, so it underestimates the entropy. Yet, the entropy heuristic 
> can credit up to 11 bits. Here I think it becomes clear that the current 
> entropy heuristic is not helpful. In addition, on systems where no high-res 
> timer is available, I assume (I have not measured it yet), the entropy 
> heuristic even overestimates the entropy.

The disks on a VM are not rotational disks, so we wouldn't be using
the add-disk-randomness entropy calculation.  And you generally don't
have a keyboard on a mouse attached to the VM, so we would be using
the entropy estimate from the interrupt timing.

As far as whether you can get 5-6 bits of entropy from interrupt
timings --- that just doesn't pass the laugh test.  The min-entropy
formulas are estimates assuming IID data sources, and it's not at all
clear (in fact, i'd argue pretty clearly _not_) that they are IID.  As
I said, take for example the network interfaces, and how NAPI gets
implemented.  And in a VM environment, where everything is synthetic,
the interrupt timings are definitely not IID, and there may be
patterns that will not detectable by statistical mechanisms.

> - albeit I like the current injection of twice the fast_pool into the 
> ChaCha20 (which means that the pathological case where the collection of 128 
> bits of entropy would result in an attack resistance of 2 * 128 bits and 
> *not* 2^128 bits is now increased to an attack strength of 2^64 * 2 bits), /
> dev/urandom has *no* entropy until that injection happens. The injection 
> happens early in the boot cycle, but in my test system still after user space 
> starts. I tried to inject "atomically" (to not fall into the aforementioned 
> pathological case trap) of 32 / 112 / 256 bits of entropy into the /dev/
> urandom RNG to have /dev/urandom at least seeded with a few bits before user 
> space starts followed by the atomic injection of the subsequent bits.

The early boot problem is a hard one.  We can inject some noise in,
but I don't think a few bits actually does much good.  So the question
is whether it's faster to get to fully seeded, or to inject in 32 bits
of entropy in the hopes that this will do some good.  Personally, I'm
not convinced.  So the tack I've taken is to have warning messages
printed when someone *does* draw from /dev/urandom before it's fully
seeded.  In many cases, it's for entirely bogus, non-cryptographic
reasons.  (For example, Python wanting to use a random salt to protect
against certain DOS attacks when Python is being used in a web server
--- a use case which is completely irrelevant when it's being used by
systemd generator scripts at boot time.)

Ultimately, I think the right answer here is we need help from the
bootloader, and ultimately some hardware help or some initialization
at factory time which isn't too easily hacked by a Tailored Access
Organization team who can intercept hardware shipments.  :-)

> A minor issue that may not be of too much importance: if there is a user 
> space entropy provider waiting with select(2) or poll(2) on /dev/random (like 
> rngd or my jitterentropy-rngd), this provider is only woken up when somebody 
> pulls on /dev/random. If /dev/urandom is pulled (and the system does not 
> receive entropy from the add*randomness noise sources), the user space 
> provider is *not* woken up. So, /dev/urandom spins as a DRNG even though it 
> could use a topping off of its entropy once in a while. In my jitterentropy-
> rngd I have handled the situation that in addition to a select(2), the daemon 
> is woken up every 5 seconds to read the entropy_avail file and starts 
> injecting data into the kernel if it falls below a threshold. Yet, this is a 
> hack. The wakeup function in the kernel should be placed at a different 
> location to also have /dev/urandom benefit from the wakeup.

Either /dev/urandom is a DRBG or is it isn't.  If it's a DRBG then you
don't need to track the entropy of the DRBG at all.  In fact, the
concept doesn't even really make sense for DRBG's.  Since we will be
reseeding the DRBG every five minutes if it is in constant use, there
will be plenty of opportunity to pull from a rngd or some other
hw_random device.

> Finally, one remark which I know you could not care less: :-) 
> 
> I try to use a known DRNG design that a lot of folks have already assessed -- 
> SP800-90A (and please, do not hint to the Dual EC DRBG as this issue was 
> pointed out already by researcher shortly after the first SP800-90A came out 
> in 2007). This way I do not need to re-invent the wheel and potentially 
> forget about things that may be helpful in a DRNG. To allow researchers to 
> assess my ChaCha20 DRNG. that used when no kernel crypto API is compiled. 
> independently from the kernel, I extracted the ChaCha20 DRNG code into a 
> standalone DRNG accessible at [1]. This standalone implementation can be 
> debugged and studied in user space. Moreover it is a simple copy of the 
> kernel code to allow researchers an easy comparison.

SP800-90A consists of a high level architecture of a DRBG, plus some
lower-level examples of how to use that high level architecture
assuming you have a hash function, or a block cipher, etc.  But it
doesn't have an example on using a stream cipher like ChaCha20.  So
all you can really do is follow the high-level architecture.  Mapping
the high-level architecture to the current /dev/random generator isn't
hard.  And no, I don't see the point of renaming things or moving
things around just to make the mapping to the SP800-90A easier.

       	      	      	       	       	  - Ted

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

#1462565

Am Freitag, 12. August 2016, 15:22:08 CEST schrieb Theodore Ts'o:

Hi Theodore,

> On Fri, Aug 12, 2016 at 11:34:55AM +0200, Stephan Mueller wrote:
> > - correlation: the interrupt noise source is closely correlated to the
> > HID/
> > block noise sources. I see that the fast_pool somehow "smears" that
> > correlation. However, I have not seen a full assessment that the
> > correlation is gone away. Given that I do not believe that the HID event
> > values (key codes, mouse coordinates) have any entropy -- the user
> > sitting at the console exactly knows what he pressed and which mouse
> > coordinates are created, and given that for block devices, only the
> > high-resolution time stamp gives any entropy, I am suggesting to remove
> > the HID/block device noise sources and leave the IRQ noise source. Maybe
> > we could record the HID event values to further stir the pool but do not
> > credit it any entropy. Of course, that would imply that the assumed
> > entropy in an IRQ event is revalued. I am currently finishing up an
> > assessment of how entropy behaves in a VM (where I hope that the report
> > is released). Please note that contrary to my initial
> > expectations, the IRQ events are the only noise sources which are almost
> > unaffected by a VMM operation. Hence, IRQs are much better in a VM
> > environment than block or HID noise sources.
> 
> The reason why I'm untroubled with leaving them in is because I beieve
> the quality of the timing information from the HID and block devices
> is better than most of the other interrupt sources.  For example, most
> network interfaces these days use NAPI, which means interrupts get
> coalesced and sent in batch, which means the time of the interrupt is
> latched off of some kind of timer --- and on many embeded devices

According to my understanding of NAPI, the network card sends one interrupt 
when receiving the first packet of a packet stream and then the driver goes 
into polling mode, disabling the interrupt. So, I cannot see any batching 
based on some on-board timer where add_interrupt_randomness is affected.
 
Can you please elaborate?

> there is a single oscillator for the entire mainboard.  We only call
> add_disk_randomness for rotational devices (e.g., only HDD's, not
> SSD's), after the interrupt has been recorded.  Yes, most of the
> entropy is probably going to be found in the high entropy time stamp
> rather than the jiffies-based timestamp, especially for the hard drive
> completion time.
> 
> I also tend to take a much more pragmatic viewpoint towards
> measurability.  Sure, the human may know what she is typing, and
> something about when she typed it (although probably not accurately
> enough on a millisecond basis, so even the jiffies number is going to
> be not easily predicted), but the analyst sitting behind the desk at
> the NSA or the BND or the MSS is probably not going to have access to
> that information.

Well, injecting a trojan to a system in user space as unprivileged user that 
starts some X11 session and that can perform the following command is all you 
need to get to the key commands of the console.

xinput list |   grep -Po 'id=\K\d+(?=.*slave\s*keyboard)' |   xargs -P0 -n1 
xinput test

That is fully within reach of not only some agencies but also other folks. It 
is similar for mice.

> 
> (Whereas the NSA or the BND probably *can* get low-level information
> about the Intel x86 CPU's internal implementation, which is why I'm
> extremely amused by the arugment --- "the internals of the Intel CPU
> are **so** complex we can't reverse engineer what's going on inside,
> so the jitter RNG *must* be good!"  Note BTW that the NSA has only

Sure, agencies may know the full internals of a CPU like they know the full 
internals of the Linux kernel with the /dev/random implementation or just like 
they know the full internals of AES. But they do not know the current state of 
the system. And the cryptographic strength comes from that state.

When you refer to my Jitter RNG, I think I have shown that its strength comes 
from the internal state of the CPU (states of the internal building blocks 
relative to each other which may cause internal wait states, state of branch 
prediction or pipelines, etc.) and not of the layout of the CPU.

> said they won't do industrial espionage for economic for economic
> gain, not that they won't engage in espionage against industrial
> entities at all.  This is why the NSA spying on Petrobras is
> considered completely fair game, even if it does enrage the
> Brazillians.  :-)
> 
> > - entropy estimate: the current entropy heuristics IMHO have nothing to do
> > with the entropy of the data coming in. Currently, the min of
> > first/second/
> > third derivative of the Jiffies time stamp is used and capped at 11. That
> > value is the entropy value credited to the event. Given that the entropy
> > rests with the high-res time stamp and not with jiffies or the event
> > value, I think that the heuristic is not helpful. I understand that it
> > underestimates on average the available entropy, but that is the only
> > relationship I see. In my mentioned entropy in VM assessment (plus the
> > BSI report on /dev/random which is unfortunately written in German, but
> > available in the Internet) I did a min entropy calculation based on
> > different min entropy formulas (SP800-90B). That calculation shows that
> > we get from the noise sources is about 5 to 6 bits. On average the
> > entropy heuristic credits between 0.5 and 1 bit for events, so it
> > underestimates the entropy. Yet, the entropy heuristic can credit up to
> > 11 bits. Here I think it becomes clear that the current entropy heuristic
> > is not helpful. In addition, on systems where no high-res timer is
> > available, I assume (I have not measured it yet), the entropy heuristic
> > even overestimates the entropy.
> 
> The disks on a VM are not rotational disks, so we wouldn't be using
> the add-disk-randomness entropy calculation.  And you generally don't
> have a keyboard on a mouse attached to the VM, so we would be using
> the entropy estimate from the interrupt timing.

On VMs, the add_disk_randomness is always used with the exception of KVM when 
using a virtio disk. All other VMs do not use virtio and offer the disk as a 
SCSI or IDE device. In fact, add_disk_randomness is only disabled when the 
kernel detects:

- SDDs

- virtio

- use of device mapper

(Btw we should be thankful that this is done on Hyper-V as we would have a 
fatal state in a very common use case where /dev/random would have collected 
no entropy and /dev/urandom would have provided bogus data before the patch 
for using the VMBus interrupts was added.)
> 
> As far as whether you can get 5-6 bits of entropy from interrupt
> timings --- that just doesn't pass the laugh test.  The min-entropy

May I ask what you find amusing? When you have a noise source for which you 
have no theoretical model, all you can do is to revert to statistical 
measurements.

> formulas are estimates assuming IID data sources, and it's not at all
> clear (in fact, i'd argue pretty clearly _not_) that they are IID.  As

Sure, they are not IID based on the SP800-90B IID verification tests. For 
that, SP800-90B has non-IID versions of the min entropy calculations. See 
section 9.1 together with 9.3 of SP800-90B where I used those non-IID 
formulas.

Sure, it is "just" some statistical test. But it is better IMHO than to brush 
away available entropy entirely just because "my stomach tells me it is not 
good".

Just see the guy that sent an email to linux-crypto today. His MIPS /dev/
random cannot produce 16 bytes of data within 4 hours (which is similar to 
what I see on POWER systems). This raises a very interesting security issue: /
dev/urandom is not seeded properly. And we all know what folks do in the wild: 
when /dev/random does not produce data, /dev/urandom is used -- all general 
user space libs (OpenSSL, libgcrypt, nettle, ...) seed from /dev/urandom per 
default.

And I call that a very insecure state of affairs.

> I said, take for example the network interfaces, and how NAPI gets

As mentioned above, I do not see NAPI as an issue for interrupt entropy.

> implemented.  And in a VM environment, where everything is synthetic,
> the interrupt timings are definitely not IID, and there may be
> patterns that will not detectable by statistical mechanisms.

As mentioned, to my very surprise, I found that interrupts are the only thing 
in a VM that works extremely well even under attack scenarios. VMMs that I 
quantiatively tested include QEMU/KVM, VirtualBox, VMWare ESXi and Hyper-V. 
After more research, I came to the conclusion that even on the theoretical 
side, it must be one of the better noise sources in a VM.

Note, this was the key motivation for me to start my own implementation of /
dev/random.
> 
> > - albeit I like the current injection of twice the fast_pool into the
> > ChaCha20 (which means that the pathological case where the collection of
> > 128 bits of entropy would result in an attack resistance of 2 * 128 bits
> > and *not* 2^128 bits is now increased to an attack strength of 2^64 * 2
> > bits), / dev/urandom has *no* entropy until that injection happens. The
> > injection happens early in the boot cycle, but in my test system still
> > after user space starts. I tried to inject "atomically" (to not fall into
> > the aforementioned pathological case trap) of 32 / 112 / 256 bits of
> > entropy into the /dev/ urandom RNG to have /dev/urandom at least seeded
> > with a few bits before user space starts followed by the atomic injection
> > of the subsequent bits.
> The early boot problem is a hard one.  We can inject some noise in,
> but I don't think a few bits actually does much good.  So the question
> is whether it's faster to get to fully seeded, or to inject in 32 bits

I am not talking about the 32 bits. We can leave the current 64 bits for the 
first seed.

I am concerned about the *two* separate injections of 64 bits. It should 
rather be *one* injection of at least 112 bit (or 128 bits). This is what I 
mean with "atomic" operation here.

> of entropy in the hopes that this will do some good.  Personally, I'm
> not convinced.  So the tack I've taken is to have warning messages
> printed when someone *does* draw from /dev/urandom before it's fully
> seeded.  In many cases, it's for entirely bogus, non-cryptographic
> reasons.  (For example, Python wanting to use a random salt to protect
> against certain DOS attacks when Python is being used in a web server
> --- a use case which is completely irrelevant when it's being used by
> systemd generator scripts at boot time.)
> 
> Ultimately, I think the right answer here is we need help from the
> bootloader, and ultimately some hardware help or some initialization
> at factory time which isn't too easily hacked by a Tailored Access
> Organization team who can intercept hardware shipments.  :-)

I agree. But we can still try to make the Linux side good as possible to cover 
people who do not have the luxury to control the hardware.
> 
[...]
> 
> > Finally, one remark which I know you could not care less: :-)
> > 
> > I try to use a known DRNG design that a lot of folks have already assessed
> > -- SP800-90A (and please, do not hint to the Dual EC DRBG as this issue
> > was pointed out already by researcher shortly after the first SP800-90A
> > came out in 2007). This way I do not need to re-invent the wheel and
> > potentially forget about things that may be helpful in a DRNG. To allow
> > researchers to assess my ChaCha20 DRNG. that used when no kernel crypto
> > API is compiled. independently from the kernel, I extracted the ChaCha20
> > DRNG code into a standalone DRNG accessible at [1]. This standalone
> > implementation can be debugged and studied in user space. Moreover it is
> > a simple copy of the kernel code to allow researchers an easy comparison.
> 
> SP800-90A consists of a high level architecture of a DRBG, plus some
> lower-level examples of how to use that high level architecture
> assuming you have a hash function, or a block cipher, etc.  But it
> doesn't have an example on using a stream cipher like ChaCha20.  So
> all you can really do is follow the high-level architecture.  Mapping
> the high-level architecture to the current /dev/random generator isn't
> hard.  And no, I don't see the point of renaming things or moving
> things around just to make the mapping to the SP800-90A easier.

Unfortunately I have seen subtle problems with DRNG implementations -- and a 
new one will emerge in the not too far future... There are examples of that 
and I like tests against reference implementations.

For example, the one key problem I have with the ChaCha20 DRNG is the 
following: when final update of the internal state is made for enhanced 
prediction resistance, ChaCha20 is used to generate one more block. That new 
block has 512 bits in size. In your implementation, you use the first 256 bits 
to inject it back into ChaCha20 as key. I use the entire 512 bits. I do not 
know whether one is better than the other (in the sense that it does not loose 
entropy). But barring any real research from other cryptographers, I guess we 
both do not know. And I have seen that such subtle issues may lead to 
catastrophic problems.

Thus, knowing valid DRNG designs may cover 99% of a new DRNG design. But the 
remaining 1% usually gives you the creeps.

Ciao
Stephan

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

#1462866

On Mon, Aug 15, 2016 at 08:13:06AM +0200, Stephan Mueller wrote:
> 
> According to my understanding of NAPI, the network card sends one interrupt 
> when receiving the first packet of a packet stream and then the driver goes 
> into polling mode, disabling the interrupt. So, I cannot see any batching 
> based on some on-board timer where add_interrupt_randomness is affected.
>  
> Can you please elaborate?

From https://wiki.linuxfoundation.org/networking/napi:

    NAPI (“New API”) is an extension to the device driver packet
    processing framework, which is designed to improve the performance
    of high-speed networking. NAPI works through:

    * Interrupt mitigation
    * High-speed networking can create thousands of interrupts per
      second, all of which tell the system something it already knew:
      it has lots of packets to process. NAPI allows drivers to run
      with (some) interrupts disabled during times of high traffic,
      with a corresponding decrease in system load.
      ...

The idea is to mitigate the CPU load from having a large number of
interrupts.  Spinning in a tight loop, wihch is what polling odoes,
doesn't help reduce the CPU load.  So it's *not* what you would want
to do on a small-count core CPU, or on a bettery operated device.

What you're thinking about is a technique to reduce interrupt latency,
which might be useful on a 32-core server CPU where trading off power
consumption for interrupt latency makes sense.  But NAPI is the exact
reverese thing --- it trades interrupt latency for CPU and power
efficiency.

NAPI in its traditional works by having the interrupt card *not* send
an interrupt after the packet comes in, and instead accumulate packets
in a buffer.  The interupt only gets sent after an short timeout, or
when the on-NIC buffer is in danger of filling.  As a result, when
interrupts get sent might be granularized based on some clock --- and
on small systems, there may only be a single CPU on that clock.

> Well, injecting a trojan to a system in user space as unprivileged user that 
> starts some X11 session and that can perform the following command is all you 
> need to get to the key commands of the console.
> 
> xinput list |   grep -Po 'id=\K\d+(?=.*slave\s*keyboard)' |   xargs -P0 -n1 
> xinput test
> 
> That is fully within reach of not only some agencies but also other folks. It 
> is similar for mice.

This doesn't result in keyboard and mice interrupts, which is how
add_input_randomness() works.  So it's mostly irrelevant.

> When you refer to my Jitter RNG, I think I have shown that its strength comes 
> from the internal state of the CPU (states of the internal building blocks 
> relative to each other which may cause internal wait states, state of branch 
> prediction or pipelines, etc.) and not of the layout of the CPU.

All of this is deterministic.  Just as AES_ENCRPT(NSA_KEY, COUNTER++)
is completely deterministic and dependant on the internal state of the
PRNG.  But it's not random, and if you don't know NSA_KEY you can't
prove that it's not really random.

> On VMs, the add_disk_randomness is always used with the exception of KVM when 
> using a virtio disk. All other VMs do not use virtio and offer the disk as a 
> SCSI or IDE device. In fact, add_disk_randomness is only disabled when the 
> kernel detects:
> 
> - SDDs
> 
> - virtio
> 
> - use of device mapper

AWS uses para-virtualized SCSI; Google Compute Engine uses
virtio-SCSI.  So the kernel should know that these are virtual
devices, and I'd argue that if we're setting the add_random flag, we
shouldn't be.

> > As far as whether you can get 5-6 bits of entropy from interrupt
> > timings --- that just doesn't pass the laugh test.  The min-entropy
> 
> May I ask what you find amusing? When you have a noise source for which you 
> have no theoretical model, all you can do is to revert to statistical 
> measurements.

So tell me, how much "minimum", "conservative" entropy do the non-IID
tests report when fed as input AES_ENCRYPT*NSA_KEY, COUNTER++)?

Sometimes, laughing is better than crying.  :-)

> Just see the guy that sent an email to linux-crypto today. His MIPS /dev/
> random cannot produce 16 bytes of data within 4 hours (which is similar to 
> what I see on POWER systems). This raises a very interesting security issue: /
> dev/urandom is not seeded properly. And we all know what folks do in the wild: 
> when /dev/random does not produce data, /dev/urandom is used -- all general 
> user space libs (OpenSSL, libgcrypt, nettle, ...) seed from /dev/urandom per 
> default.
>
> And I call that a very insecure state of affairs.

Overestimating entropy that isn't there doesn't actually make things
more secure.  It just makes people feel better.  This is especially
true if the goal is declare the /dev/urandom to be fully initialized
before userspace is started.  So if the claim is that your "LRNG" can
fully initialize the /dev/urandom pool, and it's using fundamentally
using the same interrupt sampling techniques as what is currently in
the kernel, then there is no substantive difference in security
between using /dev/urandom and using /dev/urandom with your patches
applied and enabled.

In the case of MIPS it doesn't have a high resolution timer, so it
*will* have less entropy that it can gather using interrupts compared
to an x86 system.  So i'd much rather be very conservative and
encourage people to use a CPU that *does* have a high resolution timer
or a hardware random number generator, or use some other very
carefully seeding via the bootloader or some such, rather than lull
them into a potentially false sense of security.

> As mentioned, to my very surprise, I found that interrupts are the only thing 
> in a VM that works extremely well even under attack scenarios. VMMs that I 
> quantiatively tested include QEMU/KVM, VirtualBox, VMWare ESXi and Hyper-V. 
> After more research, I came to the conclusion that even on the theoretical 
> side, it must be one of the better noise sources in a VM.

Again, how does your quantitive tests work on AES_ENCRYPT(NSA_KEY, COUNTER++)?

> I am concerned about the *two* separate injections of 64 bits. It should 
> rather be *one* injection of at least 112 bit (or 128 bits). This is what I 
> mean with "atomic" operation here.

We only consider urandom/getrandom CRNG to be initialized when 2
injections happen without an intervening extract operation.  If there
is an extract operation, we print a warning and then reset the
counter.  So by the time /dev/urandom is initialized, it has had two
"atomic" injections of entropy.  It's the same kind of atomicity which
is provided by the seqlock_t abstraction in the linux kernel.


> For example, the one key problem I have with the ChaCha20 DRNG is the 
> following: when final update of the internal state is made for enhanced 
> prediction resistance, ChaCha20 is used to generate one more block. That new 
> block has 512 bits in size. In your implementation, you use the first 256 bits 
> to inject it back into ChaCha20 as key. I use the entire 512 bits. I do not 
> know whether one is better than the other (in the sense that it does not loose 
> entropy). But barring any real research from other cryptographers, I guess we 
> both do not know. And I have seen that such subtle issues may lead to 
> catastrophic problems.

Chacha20 uses a 256-bit key, and what I'm doing is folding in 256 bits
into the ChaCha20 key.  The security strength that we're claiming fom
in the SP800-90A DRBG model is 256 bits (the maximum from the
SP800-90A set of 112, 128, 192, or 256), and so I'd argue that what
I'm doing is sufficient.

Entropy doesn't really have a meaning in a DRBG, so SP800-90A wouldn't
have anything to say anything about either alternative.

Cheers,

							- Ted

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

#1464828

Hi!

> As far as whether or not you can gather enough entropy at boot time,
> what we're really talking about how how much entropy we want to assume
> can be gathered from interrupt timings, since what you do in your code
> is not all that different from what the current random driver is
> doing.  So it's pretty easy to turn a knob and say, "hey presto, we
> can get all of the entropy we need before userspace starts!"  But
> justifying this is much harder, and using statistical tests isn't
> really sufficient as far as I'm concerned.

Actually.. I'm starting to believe that getting enough entropy before
userspace starts is more important than pretty much anything else.

We only "need" 64-bits of entropy, AFAICT. If it passes statistical
tests, I'd use it... for initial bringup.

We can switch to more conservative estimates when system is fully
running. But IMO it is very important to get _some_ randomness at the
begining...

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

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

#1465748

On Wed, Aug 17, 2016 at 11:42:55PM +0200, Pavel Machek wrote:
> 
> Actually.. I'm starting to believe that getting enough entropy before
> userspace starts is more important than pretty much anything else.
> 
> We only "need" 64-bits of entropy, AFAICT. If it passes statistical
> tests, I'd use it... for initial bringup.

Definitely not 64 bits.  Back in *1996* the estimate was that we
needed at least 75-bits in order to be protected against brute force
attacks.  It's been two *deacdes* years later, and granted Moore's law
has ceased to apply in the last couple of years, but I'm sure 64 bits
is not enough.

What is your specific concern vis-a-vis when userspace starts?  We now
print a warning if someone tries to draw from /dev/urandom, and so it
should be easy to see if someone is doing something dangerous.  The
have only been known cases (at last as far asI know where) where some
software was doing something as *insane* as to create keys right out
of the box was.  One was ssh, and at least on a modern Debian system,
that doesn't happen until fairly late in the process:

% systemd-analyze critical-chain ssh.service
The time after the unit is active or started is printed after the "@" character.
The time the unit takes to start is printed after the "+" character.

ssh.service +888ms
└─network.target @31.473s
  └─wpa_supplicant.service @32.958s +770ms
    └─basic.target @19.479s
      └─sockets.target @19.479s
        └─acpid.socket @19.479s
          └─sysinit.target @19.414s
            └─systemd-timesyncd.service @18.079s +1.330s
              └─systemd-tmpfiles-setup.service @17.512s +78ms
                └─local-fs.target @17.501s
                  └─run-user-15806.mount @43.047s
                    └─local-fs-pre.target @16.616s
                      └─systemd-tmpfiles-setup-dev.service @755ms +930ms
                        └─kmod-static-nodes.service @729ms +17ms
                          └─system.slice @653ms
                            └─-.slice @608ms

The other was HP, which was generating an RSA key very shortly after
the first time the printer was powered on.

> We can switch to more conservative estimates when system is fully
> running. But IMO it is very important to get _some_ randomness at the
> begining...

We're doing this already in the latest getrandom(2) implementation.
For the purposes of initializing the crng, we assume that each
interrupt has a single bit of entropy.  So it requires 128 initerrupts
for getrandom(2) to be fully initialized.  I'm actually worried that
this is too high as it is for architectures that don't have a
fine-grained clock.  Given that on many of these embedded platforms
there is a oscillator which drives all of the clocks and subsystems,
it just doesn't make *sense* that than each interrupt could result in
5-6 bits of entropy, no matter what a magical statistical formula
might say.

(Creation of some completely determinsitic sequences that cause the
magical statistcal formulas to claim a vast number of entropy bits is
left as an exercise to the reader.)

Cheers, 

							- Ted

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

#1465769

On Thu 2016-08-18 13:27:12, Theodore Ts'o wrote:
> On Wed, Aug 17, 2016 at 11:42:55PM +0200, Pavel Machek wrote:
> > 
> > Actually.. I'm starting to believe that getting enough entropy before
> > userspace starts is more important than pretty much anything else.
> > 
> > We only "need" 64-bits of entropy, AFAICT. If it passes statistical
> > tests, I'd use it... for initial bringup.
> 
> Definitely not 64 bits.  Back in *1996* the estimate was that we
> needed at least 75-bits in order to be protected against brute force
> attacks.  It's been two *deacdes* years later, and granted Moore's law
> has ceased to apply in the last couple of years, but I'm sure 64 bits
> is not enough.
> 
> What is your specific concern vis-a-vis when userspace starts?  We now
> print a warning if someone tries to draw from /dev/urandom, and so it
> should be easy to see if someone is doing something dangerous.  The

Well, warning is nice, but I'm afraid it is not going to stop everyone.

> have only been known cases (at last as far asI know where) where some
> software was doing something as *insane* as to create keys right out
> of the box was.  One was ssh, and at least on a modern Debian system,
> that doesn't happen until fairly late in the process:

It is more widespread than that:

rapsberry pi:
https://www.raspberrypi.org/forums/viewtopic.php?t=126892

But this is the scary part. Not limited to ssh. "We perform the
largest ever network survey of TLS and SSH servers and present
evidence that vulnerable keys are surprisingly widespread. We find
that 0.75% of TLS certificates share keys due to insufficient entropy
during key generation, and we suspect that another 1.70% come from the
same faulty implementations and may be susceptible to compromise.
Even more alarmingly, we are able to obtain RSA private keys for 0.50%
of TLS hosts and 0.03% of SSH hosts, because their public keys shared
nontrivial common factors due to entropy problems, and DSA private
keys for 1.03% of SSH hosts, because of insufficient signature
randomness"

https://factorable.net/weakkeys12.conference.pdf

Responsible devices were Gigaset SX762, ADTran Total Access
businessgrade phone/network routers, IBM RSA II remote administration
cards, BladeCenter devices, Juniper Networks Branch SRX devices,
... "We used the techniques described in Section 3.2 to identify
apparently vulnerable devices from 27 manufacturers.  These include
enterprise-grade routers from Cisco; server management cards from
Dell, Hewlett-Packard, and IBM; virtual-private-network (VPN) devices;
building security systems; network attached storage devices; and
several kinds of consumer routers and VoIP products."

> The other was HP, which was generating an RSA key very shortly after
> the first time the printer was powered on.

Its definitely more than two incidents.

> > We can switch to more conservative estimates when system is fully
> > running. But IMO it is very important to get _some_ randomness at the
> > begining...
> 
> We're doing this already in the latest getrandom(2) implementation.
> For the purposes of initializing the crng, we assume that each
> interrupt has a single bit of entropy.  So it requires 128 initerrupts
> for getrandom(2) to be fully initialized.  I'm actually worried that
> this is too high as it is for architectures that don't have a
> fine-grained clock.  Given that on many of these embedded platforms
> there is a oscillator which drives all of the clocks and subsystems,
> it just doesn't make *sense* that than each interrupt could result in
> 5-6 bits of entropy, no matter what a magical statistical formula
> might say.

From my point of view, it would make sense to factor time from RTC and
mac addresses into the initial hash. Situation in the paper was so bad
some devices had _completely identical_ keys. We should be able to do
better than that.

BTW... 128 interrupts... that's 1.3 seconds, right? Would it make
sense to wait two seconds if urandom use is attempted before it is
ready?

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

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

#1465953

On Thu, Aug 18, 2016 at 08:39:23PM +0200, Pavel Machek wrote:
> 
> But this is the scary part. Not limited to ssh. "We perform the
> largest ever network survey of TLS and SSH servers and present
> evidence that vulnerable keys are surprisingly widespread. We find
> that 0.75% of TLS certificates share keys due to insufficient entropy
> during key generation, and we suspect that another 1.70% come from the
> same faulty implementations and may be susceptible to compromise.
> Even more alarmingly, we are able to obtain RSA private keys for 0.50%
> of TLS hosts and 0.03% of SSH hosts, because their public keys shared
> nontrivial common factors due to entropy problems, and DSA private
> keys for 1.03% of SSH hosts, because of insufficient signature
> randomness"
> 
> https://factorable.net/weakkeys12.conference.pdf

That's a very old paper, and we've made a lot of changes since then.
Before that we weren't accumulating entropy from the interrupt
handler, but only from spinning disk drives, some network interrupts
(but not from all NIC's; it was quite arbitrary), and keyboard and
mouse interrupts.  So hours and hours could go by and you still
wouldn't have accumulated much entropy.

> From my point of view, it would make sense to factor time from RTC and
> mac addresses into the initial hash. Situation in the paper was so bad
> some devices had _completely identical_ keys. We should be able to do
> better than that.

We fixed that **years** ago.  In fact, the authors shared with me an
early look at that paper and I implemented add_device_entropy() over
the July 4th weekend back in 2012.  So we are indeed mixing in MAC
addresses and the hardware clock (if it is initialized that early).
In fact that was one of the first things that I did.  Note that this
doesn't really add much entropy, but it does prevent the GCD attack
from demonstrating completely identical keys.  Hence, we had
remediations in the mainline kernel before the factorable.net paper
was published (not that really helped with devices with embedded
Linux, especially since device manufactures don't see anything wrong
with shipping machines with kernels that are years and years out of
date --- OTOH, these systems were probably also shipping with dozens
of known exploitable holes in userspace, if that's any comfort.
Probably not much if you were planning on deploying lots of IOT
devices in your home network.  :-)

> BTW... 128 interrupts... that's 1.3 seconds, right? Would it make
> sense to wait two seconds if urandom use is attempted before it is
> ready?

That really depends on the system.  We can't assume that people are
using systems with a 100Hz clock interrupt.  More often than not
people are using tickless kernels these days.  That's actually the
problem with changing /dev/urandom to block until things are
initialized.

If you do that, then on some system Python will use /dev/urandom to
initialize a salt used by the Python dictionaries, to protect against
DOS attacks when Python is used to run web scripts.  This is a
completely irrelevant reason when Python is being used for systemd
generator scripts in early boot, and if /dev/urandom were to block,
then the system ends up doing nothing, and on a tickless kernels hours
and hours can go by on a VM and Python would still be blocked on
/dev/urandom.  And since none of the system scripts are running, there
are no interrupts, and so Python ends up blocking on /dev/urandom for
a very long time.  (Eventually someone will start trying to brute
force passwords on the VM's ssh port, assuming that the VM's firewall
rules allow this, and that will cause interrupts that will eventually
initialize /dev/urandom.  But that could take hours.)

And this, boys and girls, is why we can't make /dev/urandom block
until its pool is initialized.  There's too great of a chance that we
will break userspace, and then Linus will yell at us and revert the
commit.

						- Ted

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

#1466036

On Thu, Aug 18, 2016 at 10:49:47PM -0400, Theodore Ts'o wrote:
>
> That really depends on the system.  We can't assume that people are
> using systems with a 100Hz clock interrupt.  More often than not
> people are using tickless kernels these days.  That's actually the
> problem with changing /dev/urandom to block until things are
> initialized.

Couldn't we disable tickless until urandom has been seeded? In fact
perhaps we should accelerate the timer interrupt rate until it has
been seeded?

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

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

#1466578

On 08/18/16 22:56, Herbert Xu wrote:
> On Thu, Aug 18, 2016 at 10:49:47PM -0400, Theodore Ts'o wrote:
>>
>> That really depends on the system.  We can't assume that people are
>> using systems with a 100Hz clock interrupt.  More often than not
>> people are using tickless kernels these days.  That's actually the
>> problem with changing /dev/urandom to block until things are
>> initialized.
> 
> Couldn't we disable tickless until urandom has been seeded? In fact
> perhaps we should accelerate the timer interrupt rate until it has
> been seeded?
> 

The biggest problem there is that the timer interrupt adds *no* entropy
unless there is a source of asynchronicity in the system.  On PCs,
traditionally the timer has been run from a completely different crystal
(14.31818 MHz) than the CPU, which is the ideal situation, but if they
are run off the same crystal and run in lockstep, there is very little
if anything there.  On some systems, the timer may even *be* the only
source of time, and the entropy truly is zero.

	-hpa

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

#1466909

On Fri, Aug 19, 2016 at 10:20:18AM -0700, H. Peter Anvin wrote:
> On 08/18/16 22:56, Herbert Xu wrote:
> > On Thu, Aug 18, 2016 at 10:49:47PM -0400, Theodore Ts'o wrote:
> >>
> >> That really depends on the system.  We can't assume that people are
> >> using systems with a 100Hz clock interrupt.  More often than not
> >> people are using tickless kernels these days.  That's actually the
> >> problem with changing /dev/urandom to block until things are
> >> initialized.
> > 
> > Couldn't we disable tickless until urandom has been seeded? In fact
> > perhaps we should accelerate the timer interrupt rate until it has
> > been seeded?
> > 
> 
> The biggest problem there is that the timer interrupt adds *no* entropy
> unless there is a source of asynchronicity in the system.  On PCs,
> traditionally the timer has been run from a completely different crystal
> (14.31818 MHz) than the CPU, which is the ideal situation, but if they
> are run off the same crystal and run in lockstep, there is very little
> if anything there.  On some systems, the timer may even *be* the only
> source of time, and the entropy truly is zero.

Sure, but that's orthorgonal to what Ted was talking about above.

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

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

#1466197

Hi!

> > From my point of view, it would make sense to factor time from RTC and
> > mac addresses into the initial hash. Situation in the paper was so bad
> > some devices had _completely identical_ keys. We should be able to do
> > better than that.
> 
> We fixed that **years** ago.  In fact, the authors shared with me an
> early look at that paper and I implemented add_device_entropy() over
> the July 4th weekend back in 2012.  So we are indeed mixing in MAC
> addresses and the hardware clock (if it is initialized that early).
> In fact that was one of the first things that I did.  Note that this

Ok, thanks.

> > BTW... 128 interrupts... that's 1.3 seconds, right? Would it make
> > sense to wait two seconds if urandom use is attempted before it is
> > ready?
> 
> That really depends on the system.  We can't assume that people are
> using systems with a 100Hz clock interrupt.  More often than not
> people are using tickless kernels these days.  That's actually the
> problem with changing /dev/urandom to block until things are
> initialized.

Ok, let me check:

config HZ_PERIODIC
config NO_HZ_IDLE
config NO_HZ_FULL

in HZ_PERIODIC, there should be no problem.

NO_HZ_IDLE... should not be a problem either. We can easily make sure
that cpu's are not idle, something like 

     while (not_enough_entropy())
     	   schedule()

NO_HZ_FULL.... first, help text seems to imply that timer ticks still
happen when cpu is in kernel, and second, there is always one CPU that
handles timer ticks. So we are still ok.

So I believe we should add the wait to urandom. One second delay in
rare cases sounds better than alternatives.

Best regards,
									Pavel
PS: Are there systems where the timer interrupt is the only source of time?
-- 
(english) http://www.livejournal.com/~pavelmachek
(cesky, pictures) http://atrey.karlin.mff.cuni.cz/~pavel/picture/horses/blog.html

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

#1463165

On 08/11/16 05:24, Stephan Mueller wrote:
> * prevent fast noise sources from dominating slow noise sources
>   in case of /dev/random

Can someone please explain if and why this is actually desirable, and if
this assessment has been passed to someone who has actual experience
with cryptography at the professional level?

	-hpa

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

#1463415

Am Montag, 15. August 2016, 13:42:54 CEST schrieb H. Peter Anvin:

Hi H,

> On 08/11/16 05:24, Stephan Mueller wrote:
> > * prevent fast noise sources from dominating slow noise sources
> > 
> >   in case of /dev/random
> 
> Can someone please explain if and why this is actually desirable, and if
> this assessment has been passed to someone who has actual experience
> with cryptography at the professional level?

There are two motivations for that:

- the current /dev/random is compliant to NTG.1 from AIS 20/31 which requires 
(in brief words) that entropy comes from auditible noise sources. Currently in 
my LRNG only RDRAND is a fast noise source which is not auditible (and it is 
designed to cause a VM exit making it even harder to assess it). To make the 
LRNG to comply with NTG.1, RDRAND can provide entropy but must not become the 
sole entropy provider which is the case now with that change.

- the current /dev/random implementation follows the same concept with the 
exception of 3.15 and 3.16 where RDRAND was not rate-limited. In later 
versions, this was changed.

Ciao
Stephan

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

#1464202

On 08/15/16 22:45, Stephan Mueller wrote:
> Am Montag, 15. August 2016, 13:42:54 CEST schrieb H. Peter Anvin:
> 
> Hi H,
> 
>> On 08/11/16 05:24, Stephan Mueller wrote:
>>> * prevent fast noise sources from dominating slow noise sources
>>>
>>>   in case of /dev/random
>>
>> Can someone please explain if and why this is actually desirable, and if
>> this assessment has been passed to someone who has actual experience
>> with cryptography at the professional level?
> 
> There are two motivations for that:
> 
> - the current /dev/random is compliant to NTG.1 from AIS 20/31 which requires 
> (in brief words) that entropy comes from auditible noise sources. Currently in 
> my LRNG only RDRAND is a fast noise source which is not auditible (and it is 
> designed to cause a VM exit making it even harder to assess it). To make the 
> LRNG to comply with NTG.1, RDRAND can provide entropy but must not become the 
> sole entropy provider which is the case now with that change.
> 
> - the current /dev/random implementation follows the same concept with the 
> exception of 3.15 and 3.16 where RDRAND was not rate-limited. In later 
> versions, this was changed.
> 

I'm not saying it should be *sole*.  I am questioning the value in
limiting it, as it seems to me that it could only ever produce a worse
result.

	-hpa

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

#1464223

On 08/16/16 15:28, H. Peter Anvin wrote:
> On 08/15/16 22:45, Stephan Mueller wrote:
>> Am Montag, 15. August 2016, 13:42:54 CEST schrieb H. Peter Anvin:
>>
>> Hi H,
>>
>>> On 08/11/16 05:24, Stephan Mueller wrote:
>>>> * prevent fast noise sources from dominating slow noise sources
>>>>
>>>>   in case of /dev/random
>>>
>>> Can someone please explain if and why this is actually desirable, and if
>>> this assessment has been passed to someone who has actual experience
>>> with cryptography at the professional level?
>>
>> There are two motivations for that:
>>
>> - the current /dev/random is compliant to NTG.1 from AIS 20/31 which requires 
>> (in brief words) that entropy comes from auditible noise sources. Currently in 
>> my LRNG only RDRAND is a fast noise source which is not auditible (and it is 
>> designed to cause a VM exit making it even harder to assess it). To make the 
>> LRNG to comply with NTG.1, RDRAND can provide entropy but must not become the 
>> sole entropy provider which is the case now with that change.
>>
>> - the current /dev/random implementation follows the same concept with the 
>> exception of 3.15 and 3.16 where RDRAND was not rate-limited. In later 
>> versions, this was changed.
>>
> 
> I'm not saying it should be *sole*.  I am questioning the value in
> limiting it, as it seems to me that it could only ever produce a worse
> result.
> 

Also, it would be great to actually get a definition for "auditable".  A
quantum white noise source which exceeds the sampling bandwidth is an
ideal RNG; how do you "audit" that?  If what you are doing is looking
for imperfections, those imperfections can be trivially emulated.  If
what you mean is an audit on the chip or circuit level, that would
require some mechanism to know that all items were built identically
without deviation, which may be possible for intelligence agencies or
the military who have full control of their supply chain, but for anyone
else that is most likely an impossible task.  How many people are going
to crack the case and look at even a discrete transistor circuit, and
how many of *those* are going to be able to discern if that circuit is
subject to RF capture, or its output even used?

I have been trying to figure out how to reasonably solve this problem
for a long time now, and it is not just a problem for RDSEED (RDRAND is
a slightly different beast.)  The only reason RDSEED exposes the problem
particularly harshly is because it is extremely high bandwidth compared
to other noise sources and it is architecturally integrated into the
CPU, but the same would apply to an external noise generator connected
via PCIe, for example.

Incidentally, I am hoping -- and this is a personal statement and
nothing official from Intel -- that at some future date RDRAND (not
RDSEED) will be fast enough that it can completely replace even
prandom_u32(), which I really hope can be non-controversial as
prandom_u32() isn't cryptographically strong in the first place.

	-hpa

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

#1464324

Am Dienstag, 16. August 2016, 15:28:45 CEST schrieb H. Peter Anvin:

Hi Peter,

> > 
> > There are two motivations for that:
> > 
> > - the current /dev/random is compliant to NTG.1 from AIS 20/31 which
> > requires (in brief words) that entropy comes from auditible noise
> > sources. Currently in my LRNG only RDRAND is a fast noise source which is
> > not auditible (and it is designed to cause a VM exit making it even
> > harder to assess it). To make the LRNG to comply with NTG.1, RDRAND can
> > provide entropy but must not become the sole entropy provider which is
> > the case now with that change.
> > 
> > - the current /dev/random implementation follows the same concept with the
> > exception of 3.15 and 3.16 where RDRAND was not rate-limited. In later
> > versions, this was changed.
> 
> I'm not saying it should be *sole*.  I am questioning the value in
> limiting it, as it seems to me that it could only ever produce a worse
> result.

It is not about the limiting of the data. It is all about the entropy estimate 
for those noise sources and how they affect the entropy estimator behind /dev/
random. If that fast noise source injects large amount of data but does not 
increase the entropy estimator, it is of no concern.

Ciao
Stephan

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web