1 /* $NetBSD: prandom.c,v 1.1.1.4 2014/07/12 11:57:50 spz Exp $ */ 2 #ifndef LINT 3 static const char rcsid[] = "Header: /tmp/cvstest/DHCP/dst/prandom.c,v 1.10 2012/03/09 11:18:13 tomasz Exp "; 4 #endif 5 /* 6 * Portions Copyright (c) 2012,2013 by Internet Systems Consortium, Inc. ("ISC") 7 * Portions Copyright (c) 2007,2009 by Internet Systems Consortium, Inc. ("ISC") 8 * Portions Copyright (c) 1995-1998 by Trusted Information Systems, Inc. 9 * 10 * Permission to use, copy modify, and distribute this software for any 11 * purpose with or without fee is hereby granted, provided that the above 12 * copyright notice and this permission notice appear in all copies. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS" AND TRUSTED INFORMATION SYSTEMS 15 * DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL 17 * TRUSTED INFORMATION SYSTEMS BE LIABLE FOR ANY SPECIAL, DIRECT, 18 * INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING 19 * FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, 20 * NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION 21 * WITH THE USE OR PERFORMANCE OF THE SOFTWARE. 22 */ 23 24 #include <sys/cdefs.h> 25 __RCSID("$NetBSD: prandom.c,v 1.1.1.4 2014/07/12 11:57:50 spz Exp $"); 26 27 #include <stdio.h> 28 #include <sys/types.h> 29 #include <stdlib.h> 30 #include <string.h> 31 #include <unistd.h> 32 #include <fcntl.h> 33 #include <time.h> 34 #include <dirent.h> 35 #include <sys/param.h> 36 #include <sys/stat.h> 37 #include <sys/time.h> 38 39 #include <netinet/in.h> 40 #include <sys/socket.h> 41 #define NEED_PRAND_CONF 42 43 #include "cdefs.h" 44 #include "osdep.h" 45 #include "dst_internal.h" 46 #include "arpa/nameser.h" 47 48 49 #ifndef DST_NUM_HASHES 50 #define DST_NUM_HASHES 4 51 #endif 52 #ifndef DST_NUMBER_OF_COUNTERS 53 #define DST_NUMBER_OF_COUNTERS 5 /* 32 * 5 == 160 == SHA(1) > MD5 */ 54 #endif 55 56 /* 57 * the constant below is a prime number to make fixed data structures like 58 * stat and time wrap over blocks. This adds certain randomness to what is 59 * in each digested block. 60 * The prime number 2879 has the special property that when 61 * divided by 2,4 and 6 the result is also a prime numbers 62 */ 63 64 #ifndef DST_RANDOM_BLOCK_SIZE 65 #define DST_RANDOM_BLOCK_SIZE 2879 66 #endif 67 68 /* 69 * This constant dictates how many bits we shift to the right before using a 70 */ 71 #ifndef DST_SHIFT 72 #define DST_SHIFT 9 73 #endif 74 75 /* 76 * An initializer that is as bad as any other with half the bits set 77 */ 78 #ifndef DST_RANDOM_PATTERN 79 #define DST_RANDOM_PATTERN 0x8765CA93 80 #endif 81 /* 82 * things must have changed in the last 3600 seconds to be used 83 */ 84 #define MAX_OLD 3600 85 86 /* 87 * Define a single set of configuration for prand stuff. A superset 88 * works okay (failed commands return no data, missing directories 89 * are skipped, and so on. 90 */ 91 static const char *cmds[] = { 92 "/usr/bin/netstat -an 2>&1", 93 "/usr/sbin/netstat -an 2>&1", 94 "/usr/etc/netstat -an 2>&1", 95 "/bin/netstat -an 2>&1", 96 "/usr/ucb/netstat -an 2>&1", 97 98 /* AIX */ 99 "/bin/ps -ef 2>&1", 100 "/bin/df 2>&1", 101 "/usr/bin/uptime 2>&1", 102 "/usr/bin/printenv 2>&1", 103 "/usr/bin/netstat -s 2>&1", 104 "/usr/bin/w 2>&1", 105 /* Tru64 */ 106 "/usr/bin/dig com. soa +ti=1 +retry=0 2>&1", 107 "/usr/sbin/arp -an 2>&1", 108 "/usr/ucb/uptime 2>&1", 109 "/bin/iostat 2>&1", 110 /* BSD */ 111 "/bin/ps -axlw 2>&1", 112 "/usr/sbin/iostat 2>&1", 113 "/usr/sbin/vmstat 2>&1", 114 /* FreeBSD */ 115 "/usr/bin/vmstat 2>&1", 116 "/usr/bin/w 2>&1", 117 /* HP/UX */ 118 "/usr/bin/ps -ef 2>&1", 119 /* IRIX */ 120 "/usr/etc/arp -a 2>&1", 121 "/usr/bsd/uptime 2>&1", 122 "/usr/bin/printenv 2>&1", 123 "/usr/bsd/w 2>&1", 124 /* Linux */ 125 "/sbin/arp -an 2>&1", 126 "/usr/bin/vmstat 2>&1", 127 /* NetBSD */ 128 /* OpenBSD */ 129 /* QNX */ 130 "/bin/ps -a 2>&1", 131 "/bin/sin 2>&1", 132 "/bin/sin fds 2>&1", 133 "/bin/sin memory 2>&1", 134 /* Solaris */ 135 "/usr/ucb/uptime 2>&1", 136 "/usr/ucb/netstat -an 2>&1", 137 138 "/usr/bin/netstat -an 2>&1", 139 "/usr/sbin/netstat -an 2>&1", 140 "/usr/etc/netstat -an 2>&1", 141 "/bin/netstat -an 2>&1", 142 "/usr/ucb/netstat -an 2>&1", 143 NULL 144 }; 145 146 static const char *dirs[] = { 147 "/tmp", 148 "/var/tmp", 149 ".", 150 "/", 151 "/var/spool", 152 "/var/adm", 153 "/dev", 154 "/var/spool/mail", 155 "/var/mail", 156 "/home", 157 "/usr/home", 158 NULL 159 }; 160 161 static const char *files[] = { 162 "/var/adm/messages", 163 "/var/adm/wtmp", 164 "/var/adm/lastlog", 165 "/var/log/messages", 166 "/var/log/wtmp", 167 "/var/log/lastlog", 168 "/proc/stat", 169 "/proc/rtc", 170 "/proc/meminfo", 171 "/proc/interrupts", 172 "/proc/self/status", 173 "/proc/ipstats", 174 "/proc/dumper", 175 "/proc/self/as", 176 NULL 177 }; 178 179 /* 180 * these two data structure are used to process input data into digests, 181 * 182 * The first structure contains a pointer to a DST HMAC key 183 * the variables accompanying are used for 184 * step : select every step byte from input data for the hash 185 * block: number of data elements going into each hash 186 * digested: number of data elements digested so far 187 * curr: offset into the next input data for the first byte. 188 */ 189 typedef struct hash { 190 DST_KEY *key; 191 void *ctx; 192 int digested, block, step, curr; 193 } prand_hash; 194 195 /* 196 * This data structure controls number of hashes and keeps track of 197 * overall progress in generating correct number of bytes of output. 198 * output : array to store the output data in 199 * needed : how many bytes of output are needed 200 * filled : number of bytes in output so far. 201 * bytes : total number of bytes processed by this structure 202 * file_digest : the HMAC key used to digest files. 203 */ 204 typedef struct work { 205 unsigned needed, filled, bytes; 206 u_char *output; 207 prand_hash *hash[DST_NUM_HASHES]; 208 DST_KEY *file_digest; 209 } dst_work; 210 211 212 /* 213 * forward function declarations 214 */ 215 static int get_dev_random(u_char *output, unsigned size); 216 static int do_time(dst_work *work); 217 static int do_ls(dst_work *work); 218 static int unix_cmd(dst_work *work); 219 static int digest_file(dst_work *work); 220 221 static void force_hash(dst_work *work, prand_hash *hash); 222 static int do_hash(dst_work *work, prand_hash *hash, const u_char *input, 223 unsigned size); 224 static int my_digest(dst_work *tmp, const u_char *input, unsigned size); 225 static prand_hash *get_hmac_key(int step, int block); 226 227 static unsigned own_random(dst_work *work); 228 229 230 /* 231 * variables used in the quick random number generator 232 */ 233 static u_int32_t ran_val = DST_RANDOM_PATTERN; 234 static u_int32_t ran_cnt = (DST_RANDOM_PATTERN >> 10); 235 236 /* 237 * setting the quick_random generator to particular values or if both 238 * input parameters are 0 then set it to initial values 239 */ 240 241 void 242 dst_s_quick_random_set(u_int32_t val, u_int32_t cnt) 243 { 244 ran_val = (val == 0) ? DST_RANDOM_PATTERN : val; 245 ran_cnt = (cnt == 0) ? (DST_RANDOM_PATTERN >> 10) : cnt; 246 } 247 248 /* 249 * this is a quick and random number generator that seems to generate quite 250 * good distribution of data 251 */ 252 u_int32_t 253 dst_s_quick_random(int inc) 254 { 255 ran_val = ((ran_val >> 13) ^ (ran_val << 19)) ^ 256 ((ran_val >> 7) ^ (ran_val << 25)); 257 if (inc > 0) /* only increasing values accepted */ 258 ran_cnt += inc; 259 ran_val += ran_cnt++; 260 return (ran_val); 261 } 262 263 /* 264 * get_dev_random: Function to read /dev/random reliably 265 * this function returns how many bytes where read from the device. 266 * port_after.h should set the control variable HAVE_DEV_RANDOM 267 */ 268 static int 269 get_dev_random(u_char *output, unsigned size) 270 { 271 #ifdef HAVE_DEV_RANDOM 272 struct stat st; 273 int n = 0, fd = -1, s; 274 275 s = stat("/dev/random", &st); 276 if (s == 0 && S_ISCHR(st.st_mode)) { 277 if ((fd = open("/dev/random", O_RDONLY | O_NONBLOCK)) != -1) { 278 if ((n = read(fd, output, size)) < 0) 279 n = 0; 280 close(fd); 281 } 282 return (n); 283 } 284 #endif 285 return (0); 286 } 287 288 /* 289 * Portable way of getting the time values if gettimeofday is missing 290 * then compile with -DMISSING_GETTIMEOFDAY time() is POSIX compliant but 291 * gettimeofday() is not. 292 * Time of day is predictable, we are looking for the randomness that comes 293 * the last few bits in the microseconds in the timer are hard to predict when 294 * this is invoked at the end of other operations 295 */ 296 struct timeval *mtime; 297 static int 298 do_time(dst_work *work) 299 { 300 int cnt = 0; 301 static u_char tmp[sizeof(struct timeval) + sizeof(struct timezone)]; 302 struct timezone *zone; 303 304 zone = (struct timezone *) tmp; 305 mtime = (struct timeval *)(tmp + sizeof(struct timezone)); 306 gettimeofday(mtime, zone); 307 cnt = sizeof(tmp); 308 my_digest(work, tmp, sizeof(tmp)); 309 310 return (cnt); 311 } 312 313 /* 314 * this function simulates the ls command, but it uses stat which gives more 315 * information and is harder to guess 316 * Each call to this function will visit the next directory on the list of 317 * directories, in a circular manner. 318 * return value is the number of bytes added to the temp buffer 319 * 320 * do_ls() does not visit subdirectories 321 * if attacker has access to machine it can guess most of the values seen 322 * thus it is important to only visit directories that are frequently updated 323 * Attacker that has access to the network can see network traffic 324 * when NFS mounted directories are accessed and know exactly the data used 325 * but may not know exactly in what order data is used. 326 * Returns the number of bytes that where returned in stat structures 327 */ 328 static int 329 do_ls(dst_work *work) 330 { 331 struct dir_info { 332 uid_t uid; 333 gid_t gid; 334 off_t size; 335 time_t atime, mtime, ctime; 336 }; 337 static struct dir_info dir_info; 338 struct stat buf; 339 struct dirent *entry; 340 static int i = 0; 341 static unsigned long d_round = 0; 342 struct timeval tv; 343 int n = 0, out = 0; 344 unsigned dir_len; 345 346 char file_name[1024]; 347 u_char tmp_buff[1024]; 348 DIR *dir = NULL; 349 350 if (dirs[i] == NULL) /* if at the end of the list start over */ 351 i = 0; 352 if (stat(dirs[i++], &buf)) /* directory does not exist */ 353 return (0); 354 355 gettimeofday(&tv,NULL); 356 if (d_round == 0) 357 d_round = tv.tv_sec - MAX_OLD; 358 else if (i==1) /* if starting a new round cut what we accept */ 359 d_round += (tv.tv_sec - d_round)/2; 360 361 if (buf.st_atime < d_round) 362 return (0); 363 364 EREPORT(("do_ls i %d filled %4d in_temp %4d\n", 365 i-1, work->filled, work->in_temp)); 366 memcpy(tmp_buff, &buf, sizeof(buf)); 367 368 369 if ((dir = opendir(dirs[i-1])) == NULL)/* open it for read */ 370 return (0); 371 strcpy(file_name, dirs[i-1]); 372 dir_len = strlen(file_name); 373 file_name[dir_len++] = '/'; 374 while ((entry = readdir(dir))) { 375 unsigned len = strlen(entry->d_name); 376 out += len; 377 if (my_digest(work, (u_char *)entry->d_name, len)) 378 break; 379 380 memcpy(&file_name[dir_len], entry->d_name, len); 381 file_name[dir_len + len] = 0x0; 382 /* for all entries in dir get the stats */ 383 if (stat(file_name, &buf) == 0) { 384 n++; /* count successful stat calls */ 385 /* copy non static fields */ 386 dir_info.uid += buf.st_uid; 387 dir_info.gid += buf.st_gid; 388 dir_info.size += buf.st_size; 389 dir_info.atime += buf.st_atime; 390 dir_info.mtime += buf.st_mtime; 391 dir_info.ctime += buf.st_ctime; 392 out += sizeof(dir_info); 393 if(my_digest(work, (u_char *)&dir_info, 394 sizeof(dir_info))) 395 break; 396 } 397 } 398 closedir(dir); /* done */ 399 out += do_time(work); /* add a time stamp */ 400 return (out); 401 } 402 403 404 /* 405 * unix_cmd() 406 * this function executes the a command from the cmds[] list of unix commands 407 * configured in the prand_conf.h file 408 * return value is the number of bytes added to the randomness temp buffer 409 * 410 * it returns the number of bytes that where read in 411 * if more data is needed at the end time is added to the data. 412 * This function maintains a state to selects the next command to run 413 * returns the number of bytes read in from the command 414 */ 415 static int 416 unix_cmd(dst_work *work) 417 { 418 static int cmd_index = 0; 419 int cnt = 0, n; 420 FILE *pipe; 421 u_char buffer[4096]; 422 423 if (cmds[cmd_index] == NULL) 424 cmd_index = 0; 425 EREPORT(("unix_cmd() i %d filled %4d in_temp %4d\n", 426 cmd_index, work->filled, work->in_temp)); 427 pipe = popen(cmds[cmd_index++], "r"); /* execute the command */ 428 429 while ((n = fread(buffer, sizeof(char), sizeof(buffer), pipe)) > 0) { 430 cnt += n; /* process the output */ 431 if (my_digest(work, buffer, (unsigned)n)) 432 break; 433 /* this adds some randomness to the output */ 434 cnt += do_time(work); 435 } 436 while ((n = fread(buffer, sizeof(char), sizeof(buffer), pipe)) > 0) 437 ; /* drain the pipe */ 438 pclose(pipe); 439 return (cnt); /* read how many bytes where read in */ 440 } 441 442 /* 443 * digest_file() This function will read a file and run hash over it 444 * input is a file name 445 */ 446 static int 447 digest_file(dst_work *work) 448 { 449 static int f_cnt = 0; 450 static unsigned long f_round = 0; 451 FILE *fp; 452 void *ctx; 453 const char *name; 454 int no, i; 455 struct stat st; 456 struct timeval tv; 457 u_char buf[1024]; 458 459 name = files[f_cnt++]; 460 if (f_round == 0 || files[f_cnt] == NULL || work->file_digest == NULL) 461 if (gettimeofday(&tv, NULL)) /* only do this if needed */ 462 return (0); 463 if (f_round == 0) /* first time called set to one hour ago */ 464 f_round = (tv.tv_sec - MAX_OLD); 465 if (files[f_cnt] == NULL) { /* end of list of files */ 466 if(f_cnt <= 1) /* list is too short */ 467 return (0); 468 f_cnt = 0; /* start again on list */ 469 f_round += (tv.tv_sec - f_round)/2; /* set new cutoff */ 470 work->file_digest = dst_free_key(work->file_digest); 471 } 472 if (work->file_digest == NULL) { 473 work->file_digest = dst_buffer_to_key("", KEY_HMAC_MD5, 0, 0, 474 (u_char *)&tv, sizeof(tv)); 475 if (work->file_digest == NULL) 476 return (0); 477 } 478 if (access(name, R_OK) || stat(name, &st)) 479 return (0); /* no such file or not allowed to read it */ 480 if (strncmp(name, "/proc/", 6) && st.st_mtime < f_round) 481 return(0); /* file has not changed recently enough */ 482 if (dst_sign_data(SIG_MODE_INIT, work->file_digest, &ctx, 483 NULL, 0, NULL, 0)) { 484 work->file_digest = dst_free_key(work->file_digest); 485 return (0); 486 } 487 if ((fp = fopen(name, "r")) == NULL) 488 return (0); 489 for (no = 0; (i = fread(buf, sizeof(*buf), sizeof(buf), fp)) > 0; 490 no += i) 491 dst_sign_data(SIG_MODE_UPDATE, work->file_digest, &ctx, 492 buf, (unsigned)i, NULL, 0); 493 494 fclose(fp); 495 if (no >= 64) { 496 i = dst_sign_data(SIG_MODE_FINAL, work->file_digest, &ctx, 497 NULL, 0, &work->output[work->filled], 498 DST_HASH_SIZE); 499 if (i > 0) 500 work->filled += i; 501 } 502 else if (i > 0) 503 my_digest(work, buf, (unsigned)i); 504 my_digest(work, (const u_char *)name, strlen(name)); 505 return (no + strlen(name)); 506 } 507 508 /* 509 * function to perform the FINAL and INIT operation on a hash if allowed 510 */ 511 static void 512 force_hash(dst_work *work, prand_hash *hash) 513 { 514 int i = 0; 515 516 /* 517 * if more than half a block then add data to output 518 * otherwise add the digest to the next hash 519 */ 520 if ((hash->digested * 2) > hash->block) { 521 i = dst_sign_data(SIG_MODE_FINAL, hash->key, &hash->ctx, 522 NULL, 0, &work->output[work->filled], 523 DST_HASH_SIZE); 524 525 hash->digested = 0; 526 dst_sign_data(SIG_MODE_INIT, hash->key, &hash->ctx, 527 NULL, 0, NULL, 0); 528 if (i > 0) 529 work->filled += i; 530 } 531 return; 532 } 533 534 /* 535 * This function takes the input data does the selection of data specified 536 * by the hash control block. 537 * The step variable in the work structure determines which 1/step bytes 538 * are used, 539 * 540 */ 541 static int 542 do_hash(dst_work *work, prand_hash *hash, const u_char *input, unsigned size) 543 { 544 const u_char *tmp = input; 545 u_char *tp, *abuf = (u_char *)0; 546 int i, n; 547 unsigned needed, avail, dig, cnt = size; 548 unsigned tmp_size = 0; 549 550 if (cnt <= 0 || input == NULL) 551 return (0); 552 553 if (hash->step > 1) { /* if using subset of input data */ 554 tmp_size = size / hash->step + 2; 555 abuf = tp = malloc(tmp_size); 556 tmp = tp; 557 for (cnt = 0, i = hash->curr; i < size; i += hash->step, cnt++) 558 *(tp++) = input[i]; 559 /* calculate the starting point in the next input set */ 560 hash->curr = (hash->step - (i - size)) % hash->step; 561 } 562 /* digest the data in block sizes */ 563 for (n = 0; n < cnt; n += needed) { 564 avail = (cnt - n); 565 needed = hash->block - hash->digested; 566 dig = (avail < needed) ? avail : needed; 567 dst_sign_data(SIG_MODE_UPDATE, hash->key, &hash->ctx, 568 &tmp[n], dig, NULL, 0); 569 hash->digested += dig; 570 if (hash->digested >= hash->block) 571 force_hash(work, hash); 572 if (work->needed < work->filled) { 573 if (abuf) 574 SAFE_FREE2(abuf, tmp_size); 575 return (1); 576 } 577 } 578 if (tmp_size > 0) 579 SAFE_FREE2(abuf, tmp_size); 580 return (0); 581 } 582 583 /* 584 * Copy data from INPUT for length SIZE into the work-block TMP. 585 * If we fill the work-block, digest it; then, 586 * if work-block needs more data, keep filling with the rest of the input. 587 */ 588 static int 589 my_digest(dst_work *work, const u_char *input, unsigned size) 590 { 591 592 int i, full = 0; 593 static unsigned counter; 594 595 counter += size; 596 /* first do each one of the hashes */ 597 for (i = 0; i < DST_NUM_HASHES && full == 0; i++) 598 full = do_hash(work, work->hash[i], input, size) + 599 do_hash(work, work->hash[i], (u_char *) &counter, 600 sizeof(counter)); 601 /* 602 * if enough data has be generated do final operation on all hashes 603 * that have enough date for that 604 */ 605 for (i = 0; full && (i < DST_NUM_HASHES); i++) 606 force_hash(work, work->hash[i]); 607 608 return (full); 609 } 610 611 /* 612 * this function gets some semi random data and sets that as an HMAC key 613 * If we get a valid key this function returns that key initialized 614 * otherwise it returns NULL; 615 */ 616 static prand_hash * 617 get_hmac_key(int step, int block) 618 { 619 620 u_char *buff; 621 int temp = 0, n = 0; 622 unsigned size = 70; 623 DST_KEY *new_key = NULL; 624 prand_hash *new = NULL; 625 626 /* use key that is larger than digest algorithms (64) for key size */ 627 buff = malloc(size); 628 if (buff == NULL) 629 return (NULL); 630 /* do not memset the allocated memory to get random bytes there */ 631 /* time of day is somewhat random especially in the last bytes */ 632 gettimeofday((struct timeval *) &buff[n], NULL); 633 n += sizeof(struct timeval); 634 635 /* get some semi random stuff in here stir it with micro seconds */ 636 if (n < size) { 637 temp = dst_s_quick_random((int) buff[n - 1]); 638 memcpy(&buff[n], &temp, sizeof(temp)); 639 n += sizeof(temp); 640 } 641 /* get the pid of this process and its parent */ 642 if (n < size) { 643 temp = (int) getpid(); 644 memcpy(&buff[n], &temp, sizeof(temp)); 645 n += sizeof(temp); 646 } 647 if (n < size) { 648 temp = (int) getppid(); 649 memcpy(&buff[n], &temp, sizeof(temp)); 650 n += sizeof(temp); 651 } 652 /* get the user ID */ 653 if (n < size) { 654 temp = (int) getuid(); 655 memcpy(&buff[n], &temp, sizeof(temp)); 656 n += sizeof(temp); 657 } 658 #ifndef GET_HOST_ID_MISSING 659 if (n < size) { 660 temp = (int) gethostid(); 661 memcpy(&buff[n], &temp, sizeof(temp)); 662 n += sizeof(temp); 663 } 664 #endif 665 /* get some more random data */ 666 if (n < size) { 667 temp = dst_s_quick_random((int) buff[n - 1]); 668 memcpy(&buff[n], &temp, sizeof(temp)); 669 } 670 /* covert this into a HMAC key */ 671 new_key = dst_buffer_to_key("", KEY_HMAC_MD5, 0, 0, buff, size); 672 SAFE_FREE(buff); 673 674 /* get the control structure */ 675 if ((new = malloc(sizeof(prand_hash))) == NULL) 676 return (NULL); 677 new->digested = new->curr = 0; 678 new->step = step; 679 new->block = block; 680 new->key = new_key; 681 if (dst_sign_data(SIG_MODE_INIT, new_key, &new->ctx, NULL, 0, NULL, 0)) { 682 SAFE_FREE(new); 683 return (NULL); 684 } 685 686 return (new); 687 } 688 689 /* 690 * own_random() 691 * This function goes out and from various sources tries to generate enough 692 * semi random data that a hash function can generate a random data. 693 * This function will iterate between the two main random source sources, 694 * information from programs and directories in random order. 695 * This function return the number of bytes added to the random output buffer. 696 */ 697 static unsigned 698 own_random(dst_work *work) 699 { 700 int dir = 0, b; 701 int bytes, n, cmd = 0, dig = 0; 702 /* 703 * now get the initial seed to put into the quick random function from 704 * the address of the work structure 705 */ 706 bytes = (int) getpid(); 707 /* 708 * proceed while needed 709 */ 710 while (work->filled < work->needed) { 711 EREPORT(("own_random r %08x b %6d t %6d f %6d\n", 712 ran_val, bytes, work->in_temp, work->filled)); 713 /* pick a random number in the range of 0..7 based on that random number 714 * perform some operations that yield random data 715 */ 716 n = (dst_s_quick_random(bytes) >> DST_SHIFT) & 0x07; 717 switch (n) { 718 case 0: 719 case 3: 720 if (sizeof(cmds) > 2 *sizeof(*cmds)) { 721 b = unix_cmd(work); 722 cmd += b; 723 } 724 break; 725 726 case 1: 727 case 7: 728 if (sizeof(dirs) > 2 *sizeof(*dirs)) { 729 b = do_ls(work); 730 dir += b; 731 } 732 break; 733 734 case 4: 735 case 5: 736 /* retry getting data from /dev/random */ 737 b = get_dev_random(&work->output[work->filled], 738 work->needed - work->filled); 739 if (b > 0) 740 work->filled += b; 741 break; 742 743 case 6: 744 if (sizeof(files) > 2 * sizeof(*files)) { 745 b = digest_file(work); 746 dig += b; 747 } 748 break; 749 750 case 2: 751 default: /* to make sure we make some progress */ 752 work->output[work->filled++] = 0xff & 753 dst_s_quick_random(bytes); 754 b = 1; 755 break; 756 } 757 if (b > 0) 758 bytes += b; 759 } 760 return (work->filled); 761 } 762 763 764 /* 765 * dst_s_random() This function will return the requested number of bytes 766 * of randomness to the caller it will use the best available sources of 767 * randomness. 768 * The current order is to use /dev/random, precalculated randomness, and 769 * finally use some system calls and programs to generate semi random data 770 * that is then digested to generate randomness. 771 * This function is thread safe as each thread uses its own context, but 772 * concurrent treads will affect each other as they update shared state 773 * information. 774 * It is strongly recommended that this function be called requesting a size 775 * that is not a multiple of the output of the hash function used. 776 * 777 * If /dev/random is not available this function is not suitable to generate 778 * large amounts of data, rather it is suitable to seed a pseudo-random 779 * generator 780 * Returns the number of bytes put in the output buffer 781 */ 782 int 783 dst_s_random(u_char *output, unsigned size) 784 { 785 int n = 0, i; 786 unsigned s; 787 static u_char old_unused[DST_HASH_SIZE * DST_NUM_HASHES]; 788 static unsigned unused = 0; 789 790 if (size <= 0 || output == NULL) 791 return (0); 792 793 if (size >= 2048) 794 return (-1); 795 /* 796 * Read from /dev/random 797 */ 798 n = get_dev_random(output, size); 799 /* 800 * If old data is available and needed use it 801 */ 802 if (n < size && unused > 0) { 803 unsigned need = size - n; 804 if (unused <= need) { 805 memcpy(output, old_unused, unused); 806 n += unused; 807 unused = 0; 808 } else { 809 memcpy(output, old_unused, need); 810 n += need; 811 unused -= need; 812 memcpy(old_unused, &old_unused[need], unused); 813 } 814 } 815 /* 816 * If we need more use the simulated randomness here. 817 */ 818 if (n < size) { 819 dst_work *my_work = (dst_work *) malloc(sizeof(dst_work)); 820 if (my_work == NULL) 821 return (n); 822 my_work->needed = size - n; 823 my_work->filled = 0; 824 my_work->output = (u_char *) malloc(my_work->needed + 825 DST_HASH_SIZE * 826 DST_NUM_HASHES); 827 my_work->file_digest = NULL; 828 if (my_work->output == NULL) { 829 SAFE_FREE(my_work); 830 return (n); 831 } 832 memset(my_work->output, 0x0, my_work->needed); 833 /* allocate upto 4 different HMAC hash functions out of order */ 834 #if DST_NUM_HASHES >= 3 835 my_work->hash[2] = get_hmac_key(3, DST_RANDOM_BLOCK_SIZE / 2); 836 #endif 837 #if DST_NUM_HASHES >= 2 838 my_work->hash[1] = get_hmac_key(7, DST_RANDOM_BLOCK_SIZE / 6); 839 #endif 840 #if DST_NUM_HASHES >= 4 841 my_work->hash[3] = get_hmac_key(5, DST_RANDOM_BLOCK_SIZE / 4); 842 #endif 843 my_work->hash[0] = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE); 844 if (my_work->hash[0] == NULL) { /* if failure bail out */ 845 for (i = 1; i < DST_NUM_HASHES; i++) { 846 if (my_work->hash[i] != NULL) { 847 dst_free_key(my_work->hash[i]->key); 848 SAFE_FREE(my_work->hash[i]); 849 } 850 } 851 SAFE_FREE(my_work->output); 852 SAFE_FREE(my_work); 853 return (n); 854 } 855 s = own_random(my_work); 856 /* if more generated than needed store it for future use */ 857 if (s >= my_work->needed) { 858 EREPORT(("dst_s_random(): More than needed %d >= %d\n", 859 s, my_work->needed)); 860 memcpy(&output[n], my_work->output, my_work->needed); 861 n += my_work->needed; 862 /* saving unused data for next time */ 863 unused = s - my_work->needed; 864 if (unused > sizeof(old_unused)) { 865 unused = sizeof(old_unused); 866 } 867 memcpy(old_unused, &my_work->output[my_work->needed], 868 unused); 869 } else { 870 /* XXXX This should not happen */ 871 EREPORT(("Not enough %d >= %d\n", s, my_work->needed)); 872 memcpy(&output[n], my_work->output, s); 873 n += my_work->needed; 874 } 875 876 /* delete the allocated work area */ 877 for (i = 0; i < DST_NUM_HASHES; i++) { 878 if (my_work->hash[i] != NULL) { 879 dst_free_key(my_work->hash[i]->key); 880 SAFE_FREE(my_work->hash[i]); 881 } 882 } 883 SAFE_FREE(my_work->output); 884 SAFE_FREE(my_work); 885 } 886 return (n); 887 } 888 889 /* 890 * A random number generator that is fast and strong 891 * this random number generator is based on HASHing data, 892 * the input to the digest function is a collection of <NUMBER_OF_COUNTERS> 893 * counters that is incremented between digest operations 894 * each increment operation amortizes to 2 bits changed in that value 895 * for 5 counters thus the input will amortize to have 10 bits changed 896 * The counters are initially set using the strong random function above 897 * the HMAC key is selected by the same method as the HMAC keys for the 898 * strong random function. 899 * Each set of counters is used for 2^25 operations 900 * 901 * returns the number of bytes written to the output buffer 902 * or negative number in case of error 903 */ 904 int 905 dst_s_semi_random(u_char *output, unsigned size) 906 { 907 static u_int32_t counter[DST_NUMBER_OF_COUNTERS]; 908 static u_char semi_old[DST_HASH_SIZE]; 909 static int semi_loc = 0, cnt = 0; 910 static unsigned hb_size = 0; 911 static DST_KEY *my_key = NULL; 912 prand_hash *hash; 913 unsigned out = 0; 914 unsigned i; 915 int n, res; 916 917 if (output == NULL || size <= 0) 918 return (-2); 919 920 /* check if we need a new key */ 921 if (my_key == NULL || cnt > (1 << 25)) { /* get HMAC KEY */ 922 if (my_key) 923 my_key->dk_func->destroy(my_key); 924 if ((hash = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE)) == NULL) 925 return (0); 926 my_key = hash->key; 927 /* check if the key works stir the new key using some old random data */ 928 hb_size = dst_sign_data(SIG_MODE_ALL, my_key, NULL, 929 (u_char *) counter, sizeof(counter), 930 semi_old, sizeof(semi_old)); 931 if (hb_size <= 0) { 932 EREPORT(("dst_s_semi_random() Sign of alg %d failed %d\n", 933 my_key->dk_alg, hb_size)); 934 return (-1); 935 } 936 /* new set the counters to random values */ 937 dst_s_random((u_char *) counter, sizeof(counter)); 938 cnt = 0; 939 } 940 /* if old data around use it first */ 941 if (semi_loc < hb_size) { 942 if (size <= hb_size - semi_loc) { /* need less */ 943 memcpy(output, &semi_old[semi_loc], size); 944 semi_loc += size; 945 return (size); /* DONE */ 946 } else { 947 out = hb_size - semi_loc; 948 memcpy(output, &semi_old[semi_loc], out); 949 semi_loc += out; 950 } 951 } 952 /* generate more random stuff */ 953 while (out < size) { 954 /* 955 * modify at least one bit by incrementing at least one counter 956 * based on the last bit of the last counter updated update 957 * the next one. 958 * minimally this operation will modify at least 1 bit, 959 * amortized 2 bits 960 */ 961 for (n = 0; n < DST_NUMBER_OF_COUNTERS; n++) 962 i = (int) counter[n]++; 963 964 res = dst_sign_data(SIG_MODE_ALL, my_key, NULL, 965 (u_char *) counter, hb_size, 966 semi_old, sizeof(semi_old)); 967 if (res < 0) { 968 return res; 969 } 970 i = (unsigned) res; 971 if (i != hb_size) 972 EREPORT(("HMAC SIGNATURE FAILURE %d\n", i)); 973 cnt++; 974 if (size - out < i) /* Not all data is needed */ 975 semi_loc = i = size - out; 976 memcpy(&output[out], semi_old, i); 977 out += i; 978 } 979 return (out); 980 } 981