[ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Stephan Müller]

Hi,

The patch set that can be downloaded at [1] 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 or Device Mapper targets. 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 
performance improvements are visible at /dev/urandom and get_random_bytes.

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

The LRNG has a flexible design by allowing an easy replacement of the
deterministic random number generator component. Currently implemented DRNGs
are an SP800-90A DRBG and a ChaCha20 DRNG.

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

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

Ciao
Stephan

Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Jason A. Donenfeld]

Hey Stephan,

Have you considered submitting this without so many options? For
example -- just unconditionally using ChaCha20 instead of the
configurable crypto API functions? And either removing the FIPS140
compliance code, and either unconditionally including it, or just
getting rid of it? And finally just making this a part of the kernel
directly, instead of adding this as a standalone optional component?

Jason

Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Stephan Müller]

Am Freitag, 17. März 2017, 16:31:29 CET schrieb Jason A. Donenfeld:

Hi Jason,

> Hey Stephan,
> 
> Have you considered submitting this without so many options? For
> example -- just unconditionally using ChaCha20 instead of the
> configurable crypto API functions? And either removing the FIPS140
> compliance code, and either unconditionally including it, or just
> getting rid of it? And finally just making this a part of the kernel
> directly, instead of adding this as a standalone optional component?

Submitting that with various options removed is no problem as the core concept 
of my implementation is to be flexible to allow folks to easily add new noise 
sources or a DRNG replacement.

Yet, there are reasons for the different options:

- some folks want to use a known good and proven DRNG for post-processing 
(hence the offer for using an SP800-90A DRBG)

- some folks want a DRNG that is not tied to the kernel crypto API (hence the 
offer for the ChaCha20 DRNG)

- some folks need the FIPS continuous self test and some do not.

The idea for the solution in the LRNG code is that a user shall not be 
involved with these compile-time decisions. All options that are present are 
based on other kernel configuration options:

- if the kernel crypto API is present and the SP800-90A DRBG is compiled, then 
the LRNG uses the SP800-90A DRBG

- as a user may compile in different types of the SP800-90A DRBG, the LRNG 
will use the one that is available

- if no kernel crypto API is compiled, it uses the ChaCha20 DRNG

- if FIPS support is not compiled, the FIPS continuous test is not compiled

Thus, a user does not get in touch with all the options in the LRNG code. 
Shouldn't that be a good argument to keep these options?

I would like to add the LRNG code directly to the kernel and I can offer an 
official patch instead of such out-of-tree code. However, in the past I got 
shot down when I suggested an inclusion.

Ciao
Stephan

Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Jeffrey Walton]

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

A quick comment about SP800 and the hardware instructions... RDSEED is
2 to 5 times slower than RDRAND on Intel hardware, depending on the
architecture and microarchitecture. AMD's implementation of RDRAND is
orders of magnitude slower than Intel's. Testing on an Athlon 845 X4
(Bulldozer v4) @ 3.5 GHz shows it runs between 4100 and 4500 cycles
per byte. It works out to be about 1 MiB/s.

While the LRNG may reach a cryptographically acceptable seed level
much earlier then the existing /dev/random, it may not be early
enough. Some components, like systemd, will ask for random numbers and
truck-on even if they are not available. Systemd does not block or
wait if get_random_bytes fails to produce. In the bigger picture,
don't expect that software layered above will do the expected thing in
all cases.

Jeff

Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Stephan Müller]

Am Samstag, 18. März 2017, 11:11:57 CET schrieb Jeffrey Walton:

Hi Jeffrey,

> > The design and implementation is driven by a set of goals described in [2]
> > that the LRNG completely implements. Furthermore, [2] includes a
> > comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
> > AIS20/31.
> 
> A quick comment about SP800 and the hardware instructions... RDSEED is
> 2 to 5 times slower than RDRAND on Intel hardware, depending on the
> architecture and microarchitecture.

I am not sure how this statement relates to the quote above. RDSEED is the 
CBC-MACed output of the flip-flop providing the raw noise.

RDRAND is the output of the SP800-90A CTR DRBG that is seeded by the CBC-MAC 
that also feeds RDSEED. Thus, RDSEED is as fast as the noise source where 
RDRAND is a pure deterministic RNG that tries to be (re)seeded as often as 
possible.

Both instructions are totally unrelated to the SP800-90A DRBG available to the 
Linux kernel.

> AMD's implementation of RDRAND is
> orders of magnitude slower than Intel's. Testing on an Athlon 845 X4
> (Bulldozer v4) @ 3.5 GHz shows it runs between 4100 and 4500 cycles
> per byte. It works out to be about 1 MiB/s.

Please consider my speed measurements given in [1] section 3.4.6. The DRBG is 
just slightly slower than the ChaCha20 on small block sizes and twice as fast 
on larger block sizes using AES-NI on x86. As the DRBG implementation has no 
relationship to the RDRAND DRBG, I am not sure about your argument.

When I refer to hardware instructions and SP800-90A, I consider the SP800-90A 
DRBG implementation in crypto/drbg.c provided with the kernel crypto API which 
uses the raw AES/SHA cipher implementation provided by the kernel crypto API. 
Here, the implementation uses the fastest one, such as the AES-NI raw AES 
implementation on x86. Or it uses the ARM NEON SHA implementation for the 
HMAC/Hash DRBG.
> 
> While the LRNG may reach a cryptographically acceptable seed level
> much earlier then the existing /dev/random, it may not be early
> enough.

The LRNG will initialize as a DRBG during late_initcall. Thus, the DRBG is 
always present if user space calls.

However, during kernel boot, there is of course a need for earlier randomness. 
This is covered by the init DRNG documented in [1] section 2.10.

> Some components, like systemd, will ask for random numbers and
> truck-on even if they are not available. Systemd does not block or
> wait if get_random_bytes fails to produce. In the bigger picture,
> don't expect that software layered above will do the expected thing in
> all cases.

The LRNG works as a full ABI and API replacement for the current /dev/random 
implementation. I run it on my servers. It delivers random data for all use 
cases, during early kernel and user space boot as well as during runtime.

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


Ciao
Stephan

Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Jeffrey Walton]

>> > The design and implementation is driven by a set of goals described in [2]
>> > that the LRNG completely implements. Furthermore, [2] includes a
>> > comparison with RNG design suggestions such as SP800-90B, SP800-90C, and
>> > AIS20/31.
>>
>> A quick comment about SP800 and the hardware instructions... RDSEED is
>> 2 to 5 times slower than RDRAND on Intel hardware, depending on the
>> architecture and microarchitecture.
>
> I am not sure how this statement relates to the quote above. RDSEED is the
> CBC-MACed output of the flip-flop providing the raw noise.
>
> RDRAND is the output of the SP800-90A CTR DRBG that is seeded by the CBC-MAC
> that also feeds RDSEED. Thus, RDSEED is as fast as the noise source where
> RDRAND is a pure deterministic RNG that tries to be (re)seeded as often as
> possible.
>
> Both instructions are totally unrelated to the SP800-90A DRBG available to the
> Linux kernel.

SP800-90A requires an entropy source to bootstrap the Hash, HMAC and
CTR generators. That is, the Instantiate and Reseed functions need an
approved source of entropy. Both RDRAND and RDSEED are approved for
Intel chips. See SP800-90A, Section 8.6.5
(http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf).

Jeff

Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)

[Stephan Müller]

Am Samstag, 18. März 2017, 14:43:18 CET schrieb Jeffrey Walton:

Hi Jeffrey,

> > I am not sure how this statement relates to the quote above. RDSEED is the
> > CBC-MACed output of the flip-flop providing the raw noise.
> > 
> > RDRAND is the output of the SP800-90A CTR DRBG that is seeded by the
> > CBC-MAC that also feeds RDSEED. Thus, RDSEED is as fast as the noise
> > source where RDRAND is a pure deterministic RNG that tries to be
> > (re)seeded as often as possible.
> > 
> > Both instructions are totally unrelated to the SP800-90A DRBG available to
> > the Linux kernel.
> 
> SP800-90A requires an entropy source to bootstrap the Hash, HMAC and
> CTR generators. That is, the Instantiate and Reseed functions need an
> approved source of entropy. Both RDRAND and RDSEED are approved for
> Intel chips. See SP800-90A, Section 8.6.5
> (http://csrc.nist.gov/publications/nistpubs/800-90A/SP800-90A.pdf).

I am aware that SP800-90A makes the claim of having an approved noise source. 
But as of now, there is no such thing.

NIST is aware of that issue. To cover that issue during a FIPS 140-2 
validation, you have to prove your noise sources to be compliant to SP800-90B. 
I performed such noise source assessments as part of the FIPS 140-2 
validations of the Intel Sunrise Point or the Qualcomm HW DRBG FIPS 140-2 
validations. Also, I completed such assessments for the FIPS 140-2 validations 
of the legady /dev/random covering numerous Linux-based cryptographic modules 
over the last couple of years.

To get a glimpse of how such assessments for FIPS 140-2 are conducted, please 
have a look at the assessment [1] section 5.3.2.1 starting on page 72 in the 
lower half (note that I was the main author of this study). To be honest, the 
assessment in [1] section 5.5 was the main motivation for my LRNG 
implementation.

That said, [2] section 3.4.1, starting at page 34 bottom, you see the same 
SP800-90B test approach that was equally accepted by NIST during formal FIPS 
140-2 validations of other noise sources. Hence, I would conclude that my 
suggested implementation of the noise source is appropriate for a DRBG to be 
compliant to section 8.6.5 of SP800-90A.

But you mention a very important topic: is it and how is it ensured that the 
DRBG is appropriately seeded. This issue is discussed in [2] section 2.1 which 
explains the initial, minimal and full seeded stages of the DRBG.

[1] https://www.bsi.bund.de/SharedDocs/Downloads/DE/BSI/Publikationen/Studien/
ZufallinVMS/Randomness-in-VMs.pdf

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

Ciao
Stephan