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