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