contrib/dhcp-3.0/dst/prandom.c

   1 #ifndef LINT
   2 static const char rcsid[] = "$Header: /proj/cvs/prod/DHCP/dst/prandom.c,v 1.1 2001/02/22 07:22:09 mellon Exp $";
   3 #endif
   4 /*
   5  * Portions Copyright (c) 1995-1998 by Trusted Information Systems, Inc.
   6  *
   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.
  10  *
  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.
  19  */
  20
  21 #include <stdio.h>
  22 #include <sys/types.h>
  23 #include <stdlib.h>
  24 #include <string.h>
  25 #include <unistd.h>
  26 #include <fcntl.h>
  27 #include <time.h>
  28 #include <dirent.h>
  29 #include <sys/param.h>
  30 #include <sys/stat.h>
  31 #include <sys/time.h>
  32
  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"
  39
  40
  41 #ifndef DST_NUM_HASHES
  42 #define DST_NUM_HASHES 4
  43 #endif
  44 #ifndef DST_NUMBER_OF_COUNTERS
  45 #define DST_NUMBER_OF_COUNTERS 5        /* 32 * 5 == 160 == SHA(1) > MD5 */
  46 #endif
  47
  48 /*
  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
  54  */
  55
  56 #ifndef DST_RANDOM_BLOCK_SIZE
  57 #define DST_RANDOM_BLOCK_SIZE 2879
  58 #endif
  59
  60 /*
  61  * This constant dictatates how many bits we shift to the right before using a
  62  */
  63 #ifndef DST_SHIFT
  64 #define DST_SHIFT 9
  65 #endif
  66
  67 /*
  68  * An initalizer that is as bad as any other with half the bits set
  69  */
  70 #ifndef DST_RANDOM_PATTERN
  71 #define DST_RANDOM_PATTERN 0x8765CA93
  72 #endif
  73 /*
  74  * things must have changed in the last 3600 seconds to be used
  75  */
  76 #define MAX_OLD 3600
  77
  78
  79 /*
  80  *  these two data structure are used to process input data into digests,
  81  *
  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.
  88  */
  89 typedef struct hash {
  90         DST_KEY *key;
  91         void *ctx;
  92         int digested, block, step, curr;
  93 } prand_hash;
  94
  95 /*
  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.
 103  */
 104 typedef struct work {
 105         unsigned needed, filled, bytes;
 106         u_char *output;
 107         prand_hash *hash[DST_NUM_HASHES];
 108         DST_KEY *file_digest;
 109 } dst_work;
 110
 111
 112 /*
 113  * forward function declarations
 114  */
 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);
 120
 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,
 123                    unsigned size);
 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);
 126
 127 static unsigned own_random(dst_work *work);
 128
 129
 130 /*
 131  * variables used in the quick random number generator
 132  */
 133 static u_int32_t ran_val = DST_RANDOM_PATTERN;
 134 static u_int32_t ran_cnt = (DST_RANDOM_PATTERN >> 10);
 135
 136 /*
 137  * setting the quick_random generator to particular values or if both
 138  * input parameters are 0 then set it to initial vlaues
 139  */
 140
 141 void
 142 dst_s_quick_random_set(u_int32_t val, u_int32_t cnt)
 143 {
 144         ran_val = (val == 0) ? DST_RANDOM_PATTERN : val;
 145         ran_cnt = (cnt == 0) ? (DST_RANDOM_PATTERN >> 10) : cnt;
 146 }
 147
 148 /*
 149  * this is a quick and random number generator that seems to generate quite
 150  * good distribution of data
 151  */
 152 u_int32_t
 153 dst_s_quick_random(int inc)
 154 {
 155         ran_val = ((ran_val >> 13) ^ (ran_val << 19)) ^
 156                 ((ran_val >> 7) ^ (ran_val << 25));
 157         if (inc > 0)            /* only increasing values accepted */
 158                 ran_cnt += inc;
 159         ran_val += ran_cnt++;
 160         return (ran_val);
 161 }
 162
 163 /*
 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
 167  */
 168 static int
 169 get_dev_random(u_char *output, unsigned size)
 170 {
 171 #ifdef HAVE_DEV_RANDOM
 172         struct stat st;
 173         int n = 0, fd = -1, s;
 174
 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)
 179                                 n = 0;
 180                         close(fd);
 181                 }
 182                 return (n);
 183         }
 184 #endif
 185         return (0);
 186 }
 187
 188 /*
 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
 195  */
 196 struct timeval *mtime;
 197 static int
 198 do_time(dst_work *work)
 199 {
 200         int cnt = 0;
 201         static u_char tmp[sizeof(struct timeval) + sizeof(struct timezone)];
 202         struct timezone *zone;
 203
 204         zone = (struct timezone *) tmp;
 205         mtime = (struct timeval *)(tmp + sizeof(struct timezone));
 206         gettimeofday(mtime, zone);
 207         cnt = sizeof(tmp);
 208         my_digest(work, tmp, sizeof(tmp));
 209
 210         return (cnt);
 211 }
 212
 213 /*
 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
 219  *
 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
 227  */
 228 static int
 229 do_ls(dst_work *work)
 230 {
 231         struct dir_info {
 232                 uid_t  uid;
 233                 gid_t  gid;
 234                 off_t size;
 235                 time_t atime, mtime, ctime;
 236         };
 237         static struct dir_info dir_info;
 238         struct stat buf;
 239         struct dirent *entry;
 240         static int i = 0;
 241         static unsigned long d_round = 0;
 242         struct timeval tv;
 243         int n = 0, tb_i = 0, out = 0;
 244         unsigned dir_len;
 245
 246         char file_name[1024];
 247         u_char tmp_buff[1024];
 248         DIR *dir = NULL;
 249
 250         if (dirs[i] == NULL)    /* if at the end of the list start over */
 251                 i = 0;
 252         if (stat(dirs[i++], &buf))  /* directory does not exist */
 253                 return (0);
 254
 255         gettimeofday(&tv,NULL);
 256         if (d_round == 0)
 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;
 260
 261         if (buf.st_atime < d_round)
 262                 return (0);
 263
 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));
 267         tb_i += sizeof(buf);
 268
 269
 270         if ((dir = opendir(dirs[i-1])) == NULL)/* open it for read */
 271                 return (0);
 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);
 277                 out += len;
 278                 if (my_digest(work, (u_char *)entry->d_name, len))
 279                         break;
 280
 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,
 295                                      sizeof(dir_info)))
 296                                 break;
 297                 }
 298         }
 299         closedir(dir);  /* done */
 300         out += do_time(work);   /* add a time stamp */
 301         return (out);
 302 }
 303
 304
 305 /*
 306  * unix_cmd()
 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
 310  *
 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
 315  */
 316 static int
 317 unix_cmd(dst_work *work)
 318 {
 319         static int cmd_index = 0;
 320         int cnt = 0, n;
 321         FILE *pipe;
 322         u_char buffer[4096];
 323
 324         if (cmds[cmd_index] == NULL)
 325                 cmd_index = 0;
 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 */
 329
 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))
 333                         break;
 334                 /* this adds some randomness to the output */
 335                 cnt += do_time(work);
 336         }
 337         while ((n = fread(buffer, sizeof(char), sizeof(buffer), pipe)) > 0)
 338                 NULL; /* drain the pipe */
 339         pclose(pipe);
 340         return (cnt);           /* read how many bytes where read in */
 341 }
 342
 343 /*
 344  * digest_file() This function will read a file and run hash over it
 345  * input is a file name
 346  */
 347 static int
 348 digest_file(dst_work *work)
 349 {
 350         static int f_cnt = 0;
 351         static unsigned long f_round = 0;
 352         FILE *fp;
 353         void *ctx;
 354         const char *name;
 355         int no, i;
 356         struct stat st;
 357         struct timeval tv;
 358         u_char buf[1024];
 359
 360         if (f_round == 0 || files[f_cnt] == NULL || work->file_digest == NULL)
 361                 if (gettimeofday(&tv, NULL)) /* only do this if needed */
 362                         return (0);
 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 */
 368                         return (0);
 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);
 372         }
 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)
 377                         return (0);
 378         }
 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,
 384                           NULL, 0, NULL, 0)) {
 385                 work->file_digest = dst_free_key(work->file_digest);
 386                 return (0);
 387         }
 388         if ((fp = fopen(name, "r")) == NULL)
 389                 return (0);
 390         for (no = 0; (i = fread(buf, sizeof(*buf), sizeof(buf), fp)) > 0;
 391              no += i)
 392                 dst_sign_data(SIG_MODE_UPDATE, work->file_digest, &ctx,
 393                               buf, (unsigned)i, NULL, 0);
 394
 395         fclose(fp);
 396         if (no >= 64) {
 397                 i = dst_sign_data(SIG_MODE_FINAL, work->file_digest, &ctx,
 398                                   NULL, 0, &work->output[work->filled],
 399                                   DST_HASH_SIZE);
 400                 if (i > 0)
 401                         work->filled += i;
 402         }
 403         else if (i > 0)
 404                 my_digest(work, buf, (unsigned)i);
 405         my_digest(work, (const u_char *)name, strlen(name));
 406         return (no + strlen(name));
 407 }
 408
 409 /*
 410  * function to perform the FINAL and INIT operation on a hash if allowed
 411  */
 412 static void
 413 force_hash(dst_work *work, prand_hash *hash)
 414 {
 415         int i = 0;
 416
 417         /*
 418          * if more than half a block then add data to output
 419          * otherwise adde the digest to the next hash
 420          */
 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],
 424                                   DST_HASH_SIZE);
 425
 426                 hash->digested = 0;
 427                 dst_sign_data(SIG_MODE_INIT, hash->key, &hash->ctx,
 428                               NULL, 0, NULL, 0);
 429                 if (i > 0)
 430                         work->filled += i;
 431         }
 432         return;
 433 }
 434
 435 /*
 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
 439  * are used,
 440  *
 441  */
 442 static int
 443 do_hash(dst_work *work, prand_hash *hash, const u_char *input, unsigned size)
 444 {
 445         const u_char *tmp = input;
 446         u_char *tp, *abuf = (u_char *)0;
 447         int i, n;
 448         unsigned needed, avail, dig, cnt = size;
 449         unsigned tmp_size = 0;
 450
 451         if (cnt <= 0 || input == NULL)
 452                 return (0);
 453
 454         if (hash->step > 1) {   /* if using subset of input data */
 455                 tmp_size = size / hash->step + 2;
 456                 abuf = tp = malloc(tmp_size);
 457                 tmp = tp;
 458                 for (cnt = 0, i = hash->curr; i < size; i += hash->step, cnt++)
 459                         *(tp++) = input[i];
 460                 /* calcutate the starting point in the next input set */
 461                 hash->curr = (hash->step - (i - size)) % hash->step;
 462         }
 463         /* digest the data in block sizes */
 464         for (n = 0; n < cnt; n += needed) {
 465                 avail = (cnt - n);
 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) {
 474                         if (abuf)
 475                                 SAFE_FREE2(abuf, tmp_size);
 476                         return (1);
 477                 }
 478         }
 479         if (tmp_size > 0)
 480                 SAFE_FREE2(abuf, tmp_size);
 481         return (0);
 482 }
 483
 484 /*
 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.
 488  */
 489 static int
 490 my_digest(dst_work *work, const u_char *input, unsigned size)
 491 {
 492
 493         int i, full = 0;
 494         static unsigned counter;
 495
 496         counter += size;
 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,
 501                                 sizeof(counter));
 502 /*
 503  * if enough data has be generated do final operation on all hashes
 504  *  that have enough date for that
 505  */
 506         for (i = 0; full && (i < DST_NUM_HASHES); i++)
 507                 force_hash(work, work->hash[i]);
 508
 509         return (full);
 510 }
 511
 512 /*
 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;
 516  */
 517 static prand_hash *
 518 get_hmac_key(int step, int block)
 519 {
 520
 521         u_char *buff;
 522         int temp = 0, n = 0;
 523         unsigned size = 70;
 524         DST_KEY *new_key = NULL;
 525         prand_hash *new = NULL;
 526
 527         /* use key that is larger than  digest algorithms (64) for key size */
 528         buff = malloc(size);
 529         if (buff == NULL)
 530                 return (NULL);
 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);
 535
 536 /* get some semi random stuff in here stir it with micro seconds */
 537         if (n < size) {
 538                 temp = dst_s_quick_random((int) buff[n - 1]);
 539                 memcpy(&buff[n], &temp, sizeof(temp));
 540                 n += sizeof(temp);
 541         }
 542 /* get the pid of this process and its parent */
 543         if (n < size) {
 544                 temp = (int) getpid();
 545                 memcpy(&buff[n], &temp, sizeof(temp));
 546                 n += sizeof(temp);
 547         }
 548         if (n < size) {
 549                 temp = (int) getppid();
 550                 memcpy(&buff[n], &temp, sizeof(temp));
 551                 n += sizeof(temp);
 552         }
 553 /* get the user ID */
 554         if (n < size) {
 555                 temp = (int) getuid();
 556                 memcpy(&buff[n], &temp, sizeof(temp));
 557                 n += sizeof(temp);
 558         }
 559 #ifndef GET_HOST_ID_MISSING
 560         if (n < size) {
 561                 temp = (int) gethostid();
 562                 memcpy(&buff[n], &temp, sizeof(temp));
 563                 n += sizeof(temp);
 564         }
 565 #endif
 566 /* get some more random data */
 567         if (n < size) {
 568                 temp = dst_s_quick_random((int) buff[n - 1]);
 569                 memcpy(&buff[n], &temp, sizeof(temp));
 570                 n += sizeof(temp);
 571         }
 572 /* covert this into a HMAC key */
 573         new_key = dst_buffer_to_key("", KEY_HMAC_MD5, 0, 0, buff, size);
 574         SAFE_FREE(buff);
 575
 576 /* get the control structure */
 577         if ((new = malloc(sizeof(prand_hash))) == NULL)
 578                 return (NULL);
 579         new->digested = new->curr = 0;
 580         new->step = step;
 581         new->block = block;
 582         new->key = new_key;
 583         if (dst_sign_data(SIG_MODE_INIT, new_key, &new->ctx, NULL, 0, NULL, 0))
 584                 return (NULL);
 585
 586         return (new);
 587 }
 588
 589 /*
 590  * own_random()
 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.
 596  */
 597 static unsigned
 598 own_random(dst_work *work)
 599 {
 600         int dir = 0, b;
 601         int bytes, n, cmd = 0, dig = 0;
 602         int start =0;
 603 /*
 604  * now get the initial seed to put into the quick random function from
 605  * the address of the work structure
 606  */
 607         bytes = (int) getpid();
 608 /*
 609  * proceed while needed
 610  */
 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
 616  */
 617                 start = work->filled;
 618                 n = (dst_s_quick_random(bytes) >> DST_SHIFT) & 0x07;
 619                 switch (n) {
 620                     case 0:
 621                     case 3:
 622                         if (sizeof(cmds) > 2 *sizeof(*cmds)) {
 623                                 b = unix_cmd(work);
 624                                 cmd += b;
 625                         }
 626                         break;
 627
 628                     case 1:
 629                     case 7:
 630                         if (sizeof(dirs) > 2 *sizeof(*dirs)) {
 631                                 b = do_ls(work);
 632                                 dir += b;
 633                         }
 634                         break;
 635
 636                     case 4:
 637                     case 5:
 638                         /* retry getting data from /dev/random */
 639                         b = get_dev_random(&work->output[work->filled],
 640                                            work->needed - work->filled);
 641                         if (b > 0)
 642                                 work->filled += b;
 643                         break;
 644
 645                     case 6:
 646                         if (sizeof(files) > 2 * sizeof(*files)) {
 647                                 b = digest_file(work);
 648                                 dig += b;
 649                         }
 650                         break;
 651
 652                     case 2:
 653                     default:    /* to make sure we make some progress */
 654                         work->output[work->filled++] = 0xff &
 655                                 dst_s_quick_random(bytes);
 656                         b = 1;
 657                         break;
 658                 }
 659                 if (b > 0)
 660                         bytes += b;
 661         }
 662         return (work->filled);
 663 }
 664
 665
 666 /*
 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
 669  * randomness.
 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
 675  * information.
 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.
 678  *
 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
 681  * generator
 682  * Returns the number of bytes put in the output buffer
 683  */
 684 int
 685 dst_s_random(u_char *output, unsigned size)
 686 {
 687         int n = 0, i;
 688         unsigned s;
 689         static u_char old_unused[DST_HASH_SIZE * DST_NUM_HASHES];
 690         static unsigned unused = 0;
 691
 692         if (size <= 0 || output == NULL)
 693                 return (0);
 694
 695         if (size >= 2048)
 696                 return (-1);
 697         /*
 698          * Read from /dev/random
 699          */
 700         n = get_dev_random(output, size);
 701         /*
 702          *  If old data is available and needed use it
 703          */
 704         if (n < size && unused > 0) {
 705                 unsigned need = size - n;
 706                 if (unused <= need) {
 707                         memcpy(output, old_unused, unused);
 708                         n += unused;
 709                         unused = 0;
 710                 } else {
 711                         memcpy(output, old_unused, need);
 712                         n += need;
 713                         unused -= need;
 714                         memcpy(old_unused, &old_unused[need], unused);
 715                 }
 716         }
 717         /*
 718          * If we need more use the simulated randomness here.
 719          */
 720         if (n < size) {
 721                 dst_work *my_work = (dst_work *) malloc(sizeof(dst_work));
 722                 if (my_work == NULL)
 723                         return (n);
 724                 my_work->needed = size - n;
 725                 my_work->filled = 0;
 726                 my_work->output = (u_char *) malloc(my_work->needed +
 727                                                     DST_HASH_SIZE *
 728                                                     DST_NUM_HASHES);
 729                 my_work->file_digest = NULL;
 730                 if (my_work->output == NULL)
 731                         return (n);
 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);
 736 #endif
 737 #if DST_NUM_HASHES >= 2
 738                 my_work->hash[1] = get_hmac_key(7, DST_RANDOM_BLOCK_SIZE / 6);
 739 #endif
 740 #if DST_NUM_HASHES >= 4
 741                 my_work->hash[3] = get_hmac_key(5, DST_RANDOM_BLOCK_SIZE / 4);
 742 #endif
 743                 my_work->hash[0] = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE);
 744                 if (my_work->hash[0] == NULL)   /* if failure bail out */
 745                         return (n);
 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],
 756                                unused);
 757                 } else {
 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;
 762                 }
 763
 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]);
 768                 }
 769                 SAFE_FREE(my_work->output);
 770                 SAFE_FREE(my_work);
 771         }
 772         return (n);
 773 }
 774
 775 /*
 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
 786  *
 787  * returns the number of bytes written to the output buffer
 788  * or       negative number in case of error
 789  */
 790 int
 791 dst_s_semi_random(u_char *output, unsigned size)
 792 {
 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;
 798         prand_hash *hash;
 799         unsigned out = 0;
 800         unsigned i;
 801         int n;
 802
 803         if (output == NULL || size <= 0)
 804                 return (-2);
 805
 806 /* check if we need a new key */
 807         if (my_key == NULL || cnt > (1 << 25)) {        /* get HMAC KEY */
 808                 if (my_key)
 809                         my_key->dk_func->destroy(my_key);
 810                 if ((hash = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE)) == NULL)
 811                         return (0);
 812                 my_key = hash->key;
 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));
 817                 if (hb_size <= 0) {
 818                         EREPORT(("dst_s_semi_random() Sign of alg %d failed %d\n",
 819                                  my_key->dk_alg, hb_size));
 820                         return (-1);
 821                 }
 822 /* new set the counters to random values */
 823                 dst_s_random((u_char *) counter, sizeof(counter));
 824                 cnt = 0;
 825         }
 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);
 830                         semi_loc += size;
 831                         return (size);  /* DONE */
 832                 } else {
 833                         out = hb_size - semi_loc;
 834                         memcpy(output, &semi_old[semi_loc], out);
 835                         semi_loc += out;
 836                 }
 837         }
 838 /* generate more randome stuff */
 839         while (out < size) {
 840                 /*
 841                  * modify at least one bit by incrementing at least one counter
 842                  * based on the last bit of the last counter updated update
 843                  * the next one.
 844                  * minimaly this  operation will modify at least 1 bit,
 845                  * amortized 2 bits
 846                  */
 847                 for (n = 0; n < DST_NUMBER_OF_COUNTERS; n++)
 848                         i = (int) counter[n]++;
 849
 850                 i = dst_sign_data(SIG_MODE_ALL, my_key, NULL,
 851                                   (u_char *) counter, hb_size,
 852                                   semi_old, sizeof(semi_old));
 853                 if (i != hb_size)
 854                         EREPORT(("HMAC SIGNATURE FAILURE %d\n", i));
 855                 cnt++;
 856                 if (size - out < i)     /* Not all data is needed */
 857                         semi_loc = i = size - out;
 858                 memcpy(&output[out], semi_old, i);
 859                 out += i;
 860         }
 861         return (out);
 862 }