はじめに

乱数の作成方法について気になったので、調査してみた。
せっかくだから資料として残すので参考にしてほしい。

題材から見てわかると思うが、今回の記事はあまり初心者向けではない。
できる限りわかりやすい記事を心掛けるが、細かくは説明できないかもしれないので悪しからず。

後で判明したが、
ChaCha20についての記事とBlake2bについての記事は読んでおくと、最後のほうの理解が楽になる。

(Blake2の記事はBlake2bだけど、処理内容はほとんど変わらない)

PCと真正乱数

真正乱数はざっくり言うと。
疑似乱数のように、アルゴリズムによってではなく、次の値を確実に予測できず、完全ランダムなもの。
厳密な定義が言いたいのではないので、そんなもんとして考えてほしい。

ここで言いたいことは、それをPCで生成する方法として、CPUの温度や時間を使用しているらしいということ。

（確かに、CPUの温度とか物理的な現象をセンサーで感知できれば良さそうだし、腑には落ちるけど）

どこのサイトを見ても実際のソースコードを確認せずに、
「ハードウェアやセンサーから情報を取得して乱数（エントロピー）を生成している」
という一言を入れて終了している。

...普通に気になる。
どうやっているんだろう？
ハードウェアの情報はどの程度使用している？
かなり気になる。
...なるよね？なるはず。

なので、実際にソースコードから真正乱数（および疑似乱数）の生成部分を読んでいくことにした。

Linuxでの乱数作成

読んでいくのはLinuxのソースコード。

windowsやMacOSとかも見ておきたかったけど、割愛する。
というより、
ソースコードがすぐに発見できないのと、時間かかりそうだったから止めた。

読む分にはこっちが読みやすかった。

使用するCPUはx86の想定で読み進めていく。

Linuxでは乱数の生成に/dev/randomか/dev/urandomが使われている。
よくある説明としては、

/dev/random 
　真正乱数生成器、遅いけど完全な乱数を生成できる

/dev/urandom 
　暗号論的疑似乱数生成器、seedを基にアルゴリズムで乱数を作成する。seedがばれなきゃ速くて安全。

上記のデバイスドライバからアルゴリズムを読み取っていく。

..先に言っておくと、実はentropy（seed）が十分な場合、上記の2つは同じものを表している

get_random

まずいきなりだが、/dev/randomをファイルとして開くよりgetrandom(2)を使用するほうが推奨されているので、そちらのソースを読む。
一応デバイスドライバの定義としては、

random.c

const struct file_operations random_fops = {
	.read_iter = random_read_iter,
	.write_iter = random_write_iter,
	.poll = random_poll,
	.unlocked_ioctl = random_ioctl,
	.compat_ioctl = compat_ptr_ioctl,
	.fasync = random_fasync,
	.llseek = noop_llseek,
	.splice_read = copy_splice_read,
	.splice_write = iter_file_splice_write,
};

const struct file_operations urandom_fops = {
	.read_iter = urandom_read_iter,
	.write_iter = random_write_iter,
	.unlocked_ioctl = random_ioctl,
	.compat_ioctl = compat_ptr_ioctl,
	.fasync = random_fasync,
	.llseek = noop_llseek,
	.splice_read = copy_splice_read,
	.splice_write = iter_file_splice_write,
};

となっている。
デバイスドライバの構造体の読み方は割愛するが、読み取りの部分で乱数を作成するはずなので、読み取り機能のみを抜粋。

random.c

const struct file_operations random_fops = {
	.read_iter = random_read_iter,
 ..
};

const struct file_operations urandom_fops = {
	.read_iter = urandom_read_iter,
 ..
};

読み取り部分のread_iterに入力されるrandom_read_iter関数を見てみる。

static ssize_t random_read_iter(struct kiocb *kiocb, struct iov_iter *iter)
{
	int ret;

	if (!crng_ready() &&
	    ((kiocb->ki_flags & (IOCB_NOWAIT | IOCB_NOIO)) ||
	     (kiocb->ki_filp->f_flags & O_NONBLOCK)))
		return -EAGAIN;

	ret = wait_for_random_bytes();
	if (ret != 0)
		return ret;
	return get_random_bytes_user(iter);
}

省略したurandomの部分と説明（真正乱数とはあまり関係ないので）

本筋に関係ないのでここで説明する。 urandomのソースコードは以下のようになっている。

static ssize_t urandom_read_iter(struct kiocb *kiocb, struct iov_iter *iter)
{
	static int maxwarn = 10;

	/*
	 * Opportunistically attempt to initialize the RNG on platforms that
	 * have fast cycle counters, but don't (for now) require it to succeed.
	 */
	if (!crng_ready())
		try_to_generate_entropy();

	if (!crng_ready()) {
		if (!ratelimit_disable && maxwarn <= 0)
			++urandom_warning.missed;
		else if (ratelimit_disable || __ratelimit(&urandom_warning)) {
			--maxwarn;
			pr_notice("%s: uninitialized urandom read (%zu bytes read)\n",
				  current->comm, iov_iter_count(iter));
		}
	}

	return get_random_bytes_user(iter);
}

これrandomの場合との違いは、crng_readyをifで受け取るかwhileで受け取るかの違い以外ほぼない。
つまりcrng(疑似乱数生成器）の準備ができるまで待機するrandom、待機しないurandomということになり、エントロピーが十分なら乱数処理自体は同じになる。

引き続き/dev/randomの説明に戻る

一方getrandom関数のほうを見てみると、

SYSCALL_DEFINE3(getrandom, char __user *, ubuf, size_t, len, unsigned int, flags)
{
	struct iov_iter iter;
	int ret;

	if (flags & ~(GRND_NONBLOCK | GRND_RANDOM | GRND_INSECURE))
		return -EINVAL;

	/*
	 * Requesting insecure and blocking randomness at the same time makes
	 * no sense.
	 */
	if ((flags & (GRND_INSECURE | GRND_RANDOM)) == (GRND_INSECURE | GRND_RANDOM))
		return -EINVAL;

	if (!crng_ready() && !(flags & GRND_INSECURE)) {
		if (flags & GRND_NONBLOCK)
			return -EAGAIN;
		ret = wait_for_random_bytes();
		if (unlikely(ret))
			return ret;
	}

	ret = import_ubuf(ITER_DEST, ubuf, len, &iter);
	if (unlikely(ret))
		return ret;
	return get_random_bytes_user(&iter);
}

どちらもcrng（暗号論的疑似乱数生成器）の、準備ができているとwait_for_random_bytesを呼び出す。
できていなければ、get_random_bytes_userを使用している。
(import_ubufに関しては、userサイドに対するiterの初期化処理しているだけなので実質同じ）

なので結果的に同じ関数を参照している。
以後はgetrandom(2)を前提として追っていく。
こんな感じ

getrandom() =>  
wait_for_bytes() || get_random_bytes_user()

まずはwait_for_bytesから読んでいく。

wait_for_random_bytes

random.c

int wait_for_random_bytes(void)
{
	while (!crng_ready()) {
		int ret;

		try_to_generate_entropy();
		ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ);
		if (ret)
			return ret > 0 ? 0 : ret;
	}
	return 0;
}

名前から見てエントロピーの生成処理。
また2つの関数処理を行っているので、読んでいく


getrandom() =>  
wait_for_bytes() => 
try_to_generate_entropy() && wait_event_interruptible_timeout()

この深堀していく工程が死ぬほど嫌いだけど、結果的にこうしていくほうが理解できるんだよね。。

try_to_generate_entropyのコード

static void __cold try_to_generate_entropy(void)
{
	enum { NUM_TRIAL_SAMPLES = 8192, MAX_SAMPLES_PER_BIT = HZ / 15 };
	u8 stack_bytes[sizeof(struct entropy_timer_state) + SMP_CACHE_BYTES - 1];
	struct entropy_timer_state *stack = PTR_ALIGN((void *)stack_bytes, SMP_CACHE_BYTES);
	unsigned int i, num_different = 0;
	unsigned long last = random_get_entropy();
	int cpu = -1;

	for (i = 0; i < NUM_TRIAL_SAMPLES - 1; ++i) {
		stack->entropy = random_get_entropy();
		if (stack->entropy != last)
			++num_different;
		last = stack->entropy;
	}
	stack->samples_per_bit = DIV_ROUND_UP(NUM_TRIAL_SAMPLES, num_different + 1);
	if (stack->samples_per_bit > MAX_SAMPLES_PER_BIT)
		return;

	atomic_set(&stack->samples, 0);
	timer_setup_on_stack(&stack->timer, entropy_timer, 0);
	while (!crng_ready() && !signal_pending(current)) {
		/*
		 * Check !timer_pending() and then ensure that any previous callback has finished
		 * executing by checking try_to_del_timer_sync(), before queueing the next one.
		 */
		if (!timer_pending(&stack->timer) && try_to_del_timer_sync(&stack->timer) >= 0) {
			struct cpumask timer_cpus;
			unsigned int num_cpus;

			/*
			 * Preemption must be disabled here, both to read the current CPU number
			 * and to avoid scheduling a timer on a dead CPU.
			 */
			preempt_disable();

			/* Only schedule callbacks on timer CPUs that are online. */
			cpumask_and(&timer_cpus, housekeeping_cpumask(HK_TYPE_TIMER), cpu_online_mask);
			num_cpus = cpumask_weight(&timer_cpus);
			/* In very bizarre case of misconfiguration, fallback to all online. */
			if (unlikely(num_cpus == 0)) {
				timer_cpus = *cpu_online_mask;
				num_cpus = cpumask_weight(&timer_cpus);
			}

			/* Basic CPU round-robin, which avoids the current CPU. */
			do {
				cpu = cpumask_next(cpu, &timer_cpus);
				if (cpu >= nr_cpu_ids)
					cpu = cpumask_first(&timer_cpus);
			} while (cpu == smp_processor_id() && num_cpus > 1);

			/* Expiring the timer at `jiffies` means it's the next tick. */
			stack->timer.expires = jiffies;

			add_timer_on(&stack->timer, cpu);

			preempt_enable();
		}
		mix_pool_bytes(&stack->entropy, sizeof(stack->entropy));
		schedule();
		stack->entropy = random_get_entropy();
	}
	mix_pool_bytes(&stack->entropy, sizeof(stack->entropy));

	del_timer_sync(&stack->timer);
	destroy_timer_on_stack(&stack->timer);
}

長いのでまとめてざっくりと抜粋すると、ここではハッシュ関数Blake2sが使用されている。

stackを用意
1. random_get_entropyを規定回数使用して、stackのentropyを決定
2. 疑似乱数が生成可能になるまでループ
  1. ラウンドロビンでCPUを変更してクロックを取得
  2. タイマー割り込み回数をマスクしたものをスタックに保存？
  3. stack->entropyを使ってBlake2sでハッシュを作成し、input_poolに保存
  4. stack->entropyをrandom_get_entropyで上書き
3. entropyを使ってBlake2sでハッシュを作成し、input_poolに保存
4. stackに保存されているtimerを削除？

CPUのタイマー部分だけはあっているか不明だが、
(jiffiesだからカーネルの時間変数なので認識はあっているはず)
概ね挙動は正しいはず。
一番気になっていた真正乱数部分はrandom_get_entropyが担っている模様。

random_get_entropy

エントロピーの作成を行っている関数だが、CPUのアーキテクチャによって実装が違っている。
今回はx86としてみると決めているので、そちらのソースを読んでみる。

static inline unsigned long random_get_entropy(void)
{
	if (!IS_ENABLED(CONFIG_X86_TSC) &&
	    !cpu_feature_enabled(X86_FEATURE_TSC))
		return random_get_entropy_fallback();
	return rdtsc();
}
#define random_get_entropy random_get_entropy

そのCPUのクロック数を出力している。

rdtscはクロック数の取得コマンド
もう一つは以下

unsigned long random_get_entropy_fallback(void)
{
	struct tk_read_base *tkr = &tk_core.timekeeper.tkr_mono;
	struct clocksource *clock = READ_ONCE(tkr->clock);

	if (unlikely(timekeeping_suspended || !clock))
		return 0;
	return clock->read(clock);
}

同じ感じかな？

rdtscコマンドがない場合を想定しているようだし、妥当な処理だと思う。

ここまで見て考えてみる。
try_to_generate_entropyの処理では、CPUクロックからハッシュを生成してエントロピーを作成している。

getrandom() =>  
wait_for_bytes() => 
try_to_generate_entropy() && wait_event_interruptible_timeout()

という処理だったので、次に進む。

wait_event_interruptible_timeout

これに関しては、単純に時間制限以内にエントロピーの補充ができているか確認しているだけっぽい。
ソースはマクロが長いので省略。

wait_event_interruptible_timeout

#define wait_event_interruptible_timeout(wq_head, condition, timeout)		\
({										\
	long __ret = timeout;							\
	might_sleep();								\
	if (!___wait_cond_timeout(condition))					\
		__ret = __wait_event_interruptible_timeout(wq_head,		\
						condition, timeout);		\
	__ret;									\
})

#define __wait_event_hrtimeout(wq_head, condition, timeout, state)		\
({										\
	int __ret = 0;								\
	struct hrtimer_sleeper __t;						\
										\
	hrtimer_init_sleeper_on_stack(&__t, CLOCK_MONOTONIC,			\
				      HRTIMER_MODE_REL);			\
	if ((timeout) != KTIME_MAX) {						\
		hrtimer_set_expires_range_ns(&__t.timer, timeout,		\
					current->timer_slack_ns);		\
		hrtimer_sleeper_start_expires(&__t, HRTIMER_MODE_REL);		\
	}									\
										\
	__ret = ___wait_event(wq_head, condition, state, 0, 0,			\
		if (!__t.task) {						\
			__ret = -ETIME;						\
			break;							\
		}								\
		schedule());							\
										\
	hrtimer_cancel(&__t.timer);						\
	destroy_hrtimer_on_stack(&__t.timer);					\
	__ret;									\
})

一つ上の処理に戻ってプログラムを見ると、

random.c

int wait_for_random_bytes(void)
{
	while (!crng_ready()) {
		int ret;

		try_to_generate_entropy();
		ret = wait_event_interruptible_timeout(crng_init_wait, crng_ready(), HZ);
		if (ret)
			return ret > 0 ? 0 : ret;
	}
	return 0;
}

wait_for_random_bytesは、エントロピーがたまっていなければ補充を行い、既定の時間よりかかった場合はエラーを返す関数、
となる。

エントロピーが尽きているときの補充工程はわかった。
これでgetrandom関数の続きを読んでいく。

ソースコードをもう一度張っておく

SYSCALL_DEFINE3(getrandom, char __user *, ubuf, size_t, len, unsigned int, flags)
{
	struct iov_iter iter;
	int ret;

	if (flags & ~(GRND_NONBLOCK | GRND_RANDOM | GRND_INSECURE))
		return -EINVAL;

	/*
	 * Requesting insecure and blocking randomness at the same time makes
	 * no sense.
	 */
	if ((flags & (GRND_INSECURE | GRND_RANDOM)) == (GRND_INSECURE | GRND_RANDOM))
		return -EINVAL;

	if (!crng_ready() && !(flags & GRND_INSECURE)) {
		if (flags & GRND_NONBLOCK)
			return -EAGAIN;
		ret = wait_for_random_bytes();
		if (unlikely(ret))
			return ret;
	}

	ret = import_ubuf(ITER_DEST, ubuf, len, &iter);
	if (unlikely(ret))
		return ret;
	return get_random_bytes_user(&iter);
}

getrandom() =>  
wait_for_bytes() || get_random_bytes_user()

いよいよ最初に戻ってget_random_bytes_user関数を見てみる。

get_random_bytes_user

ソースコードを読んだ人は薄々分かっていたと思うが、実質ここが乱数生成のすべて。
/dev/randomだろうが、/dev/urandomだろうが、getrandomだろうが、大体ここにつながっている。

早速コードを見てみると、

static ssize_t get_random_bytes_user(struct iov_iter *iter)
{
	u32 chacha_state[CHACHA_STATE_WORDS];
	u8 block[CHACHA_BLOCK_SIZE];
	size_t ret = 0, copied;

	if (unlikely(!iov_iter_count(iter)))
		return 0;

	/*
	 * Immediately overwrite the ChaCha key at index 4 with random
	 * bytes, in case userspace causes copy_to_iter() below to sleep
	 * forever, so that we still retain forward secrecy in that case.
	 */
	crng_make_state(chacha_state, (u8 *)&chacha_state[4], CHACHA_KEY_SIZE);
	/*
	 * However, if we're doing a read of len <= 32, we don't need to
	 * use chacha_state after, so we can simply return those bytes to
	 * the user directly.
	 */
	if (iov_iter_count(iter) <= CHACHA_KEY_SIZE) {
		ret = copy_to_iter(&chacha_state[4], CHACHA_KEY_SIZE, iter);
		goto out_zero_chacha;
	}

	for (;;) {
		chacha20_block(chacha_state, block);
		if (unlikely(chacha_state[12] == 0))
			++chacha_state[13];

		copied = copy_to_iter(block, sizeof(block), iter);
		ret += copied;
		if (!iov_iter_count(iter) || copied != sizeof(block))
			break;

		BUILD_BUG_ON(PAGE_SIZE % sizeof(block) != 0);
		if (ret % PAGE_SIZE == 0) {
			if (signal_pending(current))
				break;
			cond_resched();
		}
	}

	memzero_explicit(block, sizeof(block));
out_zero_chacha:
	memzero_explicit(chacha_state, sizeof(chacha_state));
	return ret ? ret : -EFAULT;
}

...どうみてもChaChaだね。

変数名の随所にChaChaってあるし、処理もがっつり見覚えあるし、ChaCha20ですね。

ChaChaに関しては、これを読んで参考にしてほしい。

ここで重要になるのは、この箇所。

	/*
	 * Immediately overwrite the ChaCha key at index 4 with random
	 * bytes, in case userspace causes copy_to_iter() below to sleep
	 * forever, so that we still retain forward secrecy in that case.
	 */
	crng_make_state(chacha_state, (u8 *)&chacha_state[4], CHACHA_KEY_SIZE);

ChaChaはcrng（暗号論的疑似乱数生成器）なので、seed部分が乱数でなくてはならない。

ここか？
真正乱数がついにみつかったか？
追いかけてみよう。

crng_make_state

早速コードを見てみよう。


/*
 * This function returns a ChaCha state that you may use for generating
 * random data. It also returns up to 32 bytes on its own of random data
 * that may be used; random_data_len may not be greater than 32.
 */
static void crng_make_state(u32 chacha_state[CHACHA_STATE_WORDS],
			    u8 *random_data, size_t random_data_len)
{
	unsigned long flags;
	struct crng *crng;

	BUG_ON(random_data_len > 32);

	/*
	 * For the fast path, we check whether we're ready, unlocked first, and
	 * then re-check once locked later. In the case where we're really not
	 * ready, we do fast key erasure with the base_crng directly, extracting
	 * when crng_init is CRNG_EMPTY.
	 */
	if (!crng_ready()) {
		bool ready;

		spin_lock_irqsave(&base_crng.lock, flags);
		ready = crng_ready();
		if (!ready) {
			if (crng_init == CRNG_EMPTY)
				extract_entropy(base_crng.key, sizeof(base_crng.key));
			crng_fast_key_erasure(base_crng.key, chacha_state,
					      random_data, random_data_len);
		}
		spin_unlock_irqrestore(&base_crng.lock, flags);
		if (!ready)
			return;
	}

	local_lock_irqsave(&crngs.lock, flags);
	crng = raw_cpu_ptr(&crngs);

	/*
	 * If our per-cpu crng is older than the base_crng, then it means
	 * somebody reseeded the base_crng. In that case, we do fast key
	 * erasure on the base_crng, and use its output as the new key
	 * for our per-cpu crng. This brings us up to date with base_crng.
	 */
	if (unlikely(crng->generation != READ_ONCE(base_crng.generation))) {
		spin_lock(&base_crng.lock);
		crng_fast_key_erasure(base_crng.key, chacha_state,
				      crng->key, sizeof(crng->key));
		crng->generation = base_crng.generation;
		spin_unlock(&base_crng.lock);
	}

	/*
	 * Finally, when we've made it this far, our per-cpu crng has an up
	 * to date key, and we can do fast key erasure with it to produce
	 * some random data and a ChaCha state for the caller. All other
	 * branches of this function are "unlikely", so most of the time we
	 * should wind up here immediately.
	 */
	crng_fast_key_erasure(crng->key, chacha_state, random_data, random_data_len);
	local_unlock_irqrestore(&crngs.lock, flags);
}

...また面倒くさい処理が並んでいるが、ざっとみてみると。

		if (!ready) {
			if (crng_init == CRNG_EMPTY)
				extract_entropy(base_crng.key, sizeof(base_crng.key));
			crng_fast_key_erasure(base_crng.key, chacha_state,
					      random_data, random_data_len);
		}

ここの処理が重要とわかる。
他はロックとトランザクション処理っぽいし、

...まだまだ終わらないか。
でもかなりいいところまで来ているはず！

気合を入れて最後まで調査する！
現状はここまで調査している。

getrandom() =>  
get_random_bytes_user() =>
crng_make_state() => 				extract_entropy() && crng_fast_key_erasure()  <- Now!!

extract_entropy

entropyの作成部分なのは間違いない！だって名前がそうだもの！
とりあえず読んでいく。

static void extract_entropy(void *buf, size_t len)
{
	unsigned long flags;
	u8 seed[BLAKE2S_HASH_SIZE], next_key[BLAKE2S_HASH_SIZE];
	struct {
		unsigned long rdseed[32 / sizeof(long)];
		size_t counter;
	} block;
	size_t i, longs;

	for (i = 0; i < ARRAY_SIZE(block.rdseed);) {
		longs = arch_get_random_seed_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		longs = arch_get_random_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		block.rdseed[i++] = random_get_entropy();
	}

	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) */
	block.counter = 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));
		len -= i;
		buf += i;
	}

	memzero_explicit(seed, sizeof(seed));
	memzero_explicit(&block, sizeof(block));
}

...Blake2じゃん。
またBlake2s、seedの処理は全てBlake2sになるのかも？

ということは、ハッシュへの入力部分が真正乱数になるはずなので、

	for (i = 0; i < ARRAY_SIZE(block.rdseed);) {
		longs = arch_get_random_seed_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		longs = arch_get_random_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		block.rdseed[i++] = random_get_entropy();
	}

この部分が該当する。
...なんか同じような関数が二つ並んで気持ち悪いけど、なんでだろう？
一つずつ読んでいく。

この関数も実装はCPUのアーキテクチャで実装が切り替わっているので、x86の実装を読んでいく。

arch_get_random_seed_longs && arch_get_random_longs

実装が短かったので、まとめて読んでいく。


#define RDRAND_RETRY_LOOPS	10

/* Unconditional execution of RDRAND and RDSEED */

static inline bool __must_check rdrand_long(unsigned long *v)
{
	bool ok;
	unsigned int retry = RDRAND_RETRY_LOOPS;
	do {
		asm volatile("rdrand %[out]"
			     CC_SET(c)
			     : CC_OUT(c) (ok), [out] "=r" (*v));
		if (ok)
			return true;
	} while (--retry);
	return false;
}

static inline bool __must_check rdseed_long(unsigned long *v)
{
	bool ok;
	asm volatile("rdseed %[out]"
		     CC_SET(c)
		     : CC_OUT(c) (ok), [out] "=r" (*v));
	return ok;
}

/*
 * These are the generic interfaces; they must not be declared if the
 * stubs in <linux/random.h> are to be invoked.
 */

static inline size_t __must_check arch_get_random_longs(unsigned long *v, size_t max_longs)
{
	return max_longs && static_cpu_has(X86_FEATURE_RDRAND) && rdrand_long(v) ? 1 : 0;
}

static inline size_t __must_check arch_get_random_seed_longs(unsigned long *v, size_t max_longs)
{
	return max_longs && static_cpu_has(X86_FEATURE_RDSEED) && rdseed_long(v) ? 1 : 0;
}

それぞれの関数の違いは、rdseedを使うか、rdrandを使うかの違いだけみたい。
この二つの違いも調べてみたけど、
CPUレベルでの/dev/randomと/dev/urandomみたいな感じで、rdseedのほうがセキュリティ強度が高いらしい。
CPUノイズをseedにして、AESをハードウェア的に実装している物に通したものが、rdrandらしい。

やっと出てきたCPUノイズ！
これだったのか！
ちょっと感動してきた！

気を取り直して、それぞれの関数の処理を見てみると、

乱数の作成
うまくいったら1を返し、ダメだったら0を返す

という処理だった。
それを踏まえて、前の処理を見てみる。

	for (i = 0; i < ARRAY_SIZE(block.rdseed);) {
		longs = arch_get_random_seed_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		longs = arch_get_random_longs(&block.rdseed[i], ARRAY_SIZE(block.rdseed) - i);
		if (longs) {
			i += longs;
			continue;
		}
		block.rdseed[i++] = random_get_entropy();
	}

rdseedで乱数を取得
ダメだったらrdrandで乱数を取得
両方ダメならrandom_get_entropy(CPUクロック)から乱数を取得

という流れによって、真正乱数seedが作成される。

crng_fast_key_erasureはchachaの初期化処理だったので省略

# crng_fast_key_erasure 真正乱数の部分は判明しているけど、一応ね

static void crng_fast_key_erasure(u8 key[CHACHA_KEY_SIZE],
				  u32 chacha_state[CHACHA_STATE_WORDS],
				  u8 *random_data, size_t random_data_len)
{
	u8 first_block[CHACHA_BLOCK_SIZE];

	BUG_ON(random_data_len > 32);

	chacha_init_consts(chacha_state);
	memcpy(&chacha_state[4], key, CHACHA_KEY_SIZE);
	memset(&chacha_state[12], 0, sizeof(u32) * 4);
	chacha20_block(chacha_state, first_block);

	memcpy(key, first_block, CHACHA_KEY_SIZE);
	memcpy(random_data, first_block + CHACHA_KEY_SIZE, random_data_len);
	memzero_explicit(first_block, sizeof(first_block));
}

...うんChaCha！
ChaCha20の初期化処理だね

まとめ

以上をまとめて簡略化するとこうなる。

追記：　割り込み処理が定期的にinput_poolに入っていることがわかったので、hardware_noiseを追加

hardware_noise = disk割り込み or ハードウェア割り込み..etc 
rdseed = cpu-noise
rdrand = AES(rdseed)
seed = rdseed or rdrand or cpu->rdtsc or hardware_noise
getrandom() = ChaCha(Blake2s(seed))

これがLinux(x86)での真正乱数の取得と、疑似乱数の生成方法ということになる！
かなり乱雑な見方をしたけど、概ね間違ってはいないはず。
rdtscで熱や時間、rdseedでノイズを拾って使用しており、それ以外に様々な割り込み（キーボード、disk、etc）で乱数を形成していることが分かった。

結論：Linuxの乱数生成器はCPUの熱、時間、ノイズ、ハードウェア全てを使って真正乱数を作成している

以上。

ふと思ったけど...これCPUのノイズにバックドアがあったら終わり？
seed(rdseed,rdrand,rdtsc)のinput_poolに入る順番とかもわからないし、大丈夫なのかな？
極端な話CPU作成者が悪意あったら、バックドア仕込めるのでは？
ハードウェアの信頼性はどうやって担保しているんだろう？
ちょっとだけ疑問が残った。

追記：色々な割り込み処理とかで乱数を混ぜているからCPUのノイズにバックドア入ってても大丈夫。ハードウェアが信頼できるかは知らない

void add_interrupt_randomness(int irq)
{
	enum { MIX_INFLIGHT = 1U << 31 };
	unsigned long entropy = random_get_entropy();
	struct fast_pool *fast_pool = this_cpu_ptr(&irq_randomness);
	struct pt_regs *regs = get_irq_regs();
	unsigned int new_count;

	fast_mix(fast_pool->pool, entropy,
		 (regs ? instruction_pointer(regs) : _RET_IP_) ^ swab(irq));
	new_count = ++fast_pool->count;

	if (new_count & MIX_INFLIGHT)
		return;

	if (new_count < 1024 && !time_is_before_jiffies(fast_pool->last + HZ))
		return;

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

/*
 * Add device- or boot-specific data to the input pool to help
 * initialize it.
 *
 * None of this adds any entropy; it is meant to avoid the problem of
 * the entropy pool having similar initial state across largely
 * identical devices.
 */
void add_device_randomness(const void *buf, size_t len)
{
	unsigned long entropy = random_get_entropy();
	unsigned long flags;

	spin_lock_irqsave(&input_pool.lock, flags);
	_mix_pool_bytes(&entropy, sizeof(entropy));
	_mix_pool_bytes(buf, len);
	spin_unlock_irqrestore(&input_pool.lock, flags);
}

まぁそりゃハードウェアに完全依存なんかしないよな。
非常に納得できる実装だった。

感想

非常に勉強になった。
乱数生成のコードを漁っていて思うけど、

乱数は予測できたらダメ。
使っている暗号アルゴリズムに脆弱性が発見されたらダメ。
みんなで同じものを使うために、処理内容は常にオープンにするべきだから晒されっぱなし。
隠したらバックドアの危険性。
ずいぶん過酷な環境ですこと。

最後に、
専門性が強すぎてあんまり需要ないかもしれないけど、同じく勉強になったという人がいたら嬉しい。

はじめに

PCと真正乱数

Linuxでの乱数作成

get_random

wait_for_random_bytes

random_get_entropy

wait_event_interruptible_timeout

get_random_bytes_user

crng_make_state

extract_entropy

arch_get_random_seed_longs && arch_get_random_longs

まとめ

感想

参考文献