はじめに
乱数の作成方法について気になったので、調査してみた。
せっかくだから資料として残すので参考にしてほしい。
題材から見てわかると思うが、今回の記事はあまり初心者向けではない。
できる限りわかりやすい記事を心掛けるが、細かくは説明できないかもしれないので悪しからず。
後で判明したが、
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);
}
- stackを用意
- random_get_entropyを規定回数使用して、stackのentropyを決定
- 疑似乱数が生成可能になるまでループ
- ラウンドロビンでCPUを変更してクロックを取得
- タイマー割り込み回数をマスクしたものをスタックに保存？
- stack->entropyを使ってBlake2sでハッシュを作成し、input_poolに保存
- stack->entropyをrandom_get_entropyで上書き
- entropyを使ってBlake2sでハッシュを作成し、input_poolに保存
- 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);
}
まぁそりゃハードウェアに完全依存なんかしないよな。
非常に納得できる実装だった。
感想
非常に勉強になった。
乱数生成のコードを漁っていて思うけど、
乱数は予測できたらダメ。
使っている暗号アルゴリズムに脆弱性が発見されたらダメ。
みんなで同じものを使うために、処理内容は常にオープンにするべきだから晒されっぱなし。
隠したらバックドアの危険性。
ずいぶん過酷な環境ですこと。
最後に、
専門性が強すぎてあんまり需要ないかもしれないけど、同じく勉強になったという人がいたら嬉しい。
参考文献