arc4random/csprng

arc4random/csprng

[Rich Felker]

I haven't followed what's been happening with posix_random lately, but
glibc has adding the arc4random interfaces and it seems reasonable
that we should too, with the easy option to add the posix_random name
for it and whatever interface details POSIX decides on.

The glibc implementation looks like it's essentially CTR mode AES.
This is probably a pretty good choice, but unless there are strong
reasons not to I'd probably rather go with Hash-DRBG or HMAC-DRBG
utilizing the existing SHA-256 code we already have. That would avoid
the need to write or import any new cryptographic code (and the
associated risks) and keep the size cost minimal. This seems better
for forward-secrecy too, but I'd like to better understand the
conditions under which Hash-DRBG and HMAC-DRBG provide
forward-secrecy.

One topic I thought was a huge bikeshed was the whole fork-detection
or fork-safety thing, but apparently it's not for glibc and perhaps
other implementations because they've opted to make their csprng
lock-free and incurred a lot of complexity with safely replacing
pseudo-immutable state. I want to avoid most or all of this issue by
just using a proper lock, but it might still be necessary to do some
nasty hack for the case where fork is called from a signal handler
interrupting the csprng. The only way to avoid that entirely is to
block signals while the csprng runs, which is probably unjustifiably
slow.

Rich

Re: arc4random/csprng

[Florian Weimer]

On 07/02/2018 10:39 PM, Rich Felker wrote:
> I haven't followed what's been happening with posix_random lately, but
> glibc has adding the arc4random interfaces and it seems reasonable
> that we should too, with the easy option to add the posix_random name
> for it and whatever interface details POSIX decides on.

Note that it's probably not going to make it into glibc 2.28 at this point.

> One topic I thought was a huge bikeshed was the whole fork-detection
> or fork-safety thing, but apparently it's not for glibc and perhaps
> other implementations because they've opted to make their csprng
> lock-free and incurred a lot of complexity with safely replacing
> pseudo-immutable state. I want to avoid most or all of this issue by
> just using a proper lock, but it might still be necessary to do some
> nasty hack for the case where fork is called from a signal handler
> interrupting the csprng. The only way to avoid that entirely is to
> block signals while the csprng runs, which is probably unjustifiably
> slow.

The main lock (for non-current kernels) is needed for the fork detection 
counters.  Fork detection is required for compatibility with 
applications which call clone/fork system calls directly, so that the 
fork handler will not run.  Without MADV_WIPEONFORK, the only reliable 
thing I came up with is the dual-counter approach (MAP_PRIVATE vs 
MAP_SHARED) and something like software TM.  At that point, avoiding the 
lock for bit generation itself is just a very minor change.

Thanks,
Florian

Re: arc4random/csprng

[Rich Felker]

On Tue, Jul 03, 2018 at 03:36:59PM +0200, Florian Weimer wrote:
> On 07/02/2018 10:39 PM, Rich Felker wrote:
> >I haven't followed what's been happening with posix_random lately, but
> >glibc has adding the arc4random interfaces and it seems reasonable
> >that we should too, with the easy option to add the posix_random name
> >for it and whatever interface details POSIX decides on.
> 
> Note that it's probably not going to make it into glibc 2.28 at this point.

Now the race is on, I guess. ;-)

> >One topic I thought was a huge bikeshed was the whole fork-detection
> >or fork-safety thing, but apparently it's not for glibc and perhaps
> >other implementations because they've opted to make their csprng
> >lock-free and incurred a lot of complexity with safely replacing
> >pseudo-immutable state. I want to avoid most or all of this issue by
> >just using a proper lock, but it might still be necessary to do some
> >nasty hack for the case where fork is called from a signal handler
> >interrupting the csprng. The only way to avoid that entirely is to
> >block signals while the csprng runs, which is probably unjustifiably
> >slow.
> 
> The main lock (for non-current kernels) is needed for the fork
> detection counters.  Fork detection is required for compatibility
> with applications which call clone/fork system calls directly, so

How do you consider this supported usage at all? The tid in the TCB
will be invalid after such a call, and other things may be broken too.

IMO after syscall(SYS_fork or SYS_clone) the application is in an
async-signal (or even more restricted) context and certainly can't use
high level interfaces like arc4random.

Rich

Re: arc4random/csprng

[Florian Weimer]

On 07/03/2018 04:47 PM, Rich Felker wrote:

>> The main lock (for non-current kernels) is needed for the fork
>> detection counters.  Fork detection is required for compatibility
>> with applications which call clone/fork system calls directly, so
> 
> How do you consider this supported usage at all? The tid in the TCB
> will be invalid after such a call, and other things may be broken too.

Right, robust mutexes are quite broken by this.

But it's still quite common to do things with direct system calls, 
particularly for setting up containers.

I have not yet found a case which I couldn't solve with plain fork (with 
handlers) and unshare, but that's not what everyone does unfortunately.

Thanks,
Florian

Re: arc4random/csprng

[Rich Felker]

On Tue, Jul 03, 2018 at 05:08:21PM +0200, Florian Weimer wrote:
> On 07/03/2018 04:47 PM, Rich Felker wrote:
> 
> >>The main lock (for non-current kernels) is needed for the fork
> >>detection counters.  Fork detection is required for compatibility
> >>with applications which call clone/fork system calls directly, so
> >
> >How do you consider this supported usage at all? The tid in the TCB
> >will be invalid after such a call, and other things may be broken too.
> 
> Right, robust mutexes are quite broken by this.

Not just robust. Due to tid reuse, if a single-threaded parent
bypasses libc to fork, then exits, the tid that was copied into the
child's TCB could get reused for a new thread in the child, thereby
allowing two threads to lock the same recursive mutex at the same
time. Lots of other versions of this are possible too whenever
TCB->tid has a value that's not reserved against reuse.

> But it's still quite common to do things with direct system calls,
> particularly for setting up containers.
> 
> I have not yet found a case which I couldn't solve with plain fork
> (with handlers) and unshare, but that's not what everyone does
> unfortunately.

I agree you might need direct use of clone sometime for
namespace/container stuff, but I don't think there's any way it can be
made safe without careful consideration of what you do after the
operation before a subsequent execve or _exit. I don't think it makes
sense to design big machinery to support doing something that has
deeper reasons it can't work, but this is probably partly a difference
in philosophy between glibc and musl (see also: dlclose, lazy dtls,
lazy tlsdesc, ...).

Rich

Re: arc4random/csprng

[Florian Weimer]

On 07/03/2018 05:17 PM, Rich Felker wrote:

>> But it's still quite common to do things with direct system calls,
>> particularly for setting up containers.
>>
>> I have not yet found a case which I couldn't solve with plain fork
>> (with handlers) and unshare, but that's not what everyone does
>> unfortunately.
> 
> I agree you might need direct use of clone sometime for
> namespace/container stuff, but I don't think there's any way it can be
> made safe without careful consideration of what you do after the
> operation before a subsequent execve or _exit. I don't think it makes
> sense to design big machinery to support doing something that has
> deeper reasons it can't work, but this is probably partly a difference
> in philosophy between glibc and musl (see also: dlclose, lazy dtls,
> lazy tlsdesc, ...).

I would suggest to keep at least the fork detection bit, even if you do 
not reseed and deadlock or abort instead, because the duplicate stream 
of random bits could be very hard to detect otherwise.

Thanks,
Florian

Re: arc4random/csprng

[Rich Felker]

On Wed, Jul 04, 2018 at 01:36:00PM +0200, Florian Weimer wrote:
> On 07/03/2018 05:17 PM, Rich Felker wrote:
> 
> >>But it's still quite common to do things with direct system calls,
> >>particularly for setting up containers.
> >>
> >>I have not yet found a case which I couldn't solve with plain fork
> >>(with handlers) and unshare, but that's not what everyone does
> >>unfortunately.
> >
> >I agree you might need direct use of clone sometime for
> >namespace/container stuff, but I don't think there's any way it can be
> >made safe without careful consideration of what you do after the
> >operation before a subsequent execve or _exit. I don't think it makes
> >sense to design big machinery to support doing something that has
> >deeper reasons it can't work, but this is probably partly a difference
> >in philosophy between glibc and musl (see also: dlclose, lazy dtls,
> >lazy tlsdesc, ...).
> 
> I would suggest to keep at least the fork detection bit, even if you
> do not reseed and deadlock or abort instead, because the duplicate
> stream of random bits could be very hard to detect otherwise.

I don't want, and I don't think others will want, musl to be
unconditionally mmapping extra memory in every process for the sake of
safely handling programs doing invalid/unsupported hacks. What might
be acceptable is something like, at stirring time, doing:

	if (__syscall(SYS_gettid)!=self->tid) a_crash();

Another idea is adding to syscall.c (public syscall() function)
something like:

	if (n==SYS_fork || n==SYS_clone) flag=1;

and in the csprng:

	if (flag) a_crash();

or just:

	if (n==SYS_fork || n==SYS_clone)
		return __syscall_ret(-EINVAL);

In any case, the public clone() function, which should be valid to use
in a limited sense if we're offering it at all, should also be
reviewed for safety (not specific to csprng issues) and for what
properties we want to guarantee/support, like whether it's valid to do
non-AS-safe stuff after a fork-like clone in a single-threaded
process. The above flag idea may be a useful tool in this -- by
actively storing knowledge that a type of fork/clone that leaves the
process in an async signal context has taken place, we could trap a
lot of UB in the child.

Rich

Re: arc4random/csprng

[Luca Barbato]

On 02/07/2018 22:39, Rich Felker wrote:
> I haven't followed what's been happening with posix_random lately, but
> glibc has adding the arc4random interfaces and it seems reasonable
> that we should too, with the easy option to add the posix_random name
> for it and whatever interface details POSIX decides on.
> 
> The glibc implementation looks like it's essentially CTR mode AES.
> This is probably a pretty good choice, but unless there are strong
> reasons not to I'd probably rather go with Hash-DRBG or HMAC-DRBG
> utilizing the existing SHA-256 code we already have. That would avoid
> the need to write or import any new cryptographic code (and the
> associated risks) and keep the size cost minimal. This seems better
> for forward-secrecy too, but I'd like to better understand the
> conditions under which Hash-DRBG and HMAC-DRBG provide
> forward-secrecy.

From what I read the various BSDs opted for ChaCha20, not sure which are
the trade-offs for this choice thought.

lu

Re: arc4random/csprng

[Rich Felker]

On Tue, Jul 03, 2018 at 04:18:37PM +0200, Luca Barbato wrote:
> On 02/07/2018 22:39, Rich Felker wrote:
> > I haven't followed what's been happening with posix_random lately, but
> > glibc has adding the arc4random interfaces and it seems reasonable
> > that we should too, with the easy option to add the posix_random name
> > for it and whatever interface details POSIX decides on.
> > 
> > The glibc implementation looks like it's essentially CTR mode AES.
> > This is probably a pretty good choice, but unless there are strong
> > reasons not to I'd probably rather go with Hash-DRBG or HMAC-DRBG
> > utilizing the existing SHA-256 code we already have. That would avoid
> > the need to write or import any new cryptographic code (and the
> > associated risks) and keep the size cost minimal. This seems better
> > for forward-secrecy too, but I'd like to better understand the
> > conditions under which Hash-DRBG and HMAC-DRBG provide
> > forward-secrecy.
> 
> From what I read the various BSDs opted for ChaCha20, not sure which are
> the trade-offs for this choice thought.

Yes, we've been looking at chacha20 based solutions on IRC since
measuring that HMAC-SHA256-DRBG would likely be as slow as asking the
kernel for entropy (though still better because it works on kernels
where we can't do that).

I'm not sure what the BSDs do about forward secrecy with chacha20,
since straight CTR-mode stuff clearly fails. But I think DJB's design
here can be applied to get forward secrecy:

https://blog.cr.yp.to/20170723-random.html

Rich