Re: kaslr: better rng

[Maxime Villard <max%m00nbsd.net@localhost>]

Le 11/11/2017 à 20:14, Taylor R Campbell a écrit :
> If we _both_ reveal y = H(x) for some initial secret x, and then use y
> as the new secret, we've just revealed the new secret. 

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.

> 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?

(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.)

> See <https://blog.cr.yp.to/20170723-random.html> for further
> discussion of this structure (and criticism of the obscenely
> complicated NIST DRBGs in SP800-90A).
>
> It may be simpler to use a Keccak duplex like the draft entropy pool
> I've been sitting on for a while, which has some theoretically nicer
> properties[1] though hasn't yet appeared in a NIST standard the way
> SHAKE256 has.  Input from someone who is likely to care about
> certification more than I do would be appreciated here.

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

> 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.

> Finally, some minor nits:
>
> - Don't call it `rndpool', because that has a specific meaning in
>    NetBSD already, which is something else.  Just `struct prng' is
>    fine, if confined to that file.

alright

> - Define functions with foo(void), not foo(), to get prototype
>    checking from the C compiler.
>
> - Newline before function name in definitions; see share/misc/style
>    for more details.
>
> - No need for casts between void * and other types.
>
> - Use unsigned, not u_int; u_int, u_intN_t, &c., are vestiges of older
>    days.
>
> - Avoid externs in .c files.  Include the right header file for the
>    declaration of bootinfo.

These are common in the prekern and not particularly related to the prng, so
they will be addressed later. Also need to get rid of redef.h etc.

Maxime