lib/util/genrand.c

   1 /*
   2    Unix SMB/CIFS implementation.
   3
   4    Functions to create reasonable random numbers for crypto use.
   5
   6    Copyright (C) Jeremy Allison 2001
   7
   8    This program is free software; you can redistribute it and/or modify
   9    it under the terms of the GNU General Public License as published by
  10    the Free Software Foundation; either version 3 of the License, or
  11    (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16    GNU General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public License
  19    along with this program.  If not, see <http://www.gnu.org/licenses/>.
  20 */
  21
  22 #include "includes.h"
  23 #include "system/filesys.h"
  24 #include "../lib/crypto/crypto.h"
  25 #include "system/locale.h"
  26
  27 /**
  28  * @file
  29  * @brief Random number generation
  30  */
  31
  32 static unsigned char hash[258];
  33 static uint32_t counter;
  34
  35 static bool done_reseed = false;
  36 static unsigned int bytes_since_reseed = 0;
  37
  38 static int urand_fd = -1;
  39
  40 static void (*reseed_callback)(void *userdata, int *newseed);
  41 static void *reseed_callback_userdata = NULL;
  42
  43 /**
  44  Copy any user given reseed data.
  45 **/
  46
  47 _PUBLIC_ void set_rand_reseed_callback(void (*fn)(void *, int *), void *userdata)
  48 {
  49         reseed_callback = fn;
  50         reseed_callback_userdata = userdata;
  51         set_need_random_reseed();
  52 }
  53
  54 /**
  55  * Tell the random number generator it needs to reseed.
  56  */
  57 _PUBLIC_ void set_need_random_reseed(void)
  58 {
  59         done_reseed = false;
  60         bytes_since_reseed = 0;
  61 }
  62
  63 static void get_rand_reseed_data(int *reseed_data)
  64 {
  65         if (reseed_callback) {
  66                 reseed_callback(reseed_callback_userdata, reseed_data);
  67         } else {
  68                 *reseed_data = 0;
  69         }
  70 }
  71
  72 /****************************************************************
  73  Setup the seed.
  74 *****************************************************************/
  75
  76 static void seed_random_stream(unsigned char *seedval, size_t seedlen)
  77 {
  78         unsigned char j = 0;
  79         size_t ind;
  80
  81         for (ind = 0; ind < 256; ind++)
  82                 hash[ind] = (unsigned char)ind;
  83
  84         for( ind = 0; ind < 256; ind++) {
  85                 unsigned char tc;
  86
  87                 j += (hash[ind] + seedval[ind%seedlen]);
  88
  89                 tc = hash[ind];
  90                 hash[ind] = hash[j];
  91                 hash[j] = tc;
  92         }
  93
  94         hash[256] = 0;
  95         hash[257] = 0;
  96 }
  97
  98 /****************************************************************
  99  Get datasize bytes worth of random data.
 100 *****************************************************************/
 101
 102 static void get_random_stream(unsigned char *data, size_t datasize)
 103 {
 104         unsigned char index_i = hash[256];
 105         unsigned char index_j = hash[257];
 106         size_t ind;
 107
 108         for( ind = 0; ind < datasize; ind++) {
 109                 unsigned char tc;
 110                 unsigned char t;
 111
 112                 index_i++;
 113                 index_j += hash[index_i];
 114
 115                 tc = hash[index_i];
 116                 hash[index_i] = hash[index_j];
 117                 hash[index_j] = tc;
 118
 119                 t = hash[index_i] + hash[index_j];
 120                 data[ind] = hash[t];
 121         }
 122
 123         hash[256] = index_i;
 124         hash[257] = index_j;
 125 }
 126
 127 /****************************************************************
 128  Get a 16 byte hash from the contents of a file.
 129
 130  Note that the hash is initialised, because the extra entropy is not
 131  worth the valgrind pain.
 132 *****************************************************************/
 133
 134 static void do_filehash(const char *fname, unsigned char *the_hash)
 135 {
 136         unsigned char buf[1011]; /* deliberate weird size */
 137         unsigned char tmp_md4[16];
 138         int fd, n;
 139
 140         ZERO_STRUCT(tmp_md4);
 141
 142         fd = open(fname,O_RDONLY,0);
 143         if (fd == -1)
 144                 return;
 145
 146         while ((n = read(fd, (char *)buf, sizeof(buf))) > 0) {
 147                 mdfour(tmp_md4, buf, n);
 148                 for (n=0;n<16;n++)
 149                         the_hash[n] ^= tmp_md4[n];
 150         }
 151         close(fd);
 152 }
 153
 154 /**************************************************************
 155  Try and get a good random number seed. Try a number of
 156  different factors. Firstly, try /dev/urandom - use if exists.
 157
 158  We use /dev/urandom as a read of /dev/random can block if
 159  the entropy pool dries up. This leads clients to timeout
 160  or be very slow on connect.
 161
 162  If we can't use /dev/urandom then seed the stream random generator
 163  above...
 164 **************************************************************/
 165
 166 static int do_reseed(bool use_fd, int fd)
 167 {
 168         unsigned char seed_inbuf[40];
 169         uint32_t v1, v2; struct timeval tval; pid_t mypid;
 170         int reseed_data = 0;
 171
 172         if (use_fd) {
 173                 if (fd == -1) {
 174                         fd = open( "/dev/urandom", O_RDONLY,0);
 175                 }
 176                 if (fd != -1
 177                     && (read(fd, seed_inbuf, sizeof(seed_inbuf)) == sizeof(seed_inbuf))) {
 178                         seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
 179                         return fd;
 180                 }
 181         }
 182
 183         /* Add in some secret file contents */
 184
 185         do_filehash("/etc/shadow", &seed_inbuf[0]);
 186
 187         /*
 188          * Add the counter, time of day, and pid.
 189          */
 190
 191         GetTimeOfDay(&tval);
 192         mypid = getpid();
 193         v1 = (counter++) + mypid + tval.tv_sec;
 194         v2 = (counter++) * mypid + tval.tv_usec;
 195
 196         SIVAL(seed_inbuf, 32, v1 ^ IVAL(seed_inbuf, 32));
 197         SIVAL(seed_inbuf, 36, v2 ^ IVAL(seed_inbuf, 36));
 198
 199         /*
 200          * Add any user-given reseed data.
 201          */
 202
 203         get_rand_reseed_data(&reseed_data);
 204         if (reseed_data) {
 205                 size_t i;
 206                 for (i = 0; i < sizeof(seed_inbuf); i++)
 207                         seed_inbuf[i] ^= ((char *)(&reseed_data))[i % sizeof(reseed_data)];
 208         }
 209
 210         seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
 211
 212         return -1;
 213 }
 214
 215 /**
 216  Interface to the (hopefully) good crypto random number generator.
 217  Will use our internal PRNG if more than 40 bytes of random generation
 218  has been requested, otherwise tries to read from /dev/random
 219 **/
 220 _PUBLIC_ void generate_random_buffer(uint8_t *out, int len)
 221 {
 222         unsigned char md4_buf[64];
 223         unsigned char tmp_buf[16];
 224         unsigned char *p;
 225
 226         if(!done_reseed) {
 227                 bytes_since_reseed += len;
 228
 229                 /* Magic constant to try and avoid reading 40 bytes
 230                  * and setting up the PRNG if the app only ever wants
 231                  * a few bytes */
 232                 if (bytes_since_reseed < 40) {
 233                         if (urand_fd == -1) {
 234                                 urand_fd = open( "/dev/urandom", O_RDONLY,0);
 235                         }
 236                         if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
 237                                 return;
 238                         }
 239                 }
 240
 241                 urand_fd = do_reseed(true, urand_fd);
 242                 done_reseed = true;
 243         }
 244
 245         /*
 246          * Generate random numbers in chunks of 64 bytes,
 247          * then md4 them & copy to the output buffer.
 248          * This way the raw state of the stream is never externally
 249          * seen.
 250          */
 251
 252         p = out;
 253         while(len > 0) {
 254                 int copy_len = len > 16 ? 16 : len;
 255
 256                 get_random_stream(md4_buf, sizeof(md4_buf));
 257                 mdfour(tmp_buf, md4_buf, sizeof(md4_buf));
 258                 memcpy(p, tmp_buf, copy_len);
 259                 p += copy_len;
 260                 len -= copy_len;
 261         }
 262 }
 263
 264 /**
 265  Interface to the (hopefully) good crypto random number generator.
 266  Will always use /dev/urandom if available.
 267 **/
 268 _PUBLIC_ void generate_secret_buffer(uint8_t *out, int len)
 269 {
 270         if (urand_fd == -1) {
 271                 urand_fd = open( "/dev/urandom", O_RDONLY,0);
 272         }
 273         if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
 274                 return;
 275         }
 276
 277         generate_random_buffer(out, len);
 278 }
 279
 280 /**
 281   generate a single random uint32_t
 282 **/
 283 _PUBLIC_ uint32_t generate_random(void)
 284 {
 285         uint8_t v[4];
 286         generate_random_buffer(v, 4);
 287         return IVAL(v, 0);
 288 }
 289
 290
 291 /**
 292   very basic password quality checker
 293 **/
 294 _PUBLIC_ bool check_password_quality(const char *s)
 295 {
 296         int has_digit=0, has_capital=0, has_lower=0, has_special=0, has_high=0;
 297         const char* reals = s;
 298         while (*s) {
 299                 if (isdigit((unsigned char)*s)) {
 300                         has_digit |= 1;
 301                 } else if (isupper((unsigned char)*s)) {
 302                         has_capital |= 1;
 303                 } else if (islower((unsigned char)*s)) {
 304                         has_lower |= 1;
 305                 } else if (isascii((unsigned char)*s)) {
 306                         has_special |= 1;
 307                 } else {
 308                         has_high++;
 309                 }
 310                 s++;
 311         }
 312
 313         return ((has_digit + has_lower + has_capital + has_special) >= 3
 314                 || (has_high > strlen(reals)/2));
 315 }
 316
 317 /**
 318  Use the random number generator to generate a random string.
 319 **/
 320
 321 _PUBLIC_ char *generate_random_str_list(TALLOC_CTX *mem_ctx, size_t len, const char *list)
 322 {
 323         size_t i;
 324         size_t list_len = strlen(list);
 325
 326         char *retstr = talloc_array(mem_ctx, char, len + 1);
 327         if (!retstr) return NULL;
 328
 329         generate_random_buffer((uint8_t *)retstr, len);
 330         for (i = 0; i < len; i++) {
 331                 retstr[i] = list[retstr[i] % list_len];
 332         }
 333         retstr[i] = '\0';
 334
 335         return retstr;
 336 }
 337
 338 /**
 339  * Generate a random text string consisting of the specified length.
 340  * The returned string will be allocated.
 341  *
 342  * Characters used are: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 343  */
 344
 345 _PUBLIC_ char *generate_random_str(TALLOC_CTX *mem_ctx, size_t len)
 346 {
 347         char *retstr;
 348         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 349
 350 again:
 351         retstr = generate_random_str_list(mem_ctx, len, c_list);
 352         if (!retstr) return NULL;
 353
 354         /* we need to make sure the random string passes basic quality tests
 355            or it might be rejected by windows as a password */
 356         if (len >= 7 && !check_password_quality(retstr)) {
 357                 talloc_free(retstr);
 358                 goto again;
 359         }
 360
 361         return retstr;
 362 }
 363
 364 /**
 365  * Generate a random text password.
 366  */
 367
 368 _PUBLIC_ char *generate_random_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
 369 {
 370         char *retstr;
 371         /* This list does not include { or } because they cause
 372          * problems for our provision (it can create a substring
 373          * ${...}, and for Fedora DS (which treats {...} at the start
 374          * of a stored password as special
 375          *  -- Andrew Bartlett 2010-03-11
 376          */
 377         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,@$%&!?:;<=>()[]~";
 378         size_t len = max;
 379         size_t diff;
 380
 381         if (min > max) {
 382                 errno = EINVAL;
 383                 return NULL;
 384         }
 385
 386         diff = max - min;
 387
 388         if (diff > 0 ) {
 389                 size_t tmp;
 390
 391                 generate_random_buffer((uint8_t *)&tmp, sizeof(tmp));
 392
 393                 tmp %= diff;
 394
 395                 len = min + tmp;
 396         }
 397
 398 again:
 399         retstr = generate_random_str_list(mem_ctx, len, c_list);
 400         if (!retstr) return NULL;
 401
 402         /* we need to make sure the random string passes basic quality tests
 403            or it might be rejected by windows as a password */
 404         if (len >= 7 && !check_password_quality(retstr)) {
 405                 talloc_free(retstr);
 406                 goto again;
 407         }
 408
 409         return retstr;
 410 }
 411
 412 /**
 413  * Generate an array of unique text strings all of the same length.
 414  * The returned string will be allocated.
 415  * Returns NULL if the number of unique combinations cannot be created.
 416  *
 417  * Characters used are: abcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 418  */
 419 _PUBLIC_ char** generate_unique_strs(TALLOC_CTX *mem_ctx, size_t len,
 420                                      uint32_t num)
 421 {
 422         const char *c_list = "abcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 423         const unsigned c_size = 42;
 424         int i, j;
 425         unsigned rem;
 426         char ** strs = NULL;
 427
 428         if (num == 0 || len == 0)
 429                 return NULL;
 430
 431         strs = talloc_array(mem_ctx, char *, num);
 432         if (strs == NULL) return NULL;
 433
 434         for (i = 0; i < num; i++) {
 435                 char *retstr = (char *)talloc_size(strs, len + 1);
 436                 if (retstr == NULL) {
 437                         talloc_free(strs);
 438                         return NULL;
 439                 }
 440                 rem = i;
 441                 for (j = 0; j < len; j++) {
 442                         retstr[j] = c_list[rem % c_size];
 443                         rem = rem / c_size;
 444                 }
 445                 retstr[j] = 0;
 446                 strs[i] = retstr;
 447                 if (rem != 0) {
 448                         /* we were not able to fit the number of
 449                          * combinations asked for in the length
 450                          * specified */
 451                         DEBUG(0,(__location__ ": Too many combinations %u for length %u\n",
 452                                  num, (unsigned)len));
 453
 454                         talloc_free(strs);
 455                         return NULL;
 456                 }
 457         }
 458
 459         return strs;
 460 }