Re: Directions for arc4random

[Florian Weimer <fweimer at redhat dot com>]

* Adhemerval Zanella:

> On 22/10/2018 18:21, Florian Weimer wrote:
>> I would like to resubmit my arc4random patch.
>> 
>> Most of the code, and the difficult-to-review parts, are for providing
>> fork safety even if the process is forked by a system call, and not a
>> call to the glibc function fork.
>> 
>> Rich Felker said that he'd prefer to use a proper lock for this in musl:
>> 
>>   <https://www.openwall.com/lists/musl/2018/07/02/5>
>> 
>> This would make arc4random far less scalable if one global state is
>> used.  But the implementation would be greatly simplified by this,
>> especially if we do not provide async-signal-safety for arc4random.  (If
>> we always lock around arc4random invocations and the entire
>> cryptographic operations, then I think this would detect fork misuse due
>> to hangs on that lock.)

(I believe this is wrong—locks won't help us, the bit streams will still
not converge.)

>> I would like to know if I should resubmit my last, very complex
>> approach, or if I should switch to the simple, lock-based approach.
>
> It was my backlog list for some time. The first problem I see is the 
> the huge size which makes reviewing quite complicate.
>
> The first step to try simplify patch submission is remove all x86
> optimizations for AES-NI/SSE2 as you already indicate in your initial
> submission.

It's AES-NI and RDRAND, demonstrating the use of both CPU extension
hooks to verify that they are usable.  I think they do not substantially
complicate review of the rest of the patch.

> Another thing is I tend to agree with Rich, the lock-free fork/clone
> detection is quite complicated and possible troublesome for maintainability. 
> Since we have a long-standing issue of a no async-signal-safe fork 
> implementation (BZ#4737) and fork implementation still contain some 
> lock contention on multithread fork (due atfork list handling, libio 
> internal list, and malloc) I think such lock-free complexity would not 
> yield much gain.

The lock is eliminated not from fork (which doesn't have to care if we
are willing to reseed in the new process), but from regular arc4random
calls.

On the other hand, if we want to add backtracking protection, we need
either state that is fully confined to each thread, separately seeded,
or a global lock.  Backtracking protection requires serializing all
operations on the state because the output from one operation is not
predictable prior to completing the computation and replaces the
existing state, while in the counter-based approach, you can just skip
ahead.

> So I would prefer Rich suggestion of using simpler locks, albeit with
> less scalability. As you already described in your path, current kernel
> support of MADV_WIPEONFORK already provides a proper way to handle it.
> Also, the lock-free optimization is also a future option is current
> lock seems to be a problem in real-world usage.

Rich doesn't want to use MADV_WIPEONFORK because it essentially wastes a
page and the corresponding PTEs for a rarely used feature.  The other
approach with the paired locks is similar because it also needs a
dedicated page.

> I also think it would profitable to discuss how to properly handle BZ#4737
> if fork scalability is an issue. You recently brought if there is a way
> to detect if the current function has been called (directly or indirectly) 
> from a signal handler [1], not sure if were your idea to handle BZ#4737 or 
> something else (with a proper way we could fix the atfork list scalability 
> issue).
>
> [1] https://sourceware.org/ml/libc-help/2016-02/msg00029.html

Calling this recently stretches things a bit. 8-)

Wrapper functions for signal handlers are problematic because we cannot
atomically set handler flags and the function, so a handler could run
with the wrong flags.

Thanks,
Florian