random.c

讲述linux的初始化过程

 *
 * Sysctl interface
 *
 ********************************************************************/

#ifdef CONFIG_SYSCTL

#include <linux/sysctl.h>

static int sysctl_poolsize;
static int min_read_thresh, max_read_thresh;
static int min_write_thresh, max_write_thresh;
static char sysctl_bootid[16];

/*
 * This function handles a request from the user to change the pool size 
 * of the primary entropy store.
 */
static int change_poolsize(int poolsize)
{
	struct entropy_store	*new_store, *old_store;
	int			ret;
	
	if ((ret = create_entropy_store(poolsize, &new_store)))
		return ret;

	add_entropy_words(new_store, random_state->pool,
			  random_state->poolinfo.poolwords);
	credit_entropy_store(new_store, random_state->entropy_count);

	sysctl_init_random(new_store);
	old_store = random_state;
	random_state = batch_tqueue.data = new_store;
	free_entropy_store(old_store);
	return 0;
}

static int proc_do_poolsize(ctl_table *table, int write, struct file *filp,
			    void *buffer, size_t *lenp)
{
	int	ret;

	sysctl_poolsize = random_state->poolinfo.poolwords * 4;

	ret = proc_dointvec(table, write, filp, buffer, lenp);
	if (ret || !write ||
	    (sysctl_poolsize == random_state->poolinfo.poolwords * 4))
		return ret;

	return change_poolsize(sysctl_poolsize);
}

static int poolsize_strategy(ctl_table *table, int *name, int nlen,
			     void *oldval, size_t *oldlenp,
			     void *newval, size_t newlen, void **context)
{
	int	len;
	
	sysctl_poolsize = random_state->poolinfo.poolwords * 4;

	/*
	 * We only handle the write case, since the read case gets
	 * handled by the default handler (and we don't care if the
	 * write case happens twice; it's harmless).
	 */
	if (newval && newlen) {
		len = newlen;
		if (len > table->maxlen)
			len = table->maxlen;
		if (copy_from_user(table->data, newval, len))
			return -EFAULT;
	}

	if (sysctl_poolsize != random_state->poolinfo.poolwords * 4)
		return change_poolsize(sysctl_poolsize);

	return 0;
}

/*
 * These functions is used to return both the bootid UUID, and random
 * UUID.  The difference is in whether table->data is NULL; if it is,
 * then a new UUID is generated and returned to the user.
 * 
 * If the user accesses this via the proc interface, it will be returned
 * as an ASCII string in the standard UUID format.  If accesses via the 
 * sysctl system call, it is returned as 16 bytes of binary data.
 */
static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
			void *buffer, size_t *lenp)
{
	ctl_table	fake_table;
	unsigned char	buf[64], tmp_uuid[16], *uuid;

	uuid = table->data;
	if (!uuid) {
		uuid = tmp_uuid;
		uuid[8] = 0;
	}
	if (uuid[8] == 0)
		generate_random_uuid(uuid);

	sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
		"%02x%02x%02x%02x%02x%02x",
		uuid[0],  uuid[1],  uuid[2],  uuid[3],
		uuid[4],  uuid[5],  uuid[6],  uuid[7],
		uuid[8],  uuid[9],  uuid[10], uuid[11],
		uuid[12], uuid[13], uuid[14], uuid[15]);
	fake_table.data = buf;
	fake_table.maxlen = sizeof(buf);

	return proc_dostring(&fake_table, write, filp, buffer, lenp);
}

static int uuid_strategy(ctl_table *table, int *name, int nlen,
			 void *oldval, size_t *oldlenp,
			 void *newval, size_t newlen, void **context)
{
	unsigned char	tmp_uuid[16], *uuid;
	int	len;

	if (!oldval || !oldlenp)
		return 1;

	uuid = table->data;
	if (!uuid) {
		uuid = tmp_uuid;
		uuid[8] = 0;
	}
	if (uuid[8] == 0)
		generate_random_uuid(uuid);

	get_user(len, oldlenp);
	if (len) {
		if (len > 16)
			len = 16;
		if (copy_to_user(oldval, table->data, len))
			return -EFAULT;
		if (put_user(len, oldlenp))
			return -EFAULT;
	}
	return 1;
}

ctl_table random_table[] = {
	{RANDOM_POOLSIZE, "poolsize",
	 &sysctl_poolsize, sizeof(int), 0644, NULL,
	 &proc_do_poolsize, &poolsize_strategy},
	{RANDOM_ENTROPY_COUNT, "entropy_avail",
	 NULL, sizeof(int), 0444, NULL,
	 &proc_dointvec},
	{RANDOM_READ_THRESH, "read_wakeup_threshold",
	 &random_read_wakeup_thresh, sizeof(int), 0644, NULL,
	 &proc_dointvec_minmax, &sysctl_intvec, 0,
	 &min_read_thresh, &max_read_thresh},
	{RANDOM_WRITE_THRESH, "write_wakeup_threshold",
	 &random_write_wakeup_thresh, sizeof(int), 0644, NULL,
	 &proc_dointvec_minmax, &sysctl_intvec, 0,
	 &min_write_thresh, &max_write_thresh},
	{RANDOM_BOOT_ID, "boot_id",
	 &sysctl_bootid, 16, 0444, NULL,
	 &proc_do_uuid, &uuid_strategy},
	{RANDOM_UUID, "uuid",
	 NULL, 16, 0444, NULL,
	 &proc_do_uuid, &uuid_strategy},
	{0}
};

static void sysctl_init_random(struct entropy_store *random_state)
{
	min_read_thresh = 8;
	min_write_thresh = 0;
	max_read_thresh = max_write_thresh =
		random_state->poolinfo.poolwords * 32;
	random_table[1].data = &random_state->entropy_count;
}
#endif 	/* CONFIG_SYSCTL */

/********************************************************************
 *
 * Random funtions for networking
 *
 ********************************************************************/

/*
 * TCP initial sequence number picking.  This uses the random number
 * generator to pick an initial secret value.  This value is hashed
 * along with the TCP endpoint information to provide a unique
 * starting point for each pair of TCP endpoints.  This defeats
 * attacks which rely on guessing the initial TCP sequence number.
 * This algorithm was suggested by Steve Bellovin.
 *
 * Using a very strong hash was taking an appreciable amount of the total
 * TCP connection establishment time, so this is a weaker hash,
 * compensated for by changing the secret periodically.
 */

/* F, G and H are basic MD4 functions: selection, majority, parity */
#define F(x, y, z) ((z) ^ ((x) & ((y) ^ (z))))
#define G(x, y, z) (((x) & (y)) + (((x) ^ (y)) & (z)))
#define H(x, y, z) ((x) ^ (y) ^ (z))

/*
 * The generic round function.  The application is so specific that
 * we don't bother protecting all the arguments with parens, as is generally
 * good macro practice, in favor of extra legibility.
 * Rotation is separate from addition to prevent recomputation
 */
#define ROUND(f, a, b, c, d, x, s)	\
	(a += f(b, c, d) + x, a = (a << s) | (a >> (32-s)))
#define K1 0
#define K2 013240474631UL
#define K3 015666365641UL

/*
 * Basic cut-down MD4 transform.  Returns only 32 bits of result.
 */
static __u32 halfMD4Transform (__u32 const buf[4], __u32 const in[8])
{
	__u32	a = buf[0], b = buf[1], c = buf[2], d = buf[3];

	/* Round 1 */
	ROUND(F, a, b, c, d, in[0] + K1,  3);
	ROUND(F, d, a, b, c, in[1] + K1,  7);
	ROUND(F, c, d, a, b, in[2] + K1, 11);
	ROUND(F, b, c, d, a, in[3] + K1, 19);
	ROUND(F, a, b, c, d, in[4] + K1,  3);
	ROUND(F, d, a, b, c, in[5] + K1,  7);
	ROUND(F, c, d, a, b, in[6] + K1, 11);
	ROUND(F, b, c, d, a, in[7] + K1, 19);

	/* Round 2 */
	ROUND(G, a, b, c, d, in[1] + K2,  3);
	ROUND(G, d, a, b, c, in[3] + K2,  5);
	ROUND(G, c, d, a, b, in[5] + K2,  9);
	ROUND(G, b, c, d, a, in[7] + K2, 13);
	ROUND(G, a, b, c, d, in[0] + K2,  3);
	ROUND(G, d, a, b, c, in[2] + K2,  5);
	ROUND(G, c, d, a, b, in[4] + K2,  9);
	ROUND(G, b, c, d, a, in[6] + K2, 13);

	/* Round 3 */
	ROUND(H, a, b, c, d, in[3] + K3,  3);
	ROUND(H, d, a, b, c, in[7] + K3,  9);
	ROUND(H, c, d, a, b, in[2] + K3, 11);
	ROUND(H, b, c, d, a, in[6] + K3, 15);
	ROUND(H, a, b, c, d, in[1] + K3,  3);
	ROUND(H, d, a, b, c, in[5] + K3,  9);
	ROUND(H, c, d, a, b, in[0] + K3, 11);
	ROUND(H, b, c, d, a, in[4] + K3, 15);

	return buf[1] + b;	/* "most hashed" word */
	/* Alternative: return sum of all words? */
}

#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)

static __u32 twothirdsMD4Transform (__u32 const buf[4], __u32 const in[12])
{
	__u32	a = buf[0], b = buf[1], c = buf[2], d = buf[3];

	/* Round 1 */
	ROUND(F, a, b, c, d, in[ 0] + K1,  3);
	ROUND(F, d, a, b, c, in[ 1] + K1,  7);
	ROUND(F, c, d, a, b, in[ 2] + K1, 11);
	ROUND(F, b, c, d, a, in[ 3] + K1, 19);
	ROUND(F, a, b, c, d, in[ 4] + K1,  3);
	ROUND(F, d, a, b, c, in[ 5] + K1,  7);
	ROUND(F, c, d, a, b, in[ 6] + K1, 11);
	ROUND(F, b, c, d, a, in[ 7] + K1, 19);
	ROUND(F, a, b, c, d, in[ 8] + K1,  3);
	ROUND(F, d, a, b, c, in[ 9] + K1,  7);
	ROUND(F, c, d, a, b, in[10] + K1, 11);
	ROUND(F, b, c, d, a, in[11] + K1, 19);

	/* Round 2 */
	ROUND(G, a, b, c, d, in[ 1] + K2,  3);
	ROUND(G, d, a, b, c, in[ 3] + K2,  5);
	ROUND(G, c, d, a, b, in[ 5] + K2,  9);
	ROUND(G, b, c, d, a, in[ 7] + K2, 13);
	ROUND(G, a, b, c, d, in[ 9] + K2,  3);
	ROUND(G, d, a, b, c, in[11] + K2,  5);
	ROUND(G, c, d, a, b, in[ 0] + K2,  9);
	ROUND(G, b, c, d, a, in[ 2] + K2, 13);
	ROUND(G, a, b, c, d, in[ 4] + K2,  3);
	ROUND(G, d, a, b, c, in[ 6] + K2,  5);
	ROUND(G, c, d, a, b, in[ 8] + K2,  9);
	ROUND(G, b, c, d, a, in[10] + K2, 13);

	/* Round 3 */
	ROUND(H, a, b, c, d, in[ 3] + K3,  3);
	ROUND(H, d, a, b, c, in[ 7] + K3,  9);
	ROUND(H, c, d, a, b, in[11] + K3, 11);
	ROUND(H, b, c, d, a, in[ 2] + K3, 15);
	ROUND(H, a, b, c, d, in[ 6] + K3,  3);
	ROUND(H, d, a, b, c, in[10] + K3,  9);
	ROUND(H, c, d, a, b, in[ 1] + K3, 11);
	ROUND(H, b, c, d, a, in[ 5] + K3, 15);
	ROUND(H, a, b, c, d, in[ 9] + K3,  3);
	ROUND(H, d, a, b, c, in[ 0] + K3,  9);
	ROUND(H, c, d, a, b, in[ 4] + K3, 11);
	ROUND(H, b, c, d, a, in[ 8] + K3, 15);

	return buf[1] + b;	/* "most hashed" word */
	/* Alternative: return sum of all words? */
}
#endif

#undef ROUND
#undef F
#undef G
#undef H
#undef K1
#undef K2
#undef K3

/* This should not be decreased so low that ISNs wrap too fast. */
#define REKEY_INTERVAL	300
#define HASH_BITS 24

#if defined(CONFIG_IPV6) || defined(CONFIG_IPV6_MODULE)
__u32 secure_tcpv6_sequence_number(__u32 *saddr, __u32 *daddr,
				   __u16 sport, __u16 dport)
{
	static __u32	rekey_time;
	static __u32	count;
	static __u32	secret[12];
	struct timeval 	tv;
	__u32		seq;

	/* The procedure is the same as for IPv4, but addresses are longer. */

	do_gettimeofday(&tv);	/* We need the usecs below... */

	if (!rekey_time || (tv.tv_sec - rekey_time) > REKEY_INTERVAL) {
		rekey_time = tv.tv_sec;
		/* First five words are overwritten below. */
		get_random_bytes(&secret[5], sizeof(secret)-5*4);
		count = (tv.tv_sec/REKEY_INTERVAL) << HASH_BITS;
	}

	memcpy(secret, saddr, 16);
	secret[4]=(sport << 16) + dport;

	seq = (twothirdsMD4Transform(daddr, secret) &
	       ((1<<HASH_BITS)-1)) + count;

	seq += tv.tv_usec + tv.tv_sec*1000000;
	return seq;
}

__u32 secure_ipv6_id(__u32 *daddr)
{
	static time_t	rekey_time;
	static __u32	secret[12];
	time_t		t;

	/*
	 * Pick a random secret every REKEY_INTERVAL seconds.
	 */
	t = CURRENT_TIME;
	if (!rekey_time || (t - rekey_time) > REKEY_INTERVAL) {
		rekey_time = t;
		/* First word is overwritten below. */
		get_random_bytes(secret, sizeof(secret));
	}

	return twothirdsMD4Transform(daddr, secret);
}

#endif


__u32 secure_tcp_sequence_number(__u32 saddr, __u32 daddr,
				 __u16 sport, __u16 dport)
{
	static __u32	rekey_time;
	static __u32	count;
	static __u32	secret[12];
	struct timeval 	tv;
	__u32		seq;

	/*
	 * Pick a random secret every REKEY_INTERVAL seconds.
	 */
	do_gettimeofday(&tv);	/* We need the usecs below... */

	if (!rekey_time || (tv.tv_sec - rekey_time) > REKEY_INTERVAL) {
		rekey_time = tv.tv_sec;
		/* First three words are overwritten below. */
		get_random_bytes(&secret[3], sizeof(secret)-12);
		count = (tv.tv_sec/REKEY_INTERVAL) << HASH_BITS;
	}

	/*
	 *  Pick a unique starting offset for each TCP connection endpoints
	 *  (saddr, daddr, sport, dport).
	 *  Note that the words are placed into the first words to be
	 *  mixed in with the halfMD4.  This is because the starting
	 *  vector is also a random secret (at secret+8), and further
	 *  hashing fixed data into it isn't going to improve anything,
	 *  so we should get started with the variable data.
	 */
	secret[0]=saddr;
	secret[1]=daddr;
	secret[2]=(sport << 16) + dport;

	seq = (halfMD4Transform(secret+8, secret) &
	       ((1<<HASH_BITS)-1)) + count;

	/*
	 *	As close as possible to RFC 793, which
	 *	suggests using a 250 kHz clock.
	 *	Further reading shows this assumes 2 Mb/s networks.
	 *	For 10 Mb/s Ethernet, a 1 MHz clock is appropriate.
	 *	That's funny, Linux has one built i