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