Date:   Wed, 27 Apr 2022 21:26:05 -0700
From:   Nadia Heninger <nadiah@...ucsd.edu>
To:     "Jason A. Donenfeld" <Jason@...c4.com>
Cc:     noahsd@...il.com, dodis@...nyu.edu, tessaro@...washington.edu,
        torvalds@...ux-foundation.org, djb@...yp.to, tytso@....edu,
        jeanphilippe.aumasson@...il.com, jann@...jh.net,
        keescook@...omium.org, gregkh@...uxfoundation.org,
        peter@...ptojedi.org, linux-crypto@...r.kernel.org,
        linux-kernel@...r.kernel.org
Subject: Re: is "premature next" a real world rng concern, or just an academic exercise?

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@...c4.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

Powered by blists - more mailing lists