2 static const char rcsid[] = "$Header: /proj/cvs/prod/DHCP/dst/prandom.c,v 1.1 2001/02/22 07:22:09 mellon Exp $";
5 * Portions Copyright (c) 1995-1998 by Trusted Information Systems, Inc.
7 * Permission to use, copy modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
11 * THE SOFTWARE IS PROVIDED "AS IS" AND TRUSTED INFORMATION SYSTEMS
12 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
13 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
14 * TRUSTED INFORMATION SYSTEMS BE LIABLE FOR ANY SPECIAL, DIRECT,
15 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
16 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
17 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
18 * WITH THE USE OR PERFORMANCE OF THE SOFTWARE.
22 #include <sys/types.h>
29 #include <sys/param.h>
33 #include <netinet/in.h>
34 #include <sys/socket.h>
35 #define NEED_PRAND_CONF
36 #include "minires/minires.h"
37 #include "dst_internal.h"
38 #include "arpa/nameser.h"
41 #ifndef DST_NUM_HASHES
42 #define DST_NUM_HASHES 4
44 #ifndef DST_NUMBER_OF_COUNTERS
45 #define DST_NUMBER_OF_COUNTERS 5 /* 32 * 5 == 160 == SHA(1) > MD5 */
49 * the constant below is a prime number to make fixed data structues like
50 * stat and time wrap over blocks. This adds certain uncertanty to what is
51 * in each digested block.
52 * The prime number 2879 has the special property that when
53 * divided by 2,4 and 6 the result is also a prime numbers
56 #ifndef DST_RANDOM_BLOCK_SIZE
57 #define DST_RANDOM_BLOCK_SIZE 2879
61 * This constant dictatates how many bits we shift to the right before using a
68 * An initalizer that is as bad as any other with half the bits set
70 #ifndef DST_RANDOM_PATTERN
71 #define DST_RANDOM_PATTERN 0x8765CA93
74 * things must have changed in the last 3600 seconds to be used
80 * these two data structure are used to process input data into digests,
82 * The first structure is containts a pointer to a DST HMAC key
83 * the variables accompanying are used for
84 * step : select every step byte from input data for the hash
85 * block: number of data elements going into each hash
86 * digested: number of data elements digested so far
87 * curr: offset into the next input data for the first byte.
92 int digested, block, step, curr;
96 * This data structure controlls number of hashes and keeps track of
97 * overall progress in generating correct number of bytes of output.
98 * output : array to store the output data in
99 * needed : how many bytes of output are needed
100 * filled : number of bytes in output so far.
101 * bytes : total number of bytes processed by this structure
102 * file_digest : the HMAC key used to digest files.
104 typedef struct work {
105 unsigned needed, filled, bytes;
107 prand_hash *hash[DST_NUM_HASHES];
108 DST_KEY *file_digest;
113 * forward function declarations
115 static int get_dev_random(u_char *output, unsigned size);
116 static int do_time(dst_work *work);
117 static int do_ls(dst_work *work);
118 static int unix_cmd(dst_work *work);
119 static int digest_file(dst_work *work);
121 static void force_hash(dst_work *work, prand_hash *hash);
122 static int do_hash(dst_work *work, prand_hash *hash, const u_char *input,
124 static int my_digest(dst_work *tmp, const u_char *input, unsigned size);
125 static prand_hash *get_hmac_key(int step, int block);
127 static unsigned own_random(dst_work *work);
131 * variables used in the quick random number generator
133 static u_int32_t ran_val = DST_RANDOM_PATTERN;
134 static u_int32_t ran_cnt = (DST_RANDOM_PATTERN >> 10);
137 * setting the quick_random generator to particular values or if both
138 * input parameters are 0 then set it to initial vlaues
142 dst_s_quick_random_set(u_int32_t val, u_int32_t cnt)
144 ran_val = (val == 0) ? DST_RANDOM_PATTERN : val;
145 ran_cnt = (cnt == 0) ? (DST_RANDOM_PATTERN >> 10) : cnt;
149 * this is a quick and random number generator that seems to generate quite
150 * good distribution of data
153 dst_s_quick_random(int inc)
155 ran_val = ((ran_val >> 13) ^ (ran_val << 19)) ^
156 ((ran_val >> 7) ^ (ran_val << 25));
157 if (inc > 0) /* only increasing values accepted */
159 ran_val += ran_cnt++;
164 * get_dev_random: Function to read /dev/random reliably
165 * this function returns how many bytes where read from the device.
166 * port_after.h should set the control variable HAVE_DEV_RANDOM
169 get_dev_random(u_char *output, unsigned size)
171 #ifdef HAVE_DEV_RANDOM
173 int n = 0, fd = -1, s;
175 s = stat("/dev/random", &st);
176 if (s == 0 && S_ISCHR(st.st_mode)) {
177 if ((fd = open("/dev/random", O_RDONLY | O_NONBLOCK)) != -1) {
178 if ((n = read(fd, output, size)) < 0)
189 * Portable way of getting the time values if gettimeofday is missing
190 * then compile with -DMISSING_GETTIMEOFDAY time() is POSIX compliant but
191 * gettimeofday() is not.
192 * Time of day is predictable, we are looking for the randomness that comes
193 * the last few bits in the microseconds in the timer are hard to predict when
194 * this is invoked at the end of other operations
196 struct timeval *mtime;
198 do_time(dst_work *work)
201 static u_char tmp[sizeof(struct timeval) + sizeof(struct timezone)];
202 struct timezone *zone;
204 zone = (struct timezone *) tmp;
205 mtime = (struct timeval *)(tmp + sizeof(struct timezone));
206 gettimeofday(mtime, zone);
208 my_digest(work, tmp, sizeof(tmp));
214 * this function simulates the ls command, but it uses stat which gives more
215 * information and is harder to guess
216 * Each call to this function will visit the next directory on the list of
217 * directories, in a circular manner.
218 * return value is the number of bytes added to the temp buffer
220 * do_ls() does not visit subdirectories
221 * if attacker has access to machine it can guess most of the values seen
222 * thus it is important to only visit directories that are freqently updated
223 * Attacker that has access to the network can see network traffic
224 * when NFS mounted directories are accessed and know exactly the data used
225 * but may not know exactly in what order data is used.
226 * Returns the number of bytes that where returned in stat structures
229 do_ls(dst_work *work)
235 time_t atime, mtime, ctime;
237 static struct dir_info dir_info;
239 struct dirent *entry;
241 static unsigned long d_round = 0;
243 int n = 0, tb_i = 0, out = 0;
246 char file_name[1024];
247 u_char tmp_buff[1024];
250 if (dirs[i] == NULL) /* if at the end of the list start over */
252 if (stat(dirs[i++], &buf)) /* directory does not exist */
255 gettimeofday(&tv,NULL);
257 d_round = tv.tv_sec - MAX_OLD;
258 else if (i==1) /* if starting a new round cut what we accept */
259 d_round += (tv.tv_sec - d_round)/2;
261 if (buf.st_atime < d_round)
264 EREPORT(("do_ls i %d filled %4d in_temp %4d\n",
265 i-1, work->filled, work->in_temp));
266 memcpy(tmp_buff, &buf, sizeof(buf));
270 if ((dir = opendir(dirs[i-1])) == NULL)/* open it for read */
272 strcpy(file_name, dirs[i-1]);
273 dir_len = strlen(file_name);
274 file_name[dir_len++] = '/';
275 while ((entry = readdir(dir))) {
276 unsigned len = strlen(entry->d_name);
278 if (my_digest(work, (u_char *)entry->d_name, len))
281 memcpy(&file_name[dir_len], entry->d_name, len);
282 file_name[dir_len + len] = 0x0;
283 /* for all entries in dir get the stats */
284 if (stat(file_name, &buf) == 0) {
285 n++; /* count successfull stat calls */
286 /* copy non static fields */
287 dir_info.uid += buf.st_uid;
288 dir_info.gid += buf.st_gid;
289 dir_info.size += buf.st_size;
290 dir_info.atime += buf.st_atime;
291 dir_info.mtime += buf.st_mtime;
292 dir_info.ctime += buf.st_ctime;
293 out += sizeof(dir_info);
294 if(my_digest(work, (u_char *)&dir_info,
299 closedir(dir); /* done */
300 out += do_time(work); /* add a time stamp */
307 * this function executes the a command from the cmds[] list of unix commands
308 * configured in the prand_conf.h file
309 * return value is the number of bytes added to the randomness temp buffer
311 * it returns the number of bytes that where read in
312 * if more data is needed at the end time is added to the data.
313 * This function maintains a state to selects the next command to run
314 * returns the number of bytes read in from the command
317 unix_cmd(dst_work *work)
319 static int cmd_index = 0;
324 if (cmds[cmd_index] == NULL)
326 EREPORT(("unix_cmd() i %d filled %4d in_temp %4d\n",
327 cmd_index, work->filled, work->in_temp));
328 pipe = popen(cmds[cmd_index++], "r"); /* execute the command */
330 while ((n = fread(buffer, sizeof(char), sizeof(buffer), pipe)) > 0) {
331 cnt += n; /* process the output */
332 if (my_digest(work, buffer, (unsigned)n))
334 /* this adds some randomness to the output */
335 cnt += do_time(work);
337 while ((n = fread(buffer, sizeof(char), sizeof(buffer), pipe)) > 0)
338 NULL; /* drain the pipe */
340 return (cnt); /* read how many bytes where read in */
344 * digest_file() This function will read a file and run hash over it
345 * input is a file name
348 digest_file(dst_work *work)
350 static int f_cnt = 0;
351 static unsigned long f_round = 0;
360 if (f_round == 0 || files[f_cnt] == NULL || work->file_digest == NULL)
361 if (gettimeofday(&tv, NULL)) /* only do this if needed */
363 if (f_round == 0) /* first time called set to one hour ago */
364 f_round = (tv.tv_sec - MAX_OLD);
365 name = files[f_cnt++];
366 if (files[f_cnt] == NULL) { /* end of list of files */
367 if(f_cnt <= 1) /* list is too short */
369 f_cnt = 0; /* start again on list */
370 f_round += (tv.tv_sec - f_round)/2; /* set new cutoff */
371 work->file_digest = dst_free_key(work->file_digest);
373 if (work->file_digest == NULL) {
374 work->file_digest = dst_buffer_to_key("", KEY_HMAC_MD5, 0, 0,
375 (u_char *)&tv, sizeof(tv));
376 if (work->file_digest == NULL)
379 if (access(name, R_OK) || stat(name, &st))
380 return (0); /* no such file or not allowed to read it */
381 if (strncmp(name, "/proc/", 6) && st.st_mtime < f_round)
382 return(0); /* file has not changed recently enough */
383 if (dst_sign_data(SIG_MODE_INIT, work->file_digest, &ctx,
385 work->file_digest = dst_free_key(work->file_digest);
388 if ((fp = fopen(name, "r")) == NULL)
390 for (no = 0; (i = fread(buf, sizeof(*buf), sizeof(buf), fp)) > 0;
392 dst_sign_data(SIG_MODE_UPDATE, work->file_digest, &ctx,
393 buf, (unsigned)i, NULL, 0);
397 i = dst_sign_data(SIG_MODE_FINAL, work->file_digest, &ctx,
398 NULL, 0, &work->output[work->filled],
404 my_digest(work, buf, (unsigned)i);
405 my_digest(work, (const u_char *)name, strlen(name));
406 return (no + strlen(name));
410 * function to perform the FINAL and INIT operation on a hash if allowed
413 force_hash(dst_work *work, prand_hash *hash)
418 * if more than half a block then add data to output
419 * otherwise adde the digest to the next hash
421 if ((hash->digested * 2) > hash->block) {
422 i = dst_sign_data(SIG_MODE_FINAL, hash->key, &hash->ctx,
423 NULL, 0, &work->output[work->filled],
427 dst_sign_data(SIG_MODE_INIT, hash->key, &hash->ctx,
436 * This function takes the input data does the selection of data specified
437 * by the hash control block.
438 * The step varialbe in the work sturcture determines which 1/step bytes
443 do_hash(dst_work *work, prand_hash *hash, const u_char *input, unsigned size)
445 const u_char *tmp = input;
446 u_char *tp, *abuf = (u_char *)0;
448 unsigned needed, avail, dig, cnt = size;
449 unsigned tmp_size = 0;
451 if (cnt <= 0 || input == NULL)
454 if (hash->step > 1) { /* if using subset of input data */
455 tmp_size = size / hash->step + 2;
456 abuf = tp = malloc(tmp_size);
458 for (cnt = 0, i = hash->curr; i < size; i += hash->step, cnt++)
460 /* calcutate the starting point in the next input set */
461 hash->curr = (hash->step - (i - size)) % hash->step;
463 /* digest the data in block sizes */
464 for (n = 0; n < cnt; n += needed) {
466 needed = hash->block - hash->digested;
467 dig = (avail < needed) ? avail : needed;
468 dst_sign_data(SIG_MODE_UPDATE, hash->key, &hash->ctx,
469 &tmp[n], dig, NULL, 0);
470 hash->digested += dig;
471 if (hash->digested >= hash->block)
472 force_hash(work, hash);
473 if (work->needed < work->filled) {
475 SAFE_FREE2(abuf, tmp_size);
480 SAFE_FREE2(abuf, tmp_size);
485 * Copy data from INPUT for length SIZE into the work-block TMP.
486 * If we fill the work-block, digest it; then,
487 * if work-block needs more data, keep filling with the rest of the input.
490 my_digest(dst_work *work, const u_char *input, unsigned size)
494 static unsigned counter;
497 /* first do each one of the hashes */
498 for (i = 0; i < DST_NUM_HASHES && full == 0; i++)
499 full = do_hash(work, work->hash[i], input, size) +
500 do_hash(work, work->hash[i], (u_char *) &counter,
503 * if enough data has be generated do final operation on all hashes
504 * that have enough date for that
506 for (i = 0; full && (i < DST_NUM_HASHES); i++)
507 force_hash(work, work->hash[i]);
513 * this function gets some semi random data and sets that as an HMAC key
514 * If we get a valid key this function returns that key initalized
515 * otherwise it returns NULL;
518 get_hmac_key(int step, int block)
524 DST_KEY *new_key = NULL;
525 prand_hash *new = NULL;
527 /* use key that is larger than digest algorithms (64) for key size */
531 /* do not memset the allocated memory to get random bytes there */
532 /* time of day is somewhat random expecialy in the last bytes */
533 gettimeofday((struct timeval *) &buff[n], NULL);
534 n += sizeof(struct timeval);
536 /* get some semi random stuff in here stir it with micro seconds */
538 temp = dst_s_quick_random((int) buff[n - 1]);
539 memcpy(&buff[n], &temp, sizeof(temp));
542 /* get the pid of this process and its parent */
544 temp = (int) getpid();
545 memcpy(&buff[n], &temp, sizeof(temp));
549 temp = (int) getppid();
550 memcpy(&buff[n], &temp, sizeof(temp));
553 /* get the user ID */
555 temp = (int) getuid();
556 memcpy(&buff[n], &temp, sizeof(temp));
559 #ifndef GET_HOST_ID_MISSING
561 temp = (int) gethostid();
562 memcpy(&buff[n], &temp, sizeof(temp));
566 /* get some more random data */
568 temp = dst_s_quick_random((int) buff[n - 1]);
569 memcpy(&buff[n], &temp, sizeof(temp));
572 /* covert this into a HMAC key */
573 new_key = dst_buffer_to_key("", KEY_HMAC_MD5, 0, 0, buff, size);
576 /* get the control structure */
577 if ((new = malloc(sizeof(prand_hash))) == NULL)
579 new->digested = new->curr = 0;
583 if (dst_sign_data(SIG_MODE_INIT, new_key, &new->ctx, NULL, 0, NULL, 0))
591 * This function goes out and from various sources tries to generate enough
592 * semi random data that a hash function can generate a random data.
593 * This function will iterate between the two main random source sources,
594 * information from programs and directores in random order.
595 * This function return the number of bytes added to the random output buffer.
598 own_random(dst_work *work)
601 int bytes, n, cmd = 0, dig = 0;
604 * now get the initial seed to put into the quick random function from
605 * the address of the work structure
607 bytes = (int) getpid();
609 * proceed while needed
611 while (work->filled < work->needed) {
612 EREPORT(("own_random r %08x b %6d t %6d f %6d\n",
613 ran_val, bytes, work->in_temp, work->filled));
614 /* pick a random number in the range of 0..7 based on that random number
615 * perform some operations that yield random data
617 start = work->filled;
618 n = (dst_s_quick_random(bytes) >> DST_SHIFT) & 0x07;
622 if (sizeof(cmds) > 2 *sizeof(*cmds)) {
630 if (sizeof(dirs) > 2 *sizeof(*dirs)) {
638 /* retry getting data from /dev/random */
639 b = get_dev_random(&work->output[work->filled],
640 work->needed - work->filled);
646 if (sizeof(files) > 2 * sizeof(*files)) {
647 b = digest_file(work);
653 default: /* to make sure we make some progress */
654 work->output[work->filled++] = 0xff &
655 dst_s_quick_random(bytes);
662 return (work->filled);
667 * dst_s_random() This function will return the requested number of bytes
668 * of randomness to the caller it will use the best available sources of
670 * The current order is to use /dev/random, precalculated randomness, and
671 * finaly use some system calls and programs to generate semi random data that
672 * is then digested to generate randomness.
673 * This function is thread safe as each thread uses its own context, but
674 * concurrent treads will affect each other as they update shared state
676 * It is strongly recommended that this function be called requesting a size
677 * that is not a multiple of the output of the hash function used.
679 * If /dev/random is not available this function is not suitable to generate
680 * large ammounts of data, rather it is suitable to seed a pseudo-random
682 * Returns the number of bytes put in the output buffer
685 dst_s_random(u_char *output, unsigned size)
689 static u_char old_unused[DST_HASH_SIZE * DST_NUM_HASHES];
690 static unsigned unused = 0;
692 if (size <= 0 || output == NULL)
698 * Read from /dev/random
700 n = get_dev_random(output, size);
702 * If old data is available and needed use it
704 if (n < size && unused > 0) {
705 unsigned need = size - n;
706 if (unused <= need) {
707 memcpy(output, old_unused, unused);
711 memcpy(output, old_unused, need);
714 memcpy(old_unused, &old_unused[need], unused);
718 * If we need more use the simulated randomness here.
721 dst_work *my_work = (dst_work *) malloc(sizeof(dst_work));
724 my_work->needed = size - n;
726 my_work->output = (u_char *) malloc(my_work->needed +
729 my_work->file_digest = NULL;
730 if (my_work->output == NULL)
732 memset(my_work->output, 0x0, my_work->needed);
733 /* allocate upto 4 different HMAC hash functions out of order */
734 #if DST_NUM_HASHES >= 3
735 my_work->hash[2] = get_hmac_key(3, DST_RANDOM_BLOCK_SIZE / 2);
737 #if DST_NUM_HASHES >= 2
738 my_work->hash[1] = get_hmac_key(7, DST_RANDOM_BLOCK_SIZE / 6);
740 #if DST_NUM_HASHES >= 4
741 my_work->hash[3] = get_hmac_key(5, DST_RANDOM_BLOCK_SIZE / 4);
743 my_work->hash[0] = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE);
744 if (my_work->hash[0] == NULL) /* if failure bail out */
746 s = own_random(my_work);
747 /* if more generated than needed store it for future use */
748 if (s >= my_work->needed) {
749 EREPORT(("dst_s_random(): More than needed %d >= %d\n",
750 s, my_work->needed));
751 memcpy(&output[n], my_work->output, my_work->needed);
752 n += my_work->needed;
753 /* saving unused data for next time */
754 unused = s - my_work->needed;
755 memcpy(old_unused, &my_work->output[my_work->needed],
758 /* XXXX This should not happen */
759 EREPORT(("Not enough %d >= %d\n", s, my_work->needed));
760 memcpy(&output[n], my_work->output, s);
761 n += my_work->needed;
764 /* delete the allocated work area */
765 for (i = 0; i < DST_NUM_HASHES; i++) {
766 dst_free_key(my_work->hash[i]->key);
767 SAFE_FREE(my_work->hash[i]);
769 SAFE_FREE(my_work->output);
776 * A random number generator that is fast and strong
777 * this random number generator is based on HASHing data,
778 * the input to the digest function is a collection of <NUMBER_OF_COUNTERS>
779 * counters that is incremented between digest operations
780 * each increment operation amortizes to 2 bits changed in that value
781 * for 5 counters thus the input will amortize to have 10 bits changed
782 * The counters are initaly set using the strong random function above
783 * the HMAC key is selected by the same methold as the HMAC keys for the
784 * strong random function.
785 * Each set of counters is used for 2^25 operations
787 * returns the number of bytes written to the output buffer
788 * or negative number in case of error
791 dst_s_semi_random(u_char *output, unsigned size)
793 static u_int32_t counter[DST_NUMBER_OF_COUNTERS];
794 static u_char semi_old[DST_HASH_SIZE];
795 static int semi_loc = 0, cnt = 0;
796 static unsigned hb_size = 0;
797 static DST_KEY *my_key = NULL;
803 if (output == NULL || size <= 0)
806 /* check if we need a new key */
807 if (my_key == NULL || cnt > (1 << 25)) { /* get HMAC KEY */
809 my_key->dk_func->destroy(my_key);
810 if ((hash = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE)) == NULL)
813 /* check if the key works stir the new key using some old random data */
814 hb_size = dst_sign_data(SIG_MODE_ALL, my_key, NULL,
815 (u_char *) counter, sizeof(counter),
816 semi_old, sizeof(semi_old));
818 EREPORT(("dst_s_semi_random() Sign of alg %d failed %d\n",
819 my_key->dk_alg, hb_size));
822 /* new set the counters to random values */
823 dst_s_random((u_char *) counter, sizeof(counter));
826 /* if old data around use it first */
827 if (semi_loc < hb_size) {
828 if (size <= hb_size - semi_loc) { /* need less */
829 memcpy(output, &semi_old[semi_loc], size);
831 return (size); /* DONE */
833 out = hb_size - semi_loc;
834 memcpy(output, &semi_old[semi_loc], out);
838 /* generate more randome stuff */
841 * modify at least one bit by incrementing at least one counter
842 * based on the last bit of the last counter updated update
844 * minimaly this operation will modify at least 1 bit,
847 for (n = 0; n < DST_NUMBER_OF_COUNTERS; n++)
848 i = (int) counter[n]++;
850 i = dst_sign_data(SIG_MODE_ALL, my_key, NULL,
851 (u_char *) counter, hb_size,
852 semi_old, sizeof(semi_old));
854 EREPORT(("HMAC SIGNATURE FAILURE %d\n", i));
856 if (size - out < i) /* Not all data is needed */
857 semi_loc = i = size - out;
858 memcpy(&output[out], semi_old, i);