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                         if (fd != -1) {
 176                                 set_close_on_exec(fd);
 177                         }
 178                 }
 179                 if (fd != -1
 180                     && (read(fd, seed_inbuf, sizeof(seed_inbuf)) == sizeof(seed_inbuf))) {
 181                         seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
 182                         return fd;
 183                 }
 184         }
 185
 186         /* Add in some secret file contents */
 187
 188         do_filehash("/etc/shadow", &seed_inbuf[0]);
 189
 190         /*
 191          * Add the counter, time of day, and pid.
 192          */
 193
 194         GetTimeOfDay(&tval);
 195         mypid = getpid();
 196         v1 = (counter++) + mypid + tval.tv_sec;
 197         v2 = (counter++) * mypid + tval.tv_usec;
 198
 199         SIVAL(seed_inbuf, 32, v1 ^ IVAL(seed_inbuf, 32));
 200         SIVAL(seed_inbuf, 36, v2 ^ IVAL(seed_inbuf, 36));
 201
 202         /*
 203          * Add any user-given reseed data.
 204          */
 205
 206         get_rand_reseed_data(&reseed_data);
 207         if (reseed_data) {
 208                 size_t i;
 209                 for (i = 0; i < sizeof(seed_inbuf); i++)
 210                         seed_inbuf[i] ^= ((char *)(&reseed_data))[i % sizeof(reseed_data)];
 211         }
 212
 213         seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
 214
 215         return -1;
 216 }
 217
 218 /**
 219  Interface to the (hopefully) good crypto random number generator.
 220  Will use our internal PRNG if more than 40 bytes of random generation
 221  has been requested, otherwise tries to read from /dev/random
 222 **/
 223 _PUBLIC_ void generate_random_buffer(uint8_t *out, int len)
 224 {
 225         unsigned char md4_buf[64];
 226         unsigned char tmp_buf[16];
 227         unsigned char *p;
 228
 229         if(!done_reseed) {
 230                 bytes_since_reseed += len;
 231
 232                 /* Magic constant to try and avoid reading 40 bytes
 233                  * and setting up the PRNG if the app only ever wants
 234                  * a few bytes */
 235                 if (bytes_since_reseed < 40) {
 236                         if (urand_fd == -1) {
 237                                 urand_fd = open( "/dev/urandom", O_RDONLY,0);
 238                                 if (urand_fd != -1) {
 239                                         set_close_on_exec(urand_fd);
 240                                 }
 241                         }
 242                         if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
 243                                 return;
 244                         }
 245                 }
 246
 247                 urand_fd = do_reseed(true, urand_fd);
 248                 done_reseed = true;
 249         }
 250
 251         /*
 252          * Generate random numbers in chunks of 64 bytes,
 253          * then md4 them & copy to the output buffer.
 254          * This way the raw state of the stream is never externally
 255          * seen.
 256          */
 257
 258         p = out;
 259         while(len > 0) {
 260                 int copy_len = len > 16 ? 16 : len;
 261
 262                 get_random_stream(md4_buf, sizeof(md4_buf));
 263                 mdfour(tmp_buf, md4_buf, sizeof(md4_buf));
 264                 memcpy(p, tmp_buf, copy_len);
 265                 p += copy_len;
 266                 len -= copy_len;
 267         }
 268 }
 269
 270 /**
 271  Interface to the (hopefully) good crypto random number generator.
 272  Will always use /dev/urandom if available.
 273 **/
 274 _PUBLIC_ void generate_secret_buffer(uint8_t *out, int len)
 275 {
 276         if (urand_fd == -1) {
 277                 urand_fd = open( "/dev/urandom", O_RDONLY,0);
 278                 if (urand_fd != -1) {
 279                         set_close_on_exec(urand_fd);
 280                 }
 281         }
 282         if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
 283                 return;
 284         }
 285
 286         generate_random_buffer(out, len);
 287 }
 288
 289 /**
 290   generate a single random uint32_t
 291 **/
 292 _PUBLIC_ uint32_t generate_random(void)
 293 {
 294         uint8_t v[4];
 295         generate_random_buffer(v, 4);
 296         return IVAL(v, 0);
 297 }
 298
 299
 300 /**
 301   very basic password quality checker
 302 **/
 303 _PUBLIC_ bool check_password_quality(const char *s)
 304 {
 305         int has_digit=0, has_capital=0, has_lower=0, has_special=0, has_high=0;
 306         const char* reals = s;
 307         while (*s) {
 308                 if (isdigit((unsigned char)*s)) {
 309                         has_digit |= 1;
 310                 } else if (isupper((unsigned char)*s)) {
 311                         has_capital |= 1;
 312                 } else if (islower((unsigned char)*s)) {
 313                         has_lower |= 1;
 314                 } else if (isascii((unsigned char)*s)) {
 315                         has_special |= 1;
 316                 } else {
 317                         has_high++;
 318                 }
 319                 s++;
 320         }
 321
 322         return ((has_digit + has_lower + has_capital + has_special) >= 3
 323                 || (has_high > strlen(reals)/2));
 324 }
 325
 326 /**
 327  Use the random number generator to generate a random string.
 328 **/
 329
 330 _PUBLIC_ char *generate_random_str_list(TALLOC_CTX *mem_ctx, size_t len, const char *list)
 331 {
 332         size_t i;
 333         size_t list_len = strlen(list);
 334
 335         char *retstr = talloc_array(mem_ctx, char, len + 1);
 336         if (!retstr) return NULL;
 337
 338         generate_random_buffer((uint8_t *)retstr, len);
 339         for (i = 0; i < len; i++) {
 340                 retstr[i] = list[retstr[i] % list_len];
 341         }
 342         retstr[i] = '\0';
 343
 344         return retstr;
 345 }
 346
 347 /**
 348  * Generate a random text string consisting of the specified length.
 349  * The returned string will be allocated.
 350  *
 351  * Characters used are: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 352  */
 353
 354 _PUBLIC_ char *generate_random_str(TALLOC_CTX *mem_ctx, size_t len)
 355 {
 356         char *retstr;
 357         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 358
 359 again:
 360         retstr = generate_random_str_list(mem_ctx, len, c_list);
 361         if (!retstr) return NULL;
 362
 363         /* we need to make sure the random string passes basic quality tests
 364            or it might be rejected by windows as a password */
 365         if (len >= 7 && !check_password_quality(retstr)) {
 366                 talloc_free(retstr);
 367                 goto again;
 368         }
 369
 370         return retstr;
 371 }
 372
 373 /**
 374  * Generate a random text password.
 375  */
 376
 377 _PUBLIC_ char *generate_random_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
 378 {
 379         char *retstr;
 380         /* This list does not include { or } because they cause
 381          * problems for our provision (it can create a substring
 382          * ${...}, and for Fedora DS (which treats {...} at the start
 383          * of a stored password as special
 384          *  -- Andrew Bartlett 2010-03-11
 385          */
 386         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,@$%&!?:;<=>()[]~";
 387         size_t len = max;
 388         size_t diff;
 389
 390         if (min > max) {
 391                 errno = EINVAL;
 392                 return NULL;
 393         }
 394
 395         diff = max - min;
 396
 397         if (diff > 0 ) {
 398                 size_t tmp;
 399
 400                 generate_random_buffer((uint8_t *)&tmp, sizeof(tmp));
 401
 402                 tmp %= diff;
 403
 404                 len = min + tmp;
 405         }
 406
 407 again:
 408         retstr = generate_random_str_list(mem_ctx, len, c_list);
 409         if (!retstr) return NULL;
 410
 411         /* we need to make sure the random string passes basic quality tests
 412            or it might be rejected by windows as a password */
 413         if (len >= 7 && !check_password_quality(retstr)) {
 414                 talloc_free(retstr);
 415                 goto again;
 416         }
 417
 418         return retstr;
 419 }
 420
 421 /**
 422  * Generate an array of unique text strings all of the same length.
 423  * The returned string will be allocated.
 424  * Returns NULL if the number of unique combinations cannot be created.
 425  *
 426  * Characters used are: abcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 427  */
 428 _PUBLIC_ char** generate_unique_strs(TALLOC_CTX *mem_ctx, size_t len,
 429                                      uint32_t num)
 430 {
 431         const char *c_list = "abcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 432         const unsigned c_size = 42;
 433         int i, j;
 434         unsigned rem;
 435         char ** strs = NULL;
 436
 437         if (num == 0 || len == 0)
 438                 return NULL;
 439
 440         strs = talloc_array(mem_ctx, char *, num);
 441         if (strs == NULL) return NULL;
 442
 443         for (i = 0; i < num; i++) {
 444                 char *retstr = (char *)talloc_size(strs, len + 1);
 445                 if (retstr == NULL) {
 446                         talloc_free(strs);
 447                         return NULL;
 448                 }
 449                 rem = i;
 450                 for (j = 0; j < len; j++) {
 451                         retstr[j] = c_list[rem % c_size];
 452                         rem = rem / c_size;
 453                 }
 454                 retstr[j] = 0;
 455                 strs[i] = retstr;
 456                 if (rem != 0) {
 457                         /* we were not able to fit the number of
 458                          * combinations asked for in the length
 459                          * specified */
 460                         DEBUG(0,(__location__ ": Too many combinations %u for length %u\n",
 461                                  num, (unsigned)len));
 462
 463                         talloc_free(strs);
 464                         return NULL;
 465                 }
 466         }
 467
 468         return strs;
 469 }