On Mon, Jan 7, 2019 at 12:08 AM Chet Ramey <[email protected]> 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_MAX 0x7fff /* 16 bits */
+# define RANDOMLIST_SIZE 31
+#else
+# define BASH_RAND_MAX 0x7fffffff /* 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 between 0 and BASH_RAND_MAX. */
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 += 0x7fffffff;
-#endif
- return ((unsigned int)(rseed & 32767)); /* was % 32768 */
+ /* salsa20_block generates 16 32-bit/32 16-bit values */
+ /* use them all before calling chacha20_block again */
+ if(0 == random_list_idx)
+ chacha20_block((uint32_t *)chachastate);
+ random_list_idx++;
+ random_list_idx &= RANDOMLIST_SIZE;
+ return random_list[random_list_idx];
}
-/* Set the random number generator seed to SEED. */
+void
+reset_chachastate(chachastate)
+ uint64_t *chachastate;
+{
+ int i;
+ for (i = 0; i < 8; ++i)
+ chachastate[i] = 0;
+ memcpy(salsaconstant,chachastate,16);
+}
+
+/* backwards compatible 64-bit seeder */
static void
sbrand (seed)
- unsigned long seed;
+ uint64_t seed;
+{
+ reset_chachastate ();
+ chachastate[2] = seed;
+ random_list_idx = 0;
+}
+
+
+/* add seed with any binary input e.g. a string */
+/* similar to adding entropy to /dev/random */
+static void
+stringaddseedrand (seed,len,chachastate)
+ uint8_t *chachastate;
+ uint8_t *seed;
+ int len;
+{
+ int i,j;
+ for (i = 0, j = 0; i < len; ++i, ++j) {
+ /* key is supposed to go in chachastate byte[16..47]
+ but instead of first hashing the seed value to a
+ 256 bit value we simply xor the seed onto the full state */
+ chachastate[j] ^= seed[i];
+ if (j == 63) {
+ /* shake the bits before adding more */
+ /* otherwise 64 bytes repeated twice will cancel out */
+ j = 0;
+ chacha20_block ((uint32_t *)chachastate);
+ }
+ }
+ chacha20_block ((uint32_t *)chachastate);
+}
+
+static void
+stringseedrand (seed,len)
+ uint8_t *seed;
+ int len;
{
- rseed = seed;
- last_random_value = 0;
+ reset_chachastate (chachastate);
+ stringaddseedrand (seed,len,chachastate);
+ random_list_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 pid;
gettimeofday (&tv, NULL);
- sbrand (tv.tv_sec ^ tv.tv_usec ^ getpid ());
+ stringaddseedrand (&tv,sizeof(tv),chachastate);
+ pid = getpid ();
+ stringaddseedrand (&pid,sizeof(pid),chachastate);
}
+
+static int seeded_subshell = 0;
+
static SHELL_VAR *
assign_random (self, value, unused, key)
SHELL_VAR *self;
@@ -1366,7 +1482,7 @@ assign_random (self, value, unused, key)
arrayind_t unused;
char *key;
{
- sbrand (strtoul (value, (char **)NULL, 10));
+ stringseedrand (value,strlen(value));
if (subshell_environment)
seeded_subshell = getpid ();
return (self);
@@ -1385,9 +1501,7 @@ get_random_number ()
seeded_subshell = pid;
}
- do
- rv = brand ();
- while (rv == last_random_value);
+ rv = brand ();
return rv;
}
@@ -1399,7 +1513,6 @@ get_random (var)
char *p;
rv = get_random_number ();
- last_random_value = rv;
p = itos (rv);
FREE (value_cell (var));
