Remove ntdb from scripts
[Samba.git] / lib / util / genrand.c
blobc0163f4e37de34e821cfcedfec3dfce8f57e6eda
1 /*
2 Unix SMB/CIFS implementation.
4 Functions to create reasonable random numbers for crypto use.
6 Copyright (C) Jeremy Allison 2001
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.
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.
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/>.
22 #include "includes.h"
23 #include "system/filesys.h"
24 #include "../lib/crypto/crypto.h"
25 #include "system/locale.h"
27 /**
28 * @file
29 * @brief Random number generation
32 static unsigned char hash[258];
33 static uint32_t counter;
35 static bool done_reseed = false;
36 static unsigned int bytes_since_reseed = 0;
38 static int urand_fd = -1;
40 static void (*reseed_callback)(void *userdata, int *newseed);
41 static void *reseed_callback_userdata = NULL;
43 /**
44 Copy any user given reseed data.
45 **/
47 _PUBLIC_ void set_rand_reseed_callback(void (*fn)(void *, int *), void *userdata)
49 reseed_callback = fn;
50 reseed_callback_userdata = userdata;
51 set_need_random_reseed();
54 /**
55 * Tell the random number generator it needs to reseed.
57 _PUBLIC_ void set_need_random_reseed(void)
59 done_reseed = false;
60 bytes_since_reseed = 0;
63 static void get_rand_reseed_data(int *reseed_data)
65 if (reseed_callback) {
66 reseed_callback(reseed_callback_userdata, reseed_data);
67 } else {
68 *reseed_data = 0;
72 /****************************************************************
73 Setup the seed.
74 *****************************************************************/
76 static void seed_random_stream(unsigned char *seedval, size_t seedlen)
78 unsigned char j = 0;
79 size_t ind;
81 for (ind = 0; ind < 256; ind++)
82 hash[ind] = (unsigned char)ind;
84 for( ind = 0; ind < 256; ind++) {
85 unsigned char tc;
87 j += (hash[ind] + seedval[ind%seedlen]);
89 tc = hash[ind];
90 hash[ind] = hash[j];
91 hash[j] = tc;
94 hash[256] = 0;
95 hash[257] = 0;
98 /****************************************************************
99 Get datasize bytes worth of random data.
100 *****************************************************************/
102 static void get_random_stream(unsigned char *data, size_t datasize)
104 unsigned char index_i = hash[256];
105 unsigned char index_j = hash[257];
106 size_t ind;
108 for( ind = 0; ind < datasize; ind++) {
109 unsigned char tc;
110 unsigned char t;
112 index_i++;
113 index_j += hash[index_i];
115 tc = hash[index_i];
116 hash[index_i] = hash[index_j];
117 hash[index_j] = tc;
119 t = hash[index_i] + hash[index_j];
120 data[ind] = hash[t];
123 hash[256] = index_i;
124 hash[257] = index_j;
127 /****************************************************************
128 Get a 16 byte hash from the contents of a file.
130 Note that the hash is initialised, because the extra entropy is not
131 worth the valgrind pain.
132 *****************************************************************/
134 static void do_filehash(const char *fname, unsigned char *the_hash)
136 unsigned char buf[1011]; /* deliberate weird size */
137 unsigned char tmp_md4[16];
138 int fd, n;
140 ZERO_STRUCT(tmp_md4);
142 fd = open(fname,O_RDONLY,0);
143 if (fd == -1)
144 return;
146 while ((n = read(fd, (char *)buf, sizeof(buf))) > 0) {
147 mdfour(tmp_md4, buf, n);
148 for (n=0;n<16;n++)
149 the_hash[n] ^= tmp_md4[n];
151 close(fd);
154 /**************************************************************
155 Try and get a good random number seed. Try a number of
156 different factors. Firstly, try /dev/urandom - use if exists.
158 We use /dev/urandom as a read of /dev/random can block if
159 the entropy pool dries up. This leads clients to timeout
160 or be very slow on connect.
162 If we can't use /dev/urandom then seed the stream random generator
163 above...
164 **************************************************************/
166 static int do_reseed(int fd)
168 unsigned char seed_inbuf[40];
169 uint32_t v1, v2; struct timeval tval; pid_t mypid;
170 int reseed_data = 0;
172 if (fd == -1) {
173 fd = open( "/dev/urandom", O_RDONLY,0);
174 if (fd != -1) {
175 smb_set_close_on_exec(fd);
178 if (fd != -1
179 && (read(fd, seed_inbuf, sizeof(seed_inbuf)) == sizeof(seed_inbuf))) {
180 seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
181 return fd;
184 /* Add in some secret file contents */
186 do_filehash("/etc/shadow", &seed_inbuf[0]);
189 * Add the counter, time of day, and pid.
192 GetTimeOfDay(&tval);
193 mypid = getpid();
194 v1 = (counter++) + mypid + tval.tv_sec;
195 v2 = (counter++) * mypid + tval.tv_usec;
197 SIVAL(seed_inbuf, 32, v1 ^ IVAL(seed_inbuf, 32));
198 SIVAL(seed_inbuf, 36, v2 ^ IVAL(seed_inbuf, 36));
201 * Add any user-given reseed data.
204 get_rand_reseed_data(&reseed_data);
205 if (reseed_data) {
206 size_t i;
207 for (i = 0; i < sizeof(seed_inbuf); i++)
208 seed_inbuf[i] ^= ((char *)(&reseed_data))[i % sizeof(reseed_data)];
211 seed_random_stream(seed_inbuf, sizeof(seed_inbuf));
213 return -1;
217 Interface to the (hopefully) good crypto random number generator.
218 Will use our internal PRNG if more than 40 bytes of random generation
219 has been requested, otherwise tries to read from /dev/random
221 _PUBLIC_ void generate_random_buffer(uint8_t *out, int len)
223 unsigned char md4_buf[64];
224 unsigned char tmp_buf[16];
225 unsigned char *p;
227 if(!done_reseed) {
228 bytes_since_reseed += len;
230 /* Magic constant to try and avoid reading 40 bytes
231 * and setting up the PRNG if the app only ever wants
232 * a few bytes */
233 if (bytes_since_reseed < 40) {
234 if (urand_fd == -1) {
235 urand_fd = open( "/dev/urandom", O_RDONLY,0);
236 if (urand_fd != -1) {
237 smb_set_close_on_exec(urand_fd);
240 if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
241 return;
245 urand_fd = do_reseed(urand_fd);
246 done_reseed = true;
250 * Generate random numbers in chunks of 64 bytes,
251 * then md4 them & copy to the output buffer.
252 * This way the raw state of the stream is never externally
253 * seen.
256 p = out;
257 while(len > 0) {
258 int copy_len = len > 16 ? 16 : len;
260 get_random_stream(md4_buf, sizeof(md4_buf));
261 mdfour(tmp_buf, md4_buf, sizeof(md4_buf));
262 memcpy(p, tmp_buf, copy_len);
263 p += copy_len;
264 len -= copy_len;
269 Interface to the (hopefully) good crypto random number generator.
270 Will always use /dev/urandom if available.
272 _PUBLIC_ void generate_secret_buffer(uint8_t *out, int len)
274 if (urand_fd == -1) {
275 urand_fd = open( "/dev/urandom", O_RDONLY,0);
276 if (urand_fd != -1) {
277 smb_set_close_on_exec(urand_fd);
280 if(urand_fd != -1 && (read(urand_fd, out, len) == len)) {
281 return;
284 generate_random_buffer(out, len);
288 generate a single random uint32_t
290 _PUBLIC_ uint32_t generate_random(void)
292 uint8_t v[4];
293 generate_random_buffer(v, 4);
294 return IVAL(v, 0);
299 Microsoft composed the following rules (among others) for quality
300 checks. This is an abridgment from
301 http://msdn.microsoft.com/en-us/subscriptions/cc786468%28v=ws.10%29.aspx:
303 Passwords must contain characters from three of the following five
304 categories:
306 - Uppercase characters of European languages (A through Z, with
307 diacritic marks, Greek and Cyrillic characters)
308 - Lowercase characters of European languages (a through z, sharp-s,
309 with diacritic marks, Greek and Cyrillic characters)
310 - Base 10 digits (0 through 9)
311 - Nonalphanumeric characters: ~!@#$%^&*_-+=`|\(){}[]:;"'<>,.?/
312 - Any Unicode character that is categorized as an alphabetic character
313 but is not uppercase or lowercase. This includes Unicode characters
314 from Asian languages.
316 Note: for now do not check if the unicode category is
317 alphabetic character
319 _PUBLIC_ bool check_password_quality(const char *pwd)
321 size_t ofs = 0;
322 size_t num_chars = 0;
323 size_t num_digits = 0;
324 size_t num_upper = 0;
325 size_t num_lower = 0;
326 size_t num_nonalpha = 0;
327 size_t num_unicode = 0;
328 size_t num_categories = 0;
330 if (pwd == NULL) {
331 return false;
334 while (true) {
335 const char *s = &pwd[ofs];
336 size_t len = 0;
337 codepoint_t c;
339 c = next_codepoint(s, &len);
340 if (c == INVALID_CODEPOINT) {
341 return false;
342 } else if (c == 0) {
343 break;
345 ofs += len;
346 num_chars += 1;
348 if (len == 1) {
349 const char *na = "~!@#$%^&*_-+=`|\\(){}[]:;\"'<>,.?/";
351 if (isdigit(c)) {
352 num_digits += 1;
353 continue;
356 if (isupper(c)) {
357 num_upper += 1;
358 continue;
361 if (islower(c)) {
362 num_lower += 1;
363 continue;
366 if (strchr(na, c)) {
367 num_nonalpha += 1;
368 continue;
372 * the rest does not belong to
373 * a category.
375 continue;
378 if (isupper_m(c)) {
379 num_upper += 1;
380 continue;
383 if (islower_m(c)) {
384 num_lower += 1;
385 continue;
389 * Note: for now do not check if the unicode category is
390 * alphabetic character
392 * We would have to import the details from
393 * ftp://ftp.unicode.org/Public/6.3.0/ucd/UnicodeData-6.3.0d1.txt
395 num_unicode += 1;
396 continue;
399 if (num_digits > 0) {
400 num_categories += 1;
402 if (num_upper > 0) {
403 num_categories += 1;
405 if (num_lower > 0) {
406 num_categories += 1;
408 if (num_nonalpha > 0) {
409 num_categories += 1;
411 if (num_unicode > 0) {
412 num_categories += 1;
415 if (num_categories >= 3) {
416 return true;
419 return false;
423 Use the random number generator to generate a random string.
426 _PUBLIC_ char *generate_random_str_list(TALLOC_CTX *mem_ctx, size_t len, const char *list)
428 size_t i;
429 size_t list_len = strlen(list);
431 char *retstr = talloc_array(mem_ctx, char, len + 1);
432 if (!retstr) return NULL;
434 generate_random_buffer((uint8_t *)retstr, len);
435 for (i = 0; i < len; i++) {
436 retstr[i] = list[retstr[i] % list_len];
438 retstr[i] = '\0';
440 return retstr;
444 * Generate a random text string consisting of the specified length.
445 * The returned string will be allocated.
447 * Characters used are: ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,
450 _PUBLIC_ char *generate_random_str(TALLOC_CTX *mem_ctx, size_t len)
452 char *retstr;
453 const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
455 again:
456 retstr = generate_random_str_list(mem_ctx, len, c_list);
457 if (!retstr) return NULL;
459 /* we need to make sure the random string passes basic quality tests
460 or it might be rejected by windows as a password */
461 if (len >= 7 && !check_password_quality(retstr)) {
462 talloc_free(retstr);
463 goto again;
466 return retstr;
470 * Generate a random text password.
473 _PUBLIC_ char *generate_random_password(TALLOC_CTX *mem_ctx, size_t min, size_t max)
475 char *retstr;
476 /* This list does not include { or } because they cause
477 * problems for our provision (it can create a substring
478 * ${...}, and for Fedora DS (which treats {...} at the start
479 * of a stored password as special
480 * -- Andrew Bartlett 2010-03-11
482 const char *c_list = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+_-#.,@$%&!?:;<=>()[]~";
483 size_t len = max;
484 size_t diff;
486 if (min > max) {
487 errno = EINVAL;
488 return NULL;
491 diff = max - min;
493 if (diff > 0 ) {
494 size_t tmp;
496 generate_random_buffer((uint8_t *)&tmp, sizeof(tmp));
498 tmp %= diff;
500 len = min + tmp;
503 again:
504 retstr = generate_random_str_list(mem_ctx, len, c_list);
505 if (!retstr) return NULL;
507 /* we need to make sure the random string passes basic quality tests
508 or it might be rejected by windows as a password */
509 if (len >= 7 && !check_password_quality(retstr)) {
510 talloc_free(retstr);
511 goto again;
514 return retstr;
518 * Generate an array of unique text strings all of the same length.
519 * The returned string will be allocated.
520 * Returns NULL if the number of unique combinations cannot be created.
522 * Characters used are: abcdefghijklmnopqrstuvwxyz0123456789+_-#.,
524 _PUBLIC_ char** generate_unique_strs(TALLOC_CTX *mem_ctx, size_t len,
525 uint32_t num)
527 const char *c_list = "abcdefghijklmnopqrstuvwxyz0123456789+_-#.,";
528 const unsigned c_size = 42;
529 size_t i, j;
530 unsigned rem;
531 char ** strs = NULL;
533 if (num == 0 || len == 0)
534 return NULL;
536 strs = talloc_array(mem_ctx, char *, num);
537 if (strs == NULL) return NULL;
539 for (i = 0; i < num; i++) {
540 char *retstr = (char *)talloc_size(strs, len + 1);
541 if (retstr == NULL) {
542 talloc_free(strs);
543 return NULL;
545 rem = i;
546 for (j = 0; j < len; j++) {
547 retstr[j] = c_list[rem % c_size];
548 rem = rem / c_size;
550 retstr[j] = 0;
551 strs[i] = retstr;
552 if (rem != 0) {
553 /* we were not able to fit the number of
554 * combinations asked for in the length
555 * specified */
556 DEBUG(0,(__location__ ": Too many combinations %u for length %u\n",
557 num, (unsigned)len));
559 talloc_free(strs);
560 return NULL;
564 return strs;