Page MenuHomeFreeBSD

Tidy up random(4) driver after developer feedback and code audit.
ClosedPublic

Authored by markm on Mar 7 2015, 4:24 PM.
Tags
None
Referenced Files
Unknown Object (File)
Tue, Apr 16, 6:10 AM
Unknown Object (File)
Tue, Apr 16, 5:35 AM
Unknown Object (File)
Tue, Apr 16, 2:11 AM
Unknown Object (File)
Tue, Apr 16, 2:10 AM
Unknown Object (File)
Tue, Apr 16, 1:04 AM
Unknown Object (File)
Tue, Apr 16, 1:03 AM
Unknown Object (File)
Tue, Apr 16, 12:45 AM
Unknown Object (File)
Tue, Apr 16, 12:42 AM

Details

Summary

GENERAL

  • Update copyright.
  • Fix comments.
  • Improve module usage; dependancies in particular are useful, and use the crypto module rather than duplicating code.
  • Use macros for all locks.
  • Make kernel options for RANDOM_YARROW and RANDOM_DUMMY. If neither are supplied, then the default is Fortuna.
  • Move stuff out of locked regions when it does not need to be there.
  • Trim RANDOM_DEBUG printfs. Some are excess to requirement, some behind boot verbose.
  • Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks.
  • Redo read_random so as to duplicate random(4)'s read internals. This makes it a first-class citizen rather than a hack.
  • Use SYSINIT to sequence the startup.
  • Fix init/deinit sysctl stuff.
  • Add different harvesting "styles" to allow for different requirements (direct, queue, fast).
  • Add harvesting of FFS atime events. This needs to be checked for weighing down the FS code.
  • Fix the random(9) manpage. In its current state there is information rot and some hard-to fathom statements.
  • Make relevant sysctls also tunables.
  • Add basic logic to complain if the random(4) algorithm intent is not clear.
  • Repair kern.arandom. The old version went through arc4random(9) and was a bit weird.
  • Adjust arc4random stirring a bit - the current code looks a little suspect.
  • Use explicit_bzero() instead of bzero() or equivalent memset().

src/UPDATING

  • Add precursor UPDATING doom-and-gloom announcement.

src/sys/dev/random/build.sh

  • Add libz for unit tests.

src/sys/dev/random/dummy.c

  • Remove; no longer needed.

src/sys/dev/random/fortuna.c src/sys/dev/random/fortuna.h

  • Improve messy union to just uint128_t.
  • Remove unneeded 'static struct fortuna_start_cache'.
  • Tighten up up arithmetic.
  • Provide a method to allow eternal junk to be introduced; harden it against blatant by compress/hashing.
  • Assert that locks are held correctly.
  • Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks.
  • Turn into self-sufficient module (no longer requires randomdev_soft.[ch])

live_entropy_sources.c live_entropy_sources.h

  • Remove; content moved.

src/sys/dev/random/random_adaptors.c src/sys/dev/random/random_adaptors.h

  • Remove; no longer needed.

src/sys/dev/random/random_harvestq.c src/sys/dev/random/random_harvestq.h

  • Refactor to allow harvestq to be initialised twice, so we need to properly stop the kernel thread at deinit time. This is so we can later mess with pointers that would otherwise be changed under our feet.
  • Add early (re)boot-time randomness caching.

src/sys/dev/random/randomdev_soft.c src/sys/dev/random/randomdev_soft.h

  • Remove; no longer needed.

src/sys/dev/random/uint128.h

  • Provide a fake uint128_t; if a real one ever arrived, we can use that instead. All that is needed here is N=0, N++, N==0, and some localised trickery is used to manufacture a 128-bit 0ULLL.

src/sys/dev/random/unit_test.c src/sys/dev/random/unit_test.h

  • Improve unit tests; previously the testing human needed clairvoyance; now the test will do a basic check of compressibility. Clairvoyant talent is still a good idea.
  • This is still a long way off a proper unit test.

src/sys/dev/random/yarrow.c src/sys/dev/random/yarrow.h

  • Improve messy union to just uint128_t.
  • Remove unneeded 'start_cache'.
  • Fix some magic numbers elsewhere used as FAST and SLOW.
  • Provide a method to allow eternal junk to be introduced; harden it against blatant by compress/hashing.
  • Assert that locks are held correctly.
  • Fix the nasty pre- and post-read overloading by providing explictit functions to do these tasks.
  • Turn into self-sufficient module (no longer requires randomdev_soft.[ch])
Test Plan

Run the unit tests by going to sys/dev/random and typing:

$ ./build.sh
... then ...
$ ./funit_test
or
$ ./yunit_test

... and look out for crashes. These tests will be improved in time.

Diff Detail

Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
head/sys/dev/random/fortuna.c
176 ↗(On Diff #6595)

line longer than 80 character.

238 ↗(On Diff #6595)

line longer than 80 chars, there are a few more, 245 and 248, so I'll stop, but they need to be fixed.

353 ↗(On Diff #6595)

Add a KASSERT that bytecount is a multiple of RANDOM_BLOCKSIZE here. If not we are at risk of overflowing buf or put it in random_fortuna_read, but here is better. The caller, random_fortuna_read is documented as requiring a multiple, but does not enforce it, and this is a public interface.

I have looked at the calling code, and it looks like all the calling code ensures that there are enough bytes at the end of the buffer, but still, intentionally overrunning the buffer is terrible and should never be used in security code like this.

418 ↗(On Diff #6595)

We've accepted C99 as our standard, so these extra braces are unneeded, as C99 allows you to declare a new variable anywhere.

share/man/man4/random.4
38 ↗(On Diff #6515)

should we specify that this is a CSPRNG?

51 ↗(On Diff #6515)

We should link or comment that the system by default does this w/ the rc scripts.

59 ↗(On Diff #6515)

do we want to pipe this to hexdump -C so that people don't break their terminals when the run this?

63 ↗(On Diff #6515)

drop the, or add device after random(4).

98 ↗(On Diff #6515)

What about the discussion of the yarrow sysctls? Yes, the defaults are only fortuna, but we are loosing the information about yarrow.

share/man/man9/random.9
81 ↗(On Diff #6515)

why only better? maybe change to:

The
.Fn arc4rand
function will return crypographicly secure random numbers,
which are suitable for security and cryptographic purposes.

Or is this because when it isn't seeded, it isn't suitable?

129 ↗(On Diff #6515)

Why do we talk about arc4rand and read_random here, then use random() in the example?

share/man/man9/random_harvest.9
82 ↗(On Diff #6515)

Just change this to .Fn instead of using .Fo/.Fc.

117 ↗(On Diff #6515)

replace the " w/
.Em Dq very conservatively

sys/conf/files
2144 ↗(On Diff #6515)

can't you just drop the random random_yarrow from the spec? as it is covered by the random !random_dummy clause.

2146 ↗(On Diff #6515)

it sure would make things easier if we could specify random_fortuna as the default option.

2147 ↗(On Diff #6515)

same here wrt to dropping random random_yarrow.

sys/dev/random/build.sh
51 ↗(On Diff #6515)

If this is a unit test, it should be moved to src/tests/sys/dev/random and integrated into ATF.

head/sys/dev/random/fortuna.c
176 ↗(On Diff #6595)

Erm, sorry - I don't do the 80-column-only thing any more.

238 ↗(On Diff #6595)

I disagree that this needs fixing.

271 ↗(On Diff #6595)

OK, will fix.

353 ↗(On Diff #6595)

I'm happy to put in the KASSERT, but this is no public interface.

418 ↗(On Diff #6595)

I'll remove them when this can compile on MIPS (using GCC 4.2.n).

head/sys/dev/random/hash.h
32 ↗(On Diff #6595)

I will comment, thanks!

39 ↗(On Diff #6595)

Maybe not any more. At one point the kernel couldn't handle big stack variables.

head/sys/dev/random/random_harvestq.c
78 ↗(On Diff #6595)

Could be - I'll change it.

104 ↗(On Diff #6595)

Will do.

113 ↗(On Diff #6595)

Magic number. BAD, BAD! :-)

153 ↗(On Diff #6595)

That comment needs some TLC. Will fix.

201 ↗(On Diff #6595)

I've deliberately removed the RANDOM_ prefixes here.

296 ↗(On Diff #6595)

Will fix, thanks!

317 ↗(On Diff #6595)

Will investigate and fix.

337 ↗(On Diff #6595)

Will fix.

head/sys/dev/random/randomdev.c
145 ↗(On Diff #6595)

Oy. How did I end up writing *that*?

150 ↗(On Diff #6595)

Very good point!

153 ↗(On Diff #6595)

Another good point!

343 ↗(On Diff #6595)

I'm very keen to get an adaptive read rate on the "free" entropy sources. I'll be looking at this code again, myself.

head/sys/dev/random/fortuna.c
79–81 ↗(On Diff #6595)

these also go beyond 80 columns

439 ↗(On Diff #6595)

KASSERT?

head/sys/dev/random/yarrow.c
428 ↗(On Diff #6595)

Not sure what this means.

head/sys/dev/random/fortuna.c
439 ↗(On Diff #6595)

Will do.

head/sys/dev/random/yarrow.c
428 ↗(On Diff #6595)

"Complete waste of time" ;-)

It is a null function to stub a function call in higher layers.

(It may be possible to remove this; I'll check)

markm marked 34 inline comments as done.Jul 1 2015, 6:38 PM
markm added inline comments.
head/sys/dev/random/fortuna.c
353 ↗(On Diff #6595)

"Intentionally overrunning the buffer" is needed no matter what. The block cipher must generate enough data to fulfil the request, which means sometimes generating too much. I do things this way to avoid unnecessary block-transfers.

head/sys/dev/random/fortuna.c
353 ↗(On Diff #6595)

this random code is not performance critical code and being security code it should be coded safely. If you insist upon performance over safety, then you should document your assumptions, and the requirement that the calling code handle the intentional overflow. This helps people understand why the "bug" is there and is not a bug, and that future people who call the function won't misuse it.

Some more comments.

head/share/man/man4/random.4
65 ↗(On Diff #6595)

the random(4) device is seeded.

head/sys/dev/random/random_harvestq.c
242 ↗(On Diff #6595)

should probably just delete this, if you really need to know, you can turn on SYSINIT debugging which will print this.

head/sys/dev/random/randomdev.c
61 ↗(On Diff #6595)

We don't have a check for both _DUMMY and _FORTUNA.

We may also need a check for both _FORTUNA and _YARROW here, haven't checked.

65 ↗(On Diff #6595)

This isn't a minor number, this is a unit number, rename to RANDOM_UNIT?

123 ↗(On Diff #6595)

there is no lock protecting this list. It can be added/modified at run time, and we walk the list 10 times a second.

227 ↗(On Diff #6595)

why is this tsleep here? this appears to just be to slow things down, It can't depend upon randomdev_unblock to wake it up, as there is no lock to ensure that the wakeup happens, and for fortuna will only happen once.

Even switching to a pause doesn't make sense, because we don't check to make sure there is no more data and pause then. And it'd be trivial to bypass this check, as all you do is span lots of threads to do the write.

343 ↗(On Diff #6595)

Ok, I think that we should make this loop fill up hc_entropy_fast_accumulator's buf, and no more... xor'ing many, many times from rdrand or other sources doesn't make much sense... I could possibly see doing it two or three times buf size, but doing this possibly 100's of times doesn't make sense... There is only so much that xor'ing random data with more random data gets you.

head/sys/dev/random/randomdev_none.c
40 ↗(On Diff #6595)

Looks like ||defined(RANDOM_FORTUNA) needs to be added here.

head/sys/dev/random/uint128.h
46 ↗(On Diff #6595)

might want to comment that word0 is the least significant word.

head/sys/dev/random/unit_test.h
44 ↗(On Diff #6595)

rdtsc can be provided by machine/cpufunc.h instead of coping the code here.

head/sys/dev/random/yarrow.c
272 ↗(On Diff #6595)

this also may read beyond buf if wordcount is odd.

409 ↗(On Diff #6595)

KASSERT that this is a multiple of RANDOM_BLOCKSIZE.

head/sys/kern/kern_mib.c
164 ↗(On Diff #6595)

Did this get properly reviewed? Aren't there issues w/ the random device being blocked on boot, etc?

I didn't see any discussion of this.

I'm not sure this is correct or good.

head/sys/libkern/arc4random.c
59 ↗(On Diff #6595)

this is probably worse than before... if it's always zero before seeded, we now have a 100% predictable key instead of before we had a mostly predictable key.

head/sys/modules/crypto/Makefile
15 ↗(On Diff #6595)

why is this needed? The random module doesn't depend upon the crypto module, so there shouldn't be any changes here.

head/sys/net/if_ethersubr.c
429 ↗(On Diff #6595)

have you evaluated the impact of harvesting over 11x more data from ethernet subroutines than before?

This seems like a really bad change. We are now harvesting 136 bytes (on amd64) instead of only 12 bytes.

head/sys/net/if_tun.c
909 ↗(On Diff #6595)

If the above change was good, why wasn't it made here too?

head/sys/netgraph/ng_iface.c
708 ↗(On Diff #6595)

and here?

head/sys/ufs/ffs/ffs_inode.c
150 ↗(On Diff #6595)

has any benchmarks been run to test this? It's now enabled by default, but per your comment, seems expensive.

head/sys/vm/uma_core.c
2138 ↗(On Diff #6595)

There probably was a reason why this wasn't enabled by default, benchmarks?

markm removed rS FreeBSD src repository - subversion as the repository for this revision.
markm marked an inline comment as done.

Address parts of code review.

Get pre-alpha unit test to point of running.

(Added later) This passes the compile test but hasn't been checked/tested otherwise. A more complete follow-up is being worked on.

I only reviewed the changes in the new diff, I have not verified that my other comments were addressed.

sys/dev/random/fortuna.c
424

buf should be bytecount here

425

buf should be bytecount here.

sys/dev/random/random_harvestq.c
116

I believe this should be RANDOM_ACCUM_MAX not RANDOM_RING_MAX.

Are you to busy to make the requested changes? If I create a patch addressing the changes, would you accept that, or do you reject the requested changes?

In D2025#59153, @jmg wrote:

Are you to busy to make the requested changes? If I create a patch addressing the changes, would you accept that, or do you reject the requested changes?

I am working on quite a lot of stuff related to this, please be patient.

markm marked 23 inline comments as done.Jul 8 2015, 8:58 PM

Diffs to follow.

head/sys/dev/random/fortuna.c
353 ↗(On Diff #6595)

I'm happy to comment/document this.

head/sys/dev/random/random_harvestq.c
317 ↗(On Diff #6595)

This is a part of the kernel that confuses the hell out of me. Could you please propose a suitable fix?

head/sys/dev/random/randomdev.c
61 ↗(On Diff #6595)

There is no _FORTUNA option. It is implied by a lack of _DUMMY and _YARROW. I'll be removing a commented out _FORTUNA from sys/conf/NOTES.

123 ↗(On Diff #6595)

I'll be taking that risk in the sort term. A fix is on my TODO list.

227 ↗(On Diff #6595)

Please propose a fix. Linearising the writes is a desirable thing, and throttling the rate is a goal.

343 ↗(On Diff #6595)

Revisiting this is on my TODO list.

head/sys/dev/random/randomdev_none.c
40 ↗(On Diff #6595)

Negative. RANDOM_FORTUNA is implied by the absence of the other two.

head/sys/dev/random/uint128.h
46 ↗(On Diff #6595)

I think the average programmer could figure that out for themselves.

head/sys/dev/random/unit_test.h
44 ↗(On Diff #6595)

I'll look at this again when I finish the test for ARM.

head/sys/kern/kern_mib.c
164 ↗(On Diff #6595)

Please make a concrete proposal.

head/sys/libkern/arc4random.c
59 ↗(On Diff #6595)

rwatson disagrees with the approach, citing this paper: http://pdos.csail.mit.edu/papers/ub:apsys12.pdf

head/sys/modules/crypto/Makefile
15 ↗(On Diff #6595)

Modules are returning. I'm leaving it there to avoid churn.

head/sys/net/if_ethersubr.c
429 ↗(On Diff #6595)

I have done some, and I have evaluated the entropy so gained, and found it good. I'm hoping to publish this some time in the medium future, but for now the coverage is very useful. Where it is a burden, it can be disabled.

head/sys/net/if_tun.c
909 ↗(On Diff #6595)

Because I don't use the tun(4) device much, but good point, thanks!

head/sys/netgraph/ng_iface.c
708 ↗(On Diff #6595)

Same issue; I'm not much of a NG user.

head/sys/ufs/ffs/ffs_inode.c
150 ↗(On Diff #6595)

Basic benchmarks are OK. It can be disabled, and I intend to return for a proper research project.

head/sys/vm/uma_core.c
2138 ↗(On Diff #6595)

Folks are very sensitive about messing with it, and I haven't done the micro-benchmarks yet. Coarse benchmarks seem OK, and a face-to-face with rwatson has me not unhappy with this.

markm marked 12 inline comments as done.Jul 12 2015, 5:06 PM

I shall not be adding further review requests to this, as Phabricator does (what looks like be to be) weird things if you commit after closing. I'll be making ordinary commits for the smaller stuff, and I will take the more detailed projects to additional reviews here.

allanjude added inline comments.
sys/dev/random/randomdev.c
198

read_random is not taking care that len is a multiple of RANDOM_BLOCKSIZE here

this causes ZFS to panic when it tries to generate a GUID to create a new pool.

spa_generate_guid tries to read 8 bytes of random via read_random

random_fortuna_read() ASSERTs because bytecount (= 8) must be a multiple of 16

sys/dev/random/randomdev.c
198

Fixing now. Thanks!