On Sun, Dec 16, 2018 at 6:41 AM Eduardo Bustamante <dual...@gmail.com> 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 <http://www.gnu.org/licenses/>.
*/
+#include <stdint.h>
#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 += 0x7fffffff;
-#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 & 0xFFFFFFFF;
+ 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 pid;
gettimeofday (&tv, NULL);
- sbrand (tv.tv_sec ^ tv.tv_usec ^ getpid ());
+ stringaddseedrand (&tv,sizeof(tv));
+ pid = getpid ();
+ stringaddseedrand (&pid,sizeof(pid));
}
static SHELL_VAR *
@@ -1351,7 +1424,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);
@@ -1370,9 +1443,7 @@ get_random_number ()
seeded_subshell = pid;
}
- do
- rv = brand ();
- while (rv == last_random_value);
+ rv = brand ();
return rv;
}
@@ -1384,7 +1455,6 @@ get_random (var)
char *p;
rv = get_random_number ();
- last_random_value = rv;
p = itos (rv);
FREE (value_cell (var));
