prandom.c

DHCP服务器源码

}

/* 
 * 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
do_hash(dst_work *work, prand_hash *hash, const u_char *input, unsigned size)
{
	const u_char *tmp = input;
	u_char *tp, *abuf = (u_char *)0;
	int i, n;
	unsigned needed, avail, dig, cnt = size;
	unsigned tmp_size = 0;

	if (cnt <= 0 || input == NULL)
		return (0);

	if (hash->step > 1) {	/* if using subset of input data */
		tmp_size = size / hash->step + 2;
		abuf = tp = malloc(tmp_size);
		tmp = tp;
		for (cnt = 0, i = hash->curr; i < size; i += hash->step, cnt++)
			*(tp++) = input[i];
		/* calcutate the starting point in the next input set */
		hash->curr = (hash->step - (i - size)) % hash->step;
	}
	/* digest the data in block sizes */
	for (n = 0; n < cnt; n += needed) {
		avail = (cnt - n);
		needed = hash->block - hash->digested;
		dig = (avail < needed) ? avail : needed;
		dst_sign_data(SIG_MODE_UPDATE, hash->key, &hash->ctx, 
			      &tmp[n], dig, NULL, 0);
		hash->digested += dig;
		if (hash->digested >= hash->block)
			force_hash(work, hash);
		if (work->needed < work->filled) {
			if (abuf) 
				SAFE_FREE2(abuf, tmp_size);
			return (1);
		}
	}
	if (tmp_size > 0)
		SAFE_FREE2(abuf, tmp_size);
	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
my_digest(dst_work *work, const u_char *input, unsigned size)
{

	int i, full = 0;
	static unsigned counter;
	
	counter += size;
	/* first do each one of the hashes */
	for (i = 0; i < DST_NUM_HASHES && full == 0; i++) 
		full = do_hash(work, work->hash[i], input, size) +
		       do_hash(work, work->hash[i], (u_char *) &counter, 
				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++)
		force_hash(work, work->hash[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 *
get_hmac_key(int step, int block)
{

	u_char *buff;
	int temp = 0, n = 0;
	unsigned size = 70;
	DST_KEY *new_key = NULL;
	prand_hash *new = NULL;

	/* use key that is larger than  digest algorithms (64) for key size */
	buff = malloc(size);
	if (buff == NULL)
		return (NULL);
	/* do not memset the allocated memory to get random bytes there */
	/* time of day is somewhat random  expecialy in the last bytes */
	gettimeofday((struct timeval *) &buff[n], NULL);
	n += sizeof(struct timeval);

/* get some semi random stuff in here stir it with micro seconds */
	if (n < size) {
		temp = dst_s_quick_random((int) buff[n - 1]);
		memcpy(&buff[n], &temp, sizeof(temp));
		n += sizeof(temp);
	}
/* get the pid of this process and its parent */
	if (n < size) {
		temp = (int) getpid();
		memcpy(&buff[n], &temp, sizeof(temp));
		n += sizeof(temp);
	}
	if (n < size) {
		temp = (int) getppid();
		memcpy(&buff[n], &temp, sizeof(temp));
		n += sizeof(temp);
	}
/* get the user ID */
	if (n < size) {
		temp = (int) getuid();
		memcpy(&buff[n], &temp, sizeof(temp));
		n += sizeof(temp);
	}
#ifndef GET_HOST_ID_MISSING
	if (n < size) {
		temp = (int) gethostid();
		memcpy(&buff[n], &temp, sizeof(temp));
		n += sizeof(temp);
	}
#endif
/* get some more random data */
	if (n < size) {
		temp = dst_s_quick_random((int) buff[n - 1]);
		memcpy(&buff[n], &temp, sizeof(temp));
		n += sizeof(temp);
	}
/* covert this into a HMAC key */
	new_key = dst_buffer_to_key("", KEY_HMAC_MD5, 0, 0, buff, size);
	SAFE_FREE(buff);

/* get the control structure */
	if ((new = malloc(sizeof(prand_hash))) == NULL)
		return (NULL);
	new->digested = new->curr = 0;
	new->step = step;
	new->block = block;
	new->key = new_key;
	if (dst_sign_data(SIG_MODE_INIT, new_key, &new->ctx, NULL, 0, NULL, 0))
		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 unsigned
own_random(dst_work *work)
{
	int dir = 0, b;
	int bytes, n, cmd = 0, dig = 0;
	int start =0;
/* 
 * now get the initial seed to put into the quick random function from 
 * the address of the work structure 
 */
	bytes = (int) getpid();
/*
 * proceed while needed 
 */
	while (work->filled < work->needed) {
		EREPORT(("own_random r %08x b %6d t %6d f %6d\n",
			 ran_val, bytes, work->in_temp, work->filled));
/* pick a random number in the range of 0..7 based on that random number
 * perform some operations that yield random data
 */
		start = work->filled;
		n = (dst_s_quick_random(bytes) >> DST_SHIFT) & 0x07;
		switch (n) {
		    case 0:
		    case 3:
			if (sizeof(cmds) > 2 *sizeof(*cmds)) {
				b = unix_cmd(work);
				cmd += b;
			}
			break;

		    case 1:
		    case 7:
			if (sizeof(dirs) > 2 *sizeof(*dirs)) {
				b = do_ls(work);
				dir += b;
			}
			break;

		    case 4:
		    case 5:
			/* retry getting data from /dev/random */
			b = get_dev_random(&work->output[work->filled], 
					   work->needed - work->filled);
			if (b > 0)
				work->filled += b;
			break;

		    case 6:
			if (sizeof(files) > 2 * sizeof(*files)) {
				b = digest_file(work);
				dig += b;
			}
			break;

		    case 2:
		    default:	/* to make sure we make some progress */
			work->output[work->filled++] = 0xff &
				dst_s_quick_random(bytes);
			b = 1;
			break;
		}
		if (b > 0) 
			bytes += b;
	}
	return (work->filled);
}


/* 
 * 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.
 * The current order is to use /dev/random, precalculated randomness, and 
 * 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. 
 * 
 * If /dev/random is not available this function is not suitable to generate 
 * 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
dst_s_random(u_char *output, unsigned size)
{
	int n = 0, i;
	unsigned s;
	static u_char old_unused[DST_HASH_SIZE * DST_NUM_HASHES];
	static unsigned unused = 0;

	if (size <= 0 || output == NULL)
		return (0);

	if (size >= 2048)
		return (-1);
	/* 
	 * Read from /dev/random 
	 */
	n = get_dev_random(output, size);
	/* 
	 *  If old data is available and needed use it 
	 */
	if (n < size && unused > 0) {
		unsigned need = size - n;
		if (unused <= need) {
			memcpy(output, old_unused, unused);
			n += unused;
			unused = 0;
		} else {
			memcpy(output, old_unused, need);
			n += need;
			unused -= need;
			memcpy(old_unused, &old_unused[need], unused);
		}
	}
	/*
	 * If we need more use the simulated randomness here.
	 */
	if (n < size) {
		dst_work *my_work = (dst_work *) malloc(sizeof(dst_work));
		if (my_work == NULL)
			return (n);
		my_work->needed = size - n;
		my_work->filled = 0;
		my_work->output = (u_char *) malloc(my_work->needed +
						    DST_HASH_SIZE *
						    DST_NUM_HASHES);
		my_work->file_digest = NULL;
		if (my_work->output == NULL)
			return (n);
		memset(my_work->output, 0x0, my_work->needed);
/* allocate upto 4 different HMAC hash functions out of order */
#if DST_NUM_HASHES >= 3
		my_work->hash[2] = get_hmac_key(3, DST_RANDOM_BLOCK_SIZE / 2);
#endif
#if DST_NUM_HASHES >= 2
		my_work->hash[1] = get_hmac_key(7, DST_RANDOM_BLOCK_SIZE / 6);
#endif
#if DST_NUM_HASHES >= 4
		my_work->hash[3] = get_hmac_key(5, DST_RANDOM_BLOCK_SIZE / 4);
#endif
		my_work->hash[0] = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE);
		if (my_work->hash[0] == NULL)	/* if failure bail out */
			return (n);
		s = own_random(my_work);
/* if more generated than needed store it for future use */
		if (s >= my_work->needed) {
			EREPORT(("dst_s_random(): More than needed %d >= %d\n",
				 s, my_work->needed));
			memcpy(&output[n], my_work->output, my_work->needed);
			n += my_work->needed;
			/* saving unused data for next time */
			unused = s - my_work->needed;
			memcpy(old_unused, &my_work->output[my_work->needed],
			       unused);
		} else {
			/* XXXX This should not happen */
			EREPORT(("Not enough %d >= %d\n", s, my_work->needed));
			memcpy(&output[n], my_work->output, s);
			n += my_work->needed;
		}

/* delete the allocated work area */
		for (i = 0; i < DST_NUM_HASHES; i++) {
			dst_free_key(my_work->hash[i]->key);
			SAFE_FREE(my_work->hash[i]);
		}
		SAFE_FREE(my_work->output);
		SAFE_FREE(my_work);
	}
	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
dst_s_semi_random(u_char *output, unsigned size)
{
	static u_int32_t counter[DST_NUMBER_OF_COUNTERS];
	static u_char semi_old[DST_HASH_SIZE];
	static int semi_loc = 0, cnt = 0;
	static unsigned hb_size = 0;
	static DST_KEY *my_key = NULL;
	prand_hash *hash;
	unsigned out = 0;
	unsigned i;
	int n;

	if (output == NULL || size <= 0)
		return (-2);

/* check if we need a new key */
	if (my_key == NULL || cnt > (1 << 25)) {	/* get HMAC KEY */
		if (my_key)
			my_key->dk_func->destroy(my_key);
		if ((hash = get_hmac_key(1, DST_RANDOM_BLOCK_SIZE)) == NULL)
			return (0);
		my_key = hash->key;
/* check if the key works stir the new key using some old random data */
		hb_size = dst_sign_data(SIG_MODE_ALL, my_key, NULL, 
				        (u_char *) counter, sizeof(counter),
					semi_old, sizeof(semi_old));
		if (hb_size <= 0) {
			EREPORT(("dst_s_semi_random() Sign of alg %d failed %d\n",
				 my_key->dk_alg, hb_size));
			return (-1);
		}
/* new set the counters to random values */
		dst_s_random((u_char *) counter, sizeof(counter));
		cnt = 0;
	}
/* if old data around use it first */
	if (semi_loc < hb_size) {
		if (size <= hb_size - semi_loc) {	/* need less */
			memcpy(output, &semi_old[semi_loc], size);
			semi_loc += size;
			return (size);	/* DONE */
		} else {
			out = hb_size - semi_loc;
			memcpy(output, &semi_old[semi_loc], out);
			semi_loc += out;
		}
	}
/* generate more randome stuff */
	while (out < size) {
		/* 
		 * 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]++;

		i = dst_sign_data(SIG_MODE_ALL, my_key, NULL, 
				  (u_char *) counter, hb_size,
				  semi_old, sizeof(semi_old));
		if (i != hb_size)
			EREPORT(("HMAC SIGNATURE FAILURE %d\n", i));
		cnt++;
		if (size - out < i)	/* Not all data is needed */
			semi_loc = i = size - out;
		memcpy(&output[out], semi_old, i);
		out += i;
	}
	return (out);
}