# 不只是 rand() 的 RNG --- ## Who am I? - Programmer - 待會可能不小心會講出 *RNG 產生器* 這種詞 - Vim :heart: --- How we use random? ```c #include <stdlib.h> int main{ srand(0); //result of seed 0 and seed 1 might be the same printf("%d",rand()); } ``` ---- ```c #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 ```c int __random_r (struct random_data *buf, int32_t *result){ . . int32_t val = ((state[0] * 1103515245U) + 12345U) & 0x7fffffff; state[0] = val; *result = val; . ``` [Source](https://sourceware.org/git/?p=glibc.git;a=blob;f=stdlib/random_r.c;h=fa0e1d3689dca4b171e9894ab504a4d051685f25;hb=2412deae1af0ca37b096ff73517486e7d1e9fe46#l353) ::: warning `result` here would addtionaly divided by specific value as output. ::: ---- [Linear Congruential Generator](https://en.wikipedia.org/wiki/Linear_congruential_generator) $$ S_{n+1} = (aS_n + c) \ mod \ m,\ S_n \in \{0,1,... m -1 \} $$ ```c 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)](https://chagall.med.cornell.edu/BioinfoCourse/PDFs/Lecture4/random_number_generator.pdf) --- Pseudo Random Number Generator - Linear Congruential Generator - Linear Feedback Shift Register --- LFSR  - characteristic polynomial : $x^{16} + x ^ {14} + x ^ {13} + x ^ {11} + 1$ - Suppose we have $N$ bit, then the LFSR have $2^N-1$ period if its characteristic polynomial is [primitive](https://web.ntnu.edu.tw/~algo/FiniteField.html). ---- 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...  ---- ::: warning LFSR might be unsafed and you could cracked it up with SMT(z3) solver. [Z3 & LFSR](https://miaotony.xyz/2020/08/27/CTF_2020CISCN_preliminary/) ::: --- [/char/random.c](https://elixir.bootlin.com/linux/v6.5-rc3/source/drivers/char/random.c)  ---- RNG in Linux Kernel - `/dev/random` (blocked) - `/dev/urandom` (non-blocked) - above call the same function finally - `/dev/hwrng` (for hardware) ```bash cat /dev/{u}random cat /dev/hwrng ``` ---- - Entropy Collection - Entropy Extraction - Entropy Expansion - Entropy Sources ---- Entropy Collection - Use LFSR before ([commit](https://github.com/torvalds/linux/commit/66e4c2b9541503d721e936cc3898c9f25f4591ff)) - now use [BLAKE2S](https://www.blake2.net) as cryptographic hash function(It's fast) - Doesn't have pitfall that LFSR had ```c blake2s_update(&entropy_pool, input, sizeof(input)); ``` ---- Entropy Extraction - Use `RDSEED` `RDRAND` as [salt](https://en.wikipedia.org/wiki/Salt_(cryptography)) ```c 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) ```c 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; ... ``` ---- ```c ... 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; } ... } ``` --- Entropy Source - `add_device_randomness()` : entropy from data that likely differ between devices (MAC address, serial numbers), doesn't increase the estimated entropy. useful for systems with few randomness sources available(embedded systems) - `add_input_randomness()` : key or mouse event ---- 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](https://elixir.bootlin.com/linux/v6.5-rc3/source/drivers/char/random.c#L1019) - After a bunch of interrupts, queues up a worker to dump these entropy into main tool. ```c 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 ```c 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 --- /dev/hwrng - interface for hardware driver - Usually non-exist unless you have some TRNG devices. ```bash $cat /sys/class/misc/hw_random/rng_available $cat /sys/class/misc/hw_random/rng_current ``` ---- `hw_register`  ---- [/drivers/char/hw_random/core.c](https://elixir.bootlin.com/linux/v6.5-rc2/source/drivers/char/hw_random/core.c#L536) ```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 ```c static struct hwrng zero_rng = { .name= "zero_rng", .read = zero_rng_read }; static int zero_rng_init(void){ return hwrng_register(&zero_rng); } ``` ---- ```c 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 ```c 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; } ``` ---- --- test rng tool - `rngtest -c 1000 </dev/random` - `ent file` ---- `dd if=/dev/hwrng/ of=hw bs=4096 count=1`  ----  ---