Differential D14500
Implement getrandom(2) and getentropy(3) Authored by cem on Feb 25 2018, 2:44 AM. Tags None Referenced Files
Subscribers
Details The general idea here is to provide userspace programs with well-defined getrandom(2) is the more general API, and comes from the Linux world. getentropy(3) is added as a compatibility shim for the OpenBSD API. PR: 194204 Unit tests included. LTP tests pass. Here is an LTP emulation layer sufficient to run these tests on FreeBSD: $ cat lapi/getrandom.h #include <sys/random.h> $ cat lapi/syscalls.h #include <sys/syscall.h> $ cat tst_test.h #include <sys/param.h> #include <err.h> #include <errno.h> #include <stdarg.h> #include <stdio.h> #include <string.h> #include <unistd.h> static long TEST_RETURN; static int TEST_ERRNO; static inline void TEST(long a) { TEST_RETURN = a; TEST_ERRNO = errno; } #define tst_syscall syscall #define __NR_getrandom SYS_getrandom #define TPASS 1 #define TFAIL 0 #define TPASSMASK 1 #define TTERRNO 2 static size_t tot_pass, tot_fail; static inline void tst_res(int flags, const char *fmt, ...) { va_list ap; if ((flags & TPASSMASK) == TPASS) { printf("PASS "); tot_pass++; } else { printf("FAIL "); tot_fail++; } va_start(ap, fmt); vprintf(fmt, ap); va_end(ap); if (flags & TTERRNO) printf(": %d (%s)", errno, strerror(errno)); puts("\n"); } #define ARRAY_SIZE nitems static inline void SAFE_GETRLIMIT(int res, struct rlimit *out) { int ret; ret = getrlimit(res, out); if (ret != 0) err(1, "getrlimit"); } static inline void SAFE_SETRLIMIT(int res, const struct rlimit *in) { int ret; ret = setrlimit(res, in); if (ret != 0) err(1, "setrlimit"); } struct tst_test { size_t tcnt; void (*test)(unsigned); void (*test_all)(void); }; static struct tst_test test; int main(int argc __unused, char **argv __unused) { size_t i; for (i = 0; i < test.tcnt; i++) test.test(i); if (test.test_all != NULL) test.test_all(); printf("Pass: %zu/%zu\n", tot_pass, tot_pass + tot_fail); return (tot_fail != 0); } Under this emulation, all LTP getrandom(2) tests pass. (Compile with, e.g., gcc6 -Wall -Wextra -O2 -g -I. getrandom04.c.) Truss: $ LD_LIBRARY_PATH=$(cd lib/libsysdecode ; make -V .OBJDIR) $(cd usr.bin/truss ; make -V .OBJDIR)/truss.full $(cd tests/sys/kern ; make -V .OBJDIR)/sys_getrandom.full getrandom_randomness ... getrandom("@\M^Pb\M-"\M^S\M-d\^Br\^A\^A1$"...,4096,0) = 4096 (0x1000) mmap(0x0,266240,PROT_READ|PROT_WRITE,MAP_PRIVATE|MAP_ANON,-1,0x0) = 34367328256 (0x80073d000) getrandom("\aJql\M-Ej\M-S\M^]\M-+\f^\M-e\^Y"...,4096,1) = 4096 (0x1000) getrandom("\M-_\M^\_\M-K\M-I\M^I.l\M-S\M^]"...,4096,2) = 4096 (0x1000) getrandom("G\M-1Y\M^N\M^_3Y[4\M^I\M^Z\^S"...,4096,3) = 4096 (0x1000) passed writev(1,[{"passed",6},{"\n",1}],2) = 7 (0x7) ...
Diff Detail
Event TimelineThere are a very large number of changes, so older changes are hidden. Show Older Changes Comment Actions I really really don't like the Linux getrandom(2) API in general. This implementation of getrandom(2) allowed way too big read per call, allowing it in general could, although not necessarily allowing a (known and effectively useful) attack at this moment, expose continuous output of kernel PRNG to one single caller. The call itself is computational expensive, and because it was done in the kernel, it could easily allow a DoS attack the way it is currently constructed. Note that it seems, at least according to the manual page of Linux getrandom() they allowed a quite big read too, and implementing getrandom() in kernel means it's hard to mitigate this. If we must implement the same semantics, we should probably further penalize the callers by adding voluntary yields to other threads, but for compatibility I don't see any good reason not to implement it with arc4random(). The OpenBSD getentropy() API has restricted allowable maximum to 256, thereby limited the userland's ability to obtain long, continuous output sequence from the kernel and it's much narrower usage would discourage misuse too. Comment Actions What specific changes do you want made? The same criticism can be leveled at /dev/urandom. This uses the exact same kernel interface (READ_RANDOM_UIO). (Additionally, this is an orthogonal and theoretical concern — if our PRNG is vulnerable to a single caller reading continuous output, even getentropy()'s 256 bytes can be repeatedly polled by a single attacker. Additionally, it probably means SHA256 is broken.)
How? This uses the exact same interface as /dev/urandom. If random(4) can easily allow a DoS already, that problem seems orthogonal to this change.
There are already voluntary yields every PAGE_SIZE bytes in READ_RANDOM_UIO via uiomove().
arc4random() doesn't provide the blocking/non-blocking behavior essential to the API. If arc4random()'s chacha20 + reseed is superior to raw Fortuna, it could be moved inside READ_RANDOM_UIO and used by /dev/urandom as well. Comment Actions My preference would be only implementing a blocking getentropy() in kernel, but am open with other proposals as long as there is compelling reasons.
Yes, but my understanding is this new API is intended for all applications (while /dev/urandom access may be blocked with permission), e.g. an application in capability mode should have access to it.
Agreed.
This will not go through any permission checks.
You are right here, but still, why must this be done inside the kernel?
Would you mind elaborating the scenario where non-blocking behavior is desirable on FreeBSD, given that we have RANDOM_ATTACH entropy source and additional entropy can be preloaded by loader? Comment Actions I guess so, but the concern is still a completely hypothetical attack against SHA256 and Fortuna. And maybe a local DoS — I'm still unclear on that.
I suppose. The only checks on random(4) today are the VFS ones, though, and probably those only exist because of the constraints of the unix filesystem — every file must have permissions. I don't see it being especially useful to restrict access to Fortuna output on a UID basis. Do you have a use in mind?
Why must it not be done inside the kernel? The only distinction is that a smaller per-syscall threshold imposes a slightly higher CPU cost on a buggy, malicious or compromised userspace application requesting lots of bytes. It isn't an effective or principled means of resource-constraining the userspace application. I suspect but have not empirically demonstrated that a userspace application repeatedly polling the getentropy() interface for 256 bytes at a time uses approximately the same time in the kernel, if not more, as a userspace application making large read requests. Additionally, userspace CSPRNGs have a strong tradition of being broken in subtle ways.
I don't have a specific scenario in mind. It seems desirable to conform to the intent of userspace applications. If an application has decided that a non-blocking request is desirable, I don't think blocking is the right thing to do — this is the kind of behavior that drives application developers crazy. I suppose we could document that GRND_NONBLOCK is not allowed and return EINVAL if it is used? On the other hand, the random(4) manual page specifically calls this out in the second paragraph: The generator will start in an unseeded state, and will block reads until it is seeded for the first time. This may cause trouble at system boot when keys and the like are generated from random so steps should be taken to ensure a seeding as soon as possible. The prominent placement makes it seem like unseeded state could be a real problem.
I doubt RANDOM_ATTACH provides very much entropy at all, especially on embedded hardware. Is it actually sufficient to seed random(4) alone? rc.d/random and /var/db/entropy-file + /boot/entropy may provide sufficient entropy to seed random(4) most of the time. There is a chance the on-disk entropy doesn't exist — either in the installer, or if there is filesystem corruption, or an administrator simply deletes the files, or any other possible cause. /boot may be readonly and we may be unable to write out any entropy there. There may be various reasons an appliance or embedded system may want to avoid writing some entropy to disk and thus may struggle to re-seed the random device soon after reboot. Comment Actions Plus it has loosen the permission check from something that can be restricted with file system permissions or devfs rules to unrestricted.
No but you can restrict this with file system permissions or devfs rules (e.g. in a jail) now, with the proposed change, it's gone, and I'm asking for a good reason for that change.
See my comments above.
It's easier to discipline CPU usage when the code is in userland than in kernel, and there is no good reason so far that you have raised to support doing it in kernel.
But how can this be fixed by doing it in kernel?
This seems to be a non-goal.
Well, two things:
Allowing non-blocking behavior means the application developer is free to do creative and harmful things that they have no idea what it could be, and we should not give them the chance to make this kind of mistakes.
Or, that API should not exist at all. If the goal is to provide compatibility, then it's better to emulate the same API but ignore the GRND_NONBLOCK request and treat it as a blocking request.
It *can* be unseeded, but in practice it *should never* be, and when it happens (for instance on a misconfigured system), it's very visible.
I can't assert about RANDOM_ATTACH would work 100% on embedded hardware that I haven't seen and being able to seed random(4) alone, but since we are limited by the key size, it's really not that many, and the embedded systems that I ever own that runs FreeBSD would have unblocked way before mounting /, and if they don't, existing applications would break anyway. Applications demanding for cryptographically secure entropy should be blocked until the entropy device until the entropy device is unblocked. You can not both choose being secure and take the liberty of not properly feeding the entropy source properly at the same time. Comment Actions Please do not remove O3: Kernel Random Numbers Generator from reviewers, the proposed change have material impact to the kernel random number generator's behavior and I don't think it's Okay to bypass it. Comment Actions I think mapping NONBLOCK behavior to blocking transparently would be a pretty big POLA violation. If we don't want to support non-blocking operation I would much rather that we fail the request with EINVAL. That said, if existing 3rd party applications are using getrandom() with the non-blocking flag now, then the end result will be that developers decide FreeBSD is broken and just don't use the API at all on FreeBSD via #ifdef's or the like. We have limited control on what we can force application developers to do. I'm also not sure how many administrators choose to restrict access to /dev/random and /dev/urandom in practice. In our default devfs rulesets used for jails we treat /dev/random as being as fundamentally needed as /dev/null and /dev/zero. We could perhaps make access to getrandom a jail permission though such that an admin could create jails which do not permit access to the system call? Comment Actions Meta comment: This code review has turned into a culture war over whether the feature should exist at all. I don't think that's the function of code review. If you want to argue about this stuff all day, please take it to arch@. Ideally someone other than me actually takes a look at the code changes at some point and ACKs or points out problems. I reckon it is perfectly valid to review the code as-is, but request pre-commit approval from core or consensus of arch. Please, uh, focus on the code. Thank you. I think the restriction here is accidental. You're looking at urandom as if it a potential attack vector exposed to untrusted applications. And in a sense, it is. In another sense, though, it is userland crypto's only hope of providing a secure implementation. That is why it is so important it be available to all consumers. The syscall was not created on a whim.
https://lwn.net/Articles/606141/ There are problems with using fd-based random sources from library code:
https://lwn.net/Articles/711013/ Anyway, FreeBSD is not Linux nor is it OpenBSD. And a serious discussion of potential security impact is warranted. But I don't think the ability to restrict access to the devfs node is an intentional feature we are losing — it's just a historical accident.
What is the justification for needing to run a jail without access to a good random source? John suggested a compromise position where jails can restrict use of this syscall. I'm not sure I buy that it's useful, but would that be an ok compromise for you?
Sorry, maybe I'm dumb. But if they answered my question, I wouldn't be asking it. Can you clarify?
Consider userspace program consisting of while(1) { getentropy(buf, 256); }. The CPU use is all in kernel — either in READ_RANDOM_UIO or syscall entry/leave code.
Doing it in kernel (as is random(4)) has the advantage of being the smaller change and least likelihood to introduce a regression.
I don't follow. If we don't care about userspace programs, why do we provide a syscall interface at all? Why implement kevent() or O_NONBLOCK and instead just do all I/O blocking, since it is easier? The kernel exists to serve userspace applications. A secure kernel that doesn't do anything is worthless.
Well, you hope. But it is not guaranteed.
I'm not sure I buy that these are the only options.
Ok — what about the compromise of EINVAL on NONBLOCK requests?
Please at least try to work with me here. A flat "no" without justification isn't persuasive. The API exists in the real world; the question is whether we make application developers and porters emulate it on FreeBSD repeatedly, in potentially broken ways, or whether we provide native support. I am ok ignoring your NACK if this is your only feedback. I'm trying to find common ground and compromise, though.
Strongly disagree. I'd rather signal the calling program with ABRT or TERM or whatever than silently block NONBLOCK requests.
In other worse, this API *can* be useful? Misconfigured systems are real systems we cannot just ignore. Here's an example (on Linux) of early boot blocking causing problems: https://lwn.net/Articles/693189/
They get that behavior with the ordinary flags=0 invocation.
Non-block mode does not return insecure bytes; it just returns an error code instead of blocking. I don't see how this change impacts sys/dev/random number generation in any way. Please clarify. +1
A similar result will happen if we block when nonblocking was requested, except it will take them longer to debug the problem and they will be mad at us for wasting their time. I'd rather they find out sooner than later. Ideally, they even file a bug and ask for the behavior to be added.
+1
That is a compromise I can live with. Of course, there's no point implementing this if delphij will not concede any ground. Comment Actions And to clarify, I'd much prefer to have code review first, but lacking any compelling reason not to, I plan to go ahead and commit this in the next few days. Comment Actions Adding cperciva and jmg who may be able to help provide some opinions about how they think this should go.
Comment Actions Not looking at the code, but on the design front:
Comment Actions Thanks! Is jmg still active? I haven't heard from him in a couple years. Both APIs are unconditionally available, as-written. Not checking return codes is a harder problem to solve. How do you propose to handle the cases where these APIs would produce an error code today? Signal the process (with a default-terminate signal), like kern.trap_enotcap=1? I think it's an interesting suggestion. It deviates pretty far from our conventional approach to system calls, including read(2) of the random device. But, if there is consensus I am willing.
Agree.
Performance goals are a totally orthogonal concern to the API. We can worry about that separately. Current random(4) device performance is totally adequate (hundreds of MB/s).
Agreed.
Yes. There's no point providing a compatible API if it is not compatible.
I'm not sure I follow. Our random(4) Fortuna already does track when it has sufficient input to consider itself seeded, and this revision does not change that in any way. The method is: READ_RANDOM_UIO() invokes the ra_pre_read() method of the underlying algorithm (e.g., Fortuna) repeatedly until that algorithm returns true via the ra_seeded() method. (READ_RANDOM() is similar, but does not block until the algorithm is seeded -- instead returning a zero byte result.) random_fortuna_pre_read() checks fs_pool[0].fsp_length must be >= the effective min pool size, which is default DEFPOOLSIZE = 64 bytes. If this is the case, it may invoke random_fortuna_reseed_internal(). random_fortuna_reseed_internal() unblocks the random(4) device, as well as triggering ra_seeded() to return true. fs_pool[0].fsp_length begins as zero at boot. It is modified in the Fortuna ra_event_processor method, random_fortuna_process_event(), if the event's he_destination (mod NPOOLS = 32) is zero. In that case, the event's he_size is added to fsp_length . The ra_event_processor method is invoked from a couple different avenues. One possible source of entropy is random(4) device writes, via randomdev_write() -> randomdev_accumulate(). This source is restricted to PAGE_SIZE input bytes every 100 milliseconds. After hashing, the output entropy (2 32-bit words, or 8 bytes) is fed to he_destination of zero (as well as 1-7). So: a single thread write(/dev/random) takes ~700 milliseconds to seed our Fortuna. The other source of entropy is random_harvestq_fast_process_event(). This is invoked from a couple places. random_kthread walks through a global ring of collected entropy events and passes them to ra_event_processor via random_harvestq_fast_process_event. At boot, this ring is empty. random_harvestq_prime looks for a module name "boot_entropy_cache" and divvies up the contents 8 bytes at a time to incrementing he_destinations. It also subtracts 256 bytes from the front arbitrarily. For Fortuna's 32 pools, this means at least 256 + 1744 = 2000 bytes from this source are sufficient to unblock the random device. Finally, random_harvest_direct will send 8 bytes of entropy to the next he_destination round-robin. It is invoked from random_kthread when any harvest_context.hc_entropy_fast_accumulator.buf[] entry is non-zero. It is also invoked from random_sources_feed(), which invokes rs_read() methods on any registered random sources, up to some "read rate" + 1 multiple of the poolcount. (The read rate will be zero until random(4) device is successfully unblocked, so for our purposes, rs_read() is invoked only 32 times per random_sources_feed().) random_sources_feed() is invoked from random_kthread(). Some notes about random_kthread(): It starts at SI_SUB_KICK_SCHEDULER, and it blocks for 100ms every iteration, regardless of whether the underlying algorithm is seeded yet or not. Anyway: none of this is affected by this revision. Our random device already blocks until it is seeded, and I do not suggest changing that behavior.
Comment Actions Remove duplicate freebsd32_getrandom and just re-use sys_getrandom -- jhb's Comment Actions Please take a look at comments inline. I'm still not in favor of the getrandom() API but I will not object it either, as long as a cryptographer signs off it.
Comment Actions I will address the feedback, thanks!
Comment Actions Incorporate delphij's suggestions:
Comment Actions I was going to test the behavior re: interruption on Linux with the following test program, but I do not have enough free RAM on my Linux system because it is also running Chrome 😂 😂 😂 . If anyone else has 2GB of RAM spare on a Linux system, the following test might be interesting (try pressing Ctrl+C after starting it): #include <sys/random.h>
#include <err.h>
#include <limits.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
int
main(int argc, char **argv)
{
void *buf;
ssize_t ret;
buf = malloc(INT_MAX-1);
if (buf == NULL)
err(1, "malloc");
ret = getrandom(buf, INT_MAX, 0);
printf("ret: %zd\n", ret);
if (ret < 0)
err(1, "getrandom");
return 0;
}
Comment Actions Address CR feedback:
Comment Actions Could you please create a review of just the sys/dev/random/randomdev.c portion of change (see my comments inline) as this is a self-contained bugfix and is orthogonal to the rest part of this review? It's easier to understand smaller changesets and future readers of code history would have an easier time to see the reasoning when they are done in smaller and self-contained units.
Comment Actions Sure, that makes sense. I will do so.
| ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||