不只是 rand() 的 RNG

#include <stdlib.h>
#include <time.h>
int main{
    srand((unsigned)time(NULL));
    printf("%d",rand());
}

• You could use mouse event, or last interrupt time xor its type as seed?

Let's see how rand() works

int __random_r (struct random_data *buf, int32_t *result){
.
.
    int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff;
    state[0] = val;
    *result = val;
.

Source

Linear Congruential Generator
\[ S_{n+1} = (aS_n + c) \ mod \ m,\ S_n \in \{0,1,... m -1 \} \]

int __random_r (struct random_data *buf, int32_t *result){
.
.
    int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff;
    state[0] = val;
    *result = val;
.

If we want to reach a counter with a period of \(m\). \(a\), \(c\), \(m\) should satisfy the Hull-Dobell theorem. (Theorem 1)

Mersenne twister

• random used in python, R, Ruby, Matlab …
• has \(2^{19937}−1\) states, but it doesn't mean it has high quaility.

LSFR is used widely in Linux Kernel RNG

Before…

RNG in Linux Kernel

• /dev/random (blocked)
• /dev/urandom (non-blocked)
  • above call the same function finally
• /dev/hwrng (for hardware)

cat /dev/{u}random
cat /dev/hwrng

• Entropy Collection
• Entropy Extraction
• Entropy Expansion
• Entropy Sources

Entropy Collection

• Use LFSR before (commit)
• now use BLAKE2S as cryptographic hash function(It's fast)
• Doesn't have pitfall that LFSR had

blake2s_update(&entropy_pool, input, sizeof(input));

Entropy Extraction

• Use RDSEED RDRAND as salt

static void extract_entropy(void *buf, size_t len){
	spin_lock_irqsave(&input_pool.lock, flags);
	/* seed = HASHPRF(last_key, entropy_input) */
	blake2s_final(&input_pool.hash, seed);

	/* next_key = HASHPRF(seed, RDSEED || 0) */
	blake2s(next_key, (u8 *)&block, seed, sizeof(next_key), sizeof(block), sizeof(seed));
	blake2s_init_key(&input_pool.hash, BLAKE2S_HASH_SIZE, next_key, sizeof(next_key));

	spin_unlock_irqrestore(&input_pool.lock, flags);
	memzero_explicit(next_key, sizeof(next_key));

	while (len) {
		i = min_t(size_t, len, BLAKE2S_HASH_SIZE);
		/* output = HASHPRF(seed, RDSEED || ++counter) */
		++block.counter;
		blake2s(buf, (u8 *)&block, seed, i, sizeof(block), sizeof(seed));
...
}

Entropy Expansion

• From Entropy Extraction, we got 32 bytes output
• Use ChaCha20 (a stream cipher)

static void _get_random_bytes(void *buf, size_t len)
{
	...
	first_block_len = min_t(size_t, 32, len);
	crng_make_state(chacha_state, buf, first_block_len);
	len -= first_block_len;
	buf += first_block_len;
	...

	...
	while (len) {
		if (len < CHACHA_BLOCK_SIZE) {
			chacha20_block(chacha_state, tmp);
			memcpy(buf, tmp, len);
			memzero_explicit(tmp, sizeof(tmp));
			break;
		}

		chacha20_block(chacha_state, buf);
		if (unlikely(chacha_state[12] == 0))
			++chacha_state[13];
		len -= CHACHA_BLOCK_SIZE;
		buf += CHACHA_BLOCK_SIZE;
	}
    ...
}

add_interrupt_randomness()

• called by interrupt handler
• Maybe the primary source and most important source. (It takes about 60% entropy sources in my experiment.)
• mix of irq and random_get_entropy()
• Add into fast-pool with easy siphash
• After a bunch of interrupts, queues up a worker to dump these entropy into main tool.

	if (!timer_pending(&fast_pool->mix)) {
		fast_pool->mix.expires = jiffies;
		add_timer_on(&fast_pool->mix, raw_smp_processor_id());
	}

Linux Jitter Dance

https://github.com/torvalds/linux/commit/50ee7529ec45

static ssize_t urandom_read_iter(struct kiocb *kiocb, struct iov_iter *iter)
{
...
	if (!crng_ready())
		try_to_generate_entropy();
...
	return get_random_bytes_user(iter);
}

Linux Jitter Dance

• Speed up the early boot up
• Instead of waiting, doing something

static int jent_timer(char *data, size_t len)
{
        __u64 time, time2;
        time = time2 = 0;
...
        time = random_get_entropy();
        time2 = random_get_entropy();
        snprintf(data, len, "%lld\n", (time2 - time));
...
}

https://www.chronox.de/jent/doc/CPU-Jitter-NPTRNG.html

hw_register

/drivers/char/hw_random/core.c

int hwrng_register(struct hwrng *rng)
{
	...//check duplicate
	list_for_each_entry(tmp, &rng_list, list) {
		if (strcmp(tmp->name, rng->name) == 0)
			goto out_unlock;
	}
	...

	if (!current_rng ||
	    (!cur_rng_set_by_user && rng->quality > current_rng->quality)) {
		/*
		 * Set new rng as current as the new rng source
		 * provides better entropy quality and was not
		 * chosen by userspace.
		 */
		err = set_current_rng(rng);
		if (err)
			goto out_unlock;
		/* to use current_rng in add_early_randomness() we need
		 * to take a ref
		 */
		is_new_current = true;
		kref_get(&rng->ref);
	}
	...
	if (is_new_current || !rng->init) {
		add_early_randomness(rng);
	}
	...
}

Implement a simple zero hwrng

static struct hwrng zero_rng = {
    .name= "zero_rng",
    .read = zero_rng_read
};

static int zero_rng_init(void){
    return hwrng_register(&zero_rng);
}

static int zero_rng_read(struct hwrng*rng, void *data, size_t max, bool wait){
    u8 *buf;
    buf = data;
    for(int i = 0;i<max;i++){
        buf[0];
    }
    return max;
}

use rdrand as hwrng output

void get_rdrand(uint8_t *mem){
    asm("rdrand %%rax\n\t"
    	"mov %%rax, %0\n\t"
    	:"=m"(*mem)::"0");
}
static int rdrand_rng_read(struct hwrng *rng, void *data, size_t max, bool wait)
{
    u8 *buf;
    u8 rnd8[8];
    buf = data;
    int i;
    for (i=0;i<max;i++){
	    if ((i%8)==0)
	        get_hw_rand2(rnd8);
	    buf[i] = rnd8[i%8];
    }
    return max;
}

dd if=/dev/hwrng/ of=hw bs=4096 count=1