Discussion:
$RANDOM not Cryptographically secure pseudorandom number generator
Ole Tange
2018-11-21 20:07:51 UTC
Permalink
'brand' in variables.c is comparable in size to ChaCha20 and ChaCha20
is not completely broken:
https://en.wikipedia.org/wiki/Salsa20

Could we please replace 'brand' with ChaCha20?


/Ole
Chet Ramey
2018-11-21 22:43:33 UTC
Permalink
Post by Ole Tange
'brand' in variables.c is comparable in size to ChaCha20 and ChaCha20
https://en.wikipedia.org/wiki/Salsa20
Could we please replace 'brand' with ChaCha20?
What is your application that you need something more complicated than
the existing PRNG?
--
``The lyf so short, the craft so long to lerne.'' - Chaucer
``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU ***@case.edu http://tiswww.cwru.edu/~chet/
Ole Tange
2018-12-02 23:13:31 UTC
Permalink
Post by Chet Ramey
Post by Ole Tange
'brand' in variables.c is comparable in size to ChaCha20 and ChaCha20
https://en.wikipedia.org/wiki/Salsa20
Could we please replace 'brand' with ChaCha20?
What is your application that you need something more complicated than
the existing PRNG?
I do not have that currently, but it seems like a fairly small change
and it seems odd to have modern software not use modern algorithms.

Git's use of SHA1 seems to be a prime example of what can go wrong:
https://shattered.io/

If you look at the code it is really not much bigger:

#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b))))
#define QR(a, b, c, d) ( \
a += b, d ^= a, d = ROTL(d,16), \
c += d, b ^= c, b = ROTL(b,12), \
a += b, d ^= a, d = ROTL(d, 8), \
c += d, b ^= c, b = ROTL(b, 7))
#define ROUNDS 20

void chacha_block(uint32_t out[16], uint32_t const in[16])
{
int i;
uint32_t x[16];

for (i = 0; i < 16; ++i)
x[i] = in[i];
// 10 loops × 2 rounds/loop = 20 rounds
for (i = 0; i < ROUNDS; i += 2) {
// Odd round
QR(x[0], x[4], x[ 8], x[12]); // column 0
QR(x[1], x[5], x[ 9], x[13]); // column 1
QR(x[2], x[6], x[10], x[14]); // column 2
QR(x[3], x[7], x[11], x[15]); // column 3
// Even round
QR(x[0], x[5], x[10], x[15]); // diagonal 1 (main diagonal)
QR(x[1], x[6], x[11], x[12]); // diagonal 2
QR(x[2], x[7], x[ 8], x[13]); // diagonal 3
QR(x[3], x[4], x[ 9], x[14]); // diagonal 4
}
for (i = 0; i < 16; ++i)
out[i] = x[i] + in[i];
}

Can you elaborate on why you think it is a bad idea to change an
insecure PRNG into a non-broken one?


/Ole
Eduardo Bustamante
2018-12-03 04:16:16 UTC
Permalink
On Sun, Dec 2, 2018 at 3:14 PM Ole Tange <***@tange.dk> wrote:
(...)
Post by Ole Tange
https://shattered.io/
What does a PRNG have to do with a hashing function?
Post by Ole Tange
Can you elaborate on why you think it is a bad idea to change an
insecure PRNG into a non-broken one?
I think you should elaborate on why you think the current one is
"broken", not the other way around; since you're the one that claiming
that is broken, but haven't really said why that is true.

IMO, Bash's PRNG is decent enough for what its intended use is. It's
definitely not meant to be used for cryptography. If I want a strong
random number, I can rely on OpenSSL or the /dev/urandom device.


Also, I don't really see how the code you sent generates a random number:

* How do you seed the initial state?
* How do you convert the 16-element array of 32-bit numbers to an
integer in the 0 - 32767 range?

People already expect $RANDOM to behave in a certain way, so you can't
really change that interface without breaking stuff. Whatever you use
to replace the brand() function should have the same interface.
Chet Ramey
2018-12-03 14:56:33 UTC
Permalink
Post by Ole Tange
Post by Chet Ramey
Post by Ole Tange
'brand' in variables.c is comparable in size to ChaCha20 and ChaCha20
https://en.wikipedia.org/wiki/Salsa20
Could we please replace 'brand' with ChaCha20?
What is your application that you need something more complicated than
the existing PRNG?
I do not have that currently, but it seems like a fairly small change
and it seems odd to have modern software not use modern algorithms.
There has to be a compelling reason to change this, especially at a point
so close to a major release.

You might be expecting too much from bash's random number generator. Is
the problem that its period is at most 2**16? For its intended uses, the
cycle length is acceptable. Do you disagree?
--
``The lyf so short, the craft so long to lerne.'' - Chaucer
``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU ***@case.edu http://tiswww.cwru.edu/~chet/
Greg Wooledge
2018-12-03 15:03:56 UTC
Permalink
Post by Chet Ramey
There has to be a compelling reason to change this, especially at a point
so close to a major release.
You might be expecting too much from bash's random number generator. Is
the problem that its period is at most 2**16? For its intended uses, the
cycle length is acceptable. Do you disagree?
I suspect he doesn't share the same understanding of the "intended
uses" of bash's $RANDOM as the rest of us.

It's meant for displaying a random wallpaper image from a directory,
or for playing a random audio file from a directory. Or for playing a
number guessing game with a 6 year old.

It is emphatically NOT for generating passwords.
Ole Tange
2018-12-03 16:31:18 UTC
Permalink
Post by Chet Ramey
There has to be a compelling reason to change this, especially at a point
so close to a major release.
The reason for my submission was that I needed a bunch of random
numbers in a shell script, but I needed them to be high quality.
Luckily I did not just assume that Bash delivers high quality random
numbers, but I read the source code, and then found that the quality
was low. I do not think must users would do that.

The man page does not warn about the low quality either, and it does
not point to a way to get high quality numbers. Somehow we expect the
user to simply know this.

So from personal experience I have wasted a few hours on that account.

Had I simply assumed the numbers were high quality, it might have
caused problems for me at a later stage.

And it is protect users who do not read the man page and source code
that I suggest the change.
Post by Chet Ramey
You might be expecting too much from bash's random number generator. Is
the problem that its period is at most 2**16? For its intended uses, the
cycle length is acceptable. Do you disagree?
If I read the man page, I do not see what the intended use is. Where
is that documented?

If the user's view on the intended use differs from the developers',
then there is a risk of misaligned expectations. Documenting the
developers' view is IMHO a poor way of mitigating this, if there is a
simple solution that will satisfy the demanding user.

I see software daily that is being use in ways it was not intended.
Usually it does not break, and for GNU tools this (in my experience)
is especially true, because the GNU project officially endorses
writing robust programs.

So my suggestion is really just to be proactive, so that when users do
not use it in the intended way, it will still not break.

If you choose not to implement a CSPRNG, then please at least make it
clear in the man page that $RANDOM is a poor RNG, and what the
intended use is.


/Ole
Greg Wooledge
2018-12-03 17:35:51 UTC
Permalink
Post by Ole Tange
Luckily I did not just assume that Bash delivers high quality random
numbers, but I read the source code, and then found that the quality
was low. I do not think must users would do that.
You're correct. Most users would not have to read the source code to
know that the built-in PRNG in bash (or in libc, or in basically ANY
other standard thing) is of lower than cryptographic quality.

Most users already KNOW this.
Eduardo Bustamante
2018-12-03 18:53:01 UTC
Permalink
Post by Greg Wooledge
Post by Ole Tange
Luckily I did not just assume that Bash delivers high quality random
numbers, but I read the source code, and then found that the quality
was low. I do not think must users would do that.
You're correct. Most users would not have to read the source code to
know that the built-in PRNG in bash (or in libc, or in basically ANY
other standard thing) is of lower than cryptographic quality.
Most users already KNOW this.
I have to echo this. If you are writing an application that requires
high quality random number, the onus is on YOU to ensure that you're
using quality sources and a good CSRNG. It would be a user mistake to
just use whatever the standard library of the run-time you're using
provides. Do we have to change C's rand() too? Or python's "random"
module? Or perl's "rand"? Or ruby's? (etc etc)


I do agree that adding a note in the manual to this effect would be nice though.
Chet Ramey
2018-12-03 20:18:07 UTC
Permalink
Post by Ole Tange
Post by Chet Ramey
There has to be a compelling reason to change this, especially at a point
so close to a major release.
The reason for my submission was that I needed a bunch of random
numbers in a shell script, but I needed them to be high quality.
Luckily I did not just assume that Bash delivers high quality random
numbers, but I read the source code, and then found that the quality
was low. I do not think must users would do that.
This is always requirements-driven. Nobody expects to get cryptographic-
quality PRNGs out of the shell (or any of the libc interfaces, tbh), and
that's never been promised or expected. You can't really expect that from
something that only promises 16 bits.

However, for common scripting tasks like generating temporary filenames,
it's perfectly adequate.

Chet
--
``The lyf so short, the craft so long to lerne.'' - Chaucer
``Ars longa, vita brevis'' - Hippocrates
Chet Ramey, UTech, CWRU ***@case.edu http://tiswww.cwru.edu/~chet/
Loading...