Patch to unify kernel randomness into a single interface. This
removes the LCG that is random(9) and replaces it w/ arc4rand(9)..
It also converts a number of locks from MTX_DEF to MTX_SPIN to
deal w/ locking issues...
Details
Details
Diff Detail
Diff Detail
- Repository
- rS FreeBSD src repository - subversion
- Lint
No Lint Coverage - Unit
No Test Coverage
Event Timeline
There are a very large number of changes, so older changes are hidden. Show Older Changes
Comment Actions
Hi,
I have made a few comments inline. Could you please check if they should be addressed and fix these issues if they are real issues?
Thanks in advance!
| sys/libkern/arc4random.c | ||
|---|---|---|
| 53 | I think it's probably better named 'get_last_resort_seed' instead, or "best effort seed" to avoid confusion. | |
| 56 | Maybe replace that 8 with sizeof(uint64_t) or add a comment? | |
| 68 | We should probably move this to the beginning of the function as it's an interface contract. | |
| 90–91 | Why do we acquire arc4_mtx here and not after line 100 considering 'key' is on stack? I'm not very convinced with the benefit of serialization here. Additionally, getting tv_now would probably be better moved before priv_read_random? | |
| 90–91 | The comment should be changed to reflect get_best_seed. | |
| 98 | I think it's probably not a good idea to move this out the 'if (r<=0)': this would reduce entropy by stamping the pattern (of size r) over the rest of 'key'. My understanding is that the old code tries to mix good entropy with whatever is on stack at the time. | |
| sys/libkern/random.c | ||
| 59–60 | Should we call panic() here so that code calling it (probably when INVARIANT or DIAGNOSTIC is enabled) would get a hard break or remove this function completely? Another thought: maybe we pass through that to the random adapter as an entropy 0 entropy feed? | |
| sys/sys/libkern.h | ||
| 81 | I would suggest adding a comment here saying it's a no-op (or does X). | |
| 85 | Should use full prototype (random(void)), ditto for later inline functions. | |
Comment Actions
I'll update the patch to address the ones I agree with.
| sys/libkern/arc4random.c | ||
|---|---|---|
| 53 | Good idea, I'll change it.. | |
| 56 | yeh, I thought about that, but as uint64_t isn't going to change size, it's a really long way to spell 8.. :) The other option would be to do a uint64_t cc; do sizeof cc and then cc = get_cyclecount(); but now we are introducing a variable.. Also forgot that the 8 is hard coded into the be64enc name... | |
| 68 | sure, will do.. | |
| 90–91 | because that was the way the code is.. :) I would prefer not to do too much to arc4random as we place to remove it anyways.. The tv_now is just scheduling when we need to reseed next, nothing else. | |
| 90–91 | doh, yes, I agree.. | |
| 98 | I did this because we now have a "better" seed than just random junk on the stack. The old code was doing this if we got good randomness from yarrow, so I was just copying that code since we now have a "good" seed from either yarrow or from the best_effort function. | |
| sys/libkern/random.c | ||
| 59–60 | No, I want to delete this function entirely in the future. It's easy enough to grep through and remove, and we only have a handful of callers. Most seeds provided are either time, or fed out of arc4random, so reseeding w/ it isn't really useful. | |
| sys/sys/libkern.h | ||
| 81 | I plan to update the man page to document that, so putting it here till we delete it doesn't seem too useful.. | |
| 85 | sure.. I didn't get an error so didn't think about it. | |
| sys/libkern/arc4random.c | ||
|---|---|---|
| 90–91 | Ok. | |
| 98 | Yes you are right that we are using the same copying when good entropy is available -- I have misunderstood the old code here. However, when r == 0 || -1, no stamping is done because we wanted to use the stack data as a last resort. So I think my question holds -- it's probably not a very good idea to expand the (8+8+4 or 8+8+8) bytes worth of time data to 256 bytes because less entropy is available from time information and by copying the same data multiple times, we eliminated the entropy from junks on stack and that doesn't seem like an improvement. | |
| sys/libkern/random.c | ||
| 59–60 | Ok that sounds reasonable. | |
| sys/libkern/arc4random.c | ||
|---|---|---|
| 98 | someone who knows arc4random should comment on this… I don't know how strong the key needs to be seeded to be effective. From my gut, if the stack is all zeros (which it might be), then it seems like it'd be better to not use the stack, and use the last effort seed… or we hash whats on the stack, and expand the 32 to 128 bytes, and the other half to the hash of the stack… (I was also thinking of maybe having the memory test sum up memory, and using that, but, that's just keeping this on life support) But I'd prefer we just remove arc4 myself. | |
Comment Actions
update to address some of delphij's comments...
Remove the phony random function so it can't do damage... I think I
might have been able to get into a loop if the conditions were right..
The Dummy rng doesn't return data, so the code will do the right thing
(as right as it can be) even when a real adaptor isn't available..
Comment Actions
change random_uniform to eliminate a division/multiplication and
instead only use addition or simple bit operations, this should help
performance on embeded systems that don't have 64bit mul/div units..
| sys/libkern/random.c | ||
|---|---|---|
| 142 | known compile issue, I'm working on a test case for this at the same time. | |
Comment Actions
fixed compile, and included a test suite for random_uniform...
Oh, the random_uniform came from OpenBSD via Oliver Pinter of
HardenedBSD.. Sorry for not including this in the original update..
Comment Actions
Apart from the spin locks, I'm happy. If you can get the spin locks past JHB and RWatson, then I'm 100% happy.
| sys/dev/random/dummy_rng.c | ||
|---|---|---|
| 66 | I'm happy with this. Good riddance to trouble! | |
| sys/dev/random/randomdev.c | ||
| 217 | Shouldn't this be set to NULL by default? | |
| sys/dev/random/randomdev.h | ||
| 44 | Good riddance also; I'm happy to see this go. | |
| sys/dev/random/yarrow.c | ||
| 150 | This is asking for trouble; it may work, but the scheduling folks aren't going to like it. I think this should be reverted and a possibly more detailed lock sought for the kernel random(9). Spin locks are very nasty to the scheduler, as I understand things. The work done inside spin locks needs to be really short-and-sweet, and this code is not that. Also Fortuna would need the same change, if this went through. | |
| sys/libkern/arc4random.c | ||
| 52 | I'm slightly nervous of this, but it is better than we had before, so this is just me registering concern, not objecting. | |
| 89 | OK. | |
| 91–95 | More spinlocks :-(. I really think that folks like JHB or RWatson should pass judgement on this. | |
| 98 | OK. | |
| sys/libkern/random.c | ||
| 35 | Unit tests are a good thing! | |
| 63–68 | OK, good. | |
| 88 | Test looks basic but better than the nothing we had. OK. | |
| sys/sys/libkern.h | ||
| 78 | Good! | |
| 81 | OK | |
| 112 | Yes, good. | |
| sys/sys/random.h | ||
| 34–47 | I'd much prefer to just shoot this thing. OK for now, but the hunting party is sharpening knives. | |
Comment Actions
Now that the scheduler has been "fixed", I'll try to run w/ normal mutexs and see if I have any issues. If that works, I'll update the patch, and also include an update for fortuna.
| sys/dev/random/randomdev.c | ||
|---|---|---|
| 217 | C rules default it to NULL, setting it to NULL is redundant, though I don't object to setting it to NULL. | |
| sys/dev/random/yarrow.c | ||
| 150 | I would like to see that random(9) have no restrictions on where/when it can be called. Some basic interfaces that should be quick shouldn't require thinking about locks, or having to prefect random data. I have thought about using _trylock on a normal mutex, but I believe that witness would still object. If we could get it past witness, we could return error (or have one w/ flags that will wait) and then the next layer up handles the failure by generating more, and reseeding again the next time it's called. Yes, if someone dd's from /dev/random all the time, it could cause problems. | |
| sys/libkern/arc4random.c | ||
| 52 | Yeh. I agree with you. I added the hash to help diffuse the possibly poor seed. The old xor of sec w/ nsec was a poor option, but required due to the LCG. I'll run this by my friends who know more than I do about these things. I do plan on adding support for RDRAND in the future. | |
| 91–95 | This lock will change to match yarrow/fortuna. Plus, once this goes in, and I get the PCPU version of ChaCha (or something else) in, then this lock will go away. | |
| sys/libkern/random.c | ||
| 88 | Yeh, I did do a python version, and the python version for small numbers verified that all possible values were returned. I didn't do any stats tests, but they did look uniform.. | |
Comment Actions
I reverted the yarrow spin lock changes, booted the kernel, and found
the following callchain:
lapic_handle_timer -> timercb -> handleevents -> callout_process ->
softclock_call_cc -> loadav -> arc4rand
So, I restored the spin lock changes, and made the same changes to
fortuna and verified that booting works fine:
kern.random.active_adaptor: fortuna
As I said previously, I feel that we need to support calling random
and it's various other accessor methods from all contexts, not just
sleepable lock contexts.
Comment Actions
add comment about confusion on how this new panic shouldn't really be new.
| sys/libkern/arc4random.c | ||
|---|---|---|
| 89 | I'm very confused how this call into yarrow causes a panic of: How is this possible when just two lines later we are currently locking a normal mutex in this case? I don't see how witness could possibly skip this. | |
| sys/libkern/arc4random.c | ||
|---|---|---|
| 89 | I do not understand your question. Where is the sleepable mutex lock 'two lines later' ? Sleepable mutexes cannot be locked in the idle thread, because the idle thread is disallowed to be inhibited. FreeBSD has walked long enough into the realtime approach that the right policy now is to disallow doing any work in the idle thread except putting CPU into the low power state. If something non-trivial needs to be done, separate thread context must be allocated at the idle priority and used for that work. For related reasons, no non-trivial work should be done in an interrupt handler, except acknowledging the interrupt and making the hardware This is yet another case why this whole patch causes strong disagreement. | |
Comment Actions
I'm setting up to do an audit of the uses of random(9) (and friends) in the kernel this weekend. Hopefully I can make concrete suggestions at that point.
| sys/dev/random/yarrow.c | ||
|---|---|---|
| 150 | I don't believe that is possible to be able to have no restrictions on where it can be called unless it it totally lockless. I believe random(9) can be made lockless, but this will take some redesign. How many consumers of kernel random(9) and friends need cryptographic randomness, and how many are just in need of perturbation? | |
Comment Actions
loadav() does not need cryptographic randomness, it just needs perturbation. A decent LFSR-based PRNG will do.
M
Comment Actions
The problem from your panic is that loadav() is marked as C_DIRECT, so it doesn't run in a thread context, but in interrupt context. It either needs to be fixed to not use the fancy random interface as Mark suggests, or the callout needs to be changed to not use C_DIRECT. We run loadav() once every 5 seconds at most, so I'm not sure it's super critical that it be C_DIRECT anyway.
Comment Actions
All of these comments are exactly why we should make random able to be called in any context. We will continue to find many cases of this, and end up introducing more code than is worth it if we add LCG's to all of these cases.
As I said in an email, lets go for full on proper random, and I'll run reasonable benchmarks to verify that performance is not hurt. pcmstat, dtrace, etc. This whole wack-a-mole on where the next thing that needs to be fixed is stupid and we should just make random(9) crypto-secure and usable, not add more hacks to the tree.
| sys/libkern/arc4random.c | ||
|---|---|---|
| 89 | My question is how does the code in -current function? I got a panic for locking a sleep mutex, but in unpatched -current, a similar lock is obtained. | |
Comment Actions
They do not need to be separate LCGs (or LFSRs). The old random() is fine for many uses, even if its generator could be tweaked a bit. It requires no locks and is quick enough.
As I said in an email, lets go for full on proper random, and I'll run reasonable benchmarks to verify that performance is not hurt. pcmstat, dtrace, etc. This whole wack-a-mole on where the next thing that needs to be fixed is stupid and we should just make random(9) crypto-secure and usable, not add more hacks to the tree.
Not all uses of random() require cryptographic-grade randomness and all the grief that brings with it. The loadavg() function for example would have been fine with a dreadful PRNG like RANDU(). We should not be trying to shoehorn a one-size-fits all. expensive locked thing in when a cheap LCG/LFSR will do.
A quick audit based on grepping the code suggests that it is not a hard problem to fix read_random() and arc4random() use-cases to be a full-cream key generators (or demoted where necessary) and let the other cases be regular cheap PRNGs.
Comment Actions
I think arc4random() and read_random() still need to be fixed the way you are doing them (modulo this concern), and they *are* allowed to be more expensive.
| sys/libkern/random.c | ||
|---|---|---|
| 57 | After seeing the grief involved in pulling the replacement into (e.g.) loadavg, I'm rethinking this. We still need cheap-and-cheerful LFSR/LCG generators for simple perturbation problems, and for those places where bringing locking infrastructure with us is also a no-no. Thus, I think we should keep *this* cheap LCG generator as it was. | |
| sys/libkern/random.c | ||
|---|---|---|
| 57 | I disagree… there is no grief once we do this properly.. If everyone had proper security background I would agree, or we added a commit hook that required security review for all use of random, but then that would of course teach people to roll their own, possibly causing a security issue because they needed proper randomness and didn't use it because it was too hard. | |
Comment Actions
I disagree with your disagreement :-)
- This is what code review is all about.
- KISS. From a 10-line LCG you are proposing a complex infrastructure of cryptographically secure RNG generator.
We need two things:
a) Pseudo-random numbers good enough for whitening out regular trends.
b) Unpredictable numbers suitable for security.
These are not the same thing, although the latter is frequently press-ganged into service as the former through laziness or misunderstanding, and idiots have been known to use the former as the latter.
Developers need to be able to read a man(9) page that tells them this in simple terms, and makes it abundantly clear that calling statistically_random() when you mean cryptographically_random() and vice-versa is a career-limiting move! :-)
Comment Actions
Mark,
I assert that people can't well the difference between 1 and 2 and there are cases where picking 1 seems like a good choice, but later we discover that it should have been cryptographicly secure. Always using cryptographicly secure RNG ensures that an entire class of bugs is eliminated from FreeBSD. Even if 90% of the developers could tell the difference, we still should. The new ChaCha example in D2012, it would be comparable to an LCG most (99%) of the time.
| sys/libkern/arc4random.c | ||
|---|---|---|
| 89 | please ignore this.. I forgot that the code was calling random() and the old code was previously broken/racy/etc. | |
Comment Actions
We have a deadlock on the difference between 1 and 2. Let that stand for now.
Lets see what the locking experts have to say on the issue of locking.
Comment Actions
I am still opposed to splatting spin locks all over the place. We have tools in place to catch violations, and you will just have to fix things like loadavg() appropriately (either by using something simpler or by moving the context it runs in, e.g. removing C_DIRECT).
Comment Actions
I would object to the characterization of putting spin locks all over the place… It's currently in two places (rc4 and yarrow OR fortuna), and planned to dropped down to one w/ D2012. Would it be better if I merged all this work into a single patch so that people can review the end goal? (If I do, I will not break it apart if it becomes too complicated.) I realize it's difficult to convey ideas, but I feel that I have conveyed the ideas in various emails (which has clearly not been read by everyone)
Comment Actions
Well, for one it is Yarrow AND Fortuna, but only one is active ant any time, so details.
My early locks in random(4) were heavily objected to because I had "easy" lock options; spin seemed to work so "let's go". I've now been educated to think otherwise, and only put trivial work into spin locks, and the current Yarrow/Fortuna proposals are WAAAAAY off trivial. There is encryption and hashing in there FCOL, and if this ever went to hardware assist (desirable!!!) this would involve another layer of scheduling.
Comment Actions
Just because people do not agree with you does not mean they are not reading your e-mails. They may still disagree. It's hard for me to see why loadavg() really needs crypto-quality RNG. Given the infrequent updates it would be a far lower bandwidth side channel than something like the hyperthreading SSL thing. Your refusal to really consider such comments raised by multiple people doesn't really give warm fuzzies. The fact is that there are a _lot_ of kernel APIs that are not safe from interrupt context. printf() is barely safe and it's the one case that arguably should be. Most code does not run in interrupt context. The callout stuff added some recent uses, but I suspect there are actually very few places that you would need to fix and you can fix them by removing C_DIRECT_EXEC. In fact, here's the entire list for C_DIRECT_EXEC. This does not look hard to audit:
cddl/dev/profile/profile.c: pcpu->profc_expected, 0, C_DIRECT_EXEC | C_ABSOLUTE);
cddl/dev/profile/profile.c: prof->prof_expected, 0, C_DIRECT_EXEC | C_ABSOLUTE);
cddl/dev/profile/profile.c: cpu, C_DIRECT_EXEC | C_ABSOLUTE);
cddl/dev/profile/profile.c: C_DIRECT_EXEC | C_ABSOLUTE);
kern/kern_synch.c: loadav, NULL, C_DIRECT_EXEC | C_PREL(32));
kern/kern_timeout.c: flags = (direct) ? C_DIRECT_EXEC : 0;
kern/kern_timeout.c: if (flags & C_DIRECT_EXEC) {
kern/subr_sleepqueue.c: sleepq_timeout, td, PCPU_GET(cpuid), flags | C_DIRECT_EXEC);
netpfil/ipfw/ip_dummynet.c: C_HARDCLOCK | C_DIRECT_EXEC);
sys/callout.h:#define C_DIRECT_EXEC 0x0001 /* direct execution of callout */
Aside from that you have interrupt filters (and if a driver needs RNG output it can get that in the ithread instead, I can't think of a good reason to do that in a filter), the scheduler (already addressed), and the interrupt support code that schedules ithreads.
Comment Actions
When they make comments that ignore comments I made in my e-mail, it sure feels like they aren't reading emails. I don't know what else to call that then. As I said in my original email, my final solution was to use PCPU for the first sx lock, and so then we'd only have ONE spin lock in yarrow/fortune. I don't see how one spin lock becomes multiple spin locks like you said.
There are many people who say, "I fail to see why we need security here", and then months/years later realize they did. It is better to fail secure than the fail insecure. The failure of people to acknowledge that it's better to fail secure doesn't give me a lot of warm fuzzies either.
cddl/dev/profile/profile.c: pcpu->profc_expected, 0, C_DIRECT_EXEC | C_ABSOLUTE);
cddl/dev/profile/profile.c: prof->prof_expected, 0, C_DIRECT_EXEC | C_ABSOLUTE);
cddl/dev/profile/profile.c: cpu, C_DIRECT_EXEC | C_ABSOLUTE);
cddl/dev/profile/profile.c: C_DIRECT_EXEC | C_ABSOLUTE);
kern/kern_synch.c: loadav, NULL, C_DIRECT_EXEC | C_PREL(32));
kern/kern_timeout.c: flags = (direct) ? C_DIRECT_EXEC : 0;
kern/kern_timeout.c: if (flags & C_DIRECT_EXEC) {
kern/subr_sleepqueue.c: sleepq_timeout, td, PCPU_GET(cpuid), flags | C_DIRECT_EXEC);
netpfil/ipfw/ip_dummynet.c: C_HARDCLOCK | C_DIRECT_EXEC);
sys/callout.h:#define C_DIRECT_EXEC 0x0001 /* direct execution of callout */Aside from that you have interrupt filters (and if a driver needs RNG output it can get that in the ithread instead, I can't think of a good reason to do that in a filter), the scheduler (already addressed), and the interrupt support code that schedules ithreads.
I feel that random(9) should be able to be called in these other context, and yes, a spin lock is expensive, but the limited number of calls that will acquire the spin lock, and time that it will be under, I don't feel that the cost of adding restrictions to random(9) out weigh the cost of using a spin lock.
I'm just trying to get FreeBSD to be a secure OS.
Comment Actions
That is not the way to think about security; it's like putting padlocks on anything that moves, including the toilet paper.
The idea is to have a coherent threat model, and then build your code to that. Simply slapping crypto everywhere without thinking the individual cases through properly isn't the right approach. That's like putting decent locks on your doors, checking your burglar alarm and making sure the kids obey the rules; not as simple as "padlock everything", but more practical.
Aside from that you have interrupt filters (and if a driver needs RNG output it can get that in the ithread instead, I can't think of a good reason to do that in a filter), the scheduler (already addressed), and the interrupt support code that schedules ithreads.
I feel that random(9) should be able to be called in these other context, and yes, a spin lock is expensive, but the limited number of calls that will acquire the spin lock, and time that it will be under, I don't feel that the cost of adding restrictions to random(9) out weigh the cost of using a spin lock.
A spin lock is RIDICULOUSLY expensive, and where they are in the random(4) code is going to noticeably affect kernel performance. See locking(9).
I'm just trying to get FreeBSD to be a secure OS.
So are we :-). We just disagree on the details.
M
Comment Actions
I am now specifically requesting that the reseed spin locks in Fortuna and Yarrow are removed.
I also request that a more fine-grained threat model is adopted, so that a heavyweight CSPRNG is not used where a lightweight PRNG will do.
Comment Actions
A spin lock is RIDICULOUSLY expensive, and where they are in the random(4) code is going to noticeably affect kernel performance. See locking(9).
Says all the people that don't understand the change, and haven't even requested a specific benchmark etc to see if it really is a noticeablely effects kernel performance.