[PATCH] arc4random implementation

[Florian Weimer]

The attached patch provides an implementation of arc4random, 
arc4random_buf, and arc4random_uniform.

I believe it is reasonably complete, except for the documentation.  I 
will submit that part once Zack's cryptography changes have been added 
to the manual, to avoid conflicts.  More statistical tests would make 
sense as well, but the tricky part will be to weigh run time of the test 
against an extremely low false positive rate (e.g., a one-in-1024 chance 
of failure, as it happens with some statistical tests, would not be 
acceptable).

For fork detection, there are two modes, depending on the availability 
of MADV_WIPEONFORK support in the kernel.

The MADV_WIPEONFORK implementation is much simpler and has the advantage 
that it avoids deadlocks even if direct clone/fork system calls are 
performed in multi-threaded processes.  It also avoids repeated mmap 
calls, which can fail due to OOM.

The fallback implementation uses two counters (one in a MAP_PRIVATE 
mapping, one in a MAP_SHARED mapping) for fork detection.  It relies 
heavily on locking.  Direct fork/clone system calls from multi-threaded 
processes can result in deadlocks, but the detection algorithm was 
designed in such a way that it would still work with such direct system 
calls.  stdlib/arc4random-forkdetect.c and 
stdlib/tst-arc4random-forkdetect.c have the gory details.

As the source for randomness, the Linux getrandom system call, a CPU 
randomness source, and /dev/urandom are used, in that order.  The idea 
is to give the kernel a chance to implement a particular randomness 
policy, before switching to the CPU generator.  The /dev/urandom 
fallback is a bit of a wart and may of course fail in a chroot 
environment, but I don't see a way to avoid it.

Since arc4random cannot report failure, there are various situations in 
which the process may be terminated in response to calling arc4random 
(OOM, lack of /dev/urandom).  For this reason, it is currently not 
advisable to use this implementation within glibc itself.  If we want to 
change that, we need to perform the first seed using AT_RANDOM, which is 
always available (unlike getrandom or /dev/urandom).

The implementation has sysdeps hooks for the randomness generation 
(kernel and CPU) and the AES key schedule and block operation (CPU 
only).  As a proof of concept, the CPU parts are implemented for x86. 
(These parts could conceivably be committed separately.)

The generator will not pass certification due to lack of periodic 
reseeding and backtrack protection.  Adding reseeding should be easy 
enough in a follow-up patch.  Efficient backtrack protection would 
probably need per-thread key schedules, so around 160 extra bytes of TLS 
data.  It also needs more frequent reseeding.  I think these aspects 
could be corrected in response to a review for certification, if that 
ever happens.

Thanks,
Florian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: arc4random.patch
Type: text/x-patch
Size: 142481 bytes
Desc: not available
URL: <http://sourceware.org/pipermail/libc-alpha/attachments/20180531/17163f00/attachment.bin>