Re: [PATCH v2] random: reseed more often immediately after booting

[Eric Biggers]

Hi Jason,

On Wed, Mar 09, 2022 at 12:18:50PM -0700, Jason A. Donenfeld wrote:
> In order to chip away at the "premature first" problem, we augment our
> existing entropy accounting with increased reseedings at boot.

I'm very glad to see this; this is something that I've been concerned about.
I think this is basically the right solution until something more sophisticated
can be implemented (as you said).

A few comments below.

> The idea
> is that at boot, we're getting entropy from various places, and we're
> not very sure which of early boot entropy is good and which isn't. Even
> when we're crediting the entropy, we're still not totally certain that
> it's any good. Since boot is the one time (aside from a compromise) that
> we have zero entropy, it's important that we shephard entropy into the
> crng fairly often. At the same time, we don't want a "premature next"
> problem, whereby an attacker can brute force individual bits of added
> entropy. In lieu of going full-on Fortuna (for now), we can pick a
> simpler strategy of just reseeding more often during the first 5 minutes
> after boot. This is still bounded by the 256-bit entropy credit
> requirement, so we'll skip a reseeding if we haven't reached that, but
> in case entropy /is/ coming in, this ensures that it makes its way into
> the crng rather rapidly during these early stages. For this we start at
> 5 seconds after boot, and double that interval until it's more than 5
> minutes. After that, we then move to our normal schedule of reseeding
> not more than once per 5 minutes.

Break up the above into multiple paragraphs?

> +/*
> + * Return whether the crng seed is considered to be sufficiently
> + * old that a reseeding might be attempted. This is the case 5,
> + * 10, 20, 40, 80, and 160 seconds after boot, and after if the
> + * last reseeding was CRNG_RESEED_INTERVAL ago.
> + */
> +static bool crng_has_old_seed(void)
> +{
> +	static unsigned int next_init_secs = 5;
> +
> +	if (unlikely(next_init_secs < CRNG_RESEED_INTERVAL / HZ)) {

The read of 'next_init_secs' needs READ_ONCE(), since it can be written to
concurrently.

> +		unsigned int uptime = min_t(u64, INT_MAX, ktime_get_seconds());
> +		if (uptime >= READ_ONCE(next_init_secs)) {
> +			WRITE_ONCE(next_init_secs, 5U << fls(uptime / 5));
> +			return true;
> +		}
> +		return false;

The '5U << fls(uptime / 5)' expression is a little hard to understand, but it
appears to work as intended.

However, one thing that seems a bit odd is that this method can result in two
reseeds with very little time in between.  For example, if no one is using the
RNG from second 40-78, but then it is used in seconds 79-80, then it will be
reseeded at both seconds 79 and 80 if there is entropy available.

Perhaps the condition should still be:

	time_after(jiffies, READ_ONCE(base_crng.birth) + interval);

... as it is in the non-early case, but where 'interval' is a function of
'uptime' rather than always CRNG_RESEED_INTERVAL?  Maybe something like:

	interval = CRNG_RESEED_INTERVAL;
	if (uptime < 2 * CRNG_RESEED_INTERVAL / HZ)
		interval = max(5, uptime / 2) * HZ;

- Eric