prandom.c revision 7c478bd95313f5f23a4c958a745db2134aa03244
#ifndef LINT
static const char rcsid[] = "$Header: /proj/cvs/isc/bind8/src/lib/dst/prandom.c,v 1.12 2001/07/26 01:20:09 marka Exp $";
#endif
/*
* Copyright 2001-2002 Sun Microsystems, Inc. All rights reserved.
* Use is subject to license terms.
*/
#pragma ident "%Z%%M% %I% %E% SMI"
/*
* Portions Copyright (c) 1995-1998 by Trusted Information Systems, Inc.
*
* Permission to use, copy modify, and distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND TRUSTED INFORMATION SYSTEMS
* DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL
* TRUSTED INFORMATION SYSTEMS BE LIABLE FOR ANY SPECIAL, DIRECT,
* INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING
* FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
* NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION
* WITH THE USE OR PERFORMANCE OF THE SOFTWARE.
*/
#include "port_before.h"
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <fcntl.h>
#include <time.h>
#include <dirent.h>
#include "dst_internal.h"
#include "prand_conf.h"
#include "port_after.h"
#ifndef DST_NUM_HASHES
#define DST_NUM_HASHES 4
#endif
#ifndef DST_NUMBER_OF_COUNTERS
#endif
/*
* the constant below is a prime number to make fixed data structues like
* stat and time wrap over blocks. This adds certain uncertanty to what is
* in each digested block.
* The prime number 2879 has the special property that when
* divided by 2,4 and 6 the result is also a prime numbers
*/
#ifndef DST_RANDOM_BLOCK_SIZE
#define DST_RANDOM_BLOCK_SIZE 2879
#endif
/*
* This constant dictatates how many bits we shift to the right before using a
*/
#ifndef DST_SHIFT
#define DST_SHIFT 9
#endif
/*
* An initalizer that is as bad as any other with half the bits set
*/
#ifndef DST_RANDOM_PATTERN
#define DST_RANDOM_PATTERN 0x8765CA93
#endif
/*
* things must have changed in the last 3600 seconds to be used
*/
#define MAX_OLD 3600
/*
* these two data structure are used to process input data into digests,
*
* The first structure is containts a pointer to a DST HMAC key
* the variables accompanying are used for
* step : select every step byte from input data for the hash
* block: number of data elements going into each hash
* digested: number of data elements digested so far
* curr: offset into the next input data for the first byte.
*/
typedef struct hash {
void *ctx;
} prand_hash;
/*
* This data structure controlls number of hashes and keeps track of
* overall progress in generating correct number of bytes of output.
* output : array to store the output data in
* needed : how many bytes of output are needed
* filled : number of bytes in output so far.
* bytes : total number of bytes processed by this structure
* file_digest : the HMAC key used to digest files.
*/
typedef struct work {
} dst_work;
/*
* forward function declarations
*/
int size);
/*
* variables used in the quick random number generator
*/
/*
* setting the quick_random generator to particular values or if both
* input parameters are 0 then set it to initial vlaues
*/
void
{
}
/*
* this is a quick and random number generator that seems to generate quite
* good distribution of data
*/
dst_s_quick_random(int inc)
{
if (inc > 0) /* only increasing values accepted */
return (ran_val);
}
/*
* this function returns how many bytes where read from the device.
* port_after.h should set the control variable HAVE_DEV_RANDOM
*/
static int
{
#ifdef HAVE_DEV_RANDOM
int n = 0, fd = -1, s;
n = 0;
}
return (n);
}
#endif
return (0);
}
/*
* Portable way of getting the time values if gettimeofday is missing
* then compile with -DMISSING_GETTIMEOFDAY time() is POSIX compliant but
* gettimeofday() is not.
* Time of day is predictable, we are looking for the randomness that comes
* the last few bits in the microseconds in the timer are hard to predict when
* this is invoked at the end of other operations
*/
static int
{
int cnt = 0;
return (cnt);
}
/*
* this function simulates the ls command, but it uses stat which gives more
* information and is harder to guess
* Each call to this function will visit the next directory on the list of
* directories, in a circular manner.
* return value is the number of bytes added to the temp buffer
*
* do_ls() does not visit subdirectories
* if attacker has access to machine it can guess most of the values seen
* thus it is important to only visit directories that are freqently updated
* Attacker that has access to the network can see network traffic
* when NFS mounted directories are accessed and know exactly the data used
* but may not know exactly in what order data is used.
* Returns the number of bytes that where returned in stat structures
*/
static int
{
struct dir_info {
};
static int i = 0;
static unsigned long d_round = 0;
char file_name[1024];
i = 0;
return (0);
if (d_round == 0)
else if (i==1) /* if starting a new round cut what we accept */
return (0);
return (0);
break;
/* for all entries in dir get the stats */
n++; /* count successfull stat calls */
/* copy non static fields */
sizeof(dir_info)))
break;
}
}
return (out);
}
/*
* unix_cmd()
* this function executes the a command from the cmds[] list of unix commands
* configured in the prand_conf.h file
* return value is the number of bytes added to the randomness temp buffer
*
* it returns the number of bytes that where read in
* if more data is needed at the end time is added to the data.
* This function maintains a state to selects the next command to run
* returns the number of bytes read in from the command
*/
static int
{
static int cmd_index = 0;
int cnt = 0, n;
cmd_index = 0;
cnt += n; /* process the output */
break;
/* this adds some randomness to the output */
}
(void)NULL; /* drain the pipe */
return (cnt); /* read how many bytes where read in */
}
/*
* digest_file() This function will read a file and run hash over it
* input is a file name
*/
static int
{
static int f_cnt = 0;
static unsigned long f_round = 0;
void *ctx;
const char *name;
int no, i;
return (0);
if (f_round == 0) /* first time called set to one hour ago */
return (0);
f_cnt = 0; /* start again on list */
}
return (0);
}
return (0); /* no such file or not allowed to read it */
return(0); /* file has not changed recently enough */
return (0);
}
return (0);
no += i)
if (no >= 64) {
if (i > 0)
}
else if (i > 0)
}
/*
* function to perform the FINAL and INIT operation on a hash if allowed
*/
static void
{
int i = 0;
/*
* if more than half a block then add data to output
* otherwise adde the digest to the next hash
*/
if (i > 0)
}
return;
}
/*
* This function takes the input data does the selection of data specified
* by the hash control block.
* The step varialbe in the work sturcture determines which 1/step bytes
* are used,
*
*/
static int
{
return (0);
/* calcutate the starting point in the next input set */
}
/* digest the data in block sizes */
if (tmp_size > 0)
return (1);
}
}
if (tmp_size > 0)
return (0);
}
/*
* Copy data from INPUT for length SIZE into the work-block TMP.
* If we fill the work-block, digest it; then,
* if work-block needs more data, keep filling with the rest of the input.
*/
static int
{
int i, full = 0;
static unsigned counter;
/* first do each one of the hashes */
for (i = 0; i < DST_NUM_HASHES && full == 0; i++)
sizeof(counter));
/*
* if enough data has be generated do final operation on all hashes
* that have enough date for that
*/
for (i = 0; full && (i < DST_NUM_HASHES); i++)
return (full);
}
/*
* this function gets some semi random data and sets that as an HMAC key
* If we get a valid key this function returns that key initalized
* otherwise it returns NULL;
*/
static prand_hash *
{
/* use key that is larger than digest algorithms (64) for key size */
return (NULL);
/* do not memset the allocated memory to get random bytes there */
/* time of day is somewhat random expecialy in the last bytes */
n += sizeof(struct timeval);
/* get some semi random stuff in here stir it with micro seconds */
if (n < size) {
n += sizeof(temp);
}
/* get the pid of this process and its parent */
if (n < size) {
n += sizeof(temp);
}
if (n < size) {
n += sizeof(temp);
}
/* get the user ID */
if (n < size) {
n += sizeof(temp);
}
#ifndef GET_HOST_ID_MISSING
if (n < size) {
n += sizeof(temp);
}
#endif
/* get some more random data */
if (n < size) {
n += sizeof(temp);
}
/* covert this into a HMAC key */
/* get the control structure */
return (NULL);
return (NULL);
return (new);
}
/*
* own_random()
* This function goes out and from various sources tries to generate enough
* semi random data that a hash function can generate a random data.
* This function will iterate between the two main random source sources,
* information from programs and directores in random order.
* This function return the number of bytes added to the random output buffer.
*/
static int
{
int dir = 0, b;
int start =0;
/*
* now get the initial seed to put into the quick random function from
* the address of the work structure
*/
/*
* proceed while needed
*/
EREPORT(("own_random r %08x b %6d f %6d\n",
/* pick a random number in the range of 0..7 based on that random number
* perform some operations that yield random data
*/
switch (n) {
case 0:
case 3:
cmd += b;
}
break;
case 1:
case 7:
dir += b;
}
break;
case 4:
case 5:
if (b > 0)
break;
case 6:
b = digest_file(work);
dig += b;
}
break;
case 2:
default: /* to make sure we make some progress */
b = 1;
break;
}
if (b > 0)
bytes += b;
}
}
/*
* dst_s_random() This function will return the requested number of bytes
* of randomness to the caller it will use the best available sources of
* randomness.
* finaly use some system calls and programs to generate semi random data that
* is then digested to generate randomness.
* This function is thread safe as each thread uses its own context, but
* concurrent treads will affect each other as they update shared state
* information.
* It is strongly recommended that this function be called requesting a size
* that is not a multiple of the output of the hash function used.
*
* large ammounts of data, rather it is suitable to seed a pseudo-random
* generator
* Returns the number of bytes put in the output buffer
*/
int
{
int n = 0, s, i;
static int unused = 0;
return (0);
if (size >= 2048)
return (-1);
/*
*/
/*
* If old data is available and needed use it
*/
n += unused;
unused = 0;
} else {
n += need;
}
}
/*
* If we need more use the simulated randomness here.
*/
if (n < size) {
return (n);
return (n);
/* allocate upto 4 different HMAC hash functions out of order */
#if DST_NUM_HASHES >= 3
#endif
#if DST_NUM_HASHES >= 2
#endif
#if DST_NUM_HASHES >= 4
#endif
return (n);
s = own_random(my_work);
/* if more generated than needed store it for future use */
EREPORT(("dst_s_random(): More than needed %d >= %d\n",
/* saving unused data for next time */
unused);
} else {
/* XXXX This should not happen */
}
/* delete the allocated work area */
for (i = 0; i < DST_NUM_HASHES; i++) {
}
}
return (n);
}
/*
* A random number generator that is fast and strong
* this random number generator is based on HASHing data,
* the input to the digest function is a collection of <NUMBER_OF_COUNTERS>
* counters that is incremented between digest operations
* each increment operation amortizes to 2 bits changed in that value
* for 5 counters thus the input will amortize to have 10 bits changed
* The counters are initaly set using the strong random function above
* the HMAC key is selected by the same methold as the HMAC keys for the
* strong random function.
* Each set of counters is used for 2^25 operations
*
* returns the number of bytes written to the output buffer
* or negative number in case of error
*/
int
{
int out = 0, i, n;
return (-2);
/* check if we need a new key */
if (my_key)
return (0);
/* check if the key works stir the new key using some old random data */
if (hb_size <= 0) {
EREPORT(("dst_s_semi_random() Sign of alg %d failed %d\n",
return (-1);
}
/* new set the counters to random values */
cnt = 0;
}
/* if old data around use it first */
return (size); /* DONE */
} else {
}
}
/* generate more randome stuff */
/*
* modify at least one bit by incrementing at least one counter
* based on the last bit of the last counter updated update
* the next one.
* minimaly this operation will modify at least 1 bit,
* amortized 2 bits
*/
for (n = 0; n < DST_NUMBER_OF_COUNTERS; n++)
i = (int) counter[n]++;
#ifdef REPORT_ERRORS
if (i != hb_size)
EREPORT(("HMAC SIGNATURE FAILURE %d\n", i));
#endif
cnt++;
out += i;
}
return (out);
}