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 237036 : _PUBLIC_ uint32_t generate_random(void)
37 : {
38 : uint8_t v[4];
39 237036 : generate_random_buffer(v, 4);
40 237036 : return IVAL(v, 0);
41 : }
42 :
43 : /**
44 : @brief generate a random uint64
45 : **/
46 71065 : _PUBLIC_ uint64_t generate_random_u64(void)
47 : {
48 : uint8_t v[8];
49 71065 : generate_random_buffer(v, 8);
50 71065 : 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 11 : _PUBLIC_ uint64_t generate_random_u64_range(uint64_t lower, uint64_t upper)
63 : {
64 11 : return generate_random_u64() % (upper - lower) + lower;
65 : }
66 :
67 132916 : _PUBLIC_ uint64_t generate_unique_u64(uint64_t veto_value)
68 : {
69 : static struct generate_unique_u64_state {
70 : uint64_t next_value;
71 : int pid;
72 : } generate_unique_u64_state;
73 :
74 132916 : int pid = tevent_cached_getpid();
75 :
76 132916 : if (unlikely(pid != generate_unique_u64_state.pid)) {
77 1193 : generate_unique_u64_state = (struct generate_unique_u64_state) {
78 : .pid = pid,
79 : .next_value = veto_value,
80 : };
81 : }
82 :
83 252100 : while (unlikely(generate_unique_u64_state.next_value == veto_value)) {
84 1193 : generate_nonce_buffer(
85 : (void *)&generate_unique_u64_state.next_value,
86 : sizeof(generate_unique_u64_state.next_value));
87 : }
88 :
89 132916 : 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 14435 : _PUBLIC_ bool check_password_quality(const char *pwd)
114 : {
115 14435 : size_t ofs = 0;
116 14435 : size_t num_digits = 0;
117 14435 : size_t num_upper = 0;
118 14435 : size_t num_lower = 0;
119 14435 : size_t num_nonalpha = 0;
120 14435 : size_t num_unicode = 0;
121 14435 : size_t num_categories = 0;
122 :
123 14435 : if (pwd == NULL) {
124 0 : return false;
125 : }
126 :
127 253487 : while (true) {
128 267922 : const char *s = &pwd[ofs];
129 267922 : size_t len = 0;
130 : codepoint_t c;
131 :
132 267922 : c = next_codepoint(s, &len);
133 267922 : if (c == INVALID_CODEPOINT) {
134 0 : return false;
135 267922 : } else if (c == 0) {
136 14435 : break;
137 : }
138 253487 : ofs += len;
139 :
140 253487 : if (len == 1) {
141 253486 : const char *na = "~!@#$%^&*_-+=`|\\(){}[]:;\"'<>,.?/";
142 :
143 253486 : if (isdigit(c)) {
144 44538 : num_digits += 1;
145 285038 : continue;
146 : }
147 :
148 208948 : if (isupper(c)) {
149 61508 : num_upper += 1;
150 61508 : continue;
151 : }
152 :
153 147440 : if (islower(c)) {
154 100367 : num_lower += 1;
155 100367 : continue;
156 : }
157 :
158 47073 : if (strchr(na, c)) {
159 47001 : num_nonalpha += 1;
160 47001 : continue;
161 : }
162 :
163 : /*
164 : * the rest does not belong to
165 : * a category.
166 : */
167 72 : continue;
168 : }
169 :
170 1 : if (isupper_m(c)) {
171 0 : num_upper += 1;
172 0 : continue;
173 : }
174 :
175 1 : if (islower_m(c)) {
176 1 : num_lower += 1;
177 1 : 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 0 : num_unicode += 1;
188 0 : continue;
189 : }
190 :
191 14435 : if (num_digits > 0) {
192 13668 : num_categories += 1;
193 : }
194 14435 : if (num_upper > 0) {
195 5414 : num_categories += 1;
196 : }
197 14435 : if (num_lower > 0) {
198 14374 : num_categories += 1;
199 : }
200 14435 : if (num_nonalpha > 0) {
201 12734 : num_categories += 1;
202 : }
203 14435 : if (num_unicode > 0) {
204 0 : num_categories += 1;
205 : }
206 :
207 14435 : if (num_categories >= 3) {
208 14325 : return true;
209 : }
210 :
211 110 : return false;
212 : }
213 :
214 : /**
215 : Use the random number generator to generate a random string.
216 : **/
217 :
218 3484 : _PUBLIC_ char *generate_random_str_list(TALLOC_CTX *mem_ctx, size_t len, const char *list)
219 : {
220 : size_t i;
221 3484 : size_t list_len = strlen(list);
222 :
223 3484 : char *retstr = talloc_array(mem_ctx, char, len + 1);
224 3484 : if (!retstr) return NULL;
225 :
226 3484 : generate_secret_buffer((uint8_t *)retstr, len);
227 135919 : for (i = 0; i < len; i++) {
228 132435 : retstr[i] = list[retstr[i] % list_len];
229 : }
230 3484 : retstr[i] = '\0';
231 :
232 3484 : 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 226 : _PUBLIC_ char *generate_random_str(TALLOC_CTX *mem_ctx, size_t len)
243 : {
244 : char *retstr;
245 226 : const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
246 :
247 256 : again:
248 256 : retstr = generate_random_str_list(mem_ctx, len, c_list);
249 256 : 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 256 : if (len >= 7 && !check_password_quality(retstr)) {
254 30 : talloc_free(retstr);
255 30 : goto again;
256 : }
257 :
258 226 : return retstr;
259 : }
260 :
261 : /**
262 : * Generate a random text password (based on printable ascii characters).
263 : */
264 :
265 2491 : _PUBLIC_ char *generate_random_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
266 : {
267 : 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 2491 : const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,@$%&!?:;<=>()[]~";
275 2491 : size_t len = max;
276 : size_t diff;
277 :
278 2491 : if (min > max) {
279 0 : errno = EINVAL;
280 0 : return NULL;
281 : }
282 :
283 2491 : diff = max - min;
284 :
285 2491 : if (diff > 0 ) {
286 : size_t tmp;
287 :
288 1712 : generate_secret_buffer((uint8_t *)&tmp, sizeof(tmp));
289 :
290 1712 : tmp %= diff;
291 :
292 1712 : len = min + tmp;
293 : }
294 :
295 3148 : again:
296 2518 : retstr = generate_random_str_list(mem_ctx, len, c_list);
297 2518 : 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 2518 : if (len >= 7 && !check_password_quality(retstr)) {
302 27 : talloc_free(retstr);
303 27 : goto again;
304 : }
305 :
306 2491 : 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 :
317 379 : _PUBLIC_ char *generate_random_machine_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
318 : {
319 379 : TALLOC_CTX *frame = NULL;
320 : struct generate_random_machine_password_state {
321 : uint8_t password_buffer[256 * 2];
322 : uint8_t tmp;
323 : } *state;
324 379 : char *new_pw = NULL;
325 379 : size_t len = max;
326 379 : char *utf8_pw = NULL;
327 379 : size_t utf8_len = 0;
328 379 : char *unix_pw = NULL;
329 379 : size_t unix_len = 0;
330 : size_t diff;
331 : size_t i;
332 : bool ok;
333 : int cmp;
334 :
335 379 : if (max > 255) {
336 0 : errno = EINVAL;
337 0 : return NULL;
338 : }
339 :
340 379 : if (min < 14) {
341 0 : errno = EINVAL;
342 0 : return NULL;
343 : }
344 :
345 379 : if (min > max) {
346 0 : errno = EINVAL;
347 0 : return NULL;
348 : }
349 :
350 379 : frame = talloc_stackframe_pool(2048);
351 379 : state = talloc_zero(frame, struct generate_random_machine_password_state);
352 :
353 379 : diff = max - min;
354 :
355 379 : if (diff > 0) {
356 : size_t tmp;
357 :
358 88 : generate_secret_buffer((uint8_t *)&tmp, sizeof(tmp));
359 :
360 88 : tmp %= diff;
361 :
362 88 : len = min + tmp;
363 : }
364 :
365 : /*
366 : * Create a random machine account password
367 : * We create a random buffer and convert that to utf8.
368 : * This is similar to what windows is doing.
369 : *
370 : * In future we may store the raw random buffer,
371 : * but for now we need to pass the password as
372 : * char pointer through some layers.
373 : *
374 : * As most kerberos keys are derived from the
375 : * utf8 password we need to fallback to
376 : * ASCII passwords if "unix charset" is not utf8.
377 : */
378 379 : generate_secret_buffer(state->password_buffer, len * 2);
379 51561 : for (i = 0; i < len; i++) {
380 51182 : size_t idx = i*2;
381 : uint16_t c;
382 :
383 : /*
384 : * both MIT krb5 and HEIMDAL only
385 : * handle codepoints up to 0xffff.
386 : *
387 : * It means we need to avoid
388 : * 0xD800 - 0xDBFF (high surrogate)
389 : * and
390 : * 0xDC00 - 0xDFFF (low surrogate)
391 : * in the random utf16 data.
392 : *
393 : * 55296 0xD800 0154000 0b1101100000000000
394 : * 57343 0xDFFF 0157777 0b1101111111111111
395 : * 8192 0x2000 020000 0b10000000000000
396 : *
397 : * The above values show that we can check
398 : * for 0xD800 and just add 0x2000 to avoid
399 : * the surrogate ranges.
400 : *
401 : * The rest will be handled by CH_UTF16MUNGED
402 : * see utf16_munged_pull().
403 : */
404 51182 : c = SVAL(state->password_buffer, idx);
405 51182 : if (c & 0xD800) {
406 47983 : c |= 0x2000;
407 : }
408 51182 : SSVAL(state->password_buffer, idx, c);
409 : }
410 688 : ok = convert_string_talloc(frame,
411 : CH_UTF16MUNGED, CH_UTF8,
412 379 : state->password_buffer, len * 2,
413 : (void *)&utf8_pw, &utf8_len);
414 379 : if (!ok) {
415 0 : DEBUG(0, ("%s: convert_string_talloc() failed\n",
416 : __func__));
417 0 : TALLOC_FREE(frame);
418 0 : return NULL;
419 : }
420 :
421 688 : ok = convert_string_talloc(frame,
422 : CH_UTF16MUNGED, CH_UNIX,
423 379 : state->password_buffer, len * 2,
424 : (void *)&unix_pw, &unix_len);
425 379 : if (!ok) {
426 0 : goto ascii_fallback;
427 : }
428 :
429 379 : if (utf8_len != unix_len) {
430 0 : goto ascii_fallback;
431 : }
432 :
433 379 : cmp = memcmp((const uint8_t *)utf8_pw,
434 : (const uint8_t *)unix_pw,
435 : utf8_len);
436 379 : if (cmp != 0) {
437 0 : goto ascii_fallback;
438 : }
439 :
440 379 : new_pw = talloc_strdup(mem_ctx, utf8_pw);
441 379 : if (new_pw == NULL) {
442 0 : TALLOC_FREE(frame);
443 0 : return NULL;
444 : }
445 379 : talloc_set_name_const(new_pw, __func__);
446 379 : TALLOC_FREE(frame);
447 379 : return new_pw;
448 :
449 0 : ascii_fallback:
450 0 : for (i = 0; i < len; i++) {
451 : /*
452 : * truncate to ascii
453 : */
454 0 : state->tmp = state->password_buffer[i] & 0x7f;
455 0 : if (state->tmp == 0) {
456 0 : state->tmp = state->password_buffer[i] >> 1;
457 : }
458 0 : if (state->tmp == 0) {
459 0 : state->tmp = 0x01;
460 : }
461 0 : state->password_buffer[i] = state->tmp;
462 : }
463 0 : state->password_buffer[i] = '\0';
464 :
465 0 : new_pw = talloc_strdup(mem_ctx, (const char *)state->password_buffer);
466 0 : if (new_pw == NULL) {
467 0 : TALLOC_FREE(frame);
468 0 : return NULL;
469 : }
470 0 : talloc_set_name_const(new_pw, __func__);
471 0 : TALLOC_FREE(frame);
472 0 : return new_pw;
473 : }
474 :
475 : /**
476 : * Generate an array of unique text strings all of the same length.
477 : * The returned string will be allocated.
478 : * Returns NULL if the number of unique combinations cannot be created.
479 : *
480 : * Characters used are: abcdefghijklmnopqrstuvwxyz0123456789+_-#.,
481 : */
482 0 : _PUBLIC_ char** generate_unique_strs(TALLOC_CTX *mem_ctx, size_t len,
483 : uint32_t num)
484 : {
485 0 : const char *c_list = "abcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
486 0 : const unsigned c_size = 42;
487 : size_t i, j;
488 : unsigned rem;
489 0 : char ** strs = NULL;
490 :
491 0 : if (num == 0 || len == 0)
492 0 : return NULL;
493 :
494 0 : strs = talloc_array(mem_ctx, char *, num);
495 0 : if (strs == NULL) return NULL;
496 :
497 0 : for (i = 0; i < num; i++) {
498 0 : char *retstr = (char *)talloc_size(strs, len + 1);
499 0 : if (retstr == NULL) {
500 0 : talloc_free(strs);
501 0 : return NULL;
502 : }
503 0 : rem = i;
504 0 : for (j = 0; j < len; j++) {
505 0 : retstr[j] = c_list[rem % c_size];
506 0 : rem = rem / c_size;
507 : }
508 0 : retstr[j] = 0;
509 0 : strs[i] = retstr;
510 0 : if (rem != 0) {
511 : /* we were not able to fit the number of
512 : * combinations asked for in the length
513 : * specified */
514 0 : DEBUG(0,(__location__ ": Too many combinations %u for length %u\n",
515 : num, (unsigned)len));
516 :
517 0 : talloc_free(strs);
518 0 : return NULL;
519 : }
520 : }
521 :
522 0 : return strs;
523 : }
|
