* is "premature next" a real world rng concern, or just an academic exercise? @ 2022-04-27 13:58 Jason A. Donenfeld 2022-04-28 4:26 ` Nadia Heninger ` (2 more replies) 0 siblings, 3 replies; 15+ messages in thread From: Jason A. Donenfeld @ 2022-04-27 13:58 UTC (permalink / raw) To: nadiah, noahsd, dodis, tessaro, torvalds, djb, tytso, jeanphilippe.aumasson, jann, keescook, gregkh, peter Cc: linux-crypto, linux-kernel Hi folks, The Linux kernel RNG currently pretends to care about the "premature next" RNG threat model. I'm wondering whether this is sensible and corresponds to anything real. "Premature next" is the scenario in which: - Attacker compromises the current state of a fully initialized RNG with a wild 'n crazy kernel infoleak. - New bits of entropy are added directly to the key used to generate the /dev/urandom stream, without any buffering or pooling. - Attacker then, somehow having read access to /dev/urandom, samples RNG output and brute forces the individual new bits that were added. - Result: the RNG never "recovers" from the initial compromise, a so-called violation of what academics term "post-compromise security". (Note that this is a different scenario from "premature first", which relates to boot-time concerns; this email isn't about "premature first".) There are other varied scenarios to this, usually involving some combination of: a) Attacker has access to /dev/urandom output continuously or at some interesting interval. b) Attacker controls one or more entropy sources providing some subset of varying size of those new bits of entropy. The Linux kernel currently pretends to mitigate this for scenario (a) at least, using "entropy estimation". The idea is that it waits until 256 estimated "bits" of new entropy are pooled before mixing them into the key used to generate the /dev/urandom stream. Never mind the fact that entropy estimation is an impossible proposition and thus flawed, it certainly does nothing in the way of (b), since there's just one pool. The NT kernel is a bit more robust, by way of their Fortuna RNG, in which there are several pools, and entropy sources round-robin into those pools. When it's time to reseed, the first pool is used every time, the second pool is used every other time, the third pool is used every third time, the forth pool is used every forth time, and so on. In theory this should handle both (a) and (b) without needing entropy estimation, and this sort of scheduler prompts interesting questions for academics with regards to different types of scheduling (a random walk instead of round-robin? sounds like a paper topic.) and trying to characterize the rate of inputs (continuous? sporadic? modelable?). While the above "problem" maps pretty clearly to things academics are interested in -- post-compromise security for a system with a clear model and various creative solutions -- I'm wondering whether any of this matters in the real world. From conversations over the last several months with various security experts and cryptographers, including those who work on the "premature next" problem, the impression I get is that nobody actually thinks this matters back on planet Earth, even from people who write papers on it. So the purpose of this email is to solicit feedback on whether anybody can think of a plausible scenario in which it does matter. If it does matter, the next step will be to determine how much it matters exactly, in order for me to gauge the cost-benefit ratio of mitigating the issue more robustly in the kernel (e.g. Fortuna requires non-zero code complexity; does the benefit outweigh the cost of such complexity?). On the other hand, if nobody can think of any reason why this matters, then there are some nice improvements that I'm eager to make in a different direction. To review, this attack model concerns: - An attacker who compromises the RNG at one point in time via a kernel infoleak. - After that infoleak, the attacker somehow no longer has access to the system, but can prevent the RNG from recovering from the compromise by having pretty rapid access to /dev/urandom (and possibly also having compromised zero or more entropy sources). The questions are thus: 1) When does an attacker with a kernel infoleak exercise it just once, and then attempt to maintain the leak with some sort of network access to lots of /dev/urandom output (from, e.g., large nonces)? 2) Or, if it's a local user attacker, when does that attacker infoleak once, but rather than just running the exploit again, cats /dev/urandom continuously? 3) More broadly speaking, what kernel infoleak is actually acceptable to the degree that anybody would feel okay in the first place about the system continuing to run after it's been compromised? Looking forward to hearing opinions on this. There's certainly a lot to split hairs about above -- incomplete/inaccurate description of the "premature next" model, what Fortuna actually achieves, my entropy estimation remark, and so forth -- but hopefully this at least throws enough things at the board to begin the discussion. Is "premature next" just an academic exercise, rather than a real world RNG concern? Regards, Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-04-27 13:58 is "premature next" a real world rng concern, or just an academic exercise? Jason A. Donenfeld @ 2022-04-28 4:26 ` Nadia Heninger 2022-04-30 2:08 ` Sandy Harris 2022-05-01 0:49 ` tytso 2 siblings, 0 replies; 15+ messages in thread From: Nadia Heninger @ 2022-04-28 4:26 UTC (permalink / raw) To: Jason A. Donenfeld Cc: noahsd, dodis, tessaro, torvalds, djb, tytso, jeanphilippe.aumasson, jann, keescook, gregkh, peter, linux-crypto, linux-kernel Hi Jason and others, (Resending as plain text, I hope.) I expressed my opinion on this to Jason at RWC but I'll summarize here: from my perspective, entropy should be added to the pool without waiting, because giving output from an unseeded pool is worse than giving output from a poorly seeded pool or the hypothetical risk of the "premature next" attack scenario Jason outlines. Concretely, the kind of feasible exploits I can imagine resulting in a state compromise would be some kind of side-channel attack: spectre or other MDS attacks, maybe something involving SGX, maybe a plain cache attack. Here's an example: https://eprint.iacr.org/2019/996.pdf For the purposes of an academic proof of concept targeting cryptographic network protocols, the attack sequence would be 1. attacker compromises state with a side-channel attack 2. attacker observes nonces in network traffic to track state 3. attacker uses state to compromise some valuable secret. In this order of events, it would be unfortunate if only a small amount of entropy trickled in between steps 1 and 2 and between 2 and 3 so that the attacker could brute force the new state, but it would also be unfortunate if no entropy was added to the pool so that the state compromise required no brute forcing to reveal the secrets. Here's an attempt at scaling this attack up to match question #1 that Jason poses: Attacker exercises a cross-VM side-channel attack to recover urandom state from a VM serving lots of network requests. Once the attacker has recovered the state, the attacker observes the network traffic from the VM. Each nonce includes a brute-forceable amount of entropy that allows the attacker to recover the next state, and then the attacker recovers the secret keys from all the following network handshakes in sequence. If the RNG attempts to enforce post-compromise security by pooling entropy before adding it to the stream, all the traffic sent between compromise and state update is still recoverable by the attacker. But then, Jason's question #3 is valid: in this model, the attacker could just run their exploit again to recover the new state. In contrast, an unseeded RNG is much easier to exploit, and we *know* it has happened in practice, and still happens. Nadia On Wed, Apr 27, 2022 at 6:59 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: > > Hi folks, > > The Linux kernel RNG currently pretends to care about the "premature > next" RNG threat model. I'm wondering whether this is sensible and > corresponds to anything real. > > "Premature next" is the scenario in which: > - Attacker compromises the current state of a fully initialized RNG with > a wild 'n crazy kernel infoleak. > - New bits of entropy are added directly to the key used to generate the > /dev/urandom stream, without any buffering or pooling. > - Attacker then, somehow having read access to /dev/urandom, samples RNG > output and brute forces the individual new bits that were added. > - Result: the RNG never "recovers" from the initial compromise, a > so-called violation of what academics term "post-compromise security". > > (Note that this is a different scenario from "premature first", which > relates to boot-time concerns; this email isn't about "premature > first".) > > There are other varied scenarios to this, usually involving some > combination of: > a) Attacker has access to /dev/urandom output continuously or at some > interesting interval. > b) Attacker controls one or more entropy sources providing some subset > of varying size of those new bits of entropy. > > The Linux kernel currently pretends to mitigate this for scenario (a) at > least, using "entropy estimation". The idea is that it waits until 256 > estimated "bits" of new entropy are pooled before mixing them into the > key used to generate the /dev/urandom stream. Never mind the fact that > entropy estimation is an impossible proposition and thus flawed, it > certainly does nothing in the way of (b), since there's just one pool. > > The NT kernel is a bit more robust, by way of their Fortuna RNG, in > which there are several pools, and entropy sources round-robin into > those pools. When it's time to reseed, the first pool is used every > time, the second pool is used every other time, the third pool is used > every third time, the forth pool is used every forth time, and so on. In > theory this should handle both (a) and (b) without needing entropy > estimation, and this sort of scheduler prompts interesting questions for > academics with regards to different types of scheduling (a random walk > instead of round-robin? sounds like a paper topic.) and trying to > characterize the rate of inputs (continuous? sporadic? modelable?). > > While the above "problem" maps pretty clearly to things academics are > interested in -- post-compromise security for a system with a clear > model and various creative solutions -- I'm wondering whether any of > this matters in the real world. From conversations over the last several > months with various security experts and cryptographers, including those > who work on the "premature next" problem, the impression I get is that > nobody actually thinks this matters back on planet Earth, even from > people who write papers on it. > > So the purpose of this email is to solicit feedback on whether anybody > can think of a plausible scenario in which it does matter. If it does > matter, the next step will be to determine how much it matters exactly, > in order for me to gauge the cost-benefit ratio of mitigating the issue > more robustly in the kernel (e.g. Fortuna requires non-zero code > complexity; does the benefit outweigh the cost of such complexity?). On > the other hand, if nobody can think of any reason why this matters, then > there are some nice improvements that I'm eager to make in a different > direction. > > To review, this attack model concerns: > - An attacker who compromises the RNG at one point in time via a kernel > infoleak. > - After that infoleak, the attacker somehow no longer has access to the > system, but can prevent the RNG from recovering from the compromise by > having pretty rapid access to /dev/urandom (and possibly also having > compromised zero or more entropy sources). > > The questions are thus: > > 1) When does an attacker with a kernel infoleak exercise it just once, > and then attempt to maintain the leak with some sort of network access > to lots of /dev/urandom output (from, e.g., large nonces)? > > 2) Or, if it's a local user attacker, when does that attacker infoleak > once, but rather than just running the exploit again, cats /dev/urandom > continuously? > > 3) More broadly speaking, what kernel infoleak is actually acceptable to > the degree that anybody would feel okay in the first place about the > system continuing to run after it's been compromised? > > Looking forward to hearing opinions on this. There's certainly a lot to > split hairs about above -- incomplete/inaccurate description of the > "premature next" model, what Fortuna actually achieves, my entropy > estimation remark, and so forth -- but hopefully this at least throws > enough things at the board to begin the discussion. > > Is "premature next" just an academic exercise, rather than a real world > RNG concern? > > Regards, > Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-04-27 13:58 is "premature next" a real world rng concern, or just an academic exercise? Jason A. Donenfeld 2022-04-28 4:26 ` Nadia Heninger @ 2022-04-30 2:08 ` Sandy Harris 2022-05-01 0:49 ` tytso 2 siblings, 0 replies; 15+ messages in thread From: Sandy Harris @ 2022-04-30 2:08 UTC (permalink / raw) To: Jason A. Donenfeld Cc: nadiah, noahsd, dodis, tessaro, Linus Torvalds, djb, Ted Ts'o, Jean-Philippe Aumasson, Jann Horn, Kees Cook, Greg Kroah-Hartman, peter, Linux Crypto Mailing List, LKML Jason A. Donenfeld <Jason@zx2c4.com> wrote: > The Linux kernel RNG currently pretends to care about the "premature > next" RNG threat model. I'm wondering whether this is sensible and > corresponds to anything real. > > "Premature next" is the scenario in which: > - Attacker compromises the current state of a fully initialized RNG with > a wild 'n crazy kernel infoleak. > - New bits of entropy are added directly to the key used to generate the > /dev/urandom stream, without any buffering or pooling. So don't do that, then. Keep a separate input pool/buffer and put only hashed outputs from ir into the output pool. > - Attacker then, somehow having read access to /dev/urandom, samples RNG > output and brute forces the individual new bits that were added. > - Result: the RNG never "recovers" from the initial compromise, a > so-called violation of what academics term "post-compromise security". Use chunks big enough for "catastrophic reseeding", impractical to brute force, at least 64 bits & preferably larger. > Fortuna requires non-zero code > complexity; does the benefit outweigh the cost of such complexity? I'd say certainly not. > The questions are thus: > ... > 3) More broadly speaking, what kernel infoleak is actually acceptable to > the degree that anybody would feel okay in the first place about the > system continuing to run after it's been compromised? If we have a good entropy source -- e.g. running on an Intel CPU & consider their RNG instruction trustworthy, or in a VM & trust the host -- then we should be able to guarantee recovery at the next reseeding. Just dump at least 128 bits from that source into the input pool before hashing. The interesting question is whether & how soon we can guarantee recovery if no such source is available, we rely only on entropy gathering from interrupts, with or without the gcc latent entropy plugin. > Is "premature next" just an academic exercise, rather than a real world > RNG concern? No. ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-04-27 13:58 is "premature next" a real world rng concern, or just an academic exercise? Jason A. Donenfeld 2022-04-28 4:26 ` Nadia Heninger 2022-04-30 2:08 ` Sandy Harris @ 2022-05-01 0:49 ` tytso 2022-05-01 11:16 ` Jason A. Donenfeld 2 siblings, 1 reply; 15+ messages in thread From: tytso @ 2022-05-01 0:49 UTC (permalink / raw) To: Jason A. Donenfeld Cc: nadiah, noahsd, dodis, tessaro, torvalds, djb, jeanphilippe.aumasson, jann, keescook, gregkh, peter, linux-crypto, linux-kernel On Wed, Apr 27, 2022 at 03:58:51PM +0200, Jason A. Donenfeld wrote: > > 3) More broadly speaking, what kernel infoleak is actually acceptable to > the degree that anybody would feel okay in the first place about the > system continuing to run after it's been compromised? A one-time kernel infoleak where this might seem most likely is one where memory is read while the system is suspended/hibernated, or if you have a VM which is frozen and then replicated. A related version is one where a VM is getting migrated from one host to another, and the attacker is able to grab the system memory from the source "host" after the VM is migrated to the destination "host". Merely reseeding the CRNG from the input pool isn't going to help, since the attacker could have grabed not only the CRNG pool, but the input pool as well. In the case where the guest image is "freeze dried" and then reconstituted multiple times, and where the attacker hasn't actually grabed state, then all you need to do is to mix in some kind of nonce, such as the current time (which hopefully will vary across different VM "reconstitutions"), or some kind none (for example the VM ID, if that can be obtained somehow). But if the attacker can actually obtain internal state from one reconstituted VM, and use that to attack another reconstituted VM, and the attacker also knows what the nonce or time seed that was used so that different reconstituted VMs will have unique CRNG streams, this might be a place where the "premature next" attack might come into play. The simplest mitigation is if you have some kind of external RNG which you can actually trust, or at least mostly trust. e.g., either some kind of CPU-based hwrng, such as RDRAND, or a hypervisor-provided hwrng, such as Virtio-RNG. And if the hypervisor is going to playing games with reconstituting freeze-dried VM's, I'd argue it can d*mned well provide a virtio-rng facility. And the same argument could be made just as easily with live migration scenario, with the hypervisor providing some kind of notification that VM had just gotten live migrated, so it should really reseed from the virtio-rng facility right away. That leaves the variant where the kernel infoleak happened while the system was suspended. And in that case, we're talking about an attacker which had physical access to the machine (say, an "evil maid" attack while the laptop was left suspended in a hotel room in Moscow or Beijing). And in that case, there are probably far simpler ways that an "evil amid" with temporary physical access to the hardware could compromise the secuity of the unattended laptop. > Is "premature next" just an academic exercise, rather than a real world > RNG concern? I'd say it's mostly an academic exercise. Given our current model, where we only reseed the CRNG periodically, and we're hopefully getting some amount of uncertainty into the input pool, there will be a certain amount of "catastrophic reseeding" going on, which I don't think is a bad thing. But personally, I don't think the complexity of N levels of Fortuna pools are worth it. - Ted ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-01 0:49 ` tytso @ 2022-05-01 11:16 ` Jason A. Donenfeld [not found] ` <CAMvzKsiA52Si=PzOJXYwGSA1WUz-1S0A8cpgRJWDzpMkfFbX+Q@mail.gmail.com> 0 siblings, 1 reply; 15+ messages in thread From: Jason A. Donenfeld @ 2022-05-01 11:16 UTC (permalink / raw) To: tytso Cc: nadiah, noahsd, dodis, tessaro, torvalds, djb, jeanphilippe.aumasson, jann, keescook, gregkh, peter, linux-crypto, linux-kernel Hi Ted, That's a useful analysis; thanks for that. On Sat, Apr 30, 2022 at 05:49:55PM -0700, tytso wrote: > On Wed, Apr 27, 2022 at 03:58:51PM +0200, Jason A. Donenfeld wrote: > > > > 3) More broadly speaking, what kernel infoleak is actually acceptable to > > the degree that anybody would feel okay in the first place about the > > system continuing to run after it's been compromised? > > A one-time kernel infoleak where this might seem most likely is one > where memory is read while the system is suspended/hibernated, or if > you have a VM which is frozen and then replicated. A related version > is one where a VM is getting migrated from one host to another, and > the attacker is able to grab the system memory from the source "host" > after the VM is migrated to the destination "host". You've identified ~two places where compromises happen, but it's not an attack that can just be repeated simply by re-running `./sploit > state`. 1) Virtual machines: It seems like after a VM state compromise during migration, or during snapshotting, the name of the game is getting entropy into the RNG in a usable way _as soon as possible_, and not delaying that. This is Nadia's point. There's some inherent tension between waiting some amount of time to use all available entropy -- the premature next requirement -- and using everything you can as fast as you can because your output stream is compromised/duplicated and that's very bad and should be mitigated ASAP at any expense. [I'm also CC'ing Tom Risenpart, who's been following this thread, as he did some work regarding VM snapshots and compromise, and what RNG recovery in that context looks like, and arrived at pretty similar points.] You mentioned virtio-rng as a mitigation for this. That works, but only if the data read from it are actually used rather quickly. So probably /waiting/ to use that is suboptimal. One of the things added for 5.18 is this new "vmgenid" driver, which responds to fork/snapshot notifications from hypervisors, so that VMs can do something _immediately_ upon resumption/migration/etc. That's probably the best general solution to that problem. Though vmgenid is supported by QEMU, VMware, Hyper-V, and hopefully soon Firecracker, there'll still be people that don't have it for one reason or another (and it has to be enabled manually in QEMU with `-device vmgenid,guid=auto`; perhaps I should send a patch adding that to some default machine types). Maybe that's their problem, but I take as your point that we can still try to be less bad than otherwise by using more entropy more often, and not delaying as the premature next model requirements would have us do. 2) Suspend / hibernation: This is kind of the same situation as virtual machines, but the particulars are a little bit different: - There's no hypervisor giving us new seed material on resumption like we have with VM snapshots and vmgenid; but - We also always know when it happens, because it's not transparent to the OS, so at least we can attempt to do something immediately like we do with the vmgenid driver. Fortunately, most systems that are doing suspend or hibernation these days also have a RDRAND-like thing. It seems like it'd be a good idea for me to add a PM notifier, mix into the pool both ktime_get_boottime_ns() and ktime_get(), in addition to whatever type info I get from the notifier block (suspend vs hibernate vs whatever else) to account for the amount of time in the sleeping state, and then immediately reseed the crng, which will pull in a bunch of RDSEED/RDRAND/RDTSC values. This way on resumption, the system is always in a good place. I did this years ago in WireGuard -- clearing key material before suspend -- and there are some details around autosuspend (see wg_pm_notification() in drivers/net/wireguard/device.c), but it's not that hard to get right, so I'll give it a stab and send a patch. > But if the attacker can actually obtain internal state from one > reconstituted VM, and use that to attack another reconstituted VM, and > the attacker also knows what the nonce or time seed that was used so > that different reconstituted VMs will have unique CRNG streams, this > might be a place where the "premature next" attack might come into > play. This is the place where it matters, I guess. It's also where the tradeoff's from Nadia's argument come into play. System state gets compromised during VM migration / hibernation. It comes back online and starts doling out compromised random numbers. Worst case scenario is there's no RDRAND or vmgenid or virtio-rng, and we've just got the good old interrupt handler mangling cycle counters. Choices: A) recover from the compromise /slowly/ in order to mitigate premature next, or B) recover from the compromise /quickly/ in order to prevent things like nonce reuse. What is more likely? That an attacker who compromised this state at one point in time doesn't have the means to do it again elsewhere in the pipeline, will use a high bandwidth /dev/urandom output stream to mount a premature next attack, and is going after a high value target that inexplicably doesn't have RDRAND/vmgenid/virtio-rng enabled? Or that Nadia's group (or that large building in Utah) will get an Internet tap and simply start looking for repeated nonces to break? Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
[parent not found: <CAMvzKsiA52Si=PzOJXYwGSA1WUz-1S0A8cpgRJWDzpMkfFbX+Q@mail.gmail.com>]
* Re: is "premature next" a real world rng concern, or just an academic exercise? [not found] ` <CAMvzKsiA52Si=PzOJXYwGSA1WUz-1S0A8cpgRJWDzpMkfFbX+Q@mail.gmail.com> @ 2022-05-09 15:55 ` Yevgeniy Dodis 2022-05-10 15:21 ` Jason A. Donenfeld ` (2 more replies) 0 siblings, 3 replies; 15+ messages in thread From: Yevgeniy Dodis @ 2022-05-09 15:55 UTC (permalink / raw) To: Jason A. Donenfeld Cc: tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, D. J. Bernstein, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel resending in plain text... (hope got it right) On Mon, May 9, 2022 at 11:15 AM Yevgeniy Dodis <dodis@cs.nyu.edu> wrote: > > Hi Jason and all. > > Thank you for starting this fascinating discussion. I generally agree with everything Jason said. In particular, I am not > 100% convinced that the extra cost of the premature next defense is justified.(Although Windows and MacOS are adamant it is > worth it :).) > > But let me give some meta points to at least convince you this is not as obvious as Jason makes it sound. > > 1) Attacking RNGs in any model is really hard. Heck, everybody knew for years that /dev/random is a mess > (and we published it formally in 2013, although this was folklore knowledge), but in all these years nobody > (even Nadya's group :)) managed to find a practical attack. So just because the attack seems far-fetched, I do not think we should > lower our standards and do ugly stuff. Otherwise, just leave /dev/random the way it was before Jason started his awesome work. > > 2) As Jason says, there are two distinct attack vectors needed to make the premature next attack. > A) compromising the state > B) (nearly) continuously observing RNG outputs > > I agree with Jason's point that finding places where > -- A)+B) is possible, but > --- A)+A) is not possible, > is tricky. Although Nadya kind of indicated a place like that. VM1 and VM2 start with the same RNG state (for whatever > reason). VM1 is insecure, so can leak the state via A). VM2 is more secure, but obviously allows for B) through system > interface. This does not seem so hypothetical for me, especially in light of my mega-point 1) above -- almost any real-world > RNG attack is hard. > > But I want to look at it from a different angle here. Let's ask if RNGs should be secure against A) or B) individually. > > I think everybody agrees protection from B) is a must. This is the most basic definition of RNG! So let's just take itas > an axiom. > > Protection against A) is trickier. But my read of Jason's email is that all his criticism comes exactly from this point. > If your system allows for state compromise, you have bigger problems than the premature next, etc. But let's ask ourselves > the question. Are we ready to design RNGs without recovery from state compromise? I believe nobody on this list would > be comfortable saying "yes". Because this would mean we don;t need to accumulate entropy beyond system start-up. > Once we reach the point of good initial state, and state compromise is not an issue, just use straight ChaCha or whatever other > stream cipher. > > The point is, despite all arguments Jason puts, we all would feel extremely uncomfortable/uneasy to let continuous > entropy accumulation go, right? > > This means we all hopefully agree that we need protection against A) and B) individually. > > 3) Now comes the question. If we want to design a sound RNG using tools of modern cryptography, and we allow > the attacker an individual capability to enforce A) or B) individually, are we comfortable with the design where we: > * offer protection against A) > * offer protection against B) > * do NOT offer protection against A)+B), because we think it's too expensive given A)+B) is so rare? > > I do not have a convincing answer to this question, but it is at least not obvious to me. On a good note, one worry > we might have is how to even have a definition protecting A), protecting B), but not protecting A)+B). > Fortunately, our papers resolve this question (although there are still theoretical annoyances which I do not > want to get into in this email). So, at least from this perspective, we are good. We have a definition with > exactly these (suboptimal) properties. > > Anyway, these are my 2c. > Thoughts? > > Yevgeniy > > On Sun, May 1, 2022 at 7:17 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: >> >> Hi Ted, >> >> That's a useful analysis; thanks for that. >> >> On Sat, Apr 30, 2022 at 05:49:55PM -0700, tytso wrote: >> > On Wed, Apr 27, 2022 at 03:58:51PM +0200, Jason A. Donenfeld wrote: >> > > >> > > 3) More broadly speaking, what kernel infoleak is actually acceptable to >> > > the degree that anybody would feel okay in the first place about the >> > > system continuing to run after it's been compromised? >> > >> > A one-time kernel infoleak where this might seem most likely is one >> > where memory is read while the system is suspended/hibernated, or if >> > you have a VM which is frozen and then replicated. A related version >> > is one where a VM is getting migrated from one host to another, and >> > the attacker is able to grab the system memory from the source "host" >> > after the VM is migrated to the destination "host". >> >> You've identified ~two places where compromises happen, but it's not an >> attack that can just be repeated simply by re-running `./sploit > state`. >> >> 1) Virtual machines: >> >> It seems like after a VM state compromise during migration, or during >> snapshotting, the name of the game is getting entropy into the RNG in a >> usable way _as soon as possible_, and not delaying that. This is >> Nadia's point. There's some inherent tension between waiting some amount >> of time to use all available entropy -- the premature next requirement >> -- and using everything you can as fast as you can because your output >> stream is compromised/duplicated and that's very bad and should be >> mitigated ASAP at any expense. >> >> [I'm also CC'ing Tom Risenpart, who's been following this thread, as he >> did some work regarding VM snapshots and compromise, and what RNG >> recovery in that context looks like, and arrived at pretty similar >> points.] >> >> You mentioned virtio-rng as a mitigation for this. That works, but only >> if the data read from it are actually used rather quickly. So probably >> /waiting/ to use that is suboptimal. >> >> One of the things added for 5.18 is this new "vmgenid" driver, which >> responds to fork/snapshot notifications from hypervisors, so that VMs >> can do something _immediately_ upon resumption/migration/etc. That's >> probably the best general solution to that problem. >> >> Though vmgenid is supported by QEMU, VMware, Hyper-V, and hopefully soon >> Firecracker, there'll still be people that don't have it for one reason >> or another (and it has to be enabled manually in QEMU with `-device >> vmgenid,guid=auto`; perhaps I should send a patch adding that to some >> default machine types). Maybe that's their problem, but I take as your >> point that we can still try to be less bad than otherwise by using more >> entropy more often, and not delaying as the premature next model >> requirements would have us do. >> >> 2) Suspend / hibernation: >> >> This is kind of the same situation as virtual machines, but the >> particulars are a little bit different: >> >> - There's no hypervisor giving us new seed material on resumption like >> we have with VM snapshots and vmgenid; but >> >> - We also always know when it happens, because it's not transparent to >> the OS, so at least we can attempt to do something immediately like >> we do with the vmgenid driver. >> >> Fortunately, most systems that are doing suspend or hibernation these >> days also have a RDRAND-like thing. It seems like it'd be a good idea >> for me to add a PM notifier, mix into the pool both >> ktime_get_boottime_ns() and ktime_get(), in addition to whatever type >> info I get from the notifier block (suspend vs hibernate vs whatever >> else) to account for the amount of time in the sleeping state, and then >> immediately reseed the crng, which will pull in a bunch of >> RDSEED/RDRAND/RDTSC values. This way on resumption, the system is always >> in a good place. >> >> I did this years ago in WireGuard -- clearing key material before >> suspend -- and there are some details around autosuspend (see >> wg_pm_notification() in drivers/net/wireguard/device.c), but it's not >> that hard to get right, so I'll give it a stab and send a patch. >> >> > But if the attacker can actually obtain internal state from one >> > reconstituted VM, and use that to attack another reconstituted VM, and >> > the attacker also knows what the nonce or time seed that was used so >> > that different reconstituted VMs will have unique CRNG streams, this >> > might be a place where the "premature next" attack might come into >> > play. >> >> This is the place where it matters, I guess. It's also where the >> tradeoff's from Nadia's argument come into play. System state gets >> compromised during VM migration / hibernation. It comes back online and >> starts doling out compromised random numbers. Worst case scenario is >> there's no RDRAND or vmgenid or virtio-rng, and we've just got the good >> old interrupt handler mangling cycle counters. Choices: A) recover from >> the compromise /slowly/ in order to mitigate premature next, or B) >> recover from the compromise /quickly/ in order to prevent things like >> nonce reuse. >> >> What is more likely? That an attacker who compromised this state at one >> point in time doesn't have the means to do it again elsewhere in the >> pipeline, will use a high bandwidth /dev/urandom output stream to mount >> a premature next attack, and is going after a high value target that >> inexplicably doesn't have RDRAND/vmgenid/virtio-rng enabled? Or that >> Nadia's group (or that large building in Utah) will get an Internet tap >> and simply start looking for repeated nonces to break? >> >> Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-09 15:55 ` Yevgeniy Dodis @ 2022-05-10 15:21 ` Jason A. Donenfeld 2022-05-10 18:51 ` D. J. Bernstein 2022-05-11 20:26 ` Thomas Ristenpart 2022-05-11 20:46 ` Pavel Machek 2 siblings, 1 reply; 15+ messages in thread From: Jason A. Donenfeld @ 2022-05-10 15:21 UTC (permalink / raw) To: Yevgeniy Dodis Cc: tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, D. J. Bernstein, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel Hi Yevgeniy, Thanks for your email. Replies to parts are inline below: On Mon, May 9, 2022 at 11:15 AM Yevgeniy Dodis <dodis@cs.nyu.edu> wrote: > 2) As Jason says, there are two distinct attack vectors needed to make the premature next attack. > A) compromising the state > B) (nearly) continuously observing RNG outputs > > I agree with Jason's point that finding places where > -- A)+B) is possible, but > --- A)+A) is not possible, > is tricky. That's a useful way of describing the problem. > Although Nadya kind of indicated a place like that. VM1 and VM2 start > with the same RNG state (for whatever reason). VM1 is insecure, so can > leak the state via A). VM2 is more secure, but obviously allows for B) > through system interface. This does not seem so hypothetical for me, > especially in light of my mega-point 1) above -- almost any real-world > RNG attack is hard. Right, VMs are super problematic, but for that, there's now this "vmgenid" driver, where the hypervisor actually gives a 128-bit seed to guests when they're resumed, so that we can immediately reseed, which should pretty comprehensively handle that situation. > Protection against A) is trickier. But my read of Jason's email is > that all his criticism comes exactly from this point. If your system > allows for state compromise, you have bigger problems than the > premature next, etc. But let's ask ourselves the question. Are we > ready to design RNGs without recovery from state compromise? I believe > nobody on this list would be comfortable saying "yes". Because this > would mean we don;t need to accumulate entropy beyond system start-up. > Once we reach the point of good initial state, and state compromise is > not an issue, just use straight ChaCha or whatever other stream > cipher. > > The point is, despite all arguments Jason puts, we all would feel > extremely uncomfortable/uneasy to let continuous entropy accumulation > go, right? I went through the same thought experiment. If we're not considering premature next, maybe we shouldn't consider compromises _in general_, in which case we'd just seed once at boot and then never again. But as you rightfully point out, nobody here is okay with such a thing. The reason you've provided for that feeling is that A) without B) is still something important to defend against. But there's another more basic reason, which is that we really can't be certain exactly /when/ we've gathered enough entropy that the RNG is initialized. Sure, we try to estimate that using some pretty questionable algorithms, so that getrandom() can "unblock" at some point when the RNG has been deemed to be sufficiently initialized. But that is a guess at best, and the most we can say is that *eventually* it becomes initialized, but we never really know when that is, given that we can't even begin to accurately model all of the machines Linux runs on. So since we can't actually determine when we've initialized, for that reason alone our only choice is to keep gathering new entropy and reseeding periodically (or continuously, as Nadia recommends). > This means we all hopefully agree that we need protection against A) and B) individually. > > 3) Now comes the question. If we want to design a sound RNG using tools of modern cryptography, and we allow > the attacker an individual capability to enforce A) or B) individually, are we comfortable with the design where we: > * offer protection against A) > * offer protection against B) > * do NOT offer protection against A)+B), because we think it's too expensive given A)+B) is so rare? There's an additional point to consider here, which I took to be Nadia's main idea: any kind of protection against A)+B) will hinder protection against A) individually. All current solutions to A)+B) involve some form of buffering / delaying of using new entropy sources, because they're sent to different pools, or are simply not used until a certain threshold, etc. Meanwhile, better protection against A) individually involves making use of new entropy as soon as possible, to reduce the duration of time in which the RNG is compromised and doing dangerous things. Since we can't actually know when a compromise is over or when enough new entropy has been collected, the best we can do is "as soon as possible", which means any form of a delay is contrary to that goal. So it's not just that A)+B) is both an unlikely attack vector and has solutions that involve undue implementation complexity, but also that A)+B) solutions weaken solutions to the heavier problem of A) individually. > I do not have a convincing answer to this question, but it is at least > not obvious to me. On a good note, one worry we might have is how to > even have a definition protecting A), protecting B), but not > protecting A)+B). Fortunately, our papers resolve this question > (although there are still theoretical annoyances which I do not want > to get into in this email). So, at least from this perspective, we are > good. We have a definition with exactly these (suboptimal) properties. I actually would be interested to see how you have this defined. It seems like from a formal perspective, this issue with being "eventually seeded" naturally leads itself to Fortuna-like designs, where the whole design is structured around eventually meeting the desired security properties. But on the other hand a A) without B) design would suggest some notion of being properly seeded at some point in time, and when that is seems hard to define. So anyway I'm curious to learn how you've organized this. Regards, Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-10 15:21 ` Jason A. Donenfeld @ 2022-05-10 18:51 ` D. J. Bernstein 2022-05-10 20:09 ` Jason A. Donenfeld 0 siblings, 1 reply; 15+ messages in thread From: D. J. Bernstein @ 2022-05-10 18:51 UTC (permalink / raw) To: Jason A. Donenfeld, Yevgeniy Dodis, tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel [-- Attachment #1: Type: text/plain, Size: 1496 bytes --] Jason A. Donenfeld writes: > Right, VMs are super problematic, but for that, there's now this > "vmgenid" driver, where the hypervisor actually gives a 128-bit seed to > guests when they're resumed, so that we can immediately reseed, which > should pretty comprehensively handle that situation. Hmmm. If an application initializes its own RNG state from /dev/urandom, and is then cloned, and then generates an ECDSA nonce from the RNG state, and then uses this nonce to sign a message that's different across the clones, how is disaster averted? Given the goal of sending money to cryptographers, I'm pretty sure we want the answer to be a security-audit nightmare, so let me suggest the following idea. There's SIGWINCH to notify processes about window-size changes, so there should also be a signal for RNG changes, which should be called SIGRINCH, and there should be a different mechanism to address RNG output cloning inside the kernel, and there should be endless papers on Grinch Attacks, including papers that sort of prove security against Grinch Attacks, and deployment of software that's sort of protected against Grinch Attacks, and fear of the bad PR from abandoning anything labeled as protection, because, hey, _maybe_ the protection accomplishes something, and it's not as if anyone is going to be blamed for whatever damage is caused by the systems-level effect of the added complexity. ---D. J. Bernstein P.S. Yes, yes, I know the name "Grinch Attack" has been used before. [-- Attachment #2: signature.asc --] [-- Type: application/pgp-signature, Size: 833 bytes --] ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-10 18:51 ` D. J. Bernstein @ 2022-05-10 20:09 ` Jason A. Donenfeld 2022-05-10 21:33 ` Simo Sorce 0 siblings, 1 reply; 15+ messages in thread From: Jason A. Donenfeld @ 2022-05-10 20:09 UTC (permalink / raw) To: dodis, tytso, nadiah, noahsd, tessaro, torvalds, jeanphilippe.aumasson, jann, keescook, gregkh, peter, linux-crypto, linux-kernel, D. J. Bernstein Hey Dan, On Tue, May 10, 2022 at 08:51:23PM +0200, D. J. Bernstein wrote: > Jason A. Donenfeld writes: > > Right, VMs are super problematic, but for that, there's now this > > "vmgenid" driver, where the hypervisor actually gives a 128-bit seed to > > guests when they're resumed, so that we can immediately reseed, which > > should pretty comprehensively handle that situation. > > Hmmm. If an application initializes its own RNG state from /dev/urandom, > and is then cloned, and then generates an ECDSA nonce from the RNG > state, and then uses this nonce to sign a message that's different > across the clones, how is disaster averted? Currently WireGuard will drop its ephemeral session key material from the tx path, to prevent nonce use. This is because of an in-kernel mechanism I added in 5.18, which is pretty minimal and non-invasive, and came basically for free. CTRL+F for "vmgenid" in here for details: https://www.zx2c4.com/projects/linux-rng-5.17-5.18/ For 5.19 (or at this point, more likely 5.20), there's a userspace notifier in store, maybe, if I can figure out how to do it right. There's a pretty bikesheddy thread here on what shape that interface should take: https://lore.kernel.org/lkml/YnA5CUJKvqmXJxf2@zx2c4.com/ But basically there are some details about how an async interface should work, and what the virtual hardware future, if any, looks like for a memory mapped race-free polling interface. Plus some considerations on how much we should care etc. > Given the goal of sending money to cryptographers, I'm pretty sure we > want the answer to be a security-audit nightmare, so let me suggest the > following idea. There's SIGWINCH to notify processes about window-size > changes, so there should also be a signal for RNG changes, which should > be called SIGRINCH, and there should be a different mechanism to address > RNG output cloning inside the kernel, and there should be endless papers > on Grinch Attacks, including papers that sort of prove security against > Grinch Attacks, and deployment of software that's sort of protected > against Grinch Attacks, and fear of the bad PR from abandoning anything > labeled as protection, because, hey, _maybe_ the protection accomplishes > something, and it's not as if anyone is going to be blamed for whatever > damage is caused by the systems-level effect of the added complexity. I mean... you kid, but you're also kind of on point here. There are about a thousand ways of doing this kind of notification that lead to impossible-to-program-for paradigms that people will find necessary to implement, and it'll be a nightmare if not done in a sufficiently slick way. For the in-kernel thing WireGuard uses, it doesn't really matter because the kernel is one big codebase so ergonomics can change need be. But userspace is another challenge. Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-10 20:09 ` Jason A. Donenfeld @ 2022-05-10 21:33 ` Simo Sorce 2022-05-10 22:50 ` Jason A. Donenfeld 0 siblings, 1 reply; 15+ messages in thread From: Simo Sorce @ 2022-05-10 21:33 UTC (permalink / raw) To: Jason A. Donenfeld, dodis, tytso, nadiah, noahsd, tessaro, torvalds, jeanphilippe.aumasson, jann, keescook, gregkh, peter, linux-crypto, linux-kernel, D. J. Bernstein On Tue, 2022-05-10 at 22:09 +0200, Jason A. Donenfeld wrote: > For 5.19 (or at this point, more likely 5.20), there's a userspace > notifier in store, maybe, if I can figure out how to do it right. > There's a pretty bikesheddy thread here on what shape that interface > should take: https://lore.kernel.org/lkml/YnA5CUJKvqmXJxf2@zx2c4.com/ > But basically there are some details about how an async interface should > work, and what the virtual hardware future, if any, looks like for a > memory mapped race-free polling interface. Plus some considerations on > how much we should care etc. Perhaps it might be simpler to add an "epoch" number or similar exposed via something like a vDSO that proper user space implementations can then check before returning numbers from PRNGs and will immediately reseed from /dev/random if it ever changes (rare event). It is much simpler to poll for this information in user space crypto libraries than using notifications of any kind given libraries are generally not in full control of what the process does. This needs to be polled fast as well, because the whole point of initializing a PRNG in the library is that asking /dev/urandom all the time is too slow (due to context switches and syscall overhead), so anything that would require a context switch in order to pull data from the PRNG would not really fly. Note that a generic "epoch" exposed via vDSO would be useful beyond RNGs, as it would be usable by any other user space that needs to know that "I have been cloned and I need to do something now" and would be able to use it immediately w/o the kernel needing to grow any other specific interface for it. HTH. Simo. -- Simo Sorce RHEL Crypto Team Red Hat, Inc ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-10 21:33 ` Simo Sorce @ 2022-05-10 22:50 ` Jason A. Donenfeld 0 siblings, 0 replies; 15+ messages in thread From: Jason A. Donenfeld @ 2022-05-10 22:50 UTC (permalink / raw) To: Simo Sorce Cc: dodis, tytso, nadiah, noahsd, tessaro, torvalds, jeanphilippe.aumasson, jann, keescook, gregkh, peter, linux-crypto, linux-kernel, D. J. Bernstein Hi Simo, On Tue, May 10, 2022 at 05:33:34PM -0400, Simo Sorce wrote: > On Tue, 2022-05-10 at 22:09 +0200, Jason A. Donenfeld wrote: > > For 5.19 (or at this point, more likely 5.20), there's a userspace > > notifier in store, maybe, if I can figure out how to do it right. > > There's a pretty bikesheddy thread here on what shape that interface > > should take: https://lore.kernel.org/lkml/YnA5CUJKvqmXJxf2@zx2c4.com/ > > But basically there are some details about how an async interface should > > work, and what the virtual hardware future, if any, looks like for a > > memory mapped race-free polling interface. Plus some considerations on > > how much we should care etc. > > Perhaps it might be simpler to add an "epoch" number or similar exposed > [...] Could you send these ideas to the bikeshed thread that I linked rather than this premature next one. I think it'd be a good idea to keep Alex and Lennart looped in to that discussion, since they represent userspace projects that probably care about it, and not bog this one down with systems programming things pretty far from premature next threat model stuff. It's a bikeshed thing, after all... Thanks, Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-09 15:55 ` Yevgeniy Dodis 2022-05-10 15:21 ` Jason A. Donenfeld @ 2022-05-11 20:26 ` Thomas Ristenpart 2022-05-12 11:47 ` Jason A. Donenfeld 2022-05-11 20:46 ` Pavel Machek 2 siblings, 1 reply; 15+ messages in thread From: Thomas Ristenpart @ 2022-05-11 20:26 UTC (permalink / raw) To: Yevgeniy Dodis Cc: Jason A. Donenfeld, tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, D. J. Bernstein, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel Hi all, Thanks to Jason for CC’ing me on this fascinating thread. I was chatting with Jason and Nadia at RWC, and was also advocating for simplifying the design of /dev/urandom. My two cents at a high level: 1) I haven’t seen any compelling evidence that premature next attacks are a realistic threat. 2) Countermeasures against premature next complicate designs, slowing down useful entropy accumulation and need to be worked around to avoid exacerbating more pressing issues. On vulnerabilities: My and others’ prior work on VM reset threat models [1] showed pretty convincingly via experiments that the /dev/(u)random pooled design leads to problems in settings where a VM is replayed multiple times from the same (full memory snapshot). In large part this is due to the pooling and entropy estimation mechanisms in the older design. The vulnerabilities also were demonstrated in FreeBSD and Windows 7 RNGs, however, due to subtleties presumably in their reseed scheduling. The vulnerabilities described in the academic papers can be exploited in lab settings, but whether they are a pressing concern in practice remains unclear to me. At least, I haven’t heard any evidence of VM resets being exploited by threat actors. Nevertheless I think they should be fixed. Ted graciously chatted with us about it back then, but he concluded our particular suggested design was too slow (a fair assessment). VM resets also affect userland processes (in fact possibly even more so than the kernel), but that is perhaps off-topic. Boot time entropy holes that lead to factorable RSA public keys as per Nadia’s and her collaborators’ prior work does seem pretty immediately of practical risk! Unlike the above, vulnerability to premature next attacks has no supporting experimental evidence that I’m aware of. (We refer to these as “tracking” attacks in [1].) As Jason pointed out and Yevgeniy added to, these require at least a compromise of RNG state (A in his labeling), and continued access to RNG outputs after losing access to ongoing RNG state (B in his labeling). But I would like to emphasize a slightly more granular set of requirements for the kinds of premature next attacks that Fortuna and other multi-pool mechanisms protect against, building off Jason and others’ observations: A) RNG state compromise A’) Attacker silently loses access to the RNG state, not due to a reboot or VM resumption B) Attacker maintains continuous tap on RNG outputs I really think step A’ is a critical point here. By silently I mean the adversary somehow loses access without administrators knowing about compromise, and not due to an event that anyway reinitializes the RNG (reboot or VM resumption). This is critical for the threat model to make sense, since otherwise if the admin knows about the compromise, cleanup needs to occur which should include a reboot. Or if the attacker loses access but anyway we’re reinitializing the RNG, then we’re also fine. I don’t know of any credible situations where A + A’ + B arise. On designs: Fortuna, Whirlwind (from [1]), Yarrow, etc. and other multi-pool designs defend against premature next in a setting where: (1) you don’t know when a compromise starts and ends; and (2) you can’t generate entropy on demand. I don’t think other assumption is really reflective of practice — see discussion above for why (1) doesn’t seem to come up in threat models and for (2) CPU jitter dances seem to work pretty well (though performance is a question). Note that since we round-robin entropy measurements to different pools, these multi-pool designs can exacerbate the problem of quickly (re-)initializing during boot or VM resumption. I actually do not know how choice and parameterization of Fortuna, Yarrow affects the window of vulnerability in VM reset settings; we never measured this explicitly. But in any case I think we need an explicit, fast reinitialization step to be safe here (as discussed in Whirlwind design and Jason’s emails), and so a redesign should allow for fast entropy gathering loops, and those loops should immediately dump all their entropy into the RNG state for use. Thus you would need to have a code-path that avoids round-robining to slow pools in a (re)initialization routine. To me the high-level design features that seems to check all the boxes, including importantly simplicity: 1) A single pool where opportunistic entropy measurements (interrupt timings, etc.) are folded in and that is used to generate outputs. 2) An explicit “generate entropy” routine that attempts to quickly generate a large amount of entropy. Use this to (re)initialize the state upon system events like boot and VM resumption. The CPU jitter dance type mechanisms are a good bet, though someone should probably check that these work on low-end systems. Also I would advocate always folding in other sources of entropy (e.g., RDRAND) when available, performance allowing, in both 1 and 2. Given the above discussion, I don’t think it’s very important, but an extension of the above to provide some limitation of premature next concerns would be: 3) Periodically call 2. For example, when a CPU is otherwise idle. This would have same effect as Fortuna-style approaches without adding new buffers, etc. Details would need to be worked out, of course. Hope this was helpful and apologies that it got long, Cheers, -Tom [1] https://rist.tech.cornell.edu/papers/vmrng.pdf > On May 9, 2022, at 11:55 AM, Yevgeniy Dodis <dodis@cs.nyu.edu> wrote: > > resending in plain text... (hope got it right) > > On Mon, May 9, 2022 at 11:15 AM Yevgeniy Dodis <dodis@cs.nyu.edu> wrote: >> >> Hi Jason and all. >> >> Thank you for starting this fascinating discussion. I generally agree with everything Jason said. In particular, I am not >> 100% convinced that the extra cost of the premature next defense is justified.(Although Windows and MacOS are adamant it is >> worth it :).) >> >> But let me give some meta points to at least convince you this is not as obvious as Jason makes it sound. >> >> 1) Attacking RNGs in any model is really hard. Heck, everybody knew for years that /dev/random is a mess >> (and we published it formally in 2013, although this was folklore knowledge), but in all these years nobody >> (even Nadya's group :)) managed to find a practical attack. So just because the attack seems far-fetched, I do not think we should >> lower our standards and do ugly stuff. Otherwise, just leave /dev/random the way it was before Jason started his awesome work. >> >> 2) As Jason says, there are two distinct attack vectors needed to make the premature next attack. >> A) compromising the state >> B) (nearly) continuously observing RNG outputs >> >> I agree with Jason's point that finding places where >> -- A)+B) is possible, but >> --- A)+A) is not possible, >> is tricky. Although Nadya kind of indicated a place like that. VM1 and VM2 start with the same RNG state (for whatever >> reason). VM1 is insecure, so can leak the state via A). VM2 is more secure, but obviously allows for B) through system >> interface. This does not seem so hypothetical for me, especially in light of my mega-point 1) above -- almost any real-world >> RNG attack is hard. >> >> But I want to look at it from a different angle here. Let's ask if RNGs should be secure against A) or B) individually. >> >> I think everybody agrees protection from B) is a must. This is the most basic definition of RNG! So let's just take itas >> an axiom. >> >> Protection against A) is trickier. But my read of Jason's email is that all his criticism comes exactly from this point. >> If your system allows for state compromise, you have bigger problems than the premature next, etc. But let's ask ourselves >> the question. Are we ready to design RNGs without recovery from state compromise? I believe nobody on this list would >> be comfortable saying "yes". Because this would mean we don;t need to accumulate entropy beyond system start-up. >> Once we reach the point of good initial state, and state compromise is not an issue, just use straight ChaCha or whatever other >> stream cipher. >> >> The point is, despite all arguments Jason puts, we all would feel extremely uncomfortable/uneasy to let continuous >> entropy accumulation go, right? >> >> This means we all hopefully agree that we need protection against A) and B) individually. >> >> 3) Now comes the question. If we want to design a sound RNG using tools of modern cryptography, and we allow >> the attacker an individual capability to enforce A) or B) individually, are we comfortable with the design where we: >> * offer protection against A) >> * offer protection against B) >> * do NOT offer protection against A)+B), because we think it's too expensive given A)+B) is so rare? >> >> I do not have a convincing answer to this question, but it is at least not obvious to me. On a good note, one worry >> we might have is how to even have a definition protecting A), protecting B), but not protecting A)+B). >> Fortunately, our papers resolve this question (although there are still theoretical annoyances which I do not >> want to get into in this email). So, at least from this perspective, we are good. We have a definition with >> exactly these (suboptimal) properties. >> >> Anyway, these are my 2c. >> Thoughts? >> >> Yevgeniy >> >> On Sun, May 1, 2022 at 7:17 AM Jason A. Donenfeld <Jason@zx2c4.com> wrote: >>> >>> Hi Ted, >>> >>> That's a useful analysis; thanks for that. >>> >>> On Sat, Apr 30, 2022 at 05:49:55PM -0700, tytso wrote: >>>> On Wed, Apr 27, 2022 at 03:58:51PM +0200, Jason A. Donenfeld wrote: >>>>> >>>>> 3) More broadly speaking, what kernel infoleak is actually acceptable to >>>>> the degree that anybody would feel okay in the first place about the >>>>> system continuing to run after it's been compromised? >>>> >>>> A one-time kernel infoleak where this might seem most likely is one >>>> where memory is read while the system is suspended/hibernated, or if >>>> you have a VM which is frozen and then replicated. A related version >>>> is one where a VM is getting migrated from one host to another, and >>>> the attacker is able to grab the system memory from the source "host" >>>> after the VM is migrated to the destination "host". >>> >>> You've identified ~two places where compromises happen, but it's not an >>> attack that can just be repeated simply by re-running `./sploit > state`. >>> >>> 1) Virtual machines: >>> >>> It seems like after a VM state compromise during migration, or during >>> snapshotting, the name of the game is getting entropy into the RNG in a >>> usable way _as soon as possible_, and not delaying that. This is >>> Nadia's point. There's some inherent tension between waiting some amount >>> of time to use all available entropy -- the premature next requirement >>> -- and using everything you can as fast as you can because your output >>> stream is compromised/duplicated and that's very bad and should be >>> mitigated ASAP at any expense. >>> >>> [I'm also CC'ing Tom Risenpart, who's been following this thread, as he >>> did some work regarding VM snapshots and compromise, and what RNG >>> recovery in that context looks like, and arrived at pretty similar >>> points.] >>> >>> You mentioned virtio-rng as a mitigation for this. That works, but only >>> if the data read from it are actually used rather quickly. So probably >>> /waiting/ to use that is suboptimal. >>> >>> One of the things added for 5.18 is this new "vmgenid" driver, which >>> responds to fork/snapshot notifications from hypervisors, so that VMs >>> can do something _immediately_ upon resumption/migration/etc. That's >>> probably the best general solution to that problem. >>> >>> Though vmgenid is supported by QEMU, VMware, Hyper-V, and hopefully soon >>> Firecracker, there'll still be people that don't have it for one reason >>> or another (and it has to be enabled manually in QEMU with `-device >>> vmgenid,guid=auto`; perhaps I should send a patch adding that to some >>> default machine types). Maybe that's their problem, but I take as your >>> point that we can still try to be less bad than otherwise by using more >>> entropy more often, and not delaying as the premature next model >>> requirements would have us do. >>> >>> 2) Suspend / hibernation: >>> >>> This is kind of the same situation as virtual machines, but the >>> particulars are a little bit different: >>> >>> - There's no hypervisor giving us new seed material on resumption like >>> we have with VM snapshots and vmgenid; but >>> >>> - We also always know when it happens, because it's not transparent to >>> the OS, so at least we can attempt to do something immediately like >>> we do with the vmgenid driver. >>> >>> Fortunately, most systems that are doing suspend or hibernation these >>> days also have a RDRAND-like thing. It seems like it'd be a good idea >>> for me to add a PM notifier, mix into the pool both >>> ktime_get_boottime_ns() and ktime_get(), in addition to whatever type >>> info I get from the notifier block (suspend vs hibernate vs whatever >>> else) to account for the amount of time in the sleeping state, and then >>> immediately reseed the crng, which will pull in a bunch of >>> RDSEED/RDRAND/RDTSC values. This way on resumption, the system is always >>> in a good place. >>> >>> I did this years ago in WireGuard -- clearing key material before >>> suspend -- and there are some details around autosuspend (see >>> wg_pm_notification() in drivers/net/wireguard/device.c), but it's not >>> that hard to get right, so I'll give it a stab and send a patch. >>> >>>> But if the attacker can actually obtain internal state from one >>>> reconstituted VM, and use that to attack another reconstituted VM, and >>>> the attacker also knows what the nonce or time seed that was used so >>>> that different reconstituted VMs will have unique CRNG streams, this >>>> might be a place where the "premature next" attack might come into >>>> play. >>> >>> This is the place where it matters, I guess. It's also where the >>> tradeoff's from Nadia's argument come into play. System state gets >>> compromised during VM migration / hibernation. It comes back online and >>> starts doling out compromised random numbers. Worst case scenario is >>> there's no RDRAND or vmgenid or virtio-rng, and we've just got the good >>> old interrupt handler mangling cycle counters. Choices: A) recover from >>> the compromise /slowly/ in order to mitigate premature next, or B) >>> recover from the compromise /quickly/ in order to prevent things like >>> nonce reuse. >>> >>> What is more likely? That an attacker who compromised this state at one >>> point in time doesn't have the means to do it again elsewhere in the >>> pipeline, will use a high bandwidth /dev/urandom output stream to mount >>> a premature next attack, and is going after a high value target that >>> inexplicably doesn't have RDRAND/vmgenid/virtio-rng enabled? Or that >>> Nadia's group (or that large building in Utah) will get an Internet tap >>> and simply start looking for repeated nonces to break? >>> >>> Jason ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-11 20:26 ` Thomas Ristenpart @ 2022-05-12 11:47 ` Jason A. Donenfeld 2022-05-13 6:19 ` Dominik Brodowski 0 siblings, 1 reply; 15+ messages in thread From: Jason A. Donenfeld @ 2022-05-12 11:47 UTC (permalink / raw) To: Thomas Ristenpart Cc: Yevgeniy Dodis, tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, D. J. Bernstein, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel Hi Tom, On Wed, May 11, 2022 at 08:26:08PM +0000, Thomas Ristenpart wrote: > To me the high-level design features that seems to check all the > boxes, including importantly simplicity: > > 1) A single pool where opportunistic entropy measurements (interrupt > timings, etc.) are folded in and that is used to generate outputs. > > 2) An explicit “generate entropy” routine that attempts to quickly > generate a large amount of entropy. Use this to (re)initialize the > state upon system events like boot and VM resumption. The CPU jitter > dance type mechanisms are a good bet, though someone should probably > check that these work on low-end systems. > > Also I would advocate always folding in other sources of entropy > (e.g., RDRAND) when available, performance allowing, in both 1 and 2. > Given the above discussion, I don’t think it’s very important, but an > extension of the above to provide some limitation of premature next > concerns would be: RDRAND is currently mixed in during system boot and during reseeding (which now happens after sleep resumption too, as of [1]). Specifically, reseeding takes this HKDF-like form: τ = blake2s(key=last_key, input₁ ‖ input₂ ‖ … ‖ inputₙ) κ₁ = blake2s(key=τ, RDSEED ‖ 0x0) κ₂ = blake2s(key=τ, RDSEED ‖ 0x1) last_key = κ₁ crng_seed = κ₂ where RDSEED here represents 256 bits of RDSEED, RDRAND, or RDTSC, depending on what's available on the platform, operating as a sort of salt parameter. When RDSEED or RDRAND is available, this matches your suggestion. When only RDTSC is available, it's maybe jittery, but not very much because it's just called in a tight loop, which brings us to your next suggestion: > 3) Periodically call 2. For example, when a CPU is otherwise idle. > This would have same effect as Fortuna-style approaches without adding > new buffers, etc. For systems without RDSEED or RDRAND, doing jitter entropy periodically would at least be /something/ significant in the service of "solving" the premature next "problem" (in addition to the more significant VM problem in the absence of vmgenid). Your suggestion of an explicit "generate entropy" function that can be called periodically is a similar to Linus' point when he introduced jitter entropy, titling the commit, "try to actively add entropy rather than passively wait for it" [2]. It's a good point. If we have a way of generating entropy directly instead of passively waiting for it, something complicated like Fortuna isn't even necessary. (As a silly side note: since Fortuna only claims to /eventually/ recover from a compromise but can't tell you when, such jitter could be done once a week and still, on paper, accomplish the same theoretical goal...) Jitter might not be available on all architectures that Linux supports, though it likely is available for most deployed systems out there. And for 5.19, I've fixed some cycle counter fallback things so that it should hopefully be available a few more places it wasn't before. Similarly, RDSEED/RDRAND isn't available everywhere, but it is available most places these days. But on the other hand, it appears that none of us really thinks that premature next is a real problem worth complicating designs over. So maybe we can just say that it is nice when the silicon in one way or another helps with premature next, but maybe not an explicit must have. So where does that leave us? - Systems with RDSEED/RDRAND don't have premature next, due to the above KDF salt. This is probably the majority of systems out there these days. This also applies to the sleep resumption notification (and the vmgenid one), and I suspect that most systems with S3 or S0ix or whatever else these days also probably have RDRAND. - Systems with viable jitter entropy could be in a position to not have premature next too, if we added periodic jitter entropy calls per your suggestion (3). Though, the jitter dance as it currently exists involves hammering on the scheduler a bit and spiking latency, so I'm not totally sure this is really worth it to do beyond boot time. It'd need a little bit more specific engineering, anyhow, to get the details right on it. - Systems with no viable jitter nor RDSEED/RDRAND would need something like Fortuna, which doesn't seem worth it at all, given the discussion. These machines are probably in the first percentile of deployed systems too, and probably should be using something like seedrng [3] to initialize the RNG anyway. Plus, are these systems even fast enough to make condition B) viable to an attacker? > Details would need to be worked out, of course. Hope this was helpful > and apologies that it got long, Very helpful, thank you. The key takeaways for me are: - Premature next remains not a real world problem, per the reasons you and others cited. - Entropy *generation* makes most of those concerns disappear anyway, without the complexities and security issues associated with entropy long- or multi- *pooling*. Jason [1] https://git.kernel.org/crng/random/c/7edc59743da5 [2] https://git.kernel.org/crng/random/c/50ee7529ec45 [3] https://git.zx2c4.com/seedrng/about/ ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-12 11:47 ` Jason A. Donenfeld @ 2022-05-13 6:19 ` Dominik Brodowski 0 siblings, 0 replies; 15+ messages in thread From: Dominik Brodowski @ 2022-05-13 6:19 UTC (permalink / raw) To: Jason A. Donenfeld Cc: Thomas Ristenpart, Yevgeniy Dodis, tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, D. J. Bernstein, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel Am Thu, May 12, 2022 at 01:47:06PM +0200 schrieb Jason A. Donenfeld: > But on the other hand, it appears that none of us really thinks that > premature next is a real problem worth complicating designs over. So > maybe we can just say that it is nice when the silicon in one way or > another helps with premature next, but maybe not an explicit must have. > So where does that leave us? > > - Systems with RDSEED/RDRAND don't have premature next, due to the above > KDF salt. This is probably the majority of systems out there these > days. This also applies to the sleep resumption notification (and the > vmgenid one), and I suspect that most systems with S3 or S0ix or > whatever else these days also probably have RDRAND. ... and most of these systems have TPM chips with a RNG, which is (alas) usually only used at system startup, as that hw_rng device sets its quality to 0 (meaning untrusted). So there's also room for improvement involving these hw rng devices. Thanks, Dominik ^ permalink raw reply [flat|nested] 15+ messages in thread
* Re: is "premature next" a real world rng concern, or just an academic exercise? 2022-05-09 15:55 ` Yevgeniy Dodis 2022-05-10 15:21 ` Jason A. Donenfeld 2022-05-11 20:26 ` Thomas Ristenpart @ 2022-05-11 20:46 ` Pavel Machek 2 siblings, 0 replies; 15+ messages in thread From: Pavel Machek @ 2022-05-11 20:46 UTC (permalink / raw) To: Yevgeniy Dodis Cc: Jason A. Donenfeld, tytso, Nadia Heninger, Noah Stephens-Dawidowitz, Stefano Tessaro, torvalds, D. J. Bernstein, jeanphilippe.aumasson, jann, keescook, gregkh, Peter Schwabe, linux-crypto, linux-kernel [-- Attachment #1: Type: text/plain, Size: 1381 bytes --] Hi! > > > > Thank you for starting this fascinating discussion. I generally agree with everything Jason said. In particular, I am not > > 100% convinced that the extra cost of the premature next defense is justified.(Although Windows and MacOS are adamant it is > > worth it :).) > > Dunno, how big is cost of "premature next" defenses? I believe all you need to do is to reseed in batches, and that does not seem costly at runtime, and does not have high cost in kernel .text. > > But let me give some meta points to at least convince you this is not as obvious as Jason makes it sound. > > > > 1) Attacking RNGs in any model is really hard. Heck, everybody knew for years that /dev/random is a mess > > (and we published it formally in 2013, although this was folklore knowledge), but in all these years nobody > > (even Nadya's group :)) managed to find a practical attack. So just because the attack seems far-fetched, I do not think we should > > lower our standards and do ugly stuff. Otherwise, just leave > >/dev/random the way it was before Jason started his awesome work. Well, practical attacks may be hard, but when they happen... that's bad. We had weak keys generated by debian, we have various devices that with deterministic rngs... Best regards, Pavel -- People of Russia, stop Putin before his war on Ukraine escalates. [-- Attachment #2: Digital signature --] [-- Type: application/pgp-signature, Size: 181 bytes --] ^ permalink raw reply [flat|nested] 15+ messages in thread
end of thread, other threads:[~2022-05-13 6:26 UTC | newest] Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2022-04-27 13:58 is "premature next" a real world rng concern, or just an academic exercise? Jason A. Donenfeld 2022-04-28 4:26 ` Nadia Heninger 2022-04-30 2:08 ` Sandy Harris 2022-05-01 0:49 ` tytso 2022-05-01 11:16 ` Jason A. Donenfeld [not found] ` <CAMvzKsiA52Si=PzOJXYwGSA1WUz-1S0A8cpgRJWDzpMkfFbX+Q@mail.gmail.com> 2022-05-09 15:55 ` Yevgeniy Dodis 2022-05-10 15:21 ` Jason A. Donenfeld 2022-05-10 18:51 ` D. J. Bernstein 2022-05-10 20:09 ` Jason A. Donenfeld 2022-05-10 21:33 ` Simo Sorce 2022-05-10 22:50 ` Jason A. Donenfeld 2022-05-11 20:26 ` Thomas Ristenpart 2022-05-12 11:47 ` Jason A. Donenfeld 2022-05-13 6:19 ` Dominik Brodowski 2022-05-11 20:46 ` Pavel Machek
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).