Re: [bug-bash] $RANDOM not Cryptographically secure pseudorandom number generator

[Quentin]

Hello there,

I've reviewed both patches and found some things that should be either 
greatly improved, or buried some place very deep. :-p

On 2019-01-07 08:15, Ole Tange wrote:
> On Mon, Jan 7, 2019 at 12:08 AM Chet Ramey <chet.ramey@case.edu> wrote:
> > On 1/5/19 3:12 PM, Eduardo A. Bustamante López wrote:
> > > On Fri, Dec 28, 2018 at 10:24:50AM +0100, Ole Tange wrote:
> > > (...)
> > >> Patch attached.
> >
> > What's the period of the resulting RNG? That's the chief complaint 
> > with
> > the existing implementation.
>
> My implementation made that hard to determine.

The Salsa20-based RNG from salsa20.patch is completely broken.

Please do not use this earlier patch:
* it doesn't follow the Salsa20 specification (specifically, the Salsa20 
state layout is completely ignored)
* the RNG itself leaks part of the Salsa20 state (15 bits from each of 
the 16 32-bits integers) as its output, which is then used as input to 
generate the next set of numbers; this at the very least hugely 
facilitates full prediction of future values from a restricted sample 
output of the RNG

> I have updated the patch: It now supports BASH_RANDOM_16 as well as 32.
>
> I have changed the algorithm to ChaCha20, as it seems that is the
> variant that Google, FreeBSD, OpenBSD, and NetBSD have chosen, and it
> seems it is a little harder to attack.

Now this new ChaCha20-based RNG sports a much better implementation (the 
state layout is mostly correct, and it does not leak its internal 
state).

A state layout issue remains in that upon reseed, the entire state gets 
altered, which is bad: the constant in `chachastate` must remain 
unaltered, otherwise this is no longer ChaCha20 (and beyond that, it is 
unnecessary to alter both the key and nonce/counter). Also, 
`stringaddseedrand()` allegedly "shakes" the bits if the seed is longer 
than the state, by calling `chacha20_block()`, but the only thing this 
actually does is to increase the counter value in the state (since with 
the switch to ChaCha20 the block primitive rightfully no longer alters 
the whole state).

However, I've got some much more fundamental concerns with this whole 
idea. In short, just because there's a top-notch stream cipher in it 
doesn't mean it's a (good) CSPRNG. And just like with ciphers, if you 
don't know what you're doing really well, don't roll your own CSPRNG.

Specifically, this ChaCha20-based RNG may be computationally secure (see 
https://crypto.stackexchange.com/a/39194), but it's neither forward 
secret nor prediction resistant (the Salsa20-based RNG, though much more 
messy, was however forward secret). Moreover, its computational security 
isn't even that strong, since it depends on the seed remaining secret. 
The initial seed being merely a combination of the current time of day 
and shell PID, it's not random enough and could be brute-forced.

All in all, this makes for a pretty weak CSPRNG, one that I would be 
unwilling to use to generate keys. To improve it, the first step would 
be to add real entropy (from /dev/urandom) to the mix, then use a vetted 
design such as HMAC-DRBG or CTR-DRBG (this one *may* play well with 
ChaCha20). These would give us something computationally secure, forward 
secret and prediction resistant.
Sadly, this would not be trivial to reconcile with the requirement that 
seeding $RANDOM with a known value gives the same random stream (this 
conflicts with the prediction resistance property of a CSPRNG). :(

In my opinion, $RANDOM doesn't need to change: being deterministic, it's 
never gonna be a CSPRNG, so the linear congruential RNG is fine. If you 
really need some quality CSPRNG values, I'd suggest adding a 
$SECURE_RANDOM variable that just reads from /dev/urandom. Implementing 
a full CTR-DRBG seems like way too much work for a shell.

> (And please feel free to clean up my code: C is a language I code once
> every 5 years or so).

(So while I'm at it: `chachastate` keeps switching types and is 
sometimes a global, sometimes a local variable. That's confusing.)

> /OIe

Cheers,

Quentin