Am Mittwoch, 19. Juli 2017, 19:26:03 CEST schrieb Theodore Ts'o: Hi Theodore, > On Wed, Jul 19, 2017 at 08:22:18AM +0200, Stephan Müller wrote: > > In the email [1] I have expressed the core concerns I see -- none of them > > address the need to keep the Jitter RNG as one noise source. To address > > those, a very deep dive into random.c needs to be made. > > That's simply not true. The other issues besides the Jitter RNG are > really nits. > > One of your complaints is the fact that we collect both interrupt > timing and HID/block timings. First of all, we could eliminate the > HID/block timings since in practice we get the vast majority of our > entropy from the interrupt timing. I keep it because we have a real > theoretical basis for their being unpredictability from the HID/block > timings. For example, [1]. > > [1] http://world.std.com/~dtd/random/forward.pdf > > The fact that there might be double count from the perspective of > entropy is not really an issue because we do a "fast mix" of 64 > interrupts before we mix into the primary interrupt pool. And when we > do mix into the primary pool we count that only as a single bit of > entropy. The reason why I'm being super cautious here is because some > of these interrupts might be timer interrupts, or come from other > sources that might be correlated to the clock interrupt. The > conservative assumption here is that at least one of the interrupts > out of 64, on average, will come from something that the adversary can > not anticipate, such as coming from a NIC or wireless device, and that > we will get at least one bit's worth of unpredictability. > > The fact that we also mix in the jiffies plus the keyboard/mouse scan > code, is something that happens immediately. So even if you think we > should not count the fast mix interrupt count, the fact that we mix > the timing values from 64 interrupts before we credit the entropy > counter by a single bit is sufficiently conservative; we're talking > about 1/64th of a bit here. I concur with your rationale where de-facto the correlation is effect is diminished and eliminated with the fast_pool and the minimal entropy estimation of interrupts. But it does not address my concern. Maybe I was not clear, please allow me to explain it again. We have lots of entropy in the system which is discarded by the aforementioned approach (if a high-res timer is present -- without it all bets are off anyway and this should be covered in a separate discussion). At boot time, this issue is fixed by injecting 256 interrupts in the CRNG and consider it seeded. But at runtime, were we still need entropy to reseed the CRNG and to supply / dev/random. The accounting of entropy at runtime is much too conservative compared to any types of measurements that were conducted on bare metal or virtualized environment or on different architectures (if requested, I can surely share the test code and results in addition to already published studies -- see [1] table 1, 2 and 3 with figure 3.2 to get an idea). As long as a high-resolution time stamp is present, interrupts do provide much more than 1/64th bit of entropy per occurrence. [1] http://www.chronox.de/lrng/doc/lrng.pdf The implementation that was precisely outlined above present in random.c however does not allow revaluing the amount of entropy present in interrupts to a higher level simply because then the correlation issue kicks in. Thus, when we want to re-value the interrupts with a higher level of entropy, we need to take out the high-resolution time stamp (and thus the more or less sole effective entropy provider for add_[disk|input]_randomness). You mentioned that you are super conservative for interrupts due to timer interrupts. In all measurements on the different systems I conducted, I have not seen that the timer triggers an interrupt picked up by add_interrupt_randomness. For the sake of discussion, let us assume that such timer interrupts are present for a worst-case assessment. Such timer interrupts by nature should occur very periodically. Thus, it should be easy to detect them. IMHO the suggested stuck test in the LRNG exactly covers that scenario: only if the 1st, 2nd and 3rd derivative of the time stamp is non- zero, the interrupt time stamp is considered to deliver entropy. Thus, when revaluing the interrupt entropy, and removing the high-res timer from HID/block devices, the entropy heuristic in add_timer_randomness can go. As we have no formal model about entropy to begin with, we can only assume and hope we underestimate entropy with the entropy heuristic. Thus, a precise entropy update with the asymptotic calculation in credit_entropy_bits may also not really be helpful and could be discarded. > > But if you **really** think mixing in the timing of the HID event > (gathered via a different mechanism --- jiffies vs cycle counter, and > including the the keyboard scan), a patch to disable > add_keyboard_randomness() is pretty trivial. It doesn't justify a > complete rewrite of the random core. > > (BTW, granted this is anecdata, but on my laptop, the CRNG is fully > initialized before systemd has even started and before the root file > system is mounted. Agreed, I see that too. And as mentioned above, this is how I think it is appropriate. This behavior is very similar to what I see on my LRNG. > And after that point the entropy initialization > only matters for the legacy apps that use /dev/random, which doesn't > even exist in your proposed RNG, since everything just uses a > ChaCha20-based CRNG.) > I am not sure I understand the last statement. The blocking_pool (or the ChaCha20 DRNG in my LRNG) feeding /dev/random is simply a deterministic RNG with prediction resistance (in SP800-90A-speak). I.e. when one random bit shall be generated, one bit of entropy from the noise sources needs to go in. Whether you have a blocking_pool or a normal DRNG to feed /dev/random does not matter as long as it only delivers as many bits as went in as entropy. > > Another one of your complaints is a straw-man argument ("I understand > that this pathological case is not present for the legacy > /dev/random..."). First of all, how we do entropy estimation after > the CRNG boot is far less important, because the primary recommended > interface is /dev/urandom or better yet getrandom(2). Secondly, we > *don't* allow transfer of small quantums of entropy. There is a > minimum transfer limit of 64 bits, and that can easily be increased to > 128 bits if one really cared. I've never really considered recovery > from state compromise to be that important, but if one did care, > increasing that limit is a two line patch. _xfer_secondary_pool says: /* pull at least as much as a wakeup */ bytes = max_t(int, bytes, random_read_wakeup_bits / 8); This determines the minimum amount. random_read_wakeup_bits can be changed by user space: { .procname = "read_wakeup_threshold", .data = &random_read_wakeup_bits, .maxlen = sizeof(int), .mode = 0644, .proc_handler = proc_dointvec_minmax, .extra1 = &min_read_thresh, .extra2 = &max_read_thresh, }, min_read_thresh is 8. Thus, the minimum amount of transfer is 1 byte as far as I read. I concur, however, that the default is 64 (bits). This is what I would suggest to have changed to, say, the absolute minimum of 64 or 128 bits. Finally, I still think it is helpful to allow (not mandate) to involve the kernel crypto API for the DRNG maintenance (i.e. the supplier for /dev/random and /dev/urandom). The reason is that now more and more DRNG implementations in hardware pop up. Why not allowing them to be used. I.e. random.c would only contain the logic to manage entropy but uses the DRNG requested by a user. In addition allowing a replacement of the DRNG component (at compile time at least) may get us away from having a separate DRNG solution in the kernel crypto API. Some users want their chosen or a standardized DRNG to deliver random numbers. Thus, we have several DRNGs in the kernel crypto API which are seeded by get_random_bytes. Or in user space, many folks need their own DRNG in user space in addition to the kernel. IMHO this is all a waste. If we could use the user-requested DRNG when producing random numbers for get_random_bytes or /dev/urandom or getrandom. Ciao Stephan
