Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Mon, Jan 7, 2019 at 9:37 AM Eduardo A. Bustamante López
 wrote:
> On Mon, Jan 07, 2019 at 08:15:12AM +0100, Ole Tange wrote:
> > On Mon, Jan 7, 2019 at 12:08 AM Chet Ramey  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 is the performance impact (roughly 2X slower)
> >
> > The impact is not from Salsa20/ChaCha20, though, if you compare
> > patched vs. unpatched code.
> >
> > On my system BASH_RANDOM_16 is a tiny bit faster than the original,
> > while BASH_RANDOM_32 is a tiny bit slower.
>
> I find that really hard to believe. The new RNG is clearly doing more work, so
> it should be slower.

It does more work, yes, but it also produces more numbers and the work
it does is simpler: When it does 20 rounds it produces 16 or 32
numbers. The calculations in each round are parallelizable and are
mostly bit shifting. https://en.wikipedia.org/wiki/Salsa20 says it
uses 3.95 cpu cycles per byte. Given that the old version did 1
division, 1 modulo, and 2 multiplications, I would say it is not
unreasonable that they are comparable in speed.

> And that's OK. I just wanted to know by how much.
>
> What numbers are you seeing and how did you measure them?

I ran your test script on 3 versions:

* the original source. Git [3669b0bacc6]
* the patched source with BASH_RANDOM_32
* the patched source with BASH_RANDOM_16

and the results were within 1% of each other.

(I can, however, reproduce your finding that $RANDOM is twice as slow
on 5.0 as on 4.4, but it is not due to the generator).


/Ole

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Eduardo A . Bustamante López]

On Mon, Jan 07, 2019 at 08:15:12AM +0100, Ole Tange wrote:
> On Mon, Jan 7, 2019 at 12:08 AM Chet Ramey  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.
> :
> > > - Does the new RNG generate uniformly distributed numbers? (Yes)
> > > - What is the performance impact (roughly 2X slower)
> 
> The impact is not from Salsa20/ChaCha20, though, if you compare
> patched vs. unpatched code.
> 
> On my system BASH_RANDOM_16 is a tiny bit faster than the original,
> while BASH_RANDOM_32 is a tiny bit slower.

I find that really hard to believe. The new RNG is clearly doing more work, so
it should be slower. And that's OK. I just wanted to know by how much.

What numbers are you seeing and how did you measure them?

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Mon, Jan 7, 2019 at 12:08 AM Chet Ramey  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.
:
> > - Does the new RNG generate uniformly distributed numbers? (Yes)
> > - What is the performance impact (roughly 2X slower)

The impact is not from Salsa20/ChaCha20, though, if you compare
patched vs. unpatched code.

On my system BASH_RANDOM_16 is a tiny bit faster than the original,
while BASH_RANDOM_32 is a tiny bit slower.

> > - Does it break any existing tests? (Yes, easy to fix)
>
> What's the period of the resulting RNG? That's the chief complaint with
> the existing implementation.

My implementation made that hard to determine.

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.

The period in this patch is 2^128 blocks after which it wraps. Each
block results in 32 values (BASH_RANDOM_16) or 16 values
(BASH_RANDOM_32). So the period for the values is 2^133 and 2^132,
respectively.

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

/OIe
diff --git a/support/bashbug.sh b/support/bashbug.sh
index 29ce1341..54d0e5e7 100644
--- a/support/bashbug.sh
+++ b/support/bashbug.sh
@@ -26,14 +26,14 @@
 # configuration section:
 #	these variables are filled in by the make target in Makefile
 #
-MACHINE="!MACHINE!"
-OS="!OS!"
-CC="!CC!"
-CFLAGS="!CFLAGS!"
-RELEASE="!RELEASE!"
+MACHINE="x86_64"
+OS="linux-gnu"
+CC="gcc"
+CFLAGS="-g -O2 -Wno-parentheses -Wno-format-security"
+RELEASE="5.0"
 PATCHLEVEL="!PATCHLEVEL!"
-RELSTATUS="!RELSTATUS!"
-MACHTYPE="!MACHTYPE!"
+RELSTATUS="beta2"
+MACHTYPE="x86_64-pc-linux-gnu"
 
 PATH=/bin:/usr/bin:/usr/local/bin:$PATH
 export PATH
diff --git a/variables.c b/variables.c
index 638d6ecd..bb41a500 100644
--- a/variables.c
+++ b/variables.c
@@ -1309,56 +1309,172 @@ init_seconds_var ()
   INIT_DYNAMIC_VAR ("SECONDS", (v ? value_cell (v) : (char *)NULL), get_seconds, assign_seconds);
   return v;  
 }
- 
-/* The random number seed.  You can change this by setting RANDOM. */
-static unsigned long rseed = 1;
-static int last_random_value;
-static int seeded_subshell = 0;
 
-/* A linear congruential random number generator based on the example
-   one in the ANSI C standard.  This one isn't very good, but a more
-   complicated one is overkill. */
+#define BASH_RANDOM_16 1
+
+#if BASH_RANDOM_16
+/* BASH_RAND_MAX: Only 2^n-1 is supported */
+#  define BASH_RAND_MAX0x7fff  /* 16 bits */
+#  define RANDOMLIST_SIZE  31
+#else
+#  define BASH_RAND_MAX0x7fff  /* 32 bits */
+#  define RANDOMLIST_SIZE  15
+#endif
+
+/* Chacha20 Cryptographically secure pseudorandom number generator from
+   https://en.wikipedia.org/wiki/Salsa20 */
+
+/* 512 bits of state */
+uint64_t chachastate[8] = { 0, 0, 0, 0, 0, 0, 0, 0 };
+/* Chacha state:
+   expa | nd 3 | 2-by | te k
+   key  | key  | key  | key
+   key  | key  | key  | key
+   cnt  | cnt  | cnt  | cnt */
+char salsaconstant[] = "expand 32-byte k";
+/* list of random numbers ready to be served */
+uint32_t random_list[RANDOMLIST_SIZE+1];
+/* index of next random number to be served */
+int random_list_idx = 0;
+
+#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
+increase_counter (uint64_t in[8])
+{
+  /* Increase the counter (the last 16 bytes in chachastate) */
+  in[6]++;
+  if(0 == in[6]) {
+in[7]++;
+  }
+}
 
-/* Returns a pseudo-random number between 0 and 32767. */
+void
+chacha20_block(uint32_t in[16])
+{
+  int i,j;
+  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
+  }
+#if BASH_RANDOM_16
+  /* two 16-bit values per 32-bit state */
+  for (i = 0,j = 0; i < 16; i++,j += 2) {
+random_list[j] = (x[i] + in[i]) & BASH_RAND_MAX;
+random_list[j+1] = (x[i] + in[i]) >> 16 & BASH_RAND_MAX;
+  }
+#else
+  /* one 32-bit value per 32-bit state */
+  for (i = 0; i < 16; ++i) {
+random_list[i] = (x[i] + in[i]) & BASH_RAND_MAX;
+  }
+#endif
+  increase_counter((uint64_t *)in);
+}
+
+/* Returns a pseudo-random number 

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Sat, Jan 5, 2019 at 9:14 PM Eduardo A. Bustamante López
 wrote:>
> On Fri, Dec 28, 2018 at 10:24:50AM +0100, Ole Tange wrote:
> (...)
> > Patch attached.
:
> I applied the Salsa20 RNG patch (slightly modified due to the recent changes 
> in
> variables.c, attached [1]) to the tip of `devel`
> (89b3a79dd4643f210f8443856214d558572733a5) and ran a couple of tests, to 
> answer
> the following questions:
>
> - Does the new RNG generate uniformly distributed numbers? (Yes)
> - What is the performance impact (roughly 2X slower)
> - Does it break any existing tests? (Yes, easy to fix)
>
>
> 1. RNG distribution
:
> 2. Performance impact
>
> The new RNG does more work, and thus, it is expected to have a performance
> impact when generating lots of random numbers. I tested 3 systems (2 amd64 
> and 1
> armhf) and include the results below.
:
> | BASH_VERSION: 4.4.23(1)-release
> | time: 3.705
:
> | BASH_VERSION: 5.0.0(1)-rc1
> | time: 8.983

That is an unfair comparison. You need to compare 5.0.0(1)-rc1+patch
with 5.0.0(1)-rc1 to see if the delay is caused by Salsa20.

My testing says the delay is _not_ cause by that.


/Ole

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Chet Ramey]

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.
>>
>> It is basically a copy of the code snippet from Wikipedia with a few
>> trivial wrappers.
>>
>> Apart from using Salsa20 the biggest change is that you can now seed
>> RANDOM with a string.
> 
> Nice!
> 
> I applied the Salsa20 RNG patch (slightly modified due to the recent changes 
> in
> variables.c, attached [1]) to the tip of `devel`
> (89b3a79dd4643f210f8443856214d558572733a5) and ran a couple of tests, to 
> answer
> the following questions:
> 
> - Does the new RNG generate uniformly distributed numbers? (Yes)
> - What is the performance impact (roughly 2X slower)
> - Does it break any existing tests? (Yes, easy to fix)

What's the period of the resulting RNG? That's the chief complaint with
the existing implementation.


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

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Eduardo Bustamante]

On Sat, Jan 5, 2019 at 12:12 PM Eduardo A. Bustamante López
 wrote:
(...)
> 2. Performance impact
>
> The new RNG does more work, and thus, it is expected to have a performance
> impact when generating lots of random numbers. I tested 3 systems (2 amd64 
> and 1
> armhf) and include the results below.
>
>
> AMD Ryzen 7 2700X:
>
> | dualbus@system76-pc:~/src/gnu/bash$ (set -x; lscpu; for bash in /bin/bash 
> ./bash; do "$bash" ~/test-speed.sh; echo; done)
> | + lscpu
(...)

Oops, I forgot to attach the test-speed script, it's fairly simple:

| #!/bin/bash
|
| iterations=100
|
| TIMEFORMAT='time: %R'
|
| echo "iterations: $iterations"
| echo "BASH_VERSION: $BASH_VERSION"
|
| RANDOM=1
| time for ((i=0; i

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Luuk]

On 2-1-2019 02:29, Ole Tange wrote:

On Mon, Dec 31, 2018 at 8:12 PM Chet Ramey  wrote:
:

Thanks for the patch. I'll take a look after I release bash-5.0. One
question: can you reproduce the same random sequence by using the same
seed? That's for backwards compatibility, even if the sequences themselves
differ.


Yes. Seeding with a value will give the same sequence:

$ RANDOM=4; echo $RANDOM $RANDOM
21584 22135

$ RANDOM=4; echo $RANDOM $RANDOM
21584 22135



But not across systems:
luuk@WINDOWS:/mnt/c/Windows/System32$ RANDOM=4;echo $RANDOM $RANDOM
1692 27588
luuk@WINDOWS:/mnt/c/Windows/System32$ RANDOM=4;echo $RANDOM $RANDOM
1692 27588

luuk@opensuse:~> RANDOM=4; echo $RANDOM $RANDOM
32221 21043
luuk@opensuse:~> RANDOM=4; echo $RANDOM $RANDOM
32221 21043

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Mon, Dec 31, 2018 at 8:12 PM Chet Ramey  wrote:
:
> Thanks for the patch. I'll take a look after I release bash-5.0. One
> question: can you reproduce the same random sequence by using the same
> seed? That's for backwards compatibility, even if the sequences themselves
> differ.

Yes. Seeding with a value will give the same sequence:

$ RANDOM=4; echo $RANDOM $RANDOM
21584 22135

$ RANDOM=4; echo $RANDOM $RANDOM
21584 22135

For backwards compatibility integers are supported, but they are
really parsed as strings. Strings make it easier to seed with more
than 64-bits:

RANDOM=`cat GPLv3.txt`

So these give the same value on 4.4.23, but differs with the patch applied:

RANDOM=$(echo 2^64 | bc );echo $RANDOM
RANDOM=$(echo 2^65 | bc );echo $RANDOM

RANDOM="foo"; echo $RANDOM
RANDOM="bar"; echo $RANDOM

RANDOM=2; echo $RANDOM
RANDOM=" 2.0"; echo $RANDOM
RANDOM=" 2.0noise"; echo $RANDOM


/Ole

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Chet Ramey]

On 12/28/18 4:24 AM, Ole Tange wrote:
> On Sun, Dec 16, 2018 at 6:41 AM Eduardo Bustamante  wrote:
> :
>> You know no one is stopping you from submitting a patch to actually
>> fix the documentation right? (or maybe, you know, submitting an actual
>> working patch to change the random generator, not just drop some
>> irrelevant code snippet you got from Wikipedia).
> 
> Patch attached.

Thanks for the patch. I'll take a look after I release bash-5.0. One
question: can you reproduce the same random sequence by using the same
seed? That's for backwards compatibility, even if the sequences themselves
differ.

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

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Sun, Dec 16, 2018 at 6:41 AM Eduardo Bustamante  wrote:
:
> You know no one is stopping you from submitting a patch to actually
> fix the documentation right? (or maybe, you know, submitting an actual
> working patch to change the random generator, not just drop some
> irrelevant code snippet you got from Wikipedia).

Patch attached.

It is basically a copy of the code snippet from Wikipedia with a few
trivial wrappers.

Apart from using Salsa20 the biggest change is that you can now seed
RANDOM with a string.


/Ole
diff --git a/doc/bash.1 b/doc/bash.1
index 9a7a384a..4c4d3882 100644
--- a/doc/bash.1
+++ b/doc/bash.1
@@ -1825,11 +1825,16 @@ generated.  The sequence of random numbers may be initialized by assigning
 a value to
 .SM
 .BR RANDOM .
+The value can be a string.
 If
 .SM
 .B RANDOM
 is unset, it loses its special properties, even if it is
 subsequently reset.
+.SM
+.B RANDOM
+uses Salsa20 for generating the integers, which as of 2015 has
+no published cryptanalysis attacks.
 .TP
 .B READLINE_LINE
 The contents of the
diff --git a/variables.c b/variables.c
index be2446e0..a4a7af52 100644
--- a/variables.c
+++ b/variables.c
@@ -18,6 +18,7 @@
along with Bash.  If not, see .
 */
 
+#include 
 #include "config.h"
 
 #include "bashtypes.h"
@@ -1295,53 +1296,125 @@ init_seconds_var ()
   return v;  
 }
  
-/* The random number seed.  You can change this by setting RANDOM. */
-static unsigned long rseed = 1;
-static int last_random_value;
 static int seeded_subshell = 0;
 
-/* A linear congruential random number generator based on the example
-   one in the ANSI C standard.  This one isn't very good, but a more
-   complicated one is overkill. */
+/* Salsa20 Cryptographically secure pseudorandom number generator from
+   https://en.wikipedia.org/wiki/Salsa20 */
+
+#define ROTL(a,b) (((a) << (b)) | ((a) >> (32 - (b
+#define QR(a, b, c, d)(		\
+	b ^= ROTL(a + d, 7),	\
+	c ^= ROTL(b + a, 9),	\
+	d ^= ROTL(c + b,13),	\
+	a ^= ROTL(d + c,18))
+#define ROUNDS 20
+
+uint32_t salsastate[16] = {
+  /* Start value: "expand 32-byte k" */
+  'e', 'x', 'p', 'a', 'n', 'd', ' ', '3', '2', '-', 'b', 'y', 't', 'e', ' ', 'k'
+};
+
+void
+salsa20_block ()
+{
+  int i;
+  uint32_t x[16];
+
+  for (i = 0; i < 16; ++i)
+x[i] = salsastate[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 1
+QR(x[ 5], x[ 9], x[13], x[ 1]);	// column 2
+QR(x[10], x[14], x[ 2], x[ 6]);	// column 3
+QR(x[15], x[ 3], x[ 7], x[11]);	// column 4
+// Even round
+QR(x[ 0], x[ 1], x[ 2], x[ 3]);	// row 1
+QR(x[ 5], x[ 6], x[ 7], x[ 4]);	// row 2
+QR(x[10], x[11], x[ 8], x[ 9]);	// row 3
+QR(x[15], x[12], x[13], x[14]);	// row 4
+  }
+  for (i = 0; i < 16; ++i)
+salsastate[i] += x[i];
+}
+
+int state_idx = 0;
 
-/* Returns a pseudo-random number between 0 and 32767. */
 static int
 brand ()
 {
-  /* From "Random number generators: good ones are hard to find",
- Park and Miller, Communications of the ACM, vol. 31, no. 10,
- October 1988, p. 1195. filtered through FreeBSD */
-  long h, l;
-
-  /* Can't seed with 0. */
-  if (rseed == 0)
-rseed = 123459876;
-  h = rseed / 127773;
-  l = rseed % 127773;
-  rseed = 16807 * l - 2836 * h;
-#if 0
-  if (rseed < 0)
-rseed += 0x7fff;
-#endif
-  return ((unsigned int)(rseed & 32767));	/* was % 32768 */
+  /* salsa20_block generates 16 values */
+  /* use them all before calling salsa20_block again */
+  if(0 == state_idx) {
+salsa20_block ();
+  }
+  state_idx++;
+  /* Keep 0 <= state_idx < 16 */
+  state_idx &= 0xF;
+  return ((unsigned int)(salsastate[state_idx] & 32767));
 }
 
-/* Set the random number generator seed to SEED. */
+/* set salsastate to 0 */
+static void
+reset_salsastate ()
+{
+  int i;
+  for (i = 0; i < 16; ++i)
+salsastate[i] = 0;
+}
+
+/* backwards compatible 32-bit seeder */
 static void
 sbrand (seed)
  unsigned long seed;
 {
-  rseed = seed;
-  last_random_value = 0;
+  int i;
+  reset_salsastate ();
+  salsastate[0] = seed & 0x;
+  state_idx = 0;
+}
+
+/* add seed with any binary input e.g. a string */
+/* similar to adding entropy to /dev/random */
+static void
+stringaddseedrand (seed,len)
+ uint8_t *seed;
+ int len;
+{
+  int i;
+  for (i = 0; i < len; ++i) {
+salsastate[i%16] ^= seed[i];
+if (i%16 == 15)
+  /* shake the bits before adding more */
+  /* otherwise 16 bytes repeated twice will cancel out */
+  salsa20_block ();
+  }
+  salsa20_block ();
+}
+
+/* seed with binary input of any size e.g. a string */
+static void
+stringseedrand (seed,len)
+ uint8_t *seed;
+ int len;
+{
+  reset_salsastate ();
+  stringaddseedrand (seed,len);
+  state_idx = 0;
 }
 
 static void
 seedrand ()
 {
+  /* add some semi-random seed */
+  /* look at https://github.com/jirka-h/haveged for better input */
   struct timeval tv;
-
+  uint32_t 

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Chet Ramey]

On 12/15/18 5:22 PM, Ole Tange wrote:

>>> 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),
> 
> While I did not *expect* it, I honestly had hoped for it. Otherwise I
> would never have raised this.

OK. What would you expect out of a PRNG that limits the range to 0-32767?


> I feel a bit as if I am saying: "Hey this using environment variables
> to store function definitions seems like it could be a problem, but I
> do not have an exploit. I do, however, have an easy fix so that it
> will not be a problem in the future."
> 
> And you replying: "Come back when you have an exploit."
> 
> And then we simply wait for Shellshock to happen.

If at some future point you look back and want to know when your argument
went off the rails: this is it.


>> that's never been promised or expected. You can't really expect that from
>> something that only promises 16 bits.
> 
> The naive user may assume that he can simply concatenate values and
> get 128 bits:
> 
> echo $RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM
> 
> But I hope we agree that he will not get 128 bits of randomness no
> matter how many values he concatenates.

He'll get better than 16 bits.

> Or he might expect that this is not an infinite loop:
> 
>   while [ ! $RANDOM = $RANDOM ] ; do true; done

What does this have to do with the strength of a PRNG? Very few generators
will give you the same random number twice in succession.

> just like this is not:
> 
>   while [ ! $RANDOM = $(( 1+$RANDOM )) ] ; do true; done
> 
> (This one came as a surprise to me - I had totally expected $RANDOM
> would give the same value twice 1 time in 65536 tries on average.

It's very difficult to get a random number generator with a perfect period.
But even if you did, the above is a nonsensical test -- there's no reason
to think that you'd avoid two random numbers whose difference is 1 during
the sequence.

> At the very least make it clear from the documentation what $RANDOM
> can be used for. The man page does not warn about the low quality
> either, and it does not point to a way to get high quality numbers.

The bash PRNG is pretty good when generating 32 bits. It's the same
algorithm that FreeBSD and Mac OS X use for rand(). It's cutting down
to the lowest 16 bits that reduces the period.

> Somehow we expect the user to simply know this without giving him even
> a hint about this.
> 
>> However, for common scripting tasks like generating temporary filenames,
>> it's perfectly adequate.
> 
> I hope that we agree that you should never use $RANDOM for generating
> temporary file names in a dir that an attacker has write access to.

This is a different problem. There is a whole set of other issues involved
with creating temporary filenames in the presence of other processes.

The real issue is that, since the algorithm is public, the seed becomes
very important. If you have suggestions about how to improve the seeding,
please send them along.


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

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Eduardo Bustamante]

On Sat, Dec 15, 2018 at 6:08 PM Ole Tange  wrote:
(...)
> But your comment actually emphasizes my point: We _will_ have users
> who are naive enough to use $RANDOM in ways you and I would not do,
> because we know it is unsafe.
>
> Let's make those usages a little safer.

You know no one is stopping you from submitting a patch to actually
fix the documentation right? (or maybe, you know, submitting an actual
working patch to change the random generator, not just drop some
irrelevant code snippet you got from Wikipedia).

> And then we simply wait for Shellshock to happen.

Also, comparing this to shellshock is a huge strawman. Please don't do
that :), we all know better than that.

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Mon, Dec 3, 2018 at 9:18 PM Chet Ramey  wrote:
> On 12/3/18 11:31 AM, Ole Tange wrote:
> > On Mon, Dec 3, 2018 at 3:56 PM Chet Ramey  wrote:
> >
> >> There has to be a compelling reason to change this, especially at a point
> >> so close to a major release.

I would think that a major release would be the perfect opportunity to
change this: Major releases in general are known for not being 100%
compatible with earlier releases.

> > 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),

While I did not *expect* it, I honestly had hoped for it. Otherwise I
would never have raised this.

I feel a bit as if I am saying: "Hey this using environment variables
to store function definitions seems like it could be a problem, but I
do not have an exploit. I do, however, have an easy fix so that it
will not be a problem in the future."

And you replying: "Come back when you have an exploit."

And then we simply wait for Shellshock to happen.

> that's never been promised or expected. You can't really expect that from
> something that only promises 16 bits.

The naive user may assume that he can simply concatenate values and
get 128 bits:

echo $RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM-$RANDOM

But I hope we agree that he will not get 128 bits of randomness no
matter how many values he concatenates.

Or he might expect that this is not an infinite loop:

  while [ ! $RANDOM = $RANDOM ] ; do true; done

just like this is not:

  while [ ! $RANDOM = $(( 1+$RANDOM )) ] ; do true; done

(This one came as a surprise to me - I had totally expected $RANDOM
would give the same value twice 1 time in 65536 tries on average.
Tested on 4.4.19)

At the very least make it clear from the documentation what $RANDOM
can be used for. 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 without giving him even
a hint about this.

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

I hope that we agree that you should never use $RANDOM for generating
temporary file names in a dir that an attacker has write access to.
mktemp is made to do that in a secure fashion.

But your comment actually emphasizes my point: We _will_ have users
who are naive enough to use $RANDOM in ways you and I would not do,
because we know it is unsafe.

Let's make those usages a little safer.


/Ole

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Chet Ramey]

On 12/3/18 11:31 AM, Ole Tange wrote:
> On Mon, Dec 3, 2018 at 3:56 PM Chet Ramey  wrote:
> 
>> 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, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Eduardo Bustamante]

On Mon, Dec 3, 2018 at 9:36 AM Greg Wooledge  wrote:
>
> On Mon, Dec 03, 2018 at 05:31:18PM +0100, Ole Tange wrote:
> > 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.

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Greg Wooledge]

On Mon, Dec 03, 2018 at 05:31:18PM +0100, Ole Tange wrote:
> 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.

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Mon, Dec 3, 2018 at 3:56 PM Chet Ramey  wrote:

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

> 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

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Greg Wooledge]

On Mon, Dec 03, 2018 at 09:56:33AM -0500, Chet Ramey wrote:
> 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.

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Chet Ramey]

On 12/2/18 6:13 PM, Ole Tange wrote:
> On Wed, Nov 21, 2018 at 11:45 PM Chet Ramey  wrote:
>> On 11/21/18 3:07 PM, Ole Tange wrote:
>>> '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?
>>
>> 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, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Eduardo Bustamante]

On Sun, Dec 2, 2018 at 3:14 PM Ole Tange  wrote:
(...)
> Git's use of SHA1 seems to be a prime example of what can go wrong:
> https://shattered.io/

What does a PRNG have to do with a hashing function?

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

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Ole Tange]

On Wed, Nov 21, 2018 at 11:45 PM Chet Ramey  wrote:
> On 11/21/18 3:07 PM, Ole Tange wrote:
> > '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?
>
> 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

Re: $RANDOM not Cryptographically secure pseudorandom number generator

[Chet Ramey]

On 11/21/18 3:07 PM, Ole Tange wrote:
> '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?

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, CWRUc...@case.eduhttp://tiswww.cwru.edu/~chet/