2022-04-27 14:27:43

by Jason A. Donenfeld

[permalink] [raw]
Subject: is "premature next" a real world rng concern, or just an academic exercise?

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


2022-05-01 17:21:17

by Sandy Harris

[permalink] [raw]
Subject: Re: is "premature next" a real world rng concern, or just an academic exercise?

Jason A. Donenfeld <[email protected]> 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.

2022-05-02 10:05:31

by Jason A. Donenfeld

[permalink] [raw]
Subject: Re: is "premature next" a real world rng concern, or just an academic exercise?

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