loader: Expand EFI entropy if < 2048 bytes

[cperciva]

Summary

The EFI RNG on some platforms takes a long time if we request 2048
bytes of entropy, so we would like to request less; but our kernel
Fortuna RNG needs to be fed 2048 bytes in order to consider itself
"fully seeded".

Since 64 bytes of entropy is plenty to be cryptographically secure
(an attack of cost ~ 2^128 is infeasible, which implies a mere 16
bytes of entropy), use PBKDF2 (aka pkcs5v2_genkey_raw) to spread
the entropy across 2048 bytes. This is secure since PBKDF2 has
the property that every subset of output bytes has within O(1) of
the maximum possible amount of entropy.

Sponsored by: Amazon

[pjd]

stand/efi/loader/main.c

1266

Can you please explain the two lines above? I read it as "if the caller requests too little entropy to be secure, don't bother spreading it", but I'm not sure if this was the intent or am I reading the code wrong.

1291

Missing free(buf);

[cem]

I don't think there's any reason to spread this using pbkdf2 just to defeat the Fortuna input seeding thresholds. You might as well seed the 64 bytes and then 2048-64 bytes of zero, or whatever. (Internally Fortuna is compressing the provided seed material using SHA2.)

Basically your goal is to assert that this source is perfectly trustworthy and has relatively high bits-per-byte of actual entropy. That is probably reasonable.

(Maybe Fortuna should have a seeding mode for this built in and incorporate x86 rdrand/rdseed like this too.)

[cperciva]

In D46635#1063113, @cem wrote:

I don't think there's any reason to spread this using pbkdf2 just to defeat the Fortuna input seeding thresholds. You might as well seed the 64 bytes and then 2048-64 bytes of zero, or whatever. (Internally Fortuna is compressing the provided seed material using SHA2.)

Basically your goal is to assert that this source is perfectly trustworthy and has relatively high bits-per-byte of actual entropy. That is probably reasonable.

(Maybe Fortuna should have a seeding mode for this built in and incorporate x86 rdrand/rdseed like this too.)

In random_early_prime we divide the input into blocks of size sizeof(event.he_entropy)) and then process those one by one, with each block only being fed into one pool. so simply padding the entropy with zeros would result in most of the pools having no entropy.

stand/efi/loader/main.c

1266

Yes, that was the intention -- don't make an insecurely low amount of entropy look (to Fortuna) like it's large enough. Ok if I add more explanation to the commit message?

[cem]

In random_early_prime we divide the input into blocks of size sizeof(event.he_entropy)) and then process those one by one, with each block only being fed into one pool. so simply padding the entropy with zeros would result in most of the pools having no entropy.

Sure. But Fortuna seeds derive from all pools, only relying on at least one pool being uncompromised. (You could also just re-input the same 64 bytes 32x to touch all pools, although I don't think this buys you any additional safety.)

[pjd]

stand/efi/loader/main.c

1266

I'd suggest adding a comment to the code too.

[imp]

stand/efi/loader/main.c

1266

Especially since 64 is a magic number... as is 2048... please use #defines for these as well...

[pjd]

In D46635#1063118, @cem wrote:

In random_early_prime we divide the input into blocks of size sizeof(event.he_entropy)) and then process those one by one, with each block only being fed into one pool. so simply padding the entropy with zeros would result in most of the pools having no entropy.

Sure. But Fortuna seeds derive from all pools, only relying on at least one pool being uncompromised. (You could also just re-input the same 64 bytes 32x to touch all pools, although I don't think this buys you any additional safety.)

From all the options mentioned here, spreading the entropy seems least risky, also in case we (or someone building a product on FreeBSD) decide to replace Fortuna.

[cperciva]

Avoid magic numbers, and add comments.

[cperciva]

Add missing free(buf)

[cperciva]

This now depends on https://reviews.freebsd.org/D46693 which exposes some Fortuna constants.

[cem]

This is now sort of a layering violation, right? We're assuming Fortuna implements devrandom, but the interface is pluggable. We have 2-3 implementations in tree, and integrators might write their own for compliance reasons.

I would suggest adding a new interface to devrandom for providing boot-time trusted entropy (sufficient for initial seeding), and let devrandom implementations integrate that entropy appropriately.

[cperciva]

In D46635#1064502, @cem wrote:

This is now sort of a layering violation, right? We're assuming Fortuna implements devrandom, but the interface is pluggable. We have 2-3 implementations in tree, and integrators might write their own for compliance reasons.

I would suggest adding a new interface to devrandom for providing boot-time trusted entropy (sufficient for initial seeding), and let devrandom implementations integrate that entropy appropriately.

Yes it's a layering violation, but if the kernel is configured to need a different amount of seeding the worst case outcome here is that the boot process takes a bit longer. So I'm not too worried.

And yes, I considered doing the entropy spreading in devrandom, but figured it was cleaner just to keep the existing code. The only place where any of these changes will matter by default is EC2 -- everywhere else the default is to get 2048 bytes from EFI so there won't be any PBKDF2 going on. We only need to reduce the EFI RNG request to 64 bytes in EC2 because Graviton 2 systems have a weirdly slow EFI RNG.

[cperciva]

@pjd Are you ok with this now?