Received-SPF: pass (google.com: domain of linux-crypto-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
Date:   Thu, 12 May 2022 13:47:06 +0200
From:   "Jason A. Donenfeld" <Jason@zx2c4.com>
To:     Thomas Ristenpart <ristenpart@cornell.edu>
Cc:     Yevgeniy Dodis <dodis@cs.nyu.edu>, tytso <tytso@mit.edu>,
        Nadia Heninger <nadiah@cs.ucsd.edu>,
        Noah Stephens-Dawidowitz <noahsd@gmail.com>,
        Stefano Tessaro <tessaro@cs.washington.edu>,
        "torvalds@linux-foundation.org" <torvalds@linux-foundation.org>,
        "D. J. Bernstein" <djb@cr.yp.to>,
        "jeanphilippe.aumasson@gmail.com" <jeanphilippe.aumasson@gmail.com>,
        "jann@thejh.net" <jann@thejh.net>,
        "keescook@chromium.org" <keescook@chromium.org>,
        "gregkh@linuxfoundation.org" <gregkh@linuxfoundation.org>,
        Peter Schwabe <peter@cryptojedi.org>,
        "linux-crypto@vger.kernel.org" <linux-crypto@vger.kernel.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>
Subject: Re: is "premature next" a real world rng concern, or just an
 academic exercise?
Message-ID: <YnzzuuLPssc3/tVe@zx2c4.com>
References: <YmlMGx6+uigkGiZ0@zx2c4.com>
 <Ym3ZM1P+uYYABtRm@mit.edu>
 <Ym5sICj5iBMn2w/E@zx2c4.com>
 <CAMvzKsiA52Si=PzOJXYwGSA1WUz-1S0A8cpgRJWDzpMkfFbX+Q@mail.gmail.com>
 <CAMvzKsiMY_+8HZqeFqD3tR65a3-JB0LG=+0jBBy1zF4GanrsGA@mail.gmail.com>
 <7EB51D84-90A4-4C97-9A81-14A8C32990F7@cornell.edu>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <7EB51D84-90A4-4C97-9A81-14A8C32990F7@cornell.edu>
Precedence: bulk

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/