lib/sh/random.c

   1 /* random.c -- Functions for managing 16-bit and 32-bit random numbers. */
   2
   3 /* Copyright (C) 2020 Free Software Foundation, Inc.
   4
   5    This file is part of GNU Bash, the Bourne Again SHell.
   6
   7    Bash is free software: you can redistribute it and/or modify
   8    it under the terms of the GNU General Public License as published by
   9    the Free Software Foundation, either version 3 of the License, or
  10    (at your option) any later version.
  11
  12    Bash is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15    GNU General Public License for more details.
  16
  17    You should have received a copy of the GNU General Public License
  18    along with Bash.  If not, see <http://www.gnu.org/licenses/>.
  19 */
  20
  21 #include "config.h"
  22
  23 #include "bashtypes.h"
  24
  25 #if defined (HAVE_SYS_RANDOM_H)
  26 #  include <sys/random.h>
  27 #endif
  28
  29 #if defined (HAVE_UNISTD_H)
  30 #  include <unistd.h>
  31 #endif
  32 #include "filecntl.h"
  33
  34 #include <stdio.h>
  35 #include "bashansi.h"
  36
  37 #include "shell.h"
  38
  39 extern time_t shell_start_time;
  40
  41 extern int last_random_value;
  42
  43 static u_bits32_t intrand32 PARAMS((u_bits32_t));
  44 static u_bits32_t genseed PARAMS((void));
  45
  46 static u_bits32_t brand32 PARAMS((void));
  47 static void sbrand32 PARAMS((u_bits32_t));
  48 static void perturb_rand32 PARAMS((void));
  49
  50 /* The random number seed.  You can change this by setting RANDOM. */
  51 static u_bits32_t rseed = 1;
  52
  53 /* Returns a 32-bit pseudo-random number. */
  54 static u_bits32_t
  55 intrand32 (last)
  56      u_bits32_t last;
  57 {
  58   /* Minimal Standard generator from
  59      "Random number generators: good ones are hard to find",
  60      Park and Miller, Communications of the ACM, vol. 31, no. 10,
  61      October 1988, p. 1195. Filtered through FreeBSD.
  62
  63      x(n+1) = 16807 * x(n) mod (m).
  64
  65      We split up the calculations to avoid overflow.
  66
  67      h = last / q; l = x - h * q; t = a * l - h * r
  68      m = 2147483647, a = 16807, q = 127773, r = 2836
  69
  70      There are lots of other combinations of constants to use; look at
  71      https://www.gnu.org/software/gsl/manual/html_node/Other-random-number-generators.html#Other-random-number-generators */
  72
  73   bits32_t h, l, t;
  74   u_bits32_t ret;
  75
  76   /* Can't seed with 0. */
  77   ret = (last == 0) ? 123459876 : last;
  78   h = ret / 127773;
  79   l = ret - (127773 * h);
  80   t = 16807 * l - 2836 * h;
  81   ret = (t < 0) ? t + 0x7fffffff : t;
  82
  83   return (ret);
  84 }
  85
  86 static u_bits32_t
  87 genseed ()
  88 {
  89   struct timeval tv;
  90   u_bits32_t iv;
  91
  92   gettimeofday (&tv, NULL);
  93   iv = (u_bits32_t)seedrand;            /* let the compiler truncate */
  94   iv = tv.tv_sec ^ tv.tv_usec ^ getpid () ^ getppid () ^ current_user.uid ^ iv;
  95   return (iv);
  96 }
  97
  98 #define BASH_RAND_MAX   32767           /* 0x7fff - 16 bits */
  99
 100 /* Returns a pseudo-random number between 0 and 32767. */
 101 int
 102 brand ()
 103 {
 104   unsigned int ret;
 105
 106   rseed = intrand32 (rseed);
 107   if (shell_compatibility_level > 50)
 108     ret = (rseed >> 16) ^ (rseed & 65535);
 109   else
 110     ret = rseed;
 111   return (ret & BASH_RAND_MAX);
 112 }
 113
 114 /* Set the random number generator seed to SEED. */
 115 void
 116 sbrand (seed)
 117      unsigned long seed;
 118 {
 119   rseed = seed;
 120   last_random_value = 0;
 121 }
 122
 123 void
 124 seedrand ()
 125 {
 126   u_bits32_t iv;
 127
 128   iv = genseed ();
 129   sbrand (iv);
 130 }
 131
 132 static u_bits32_t rseed32 = 1073741823;
 133 static int last_rand32;
 134
 135 static int urandfd = -1;
 136
 137 #define BASH_RAND32_MAX 0x7fffffff      /* 32 bits */
 138
 139 /* Returns a 32-bit pseudo-random number between 0 and 4294967295. */
 140 static u_bits32_t
 141 brand32 ()
 142 {
 143   u_bits32_t ret;
 144
 145   rseed32 = intrand32 (rseed32);
 146   return (rseed32 & BASH_RAND32_MAX);
 147 }
 148
 149 static void
 150 sbrand32 (seed)
 151      u_bits32_t seed;
 152 {
 153   last_rand32 = rseed32 = seed;
 154 }
 155
 156 void
 157 seedrand32 ()
 158 {
 159   u_bits32_t iv;
 160
 161   iv = genseed ();
 162   sbrand32 (iv);
 163 }
 164
 165 static void
 166 perturb_rand32 ()
 167 {
 168   rseed32 ^= genseed ();
 169 }
 170
 171 /* Force another attempt to open /dev/urandom on the next call to get_urandom32 */
 172 void
 173 urandom_close ()
 174 {
 175   if (urandfd >= 0)
 176     close (urandfd);
 177   urandfd = -1;
 178 }
 179
 180 #if !defined (HAVE_GETRANDOM)
 181 /* Imperfect emulation of getrandom(2). */
 182 #ifndef GRND_NONBLOCK
 183 #  define GRND_NONBLOCK 1
 184 #  define GRND_RANDOM 2
 185 #endif
 186
 187 static ssize_t
 188 getrandom (buf, len, flags)
 189      void *buf;
 190      size_t len;
 191      unsigned int flags;
 192 {
 193   int oflags;
 194   ssize_t r;
 195   static int urand_unavail = 0;
 196
 197 #if HAVE_GETENTROPY
 198   r = getentropy (buf, len);
 199   return (r == 0) ? len : -1;
 200 #endif
 201
 202   if (urandfd == -1 && urand_unavail == 0)
 203     {
 204       oflags = O_RDONLY;
 205       if (flags & GRND_NONBLOCK)
 206         oflags |= O_NONBLOCK;
 207       urandfd = open ("/dev/urandom", oflags, 0);
 208       if (urandfd >= 0)
 209         SET_CLOSE_ON_EXEC (urandfd);
 210       else
 211         {
 212           urand_unavail = 1;
 213           return -1;
 214         }
 215     }
 216   if (urandfd >= 0 && (r = read (urandfd, buf, len)) == len)
 217     return (r);
 218   return -1;
 219 }
 220 #endif
 221
 222 u_bits32_t
 223 get_urandom32 ()
 224 {
 225   u_bits32_t ret;
 226
 227   if (getrandom ((void *)&ret, sizeof (ret), GRND_NONBLOCK) == sizeof (ret))
 228     return (last_rand32 = ret);
 229
 230 #if defined (HAVE_ARC4RANDOM)
 231   ret = arc4random ();
 232 #else
 233   if (subshell_environment)
 234     perturb_rand32 ();
 235   do
 236     ret = brand32 ();
 237   while (ret == last_rand32);
 238 #endif
 239   return (last_rand32 = ret);
 240 }