Re: kaslr: better rng

[Taylor R Campbell <campbell+netbsd-tech-kern%mumble.net@localhost>]

> Date: Sat, 11 Nov 2017 21:48:54 +0100
> From: Maxime Villard <max%m00nbsd.net@localhost>
> 
> The hash of y against rdtsc and rdseed is the new secret, not just y. It's
> not a recurrent Yn+1 = H(Yn) construction from a single Y0 seed - in which
> case one leak in the chain would indeed compromise the randomness of the
> following generations. It's rather Yn+1 = H(Yn, rdtsc, rdseed), where even
> if Yn is entirely revealed, you still can't predict Yn+1 reliably.
> 
> But I understand that re-using potentially revealed information in
> the hash weakens the prng in probably non-negligible ways, and that
> splitting the output as you said is better.

A little more to the point, the kernel's cryptography should be secure
if _either_

(a) the original seed on disk is unpredictable, _or_
(b) the seed we get out of rdseed is unpredictable.

I don't expect more than a few bits of the tsc to be unpredictable,
and not every machine supports rdseed.  If we don't assume they're
unpredictable, then it reduces to Yn+1 = H(Yn) for some predictable H.

Speaking of which, you should read 256 bits out of rdseed, not 64, and
fall back to rdrand if rdseed is not available.

> > Rather, we should carve up the output of SHAKE256 into a new 32-byte secret
> > and an n-byte buffer of outputs for some convenient n:
> > 
> > nseed(32) || buffer(480) = SHAKE256(oseed(32) || whatever else)
> 
> The output size we use is 32 bytes, not 512. So I guess we should increase it
> to 64, keep the lower half secret (and pass it to the hash function), and use
> the upper half as a random (and potentially revealed) buffer?

Whatever's convenient.  It doesn't really matter for security.

> (Side note regarding "revealed": if 32byte-worth of
> randomly-generated kernel VAs were to be revealed, we would be
> having a much bigger problem in the first place.)

Yes, but it's easier to engineer this by using a generically secure
PRNG; then I don't even have to think about quantifying the impact of
downstream leaks.

> I would favor certified algorithms, not that my opinion matters lot in this
> regard.

I care about security, understandability, and maintainability, not
about certification, but as I understand it the reason we use
AES128-CTR-DRBG for /dev/random is to make certification easier.  tls@
can probably comment on this.

> > Also, where do you update the seed that is then passed to rnd_seed to
> > initialize the real kernel entropy pool?
> 
> I don't, and that's a problem. To update the seed we need to
> recompute its SHA1 signature, and I'm not implementing SHA1 in the
> prekern (yet?). Either we extend entropy-file to contain three
> separate seeds (bootloader / prekern / kernel), or we choose to use
> SHA3 by default in the kernel and have the prekern update the seed
> and recompute its signature dynamically.

Blahh!  I don't even know why we have the SHA1 hash there.

Can you just use the SHA1 in libkern (and the SHA3 that will with any
luck soon be in libkern), or are there constraints on the size of the
prekern that prevent you from doing so?