[openssl-dev] Improving OpenSSL default RNG

[Benjamin Kaduk]

On 10/23/2015 08:22 AM, Alessandro Ghedini wrote:
> Hello everyone,
>
> (sorry for the wall of text...)
>
> one of the things that both BoringSSL and LibreSSL have in common is the
> replacement of OpenSSL's default RNG RAND_SSLeay() with a simpler and saner
> alternative. Given RAND_SSLeay() complexity I think it'd be worth to at least
> consider possible alternatives for OpenSSL.

I heartily support this; the existing RAND_SSLeay() is a bit frightening
(though I take some solace in the existence of ENGINE_rdrand()).

> BoringSSL started using the system RNG (e.g. /dev/urandom) for every call to
> RAND_bytes(). Additionally, if the RDRAND instruction is available, the output
> of RDRAND is mixed with the output of the system RNG using ChaCha20. This uses
> thread-local storage to keep the global RNG state.

/dev/urandom is simple and safe absent the chroot case.  (Note that
capsicum-using applications will frequently open a fd for /dev/urandom
before entering capability mode and leave it open; the same might be
worth considering.)  Concerns about "running out of entropy" are
unfounded; the kernel uses a CS-PRNG and if we trust its output to seed
our own scheme, we can trust its output indefinitely.

Intel recommends calling RDRAND in a loop since it does not always
return successfully, and IIRC best practice is to mix it in with other
inputs (i.e., not use it directly).

> Incidentally, BoringSSL added a whole new API for thread-local storage which
> OpenSSL could adopt given that e.g. the ASYNC support could benefit from it
> (there are other interesting bits in BoringSSL, like the new threading API that
> could also be adopted by OpenSSL).
>
> The BoringSSL method is very simple but it needs a read from /dev/urandom for
> every call to RAND_bytes() which can be slow (though, BoringSSL's RAND_bytes()
> seems to implement some sort of buffering for /dev/urandom so the cost may be
> lower).

Keeping the default method simple, slow, and reliable could be a
reasonable approach, given that there is always the option of inserting
an alternate implementation if performance is a concern.  ("Simple"
probably means "rely on the kernel for everything, do not use
thread-local storage, etc.")

It might also be worth having a more complicated scheme that does use
thread-local storage (on systems where we know how to implement it) and
runs fortuna or something similar, but that does not necessarily need to
be the default implementation, in my opinion.

>
> On the other hand, LibreSSL replaced the whole RAND_* API with calls to
> OpenBSD's arc4random(). This is a nice and simple scheme that uses ChaCha20 to
> mix the internal RNG state, which is regularly reseeded from the system RNG.
> The core logic of this (excluding ChaCha20 and platform-specific bits) is
> implemented in less than 200 lines of code and, at least in theory, it's the
> one that provides the best performance/simplicity trade-off (ChaCha20 can be
> pretty fast even for non-asm platform-generic implementations).

A single syscall to get entropy is nice, whether it's a sysctl node,
getentropy(), getrandom(), or some other spelling; a library call like
arc4random() is almost as good.  But I don't think we're in a position
to rip out the RAND_* API layer as LibreSSL did.

> Both of these methods are robust and mostly platform-indipendent (e.g. none of
> them uses the system time, PID or uninitilized buffers to seed the RNG state)
> and have simple implementations, so I think OpenSSL can benefit a lot from
> adopting one of them. The astute readers may point out that OpenSSL doesn't
> support ChaCha20 yet, but that's hopefully coming soon.
>
> I think there's also room for improvement in the platform-specific RAND_poll()
> implementations, e.g.:
>
> - on Linux getrandom() should be used if available
> - on OpenBSD getentropy() should be used instead of arc4random()
> - the /dev/urandom code IMO can be simplified
> - the non-CryptGenRandom() code on Windows is just crazy. Do we even support
>   Windows versions before XP?
> - is EGD actually used anywhere today?

"I really hope not."

> - what about Netware, OS/2 and VMS, do we have any users on them? IIRC support
>   for other platforms has already been removed, what are the criteria for
>   keeping support for one?
> - etc...
>
> For comparison, OpenBSD's getentropy() implementation [0] is much cleaner and
> supports many of the platforms supported by OpenSSL.
>
> So, any thought? If there's interest in this, I can look into investigating
> these things more in detail and propose possible patches.
>

I'll just note in closing that there are a number of "fortuna-like"
implementations out there that are not actually fortuna, for example,
were implemented based off of the wikipedia article and not the actual
textbook. 
https://github.com/krb5/krb5/blob/master/src/lib/crypto/krb/prng_fortuna.c
was implemented from _Cryptography Engineering_, and I think
https://github.com/freebsd/freebsd/blob/master/sys/dev/random/fortuna.c
is another.

-Ben