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(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 (fd == -1) {
 173                 fd = open( "/dev/urandom", O_RDONLY,0);
 174                 if (fd != -1) {
 175                         smb_set_close_on_exec(fd);
 176                 }
 177         }
 178         if (fd != -1
 179             && (read(fd, seed_inbuf, sizeof(seed_inbuf)) == sizeof(seed_inbuf))) {
 180                 seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
 181                 return fd;
 182         }
 183
 184         /* Add in some secret file contents */
 185
 186         do_filehash("/etc/shadow", &seed_inbuf[0]);
 187
 188         /*
 189          * Add the counter, time of day, and pid.
 190          */
 191
 192         GetTimeOfDay(&tval);
 193         mypid = getpid();
 194         v1 = (counter++) + mypid + tval.tv_sec;
 195         v2 = (counter++) * mypid + tval.tv_usec;
 196
 197         SIVAL(seed_inbuf, 32, v1 ^ IVAL(seed_inbuf, 32));
 198         SIVAL(seed_inbuf, 36, v2 ^ IVAL(seed_inbuf, 36));
 199
 200         /*
 201          * Add any user-given reseed data.
 202          */
 203
 204         get_rand_reseed_data(&reseed_data);
 205         if (reseed_data) {
 206                 size_t i;
 207                 for (i = 0; i < sizeof(seed_inbuf); i++)
 208                         seed_inbuf[i] ^= ((char *)(&reseed_data))[i % sizeof(reseed_data)];
 209         }
 210
 211         seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
 212
 213         return -1;
 214 }
 215
 216 /**
 217  Interface to the (hopefully) good crypto random number generator.
 218  Will use our internal PRNG if more than 40 bytes of random generation
 219  has been requested, otherwise tries to read from /dev/random
 220 **/
 221 _PUBLIC_ void generate_random_buffer(uint8_t *out, int len)
 222 {
 223         unsigned char md4_buf[64];
 224         unsigned char tmp_buf[16];
 225         unsigned char *p;
 226
 227         if(!done_reseed) {
 228                 bytes_since_reseed += len;
 229
 230                 /* Magic constant to try and avoid reading 40 bytes
 231                  * and setting up the PRNG if the app only ever wants
 232                  * a few bytes */
 233                 if (bytes_since_reseed < 40) {
 234                         if (urand_fd == -1) {
 235                                 urand_fd = open( "/dev/urandom", O_RDONLY,0);
 236                                 if (urand_fd != -1) {
 237                                         smb_set_close_on_exec(urand_fd);
 238                                 }
 239                         }
 240                         if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
 241                                 return;
 242                         }
 243                 }
 244
 245                 urand_fd = do_reseed(urand_fd);
 246                 done_reseed = true;
 247         }
 248
 249         /*
 250          * Generate random numbers in chunks of 64 bytes,
 251          * then md4 them & copy to the output buffer.
 252          * This way the raw state of the stream is never externally
 253          * seen.
 254          */
 255
 256         p = out;
 257         while(len > 0) {
 258                 int copy_len = len > 16 ? 16 : len;
 259
 260                 get_random_stream(md4_buf, sizeof(md4_buf));
 261                 mdfour(tmp_buf, md4_buf, sizeof(md4_buf));
 262                 memcpy(p, tmp_buf, copy_len);
 263                 p += copy_len;
 264                 len -= copy_len;
 265         }
 266 }
 267
 268 /**
 269  Interface to the (hopefully) good crypto random number generator.
 270  Will always use /dev/urandom if available.
 271 **/
 272 _PUBLIC_ void generate_secret_buffer(uint8_t *out, int len)
 273 {
 274         if (urand_fd == -1) {
 275                 urand_fd = open( "/dev/urandom", O_RDONLY,0);
 276                 if (urand_fd != -1) {
 277                         smb_set_close_on_exec(urand_fd);
 278                 }
 279         }
 280         if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
 281                 return;
 282         }
 283
 284         generate_random_buffer(out, len);
 285 }
 286
 287 /**
 288   generate a single random uint32_t
 289 **/
 290 _PUBLIC_ uint32_t generate_random(void)
 291 {
 292         uint8_t v[4];
 293         generate_random_buffer(v, 4);
 294         return IVAL(v, 0);
 295 }
 296
 297
 298 /**
 299   Microsoft composed the following rules (among others) for quality
 300   checks. This is an abridgment from
 301   http://msdn.microsoft.com/en-us/subscriptions/cc786468%28v=ws.10%29.aspx:
 302
 303   Passwords must contain characters from three of the following five
 304   categories:
 305
 306    - Uppercase characters of European languages (A through Z, with
 307      diacritic marks, Greek and Cyrillic characters)
 308    - Lowercase characters of European languages (a through z, sharp-s,
 309      with diacritic marks, Greek and Cyrillic characters)
 310    - Base 10 digits (0 through 9)
 311    - Nonalphanumeric characters: ~!@#$%^&*_-+=`|\(){}[]:;"'<>,.?/
 312    - Any Unicode character that is categorized as an alphabetic character
 313      but is not uppercase or lowercase. This includes Unicode characters
 314      from Asian languages.
 315
 316  Note: for now do not check if the unicode category is
 317        alphabetic character
 318 **/
 319 _PUBLIC_ bool check_password_quality(const char *pwd)
 320 {
 321         size_t ofs = 0;
 322         size_t num_chars = 0;
 323         size_t num_digits = 0;
 324         size_t num_upper = 0;
 325         size_t num_lower = 0;
 326         size_t num_nonalpha = 0;
 327         size_t num_unicode = 0;
 328         size_t num_categories = 0;
 329
 330         if (pwd == NULL) {
 331                 return false;
 332         }
 333
 334         while (true) {
 335                 const char *s = &pwd[ofs];
 336                 size_t len = 0;
 337                 codepoint_t c;
 338
 339                 c = next_codepoint(s, &len);
 340                 if (c == INVALID_CODEPOINT) {
 341                         return false;
 342                 } else if (c == 0) {
 343                         break;
 344                 }
 345                 ofs += len;
 346                 num_chars += 1;
 347
 348                 if (len == 1) {
 349                         const char *na = "~!@#$%^&*_-+=`|\\(){}[]:;\"'<>,.?/";
 350
 351                         if (isdigit(c)) {
 352                                 num_digits += 1;
 353                                 continue;
 354                         }
 355
 356                         if (isupper(c)) {
 357                                 num_upper += 1;
 358                                 continue;
 359                         }
 360
 361                         if (islower(c)) {
 362                                 num_lower += 1;
 363                                 continue;
 364                         }
 365
 366                         if (strchr(na, c)) {
 367                                 num_nonalpha += 1;
 368                                 continue;
 369                         }
 370
 371                         /*
 372                          * the rest does not belong to
 373                          * a category.
 374                          */
 375                         continue;
 376                 }
 377
 378                 if (isupper_m(c)) {
 379                         num_upper += 1;
 380                         continue;
 381                 }
 382
 383                 if (islower_m(c)) {
 384                         num_lower += 1;
 385                         continue;
 386                 }
 387
 388                 /*
 389                  * Note: for now do not check if the unicode category is
 390                  *       alphabetic character
 391                  *
 392                  * We would have to import the details from
 393                  * ftp://ftp.unicode.org/Public/6.3.0/ucd/UnicodeData-6.3.0d1.txt
 394                  */
 395                 num_unicode += 1;
 396                 continue;
 397         }
 398
 399         if (num_digits > 0) {
 400                 num_categories += 1;
 401         }
 402         if (num_upper > 0) {
 403                 num_categories += 1;
 404         }
 405         if (num_lower > 0) {
 406                 num_categories += 1;
 407         }
 408         if (num_nonalpha > 0) {
 409                 num_categories += 1;
 410         }
 411         if (num_unicode > 0) {
 412                 num_categories += 1;
 413         }
 414
 415         if (num_categories >= 3) {
 416                 return true;
 417         }
 418
 419         return false;
 420 }
 421
 422 /**
 423  Use the random number generator to generate a random string.
 424 **/
 425
 426 _PUBLIC_ char *generate_random_str_list(TALLOC_CTX *mem_ctx, size_t len, const char *list)
 427 {
 428         size_t i;
 429         size_t list_len = strlen(list);
 430
 431         char *retstr = talloc_array(mem_ctx, char, len + 1);
 432         if (!retstr) return NULL;
 433
 434         generate_random_buffer((uint8_t *)retstr, len);
 435         for (i = 0; i < len; i++) {
 436                 retstr[i] = list[retstr[i] % list_len];
 437         }
 438         retstr[i] = '\0';
 439
 440         return retstr;
 441 }
 442
 443 /**
 444  * Generate a random text string consisting of the specified length.
 445  * The returned string will be allocated.
 446  *
 447  * Characters used are: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 448  */
 449
 450 _PUBLIC_ char *generate_random_str(TALLOC_CTX *mem_ctx, size_t len)
 451 {
 452         char *retstr;
 453         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 454
 455 again:
 456         retstr = generate_random_str_list(mem_ctx, len, c_list);
 457         if (!retstr) return NULL;
 458
 459         /* we need to make sure the random string passes basic quality tests
 460            or it might be rejected by windows as a password */
 461         if (len >= 7 && !check_password_quality(retstr)) {
 462                 talloc_free(retstr);
 463                 goto again;
 464         }
 465
 466         return retstr;
 467 }
 468
 469 /**
 470  * Generate a random text password.
 471  */
 472
 473 _PUBLIC_ char *generate_random_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
 474 {
 475         char *retstr;
 476         /* This list does not include { or } because they cause
 477          * problems for our provision (it can create a substring
 478          * ${...}, and for Fedora DS (which treats {...} at the start
 479          * of a stored password as special
 480          *  -- Andrew Bartlett 2010-03-11
 481          */
 482         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,@$%&!?:;<=>()[]~";
 483         size_t len = max;
 484         size_t diff;
 485
 486         if (min > max) {
 487                 errno = EINVAL;
 488                 return NULL;
 489         }
 490
 491         diff = max - min;
 492
 493         if (diff > 0 ) {
 494                 size_t tmp;
 495
 496                 generate_random_buffer((uint8_t *)&tmp, sizeof(tmp));
 497
 498                 tmp %= diff;
 499
 500                 len = min + tmp;
 501         }
 502
 503 again:
 504         retstr = generate_random_str_list(mem_ctx, len, c_list);
 505         if (!retstr) return NULL;
 506
 507         /* we need to make sure the random string passes basic quality tests
 508            or it might be rejected by windows as a password */
 509         if (len >= 7 && !check_password_quality(retstr)) {
 510                 talloc_free(retstr);
 511                 goto again;
 512         }
 513
 514         return retstr;
 515 }
 516
 517 /**
 518  * Generate an array of unique text strings all of the same length.
 519  * The returned string will be allocated.
 520  * Returns NULL if the number of unique combinations cannot be created.
 521  *
 522  * Characters used are: abcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 523  */
 524 _PUBLIC_ char** generate_unique_strs(TALLOC_CTX *mem_ctx, size_t len,
 525                                      uint32_t num)
 526 {
 527         const char *c_list = "abcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 528         const unsigned c_size = 42;
 529         int i, j;
 530         unsigned rem;
 531         char ** strs = NULL;
 532
 533         if (num == 0 || len == 0)
 534                 return NULL;
 535
 536         strs = talloc_array(mem_ctx, char *, num);
 537         if (strs == NULL) return NULL;
 538
 539         for (i = 0; i < num; i++) {
 540                 char *retstr = (char *)talloc_size(strs, len + 1);
 541                 if (retstr == NULL) {
 542                         talloc_free(strs);
 543                         return NULL;
 544                 }
 545                 rem = i;
 546                 for (j = 0; j < len; j++) {
 547                         retstr[j] = c_list[rem % c_size];
 548                         rem = rem / c_size;
 549                 }
 550                 retstr[j] = 0;
 551                 strs[i] = retstr;
 552                 if (rem != 0) {
 553                         /* we were not able to fit the number of
 554                          * combinations asked for in the length
 555                          * specified */
 556                         DEBUG(0,(__location__ ": Too many combinations %u for length %u\n",
 557                                  num, (unsigned)len));
 558
 559                         talloc_free(strs);
 560                         return NULL;
 561                 }
 562         }
 563
 564         return strs;
 565 }