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