Kernel RNG rework; when opencrypto really doesn't win

[Thor Lancelot Simon <tls%panix.com@localhost>]

On Tue, Nov 08, 2011 at 07:25:48PM +0100, Matthias Drochner wrote:
> 
> tls%panix.com@localhost said:
> > There's a new patch at http://www.panix.com/~tls/rnd4.diff
> 
> I've been running a system with this for a couple of hours now and it appears
> stable. (With "rnd3.diff" I got locking related panics indeed.)
> Just some mostly formal comments:
> -shouldn't the remaining uses of arc4random() be converted to
>  cprng_strong/fast
>  as appropriate (what I noticed was in "opencrypto") and arc4random removed
>  from public namespace?

It seemed to me there were some parts of the kernel where it was legitimate
to ask for arc4random in particular -- but I might have missed some where
it was not.  I'll check again.

> -not a big issue, but it seems wrong to me that the arc4random implementation
>  in lib/libkern calls back into the kernel's rngtest(). I'd suggest to move
>  rngtest() to libkern as well -- it doesn't have any connection to kernel
>  specific services.

I don't see any particular reason why not to do this.  I'll try it later
this week.

Though that may be true of quite a bit of support code in sys/kern...

> -while the NIST thing is approved and so, arc4random is still strong enough
>  for most uses, as I understand it. The mapping cprng_fast/strong to
>  arc4random/nist_ctr could be controlled by some kernel defines, with the
>  option to map both to arc4random. At least I wouldn't remove all the
>  infrastructure which makes rijndael an optional kernel component, in case
>  someone wants to do this later.

I don't particularly want to jam another layer of runtime indirection
in the middle.  Adding a lock to arc4random() already increases cost
more than I like -- do we want to add a cache-blowing call through a
function pointer as well?  I'd kind of rather not.  I do think it would
be reasonable to be able to select different stream generators at
compile time.

The infrastructure to make rijndael optional is about 4 lines in
sys/conf/files.  Easy to put back if someone wants to, but since there
is no simple way to default kernel options to "on", it's either take
it out for now, or make nist_ctr_drbg one of those "options" that has
to be present in std.platform or your compile fails.  I hate those
fake "options" so I'd rather not.

> -would it be feasible to use the opencrypto framework for AES stuff, to
>  get crypto hardware support? From a brief look at the code, my impression
>  is that key scheduling code may be called at random number extraction
>  time. With opencrypto, as it looks now, this would mean memory allocations
>  etc. which would be too expensive. Did you look at this?

I did look at it.  We don't do ECB mode in opencrypto (did it change
while I wasn't looking?), and the API is really too heavyweight to do
so efficiently.  The CTR_DRBG does repeatedly encrypt a counter, but it
is not standard AES CTR mode, and I do not think it's possible to use
a standard AES CTR implementation to accellerate it.

It is certainly possible to use a CPU-optimized software AES implementation
to accellerate it, though, since those do ECB mode and there is no special
call overhead for using them to do it rather than plain software.  This
brings me back to a rather sore subject for me -- this is *precisely*
why I have been opposed, for a long time, to using opencrypto backend
drivers for algorithm accelleration via special instructions, rather than
MD source files implementing the standard algorithm APIs.

Now, we do not have Intel AES acceleration support in the kernel.  But
let's use the VIA PadLock implementation as an example instead.  We use
an opencrypto driver for PadLock.  That means we can't use it in this case
to accellerate CTR_DRBG -- not without adding ECB support to opencrypto
itself.  Even if we did, it would be very inefficient since each single
block ECB request would have to flow up and down all of opencrypto's
layers.

If, instead, our PadLock support had been implemented as an x86 MD
optimization in crypto/rijndael, opencrypto would still be accellerated
(because cryptosoft would be) but so would other kernel users of rijndael
that are basically synchronous, like the current cgd implementation, or
always submitting small requests, like CTR_DRBG.

So I do not think we should necessarily take the path FreeBSD and
OpenBSD did, and implement the Intel AES support in opencrypto itself;
though I am not sure it would win for this purpose anyway, since one
does have to use the FP regs in-kernel and saving/restoring them just
to do one block at a time may still lose compared to (naive) software.

> -the aes256 header seems to be unused.

It's there to allow switching to AES256 via a single-line source change,
which could easily be a kernel option, I suppose.

> -not directly related: What is the "Mersenne Twister" code in libkern
>  good for?

See my response to Christos.

Thanks for your comments!

Thor