random.c

来自「linux 内核源代码」· C语言 代码 · 共 1,669 行 · 第 1/4 页

	.lock = __SPIN_LOCK_UNLOCKED(&input_pool.lock),
	.pool = input_pool_data
};

static struct entropy_store blocking_pool = {
	.poolinfo = &poolinfo_table[1],
	.name = "blocking",
	.limit = 1,
	.pull = &input_pool,
	.lock = __SPIN_LOCK_UNLOCKED(&blocking_pool.lock),
	.pool = blocking_pool_data
};

static struct entropy_store nonblocking_pool = {
	.poolinfo = &poolinfo_table[1],
	.name = "nonblocking",
	.pull = &input_pool,
	.lock = __SPIN_LOCK_UNLOCKED(&nonblocking_pool.lock),
	.pool = nonblocking_pool_data
};

/*
 * This function adds a byte into the entropy "pool".  It does not
 * update the entropy estimate.  The caller should call
 * credit_entropy_store if this is appropriate.
 *
 * The pool is stirred with a primitive polynomial of the appropriate
 * degree, and then twisted.  We twist by three bits at a time because
 * it's cheap to do so and helps slightly in the expected case where
 * the entropy is concentrated in the low-order bits.
 */
static void __add_entropy_words(struct entropy_store *r, const __u32 *in,
				int nwords, __u32 out[16])
{
	static __u32 const twist_table[8] = {
		0x00000000, 0x3b6e20c8, 0x76dc4190, 0x4db26158,
		0xedb88320, 0xd6d6a3e8, 0x9b64c2b0, 0xa00ae278 };
	unsigned long i, add_ptr, tap1, tap2, tap3, tap4, tap5;
	int new_rotate, input_rotate;
	int wordmask = r->poolinfo->poolwords - 1;
	__u32 w, next_w;
	unsigned long flags;

	/* Taps are constant, so we can load them without holding r->lock.  */
	tap1 = r->poolinfo->tap1;
	tap2 = r->poolinfo->tap2;
	tap3 = r->poolinfo->tap3;
	tap4 = r->poolinfo->tap4;
	tap5 = r->poolinfo->tap5;
	next_w = *in++;

	spin_lock_irqsave(&r->lock, flags);
	prefetch_range(r->pool, wordmask);
	input_rotate = r->input_rotate;
	add_ptr = r->add_ptr;

	while (nwords--) {
		w = rol32(next_w, input_rotate);
		if (nwords > 0)
			next_w = *in++;
		i = add_ptr = (add_ptr - 1) & wordmask;
		/*
		 * Normally, we add 7 bits of rotation to the pool.
		 * At the beginning of the pool, add an extra 7 bits
		 * rotation, so that successive passes spread the
		 * input bits across the pool evenly.
		 */
		new_rotate = input_rotate + 14;
		if (i)
			new_rotate = input_rotate + 7;
		input_rotate = new_rotate & 31;

		/* XOR in the various taps */
		w ^= r->pool[(i + tap1) & wordmask];
		w ^= r->pool[(i + tap2) & wordmask];
		w ^= r->pool[(i + tap3) & wordmask];
		w ^= r->pool[(i + tap4) & wordmask];
		w ^= r->pool[(i + tap5) & wordmask];
		w ^= r->pool[i];
		r->pool[i] = (w >> 3) ^ twist_table[w & 7];
	}

	r->input_rotate = input_rotate;
	r->add_ptr = add_ptr;

	if (out) {
		for (i = 0; i < 16; i++) {
			out[i] = r->pool[add_ptr];
			add_ptr = (add_ptr - 1) & wordmask;
		}
	}

	spin_unlock_irqrestore(&r->lock, flags);
}

static inline void add_entropy_words(struct entropy_store *r, const __u32 *in,
				     int nwords)
{
	__add_entropy_words(r, in, nwords, NULL);
}

/*
 * Credit (or debit) the entropy store with n bits of entropy
 */
static void credit_entropy_store(struct entropy_store *r, int nbits)
{
	unsigned long flags;

	spin_lock_irqsave(&r->lock, flags);

	if (r->entropy_count + nbits < 0) {
		DEBUG_ENT("negative entropy/overflow (%d+%d)\n",
			  r->entropy_count, nbits);
		r->entropy_count = 0;
	} else if (r->entropy_count + nbits > r->poolinfo->POOLBITS) {
		r->entropy_count = r->poolinfo->POOLBITS;
	} else {
		r->entropy_count += nbits;
		if (nbits)
			DEBUG_ENT("added %d entropy credits to %s\n",
				  nbits, r->name);
	}

	spin_unlock_irqrestore(&r->lock, flags);
}

/*********************************************************************
 *
 * Entropy input management
 *
 *********************************************************************/

/* There is one of these per entropy source */
struct timer_rand_state {
	cycles_t last_time;
	long last_delta,last_delta2;
	unsigned dont_count_entropy:1;
};

static struct timer_rand_state input_timer_state;
static struct timer_rand_state *irq_timer_state[NR_IRQS];

/*
 * This function adds entropy to the entropy "pool" by using timing
 * delays.  It uses the timer_rand_state structure to make an estimate
 * of how many bits of entropy this call has added to the pool.
 *
 * The number "num" is also added to the pool - it should somehow describe
 * the type of event which just happened.  This is currently 0-255 for
 * keyboard scan codes, and 256 upwards for interrupts.
 *
 */
static void add_timer_randomness(struct timer_rand_state *state, unsigned num)
{
	struct {
		cycles_t cycles;
		long jiffies;
		unsigned num;
	} sample;
	long delta, delta2, delta3;

	preempt_disable();
	/* if over the trickle threshold, use only 1 in 4096 samples */
	if (input_pool.entropy_count > trickle_thresh &&
	    (__get_cpu_var(trickle_count)++ & 0xfff))
		goto out;

	sample.jiffies = jiffies;
	sample.cycles = get_cycles();
	sample.num = num;
	add_entropy_words(&input_pool, (u32 *)&sample, sizeof(sample)/4);

	/*
	 * Calculate number of bits of randomness we probably added.
	 * We take into account the first, second and third-order deltas
	 * in order to make our estimate.
	 */

	if (!state->dont_count_entropy) {
		delta = sample.jiffies - state->last_time;
		state->last_time = sample.jiffies;

		delta2 = delta - state->last_delta;
		state->last_delta = delta;

		delta3 = delta2 - state->last_delta2;
		state->last_delta2 = delta2;

		if (delta < 0)
			delta = -delta;
		if (delta2 < 0)
			delta2 = -delta2;
		if (delta3 < 0)
			delta3 = -delta3;
		if (delta > delta2)
			delta = delta2;
		if (delta > delta3)
			delta = delta3;

		/*
		 * delta is now minimum absolute delta.
		 * Round down by 1 bit on general principles,
		 * and limit entropy entimate to 12 bits.
		 */
		credit_entropy_store(&input_pool,
				     min_t(int, fls(delta>>1), 11));
	}

	if(input_pool.entropy_count >= random_read_wakeup_thresh)
		wake_up_interruptible(&random_read_wait);

out:
	preempt_enable();
}

void add_input_randomness(unsigned int type, unsigned int code,
				 unsigned int value)
{
	static unsigned char last_value;

	/* ignore autorepeat and the like */
	if (value == last_value)
		return;

	DEBUG_ENT("input event\n");
	last_value = value;
	add_timer_randomness(&input_timer_state,
			     (type << 4) ^ code ^ (code >> 4) ^ value);
}
EXPORT_SYMBOL_GPL(add_input_randomness);

void add_interrupt_randomness(int irq)
{
	if (irq >= NR_IRQS || irq_timer_state[irq] == NULL)
		return;

	DEBUG_ENT("irq event %d\n", irq);
	add_timer_randomness(irq_timer_state[irq], 0x100 + irq);
}

#ifdef CONFIG_BLOCK
void add_disk_randomness(struct gendisk *disk)
{
	if (!disk || !disk->random)
		return;
	/* first major is 1, so we get >= 0x200 here */
	DEBUG_ENT("disk event %d:%d\n", disk->major, disk->first_minor);

	add_timer_randomness(disk->random,
			     0x100 + MKDEV(disk->major, disk->first_minor));
}

EXPORT_SYMBOL(add_disk_randomness);
#endif

#define EXTRACT_SIZE 10

/*********************************************************************
 *
 * Entropy extraction routines
 *
 *********************************************************************/

static ssize_t extract_entropy(struct entropy_store *r, void * buf,
			       size_t nbytes, int min, int rsvd);

/*
 * This utility inline function is responsible for transfering entropy
 * from the primary pool to the secondary extraction pool. We make
 * sure we pull enough for a 'catastrophic reseed'.
 */
static void xfer_secondary_pool(struct entropy_store *r, size_t nbytes)
{
	__u32 tmp[OUTPUT_POOL_WORDS];

	if (r->pull && r->entropy_count < nbytes * 8 &&
	    r->entropy_count < r->poolinfo->POOLBITS) {
		/* If we're limited, always leave two wakeup worth's BITS */
		int rsvd = r->limit ? 0 : random_read_wakeup_thresh/4;
		int bytes = nbytes;

		/* pull at least as many as BYTES as wakeup BITS */
		bytes = max_t(int, bytes, random_read_wakeup_thresh / 8);
		/* but never more than the buffer size */
		bytes = min_t(int, bytes, sizeof(tmp));

		DEBUG_ENT("going to reseed %s with %d bits "
			  "(%d of %d requested)\n",
			  r->name, bytes * 8, nbytes * 8, r->entropy_count);

		bytes=extract_entropy(r->pull, tmp, bytes,
				      random_read_wakeup_thresh / 8, rsvd);
		add_entropy_words(r, tmp, (bytes + 3) / 4);
		credit_entropy_store(r, bytes*8);
	}
}

/*
 * These functions extracts randomness from the "entropy pool", and
 * returns it in a buffer.
 *
 * The min parameter specifies the minimum amount we can pull before
 * failing to avoid races that defeat catastrophic reseeding while the
 * reserved parameter indicates how much entropy we must leave in the
 * pool after each pull to avoid starving other readers.
 *
 * Note: extract_entropy() assumes that .poolwords is a multiple of 16 words.
 */

static size_t account(struct entropy_store *r, size_t nbytes, int min,
		      int reserved)
{
	unsigned long flags;

	BUG_ON(r->entropy_count > r->poolinfo->POOLBITS);

	/* Hold lock while accounting */
	spin_lock_irqsave(&r->lock, flags);

	DEBUG_ENT("trying to extract %d bits from %s\n",
		  nbytes * 8, r->name);

	/* Can we pull enough? */
	if (r->entropy_count / 8 < min + reserved) {
		nbytes = 0;
	} else {
		/* If limited, never pull more than available */
		if (r->limit && nbytes + reserved >= r->entropy_count / 8)
			nbytes = r->entropy_count/8 - reserved;

		if(r->entropy_count / 8 >= nbytes + reserved)
			r->entropy_count -= nbytes*8;
		else
			r->entropy_count = reserved;

		if (r->entropy_count < random_write_wakeup_thresh)
			wake_up_interruptible(&random_write_wait);
	}

	DEBUG_ENT("debiting %d entropy credits from %s%s\n",
		  nbytes * 8, r->name, r->limit ? "" : " (unlimited)");

	spin_unlock_irqrestore(&r->lock, flags);

	return nbytes;
}

static void extract_buf(struct entropy_store *r, __u8 *out)
{
	int i;
	__u32 data[16], buf[5 + SHA_WORKSPACE_WORDS];

	sha_init(buf);
	/*
	 * As we hash the pool, we mix intermediate values of
	 * the hash back into the pool.  This eliminates
	 * backtracking attacks (where the attacker knows
	 * the state of the pool plus the current outputs, and
	 * attempts to find previous ouputs), unless the hash
	 * function can be inverted.
	 */
	for (i = 0; i < r->poolinfo->poolwords; i += 16) {
		/* hash blocks of 16 words = 512 bits */
		sha_transform(buf, (__u8 *)(r->pool + i), buf + 5);
		/* feed back portion of the resulting hash */
		add_entropy_words(r, &buf[i % 5], 1);
	}

	/*
	 * To avoid duplicates, we atomically extract a
	 * portion of the pool while mixing, and hash one
	 * final time.
	 */
	__add_entropy_words(r, &buf[i % 5], 1, data);
	sha_transform(buf, (__u8 *)data, buf + 5);

	/*
	 * In case the hash function has some recognizable
	 * output pattern, we fold it in half.
	 */

	buf[0] ^= buf[3];
	buf[1] ^= buf[4];
	buf[2] ^= rol32(buf[2], 16);
	memcpy(out, buf, EXTRACT_SIZE);
	memset(buf, 0, sizeof(buf));
}

static ssize_t extract_entropy(struct entropy_store *r, void * buf,
			       size_t nbytes, int min, int reserved)
{
	ssize_t ret = 0, i;
	__u8 tmp[EXTRACT_SIZE];

	xfer_secondary_pool(r, nbytes);
	nbytes = account(r, nbytes, min, reserved);

	while (nbytes) {
		extract_buf(r, tmp);
		i = min_t(int, nbytes, EXTRACT_SIZE);
		memcpy(buf, tmp, i);
		nbytes -= i;
		buf += i;
		ret += i;
	}

	/* Wipe data just returned from memory */
	memset(tmp, 0, sizeof(tmp));

	return ret;
}

static ssize_t extract_entropy_user(struct entropy_store *r, void __user *buf,
				    size_t nbytes)
{
	ssize_t ret = 0, i;
	__u8 tmp[EXTRACT_SIZE];