Page MenuHomeFreeBSD

Fortuna: Fix false negatives in is_random_seeded()
ClosedPublic

Authored by cem on May 11 2019, 4:31 PM.

Details

Summary

We may have had sufficient entropy to consider Fortuna seeded, but the
random_fortuna_seeded() function would produce a false negative if
fs_counter was still zero. This condition could arise after
random_harvestq_prime() processed the /boot/entropy file and before any
read-type operation invoked "pre_read()." Fortuna's fs_counter variable is
only incremented (if certain conditions are met) by reseeding, which is
invoked by random_fortuna_pre_read().

The conditions under which Fortuna will reseed (including initial seeding)
are: (a) sufficient "entropy" (by sheer byte count; default 64) is collected
in the zeroth pool (of 32 pools), and (b) it has been at least 100ms since
the last reseed (to prevent trivial DoS; part of FS&K design). Prior to
this revision, initial seeding might have been prevented if the reseed
function was invoked during the first 100ms of boot.

This revision addresses both of these issues. If random_fortuna_seeded()
observes a zero fs_counter, it invokes random_fortuna_pre_read() and checks
again. This addresses the problem where entropy actually was sufficient,
but nothing had attempted a read -> pre_read yet.

The second change is to disable the 100ms reseed guard when Fortuna has
never been seeded yet (fs_lasttime == 0). The guard is intended to prevent
gratuitous subsequent reseeds, not initial seeding!

Test Plan
Loading configured modules...
/boot/entropy size=0x1000                                                                 <<<<<<<
...
---<<BOOT>>---
Copyright (c) 1992-2019 The FreeBSD Project.
Copyright (c) 1979, 1980, 1983, 1986, 1988, 1989, 1991, 1992, 1993, 1994
        The Regents of the University of California. All rights reserved.
FreeBSD is a registered trademark of The FreeBSD Foundation.
...
  AMD Extended Feature Extensions ID EBX=0x7<CLZERO,IRPerf,XSaveErPtr>
  TSC: P-state invariant
Hypervisor: Origin = "bhyve bhyve "
real memory  = 536870912 (512 MB)
avail memory = 477011968 (454 MB)
Event timer "LAPIC" quality 600
ACPI APIC Table: <BHYVE  BVMADT  >
FreeBSD/SMP: Multiprocessor System Detected: 4 CPUs
FreeBSD/SMP: 1 package(s) x 2 core(s) x 2 hardware threads
random: unblocking device.                                                                  <<<<<<
ioapic0 <Version 1.1> irqs 0-31 on motherboard
Launching APs: 1 3 2
random: entropy device external interface

(No "__stack_chk_init" errors.)

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

cem created this revision.May 11 2019, 4:31 PM
cem updated this revision to Diff 57319.May 11 2019, 4:38 PM

Fix lock recursion; didn't recall that pre_read invoked seeded().

cem edited the test plan for this revision. (Show Details)May 11 2019, 4:40 PM
delphij accepted this revision.May 13 2019, 4:11 PM
This revision is now accepted and ready to land.May 13 2019, 4:11 PM
cem added a comment.EditedMay 13 2019, 7:10 PM

Thanks for reviewing, Xin!

I think it is still a little concerning that /boot/entropy is only written on clean shutdown and /var/db/entropy* is only incorporated into Fortuna after multiuser starts, but that is a preexisting issue.

Edit: ok, the problem is not that bad. I had forgotten that it is rewritten on clean multiuser at boot time as well. So the repeated DoS has to occur very early during multiuser.

(That is, if an attacker can repeatedly cause unclean shutdown through some DoS, and other sources of entropy are infrequent or unavailable for harvest, early Fortuna output can be made to be predictable / low-entropy. We know early Fortuna output is used to seed arc4random(9) (as used by __stack_chk_init) extremely early, which means potentially the first 64kB block of arc4random(9) output is predictable in this scenario long after multiuser feeds /var/db/entropy into Fortuna (up to 300 seconds) and stack_chk cookies are predictable until clean shutdown.)

D19928, which registers fast random sources prior to __stack_chk_init, won't improve this alone. But it might be a useful component — e.g., one idea is maybe we harvest fast sources once or twice before initial seeding, even if fsp_length is already nominally sufficient. Another idea might be to signal arc4random(9) to reseed promptly after /var/db/entropy is loaded by userspace, rather than eventually. Or maybe we could modify save-entropy to write out /boot/entropy file(s) too (perhaps with an admin knob to disable, depending on /boot media). The latter seems closest to the FS&K model, although I have to assume there was some reason we chose /var/db instead of /boot.

This revision was automatically updated to reflect the committed changes.