Page MenuHomeFreeBSD

Limit the harvest rate of "fast" entropy for random(4) so as not to overload the system.
ClosedPublic

Authored by markm on Aug 23 2018, 4:52 PM.

Details

Summary

Limit the amount of "fast" entropy. We don't need nearly as much
for security, and the excess just slows things down badly.

PR: 230808
Submitted by: rwmaillists@googlemail.com, but tweeked by me
Reported by: Danilo Egea Gondolfo <danilo@FreeBSD.org>

Test Plan

Make the PRNG work hard while doing something intensive like "make
world". To make the PRNG work hard, do e.g.
$ dd if=/dev/random of=/dev/null bs=$((1024*1024))

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

markm created this revision.Aug 23 2018, 4:52 PM
markm added a comment.Aug 23 2018, 4:56 PM

This improves things drastically from what they were. More detailed work will follow.

sys/dev/random/random_harvestq.c
220 ↗(On Diff #47182)

I am aware of more improvements that can be made here, but I don't want "perfect to be the enemy of good enough".

delphij added inline comments.
sys/dev/random/random_harvestq.c
219 ↗(On Diff #47182)

Can you add a comment to explain what was the purpose for "+ 1" here? (My guess is that it's to make sure that the code below would at least perform a read once, but it's not exactly clear to me why we would do it when read_rate is a non-zero value).

If the goal is to have a non-zero local_read_rate, it's probably a good idea to use a construction like:

local_read_rate = atomic_readandclear_32(&read_rate);
/* Perform at least one read per round */
local_read_rate = MAX(local_read_rate, 1);
/* But not exceeding RANDOM_KEYSIZE_WORDS */

instead?

markm added inline comments.Aug 23 2018, 5:09 PM
sys/dev/random/random_harvestq.c
220 ↗(On Diff #47182)

The most obvious "safe" optimisation is to to remove local_read_rate altogether and always read some constant size of junk, such as RANDOM_KEYSIZE_WORDS, or possibly even 1 or 2 32-bit words.

markm updated this revision to Diff 47188.Aug 23 2018, 5:20 PM

Address review commnts from delphij.

markm marked an inline comment as done.Aug 23 2018, 5:21 PM
cem accepted this revision.Aug 23 2018, 5:24 PM

I think the improvement is conservatively correct re: my reading of Fortuna, and no need to let perfect be the enemy of good for now.

sys/dev/random/random_harvestq.c
219 ↗(On Diff #47182)

It's just a straightforward refactor of the previous +1 which was lower in the for-loop condition. This way the MIN() below can be spelled RANDOM_KEYSIZE_WORDS rather than RANDOM_KEYSIZE_WORDS - 1.

I agree it may not have purpose, but it is not really a regression in this patch ­— and this patch gives us the bulk of the improvement.

220 ↗(On Diff #47182)

That optimization may not be safe for Yarrow, right? That is part of my motivation for encouraging removal of Yarrow for 12.0.

This revision is now accepted and ready to land.Aug 23 2018, 5:24 PM
markm added inline comments.Aug 23 2018, 5:31 PM
sys/dev/random/random_harvestq.c
220 ↗(On Diff #47182)

There is a better reason to deprecate Yarrow (apologies for not bringing it up before); Yarrow's authors no longer recommend its use.

markm marked 2 inline comments as done.Aug 23 2018, 5:52 PM
delphij accepted this revision.Aug 23 2018, 6:12 PM

Looks good to me. @jmg do you have any concerns if this is landed as-is?

cem added inline comments.Aug 23 2018, 6:37 PM
sys/dev/random/random_harvestq.c
220 ↗(On Diff #47182)

Right. Emphasis on "part of." :-)

(I'm aware Yarrow and Fortuna share most of the same authors, and Fortuna builds on lessons learned from Yarrow. It is fresh in my mind — just read the chapter twice yesterday :-).)

markm marked 4 inline comments as done.Aug 23 2018, 7:10 PM
markm added a comment.Aug 23 2018, 7:19 PM

Thanks folks! Tinderbox build going, then I'll commit.

This revision was automatically updated to reflect the committed changes.
jmg added a comment.Aug 24 2018, 5:23 PM

@delphij this is my comment copied over from https://reviews.freebsd.org/D16866?id=47165 that was unaddressed.

head/sys/dev/random/random_harvestq.c
223

this still results in excessive seeding. It caps the read rate to pools*8*8, or putting 64 bytes per pool in for every 4 bytes read. As most things will read a minimum of 16 bytes (128 bits), the smallest expected value for read_rate is 5 (the increment isn't a proper ceil function), or 40 bytes per pool for every read. With the number of pools, that's a lot of extra work still.

gordon added a subscriber: gordon.Aug 24 2018, 6:11 PM

@markm Can you please specifically address the comment @jmg posted on this review (and it's ancestor)?

Thanks,
Gordon

markm added a comment.Aug 24 2018, 7:15 PM
In D16873#359829, @jmg wrote:

@delphij this is my comment copied over from https://reviews.freebsd.org/D16866?id=47165 that was unaddressed.

I needed to get something that was a drastic improvement over the stats quo, and pretty quickly too. I acknowledged that it was not perfect, and could stand some tweeking. I believe I achieved that goal.

This is a "good" fix, not a "perfect" one. I will work on something closer to "perfect" when I don't need to do it in quite such a rush.

cem added inline comments.Aug 24 2018, 8:22 PM
head/sys/dev/random/random_harvestq.c
223

This revision is aiming for "drastic improvement," not perfection. I 100% agree that there is a lot that can still be done to improve devrandom's performance, and that should be pursued, but with this change it is less of an existential crisis.
More aggressive reductions in feeding also carry slightly higher risk than this very conservative fix.

I'd like to point to the 100 ms sleep in the random_harvestq kthread — we accumulate read rate over 100ms (or longer) intervals. Now that we're capping read rate at RANDOM_KEYSIZE_WORDS (8), we bound entropy collection at 2kB per 100 ms or 20 kB/s. This may still be excessive, but it is de minimis for something like RDRAND which can do ~500 MB/s. We're looking at savings of less than 40 microseconds per second or ~0.004% on modern amd64 hardware.

As you touched on in the other review, we would get more return from our efforts by focusing on things like better education around initial seeding.

Just my 2¢.

jmg added a comment.Aug 24 2018, 9:12 PM

simple fix, limit local_read_rate to be 0 or 1. Even more simple that the fix that was committed.