lib/util/genrand_util.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/locale.h"
  24
  25 /**
  26  * @file
  27  * @brief Random number generation
  28  */
  29
  30 /**
  31   generate a single random uint32_t
  32 **/
  33 _PUBLIC_ uint32_t generate_random(void)
  34 {
  35         uint8_t v[4];
  36         generate_random_buffer(v, 4);
  37         return IVAL(v, 0);
  38 }
  39
  40 /**
  41   @brief generate a random uint64
  42 **/
  43 _PUBLIC_ uint64_t generate_random_u64(void)
  44 {
  45         uint8_t v[8];
  46         generate_random_buffer(v, 8);
  47         return BVAL(v, 0);
  48 }
  49
  50 _PUBLIC_ uint64_t generate_unique_u64(uint64_t veto_value)
  51 {
  52         static struct generate_unique_u64_state {
  53                 uint64_t next_value;
  54                 int pid;
  55         } generate_unique_u64_state;
  56
  57         int pid = getpid();
  58
  59         if (unlikely(pid != generate_unique_u64_state.pid)) {
  60                 generate_unique_u64_state = (struct generate_unique_u64_state) {
  61                         .pid = pid,
  62                         .next_value = veto_value,
  63                 };
  64         }
  65
  66         while (unlikely(generate_unique_u64_state.next_value == veto_value)) {
  67                 generate_nonce_buffer(
  68                                 (void *)&generate_unique_u64_state.next_value,
  69                                 sizeof(generate_unique_u64_state.next_value));
  70         }
  71
  72         return generate_unique_u64_state.next_value++;
  73 }
  74
  75 /**
  76   Microsoft composed the following rules (among others) for quality
  77   checks. This is an abridgment from
  78   http://msdn.microsoft.com/en-us/subscriptions/cc786468%28v=ws.10%29.aspx:
  79
  80   Passwords must contain characters from three of the following five
  81   categories:
  82
  83    - Uppercase characters of European languages (A through Z, with
  84      diacritic marks, Greek and Cyrillic characters)
  85    - Lowercase characters of European languages (a through z, sharp-s,
  86      with diacritic marks, Greek and Cyrillic characters)
  87    - Base 10 digits (0 through 9)
  88    - Nonalphanumeric characters: ~!@#$%^&*_-+=`|\(){}[]:;"'<>,.?/
  89    - Any Unicode character that is categorized as an alphabetic character
  90      but is not uppercase or lowercase. This includes Unicode characters
  91      from Asian languages.
  92
  93  Note: for now do not check if the unicode category is
  94        alphabetic character
  95 **/
  96 _PUBLIC_ bool check_password_quality(const char *pwd)
  97 {
  98         size_t ofs = 0;
  99         size_t num_chars = 0;
 100         size_t num_digits = 0;
 101         size_t num_upper = 0;
 102         size_t num_lower = 0;
 103         size_t num_nonalpha = 0;
 104         size_t num_unicode = 0;
 105         size_t num_categories = 0;
 106
 107         if (pwd == NULL) {
 108                 return false;
 109         }
 110
 111         while (true) {
 112                 const char *s = &pwd[ofs];
 113                 size_t len = 0;
 114                 codepoint_t c;
 115
 116                 c = next_codepoint(s, &len);
 117                 if (c == INVALID_CODEPOINT) {
 118                         return false;
 119                 } else if (c == 0) {
 120                         break;
 121                 }
 122                 ofs += len;
 123                 num_chars += 1;
 124
 125                 if (len == 1) {
 126                         const char *na = "~!@#$%^&*_-+=`|\\(){}[]:;\"'<>,.?/";
 127
 128                         if (isdigit(c)) {
 129                                 num_digits += 1;
 130                                 continue;
 131                         }
 132
 133                         if (isupper(c)) {
 134                                 num_upper += 1;
 135                                 continue;
 136                         }
 137
 138                         if (islower(c)) {
 139                                 num_lower += 1;
 140                                 continue;
 141                         }
 142
 143                         if (strchr(na, c)) {
 144                                 num_nonalpha += 1;
 145                                 continue;
 146                         }
 147
 148                         /*
 149                          * the rest does not belong to
 150                          * a category.
 151                          */
 152                         continue;
 153                 }
 154
 155                 if (isupper_m(c)) {
 156                         num_upper += 1;
 157                         continue;
 158                 }
 159
 160                 if (islower_m(c)) {
 161                         num_lower += 1;
 162                         continue;
 163                 }
 164
 165                 /*
 166                  * Note: for now do not check if the unicode category is
 167                  *       alphabetic character
 168                  *
 169                  * We would have to import the details from
 170                  * ftp://ftp.unicode.org/Public/6.3.0/ucd/UnicodeData-6.3.0d1.txt
 171                  */
 172                 num_unicode += 1;
 173                 continue;
 174         }
 175
 176         if (num_digits > 0) {
 177                 num_categories += 1;
 178         }
 179         if (num_upper > 0) {
 180                 num_categories += 1;
 181         }
 182         if (num_lower > 0) {
 183                 num_categories += 1;
 184         }
 185         if (num_nonalpha > 0) {
 186                 num_categories += 1;
 187         }
 188         if (num_unicode > 0) {
 189                 num_categories += 1;
 190         }
 191
 192         if (num_categories >= 3) {
 193                 return true;
 194         }
 195
 196         return false;
 197 }
 198
 199 /**
 200  Use the random number generator to generate a random string.
 201 **/
 202
 203 _PUBLIC_ char *generate_random_str_list(TALLOC_CTX *mem_ctx, size_t len, const char *list)
 204 {
 205         size_t i;
 206         size_t list_len = strlen(list);
 207
 208         char *retstr = talloc_array(mem_ctx, char, len + 1);
 209         if (!retstr) return NULL;
 210
 211         generate_secret_buffer((uint8_t *)retstr, len);
 212         for (i = 0; i < len; i++) {
 213                 retstr[i] = list[retstr[i] % list_len];
 214         }
 215         retstr[i] = '\0';
 216
 217         return retstr;
 218 }
 219
 220 /**
 221  * Generate a random text string consisting of the specified length.
 222  * The returned string will be allocated.
 223  *
 224  * Characters used are: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 225  */
 226
 227 _PUBLIC_ char *generate_random_str(TALLOC_CTX *mem_ctx, size_t len)
 228 {
 229         char *retstr;
 230         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 231
 232 again:
 233         retstr = generate_random_str_list(mem_ctx, len, c_list);
 234         if (!retstr) return NULL;
 235
 236         /* we need to make sure the random string passes basic quality tests
 237            or it might be rejected by windows as a password */
 238         if (len >= 7 && !check_password_quality(retstr)) {
 239                 talloc_free(retstr);
 240                 goto again;
 241         }
 242
 243         return retstr;
 244 }
 245
 246 /**
 247  * Generate a random text password (based on printable ascii characters).
 248  */
 249
 250 _PUBLIC_ char *generate_random_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
 251 {
 252         char *retstr;
 253         /* This list does not include { or } because they cause
 254          * problems for our provision (it can create a substring
 255          * ${...}, and for Fedora DS (which treats {...} at the start
 256          * of a stored password as special
 257          *  -- Andrew Bartlett 2010-03-11
 258          */
 259         const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,@$%&!?:;<=>()[]~";
 260         size_t len = max;
 261         size_t diff;
 262
 263         if (min > max) {
 264                 errno = EINVAL;
 265                 return NULL;
 266         }
 267
 268         diff = max - min;
 269
 270         if (diff > 0 ) {
 271                 size_t tmp;
 272
 273                 generate_secret_buffer((uint8_t *)&tmp, sizeof(tmp));
 274
 275                 tmp %= diff;
 276
 277                 len = min + tmp;
 278         }
 279
 280 again:
 281         retstr = generate_random_str_list(mem_ctx, len, c_list);
 282         if (!retstr) return NULL;
 283
 284         /* we need to make sure the random string passes basic quality tests
 285            or it might be rejected by windows as a password */
 286         if (len >= 7 && !check_password_quality(retstr)) {
 287                 talloc_free(retstr);
 288                 goto again;
 289         }
 290
 291         return retstr;
 292 }
 293
 294 /**
 295  * Generate a random machine password (based on random utf16 characters,
 296  * converted to utf8). min must be at least 14, max must be at most 255.
 297  *
 298  * If 'unix charset' is not utf8, the password consist of random ascii
 299  * values!
 300  */
 301
 302 _PUBLIC_ char *generate_random_machine_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
 303 {
 304         TALLOC_CTX *frame = NULL;
 305         struct generate_random_machine_password_state {
 306                 uint8_t password_buffer[256 * 2];
 307                 uint8_t tmp;
 308         } *state;
 309         char *new_pw = NULL;
 310         size_t len = max;
 311         char *utf8_pw = NULL;
 312         size_t utf8_len = 0;
 313         char *unix_pw = NULL;
 314         size_t unix_len = 0;
 315         size_t diff;
 316         size_t i;
 317         bool ok;
 318         int cmp;
 319
 320         if (max > 255) {
 321                 errno = EINVAL;
 322                 return NULL;
 323         }
 324
 325         if (min < 14) {
 326                 errno = EINVAL;
 327                 return NULL;
 328         }
 329
 330         if (min > max) {
 331                 errno = EINVAL;
 332                 return NULL;
 333         }
 334
 335         frame = talloc_stackframe_pool(2048);
 336         state = talloc_zero(frame, struct generate_random_machine_password_state);
 337
 338         diff = max - min;
 339
 340         if (diff > 0) {
 341                 size_t tmp;
 342
 343                 generate_secret_buffer((uint8_t *)&tmp, sizeof(tmp));
 344
 345                 tmp %= diff;
 346
 347                 len = min + tmp;
 348         }
 349
 350         /*
 351          * Create a random machine account password
 352          * We create a random buffer and convert that to utf8.
 353          * This is similar to what windows is doing.
 354          *
 355          * In future we may store the raw random buffer,
 356          * but for now we need to pass the password as
 357          * char pointer through some layers.
 358          *
 359          * As most kerberos keys are derived from the
 360          * utf8 password we need to fallback to
 361          * ASCII passwords if "unix charset" is not utf8.
 362          */
 363         generate_secret_buffer(state->password_buffer, len * 2);
 364         for (i = 0; i < len; i++) {
 365                 size_t idx = i*2;
 366                 uint16_t c;
 367
 368                 /*
 369                  * both MIT krb5 and HEIMDAL only
 370                  * handle codepoints up to 0xffff.
 371                  *
 372                  * It means we need to avoid
 373                  * 0xD800 - 0xDBFF (high surrogate)
 374                  * and
 375                  * 0xDC00 - 0xDFFF (low surrogate)
 376                  * in the random utf16 data.
 377                  *
 378                  * 55296 0xD800 0154000 0b1101100000000000
 379                  * 57343 0xDFFF 0157777 0b1101111111111111
 380                  * 8192  0x2000  020000   0b10000000000000
 381                  *
 382                  * The above values show that we can check
 383                  * for 0xD800 and just add 0x2000 to avoid
 384                  * the surrogate ranges.
 385                  *
 386                  * The rest will be handled by CH_UTF16MUNGED
 387                  * see utf16_munged_pull().
 388                  */
 389                 c = SVAL(state->password_buffer, idx);
 390                 if (c & 0xD800) {
 391                         c |= 0x2000;
 392                 }
 393                 SSVAL(state->password_buffer, idx, c);
 394         }
 395         ok = convert_string_talloc(frame,
 396                                    CH_UTF16MUNGED, CH_UTF8,
 397                                    state->password_buffer, len * 2,
 398                                    (void *)&utf8_pw, &utf8_len);
 399         if (!ok) {
 400                 DEBUG(0, ("%s: convert_string_talloc() failed\n",
 401                           __func__));
 402                 TALLOC_FREE(frame);
 403                 return NULL;
 404         }
 405
 406         ok = convert_string_talloc(frame,
 407                                    CH_UTF16MUNGED, CH_UNIX,
 408                                    state->password_buffer, len * 2,
 409                                    (void *)&unix_pw, &unix_len);
 410         if (!ok) {
 411                 goto ascii_fallback;
 412         }
 413
 414         if (utf8_len != unix_len) {
 415                 goto ascii_fallback;
 416         }
 417
 418         cmp = memcmp((const uint8_t *)utf8_pw,
 419                      (const uint8_t *)unix_pw,
 420                      utf8_len);
 421         if (cmp != 0) {
 422                 goto ascii_fallback;
 423         }
 424
 425         new_pw = talloc_strdup(mem_ctx, utf8_pw);
 426         if (new_pw == NULL) {
 427                 TALLOC_FREE(frame);
 428                 return NULL;
 429         }
 430         talloc_set_name_const(new_pw, __func__);
 431         TALLOC_FREE(frame);
 432         return new_pw;
 433
 434 ascii_fallback:
 435         for (i = 0; i < len; i++) {
 436                 /*
 437                  * truncate to ascii
 438                  */
 439                 state->tmp = state->password_buffer[i] & 0x7f;
 440                 if (state->tmp == 0) {
 441                         state->tmp = state->password_buffer[i] >> 1;
 442                 }
 443                 if (state->tmp == 0) {
 444                         state->tmp = 0x01;
 445                 }
 446                 state->password_buffer[i] = state->tmp;
 447         }
 448         state->password_buffer[i] = '\0';
 449
 450         new_pw = talloc_strdup(mem_ctx, (const char *)state->password_buffer);
 451         if (new_pw == NULL) {
 452                 TALLOC_FREE(frame);
 453                 return NULL;
 454         }
 455         talloc_set_name_const(new_pw, __func__);
 456         TALLOC_FREE(frame);
 457         return new_pw;
 458 }
 459
 460 /**
 461  * Generate an array of unique text strings all of the same length.
 462  * The returned string will be allocated.
 463  * Returns NULL if the number of unique combinations cannot be created.
 464  *
 465  * Characters used are: abcdefghijklmnopqrstuvwxyz0123456789+_-#.,
 466  */
 467 _PUBLIC_ char** generate_unique_strs(TALLOC_CTX *mem_ctx, size_t len,
 468                                      uint32_t num)
 469 {
 470         const char *c_list = "abcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
 471         const unsigned c_size = 42;
 472         size_t i, j;
 473         unsigned rem;
 474         char ** strs = NULL;
 475
 476         if (num == 0 || len == 0)
 477                 return NULL;
 478
 479         strs = talloc_array(mem_ctx, char *, num);
 480         if (strs == NULL) return NULL;
 481
 482         for (i = 0; i < num; i++) {
 483                 char *retstr = (char *)talloc_size(strs, len + 1);
 484                 if (retstr == NULL) {
 485                         talloc_free(strs);
 486                         return NULL;
 487                 }
 488                 rem = i;
 489                 for (j = 0; j < len; j++) {
 490                         retstr[j] = c_list[rem % c_size];
 491                         rem = rem / c_size;
 492                 }
 493                 retstr[j] = 0;
 494                 strs[i] = retstr;
 495                 if (rem != 0) {
 496                         /* we were not able to fit the number of
 497                          * combinations asked for in the length
 498                          * specified */
 499                         DEBUG(0,(__location__ ": Too many combinations %u for length %u\n",
 500                                  num, (unsigned)len));
 501
 502                         talloc_free(strs);
 503                         return NULL;
 504                 }
 505         }
 506
 507         return strs;
 508 }