arc4random (was Re: Remove add-ons mechanism)

arc4random (was Re: Remove add-ons mechanism)

[Zack Weinberg]

On Fri, Sep 29, 2017 at 7:04 AM, Florian Weimer <fweimer@redhat.com> wrote:
> On 09/29/2017 12:01 AM, Zack Weinberg wrote:
>> I don't disagree with this patch exactly, but I was thinking of using
>> the add-ons mechanism to prototype a CSPRNG addition to glibc
>
> I've got something towards an implementation of arc4random (not certifiable,
> but it should be unpredictable in practice).

I'm delighted to hear that, and please let me know if i can help in
any way.  I don't have a whole lot of time toward libc hacking this
cycle but I would really like to see it done this cycle, so I'll find
the time. :)

> I think I found a way to do full fork protection even without
> MADV_WIPEONFORK, using a global counter in a MAP_SHARED segment. Reseeding
> is still needed to deal with a counter overflow on 32-bit architectures, and
> there is some overhead by the globally shared counter, but I think it is
> superior to all approaches I've seen so far (and it does not require a fork
> handler or a system call for every random number generation).

Is the idea that after a fork, processes may share RNG state but they
see each others' counter increments so they won't return the same
random bits from paired calls?  Kind of like how it would work for
multiple threads with a shared but atomically accessed RNG state?

zw

Re: arc4random

[Florian Weimer]

On 09/30/2017 01:58 AM, Zack Weinberg wrote:

>> I think I found a way to do full fork protection even without
>> MADV_WIPEONFORK, using a global counter in a MAP_SHARED segment. Reseeding
>> is still needed to deal with a counter overflow on 32-bit architectures, and
>> there is some overhead by the globally shared counter, but I think it is
>> superior to all approaches I've seen so far (and it does not require a fork
>> handler or a system call for every random number generation).
> 
> Is the idea that after a fork, processes may share RNG state but they
> see each others' counter increments so they won't return the same
> random bits from paired calls?  Kind of like how it would work for
> multiple threads with a shared but atomically accessed RNG state?

Exactly.  There's also a per-thread cache of an output block from the 
underlying DRBG, but without MADV_WIPEONFORK, that's invalidated if 
arc4random is called from multiple threads (because the global counter 
does not match the expected value anymore).  But at least it's not 
necessary to acquire a lock around the actual cryptographic operation.

But all this is only possible for 64-bit atomics.  If those are not 
available, I'm not sure what we can do.  The initial implementation will 
have a 32-bit counter in the shared page and a lock (not shared across 
processes) which is acquired around the entire arc4random operation.  If 
the 32-bit counter overflows, we need to replace the page with the 
global state with a new one (using MAP_FIXED) and reinitialize the 
secrets.  I don't think we can use any of the usual techniques for 
building a >32-bit counter from two 32-bit values because they rely on 
flag bits and waiting, but the other process can die at any time, and a 
waiting operation would get stuck at that point.

Thanks,
Florian