Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)
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
Re: [ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)
>> > 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)
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)
> 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)
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)
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
[ANNOUNCE] /dev/random - a new approach (code for 4.11-rc1)
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