Thursday Sep 12, 2013

Solaris Random Number Generation

The following was originally written to assist some of our new hires in learning about how our random number generators work and also to provide context for some questions that were asked as part of the ongoing (at the time of writing) FIPS 140-2 evaluation of the Solaris 11 Cryptographic Framework.

Updated Febuary 2016 to cover changes in Solaris 11.3

1. Consumer Interfaces

The Solaris random number generation (RNG) system is used to generate random numbers, which utilizes both hardware and software mechanisms for entropy collection. It has consumer interfaces for applications; it can generate high-quality random numbers suitable for long term asymmetric keys and pseudo-random numbers for session keys or other cryptographic uses, such as a nonce.

1.1 Interface to user space

The random(7D) device driver provides the /dev/random and /dev/urandom devices to user space, but it doesn't implement any of the random number generation or extraction itself.

There is a single kernel module (random) for implementing both the /dev/random and /dev/urandom devices. The two primary entry points are rnd_read() and rnd_write() for servicing read(2) and write(2) system calls respectively.

rnd_read() calls either kcf_rnd_get_bytes() or kcf_rnd_get_pseudo_bytes() depending on wither the device node is an instance of /dev/random or /dev/urandom respectively. In FIPS mode, if /dev/random has been opened for nonblocking reads (neither O_NBLOCK nor O_NDELAY set), the rnd_read call will call fips_random_get_bytes() There is a cap on the maximum number of bytes that can be transfered in a single read, MAXRETBYTES_RANDOM (1040) and MAXRETBYTES_URANDOM(128 * 1040) respectively.

rnd_write() uses random_add_entropy() and random_add_pseduo_entropy() they both pass 0 as the estimate of the amount of entropy that came from userspace, so we don't trust userspace to estimate the value of the entropy being provided.

1.2 Interface in kernel space

The kcf module provides an API for randomnes for in kernel KCF consumers. It implements the functions mentioned above that are called to service the read(2)/write(2) calls and also provides the interfaces for kernel consumers to access the random and urandom pools.

If no providers are configured no randomness can be returned and a message logged informing the administrator of the mis-configuration.

2. /dev/random

We periodically collect random bits from providers which are registered with the Kernel Cryptographic Framework (kCF) as capable of random number generation. The random bits are maintained in a cache and it is used for high quality random numbers (/dev/random) requests. If the cache has sufficient random bytes available the request is serviced from the cache.Otherwise we pick a provider and call its SPI routine.If we do not get enough random bytes from the provider call we fill in the remainder of the request by continously replenishing the cache and using that until the full requested size is met.

The maximum request size that will be serviced for a single read(2) system call on /dev/random is 1040 bytes.

2.1 Initialization

kcf_rnd_init() is where we setup the locks and get everything started, it is called by the _init() routine in the kcf module, which itself is called on very early in system boot - before the root filesystem is mounted and most modules are loaded.

For /dev/random and random_get_bytes() a static array of 1024 bytes is setup by kcf_rnd_init().

We start by placing the value of gethrtime(), high resolution time since the boot time, and drv_getparam(), the current time of day as the initial seed values into the pool (both of these are 64 bit integers).We set the number of random bytes available in the pool to 0.

2.2 Adding randomness to the rndpool

The rndc_addbytes() function adds new random bytes to the pool (aka cache). It holds the rndpool_lock mutex while it xor in the bytes to the rndpool.The starting point is the global rindex variable which is updated as each byte is added.It also increases the rnbyte_cnt.

If the rndpool becomes full before the passed in number of bytes is all used we continue to add the bytes to the pool/cache but do not increase rndbyte_cnt, it also moves on the global findex to match rindex as it does so.

2.3 Scheduled generation

The kcf_rnd_schedule_timeout() ensures that we periodically add bytes to the rndpool.The timeout is itself randomly generated by reading (but not consuming) the first 32 bits of rndpool to derive a new time out of between 2 and 5.544480 seconds. When the timeout expires the KCF rnd_handler() function [ from kcf_random.c ] is called.

If we have readers blocked for entropy or the count of available bytes is less than the pool size we start an asynchronous task to call rngprov_getbyte() gather more entropy from the available providers.

If there is at least the minimum (20 bytes) of entropy available we wake up the threads stopped in a poll(2)/select(2) of /dev/random. If there are any threads waiting on entropy we wake those up too.The waiting and wake up is performed by cv_wait_sig() and cv_broadcast(), this means that the pool lock will be held when cv_broadcast wakes up a thread it will have the random pool lock held.

Finally we schedule the next time out.

2.4 External caller Seeding

The random_add_entropy() call is able able to provide entropy from an external (to KCF or its providers) source of randomness.It takes a buffer and a size as well as an estimated amount of entropy in the buffer. There are no callers in Solaris that provide a non 0 value for the estimate of entropy to random_add_entropy().The only caller of random_add_entropy() is actually the write(2) entry point for /dev/random.

Seeding is performed by calling the first available software entropy provider plugged into KCF and calling its KCF_SEED_RANDOM entropy function. The term "software" here really means "device driver driven" rather than CPU instruction set driven.For example the n2rng provideris device driver driven but the architecture based Intel RDRAND is regarded as "software". The terminology is for legacy reasons from the early years of the Solaris cryptographic framework. This does however mean we never attempt to seed the hardware RNG on SPARC S2 or S3 core based systems (T2 through M6 inclusive) but we will attempt to do so on Intel CPUs with RDRAND

2.5 Extraction for /dev/random

We treat rndpool as a circular buffer with findex and rindex tracking the front and back respectively. Both start at position 0 during initialization.

To extract randomness from the pool we use kcf_rnd_get_bytes(). It calls rnd_get_bytes() with the rndpool_lock held. The lock will be released by rnd_get_bytes() on both sucess and failure cases. If the number of bytes requested from rnd_get_bytes() is less than or equal to the number of available bytes (rnbyte_cnt) in the cache then we call rndc_getbytes() immediately, i.e. we use the randomness from the pool. Otherwise we release the rndpool_lock and call rngprov_getbytes() with the number of bytes we want. If that still wasn't enough, we loop picking up as many bytes as we can by successive calls. If at any time the rnbyte_cnt in the pool is less than 20 bytes we wait on the read condition variable (rndpool_read_cv) and try again when we are woken up.

2.6 KCF Random Providers

KCF has the concept of "hardware" and "software" providers. The terminology is a legacy one from before hardware support for cryptographic algorithms and random number generation was available as unprivileged CPU instructions.

It really now maps to "hardware" being a provider that has a specific device driver, such as n2rng and "software" meaning CPU instructions or some other pure software mechanism. It doesn't mean that there is no "hardware" involved since on Intel CPUs with the RDRAND instruction calls are in the intelrd provider but it is regarded as a "software" provider. **REALLY???**

2.6.1 swrand: Random Number Provider

All Solaris installs have a KCF random provider called "swrand". This provider periodically collects unpredictable input and processes it into a pool of entropy. It implements its own extraction and generation algorithms.

It uses a pool called srndpool of 1000 bytes and a list of "raw entropy" chunks. These chunks consist of some collected bytes and an estimate of bits of entropy in those bytes.

The swrand provider has two different raw entropy sources:

  • By reading blocks of physical memory and detecting if changes occurred in the blocks read.

    Physical memory is divided into blocks of fixed size. A block of memory is chosen from the possible blocks and a one byte "checksum" of the block is computed and compared against the previous "checksum" computed for that block. If the single-byte checksum has not changed, no "raw entropy" is added to the pool from this source. If a change is detected then a hash of the block is computed and added to the raw entropy list with 15 bits of entropy credited to it.

  • By measuring the time the above computation takes (both the changing and non-changing cases) and computing the differences in the measured time.

    This method measures the amount of time it takes to read, checksum and (in the "change detected" case) hash a physical memory block (as described above). The time measured can vary depending on system load, scheduling and other factors. Differences between consecutive measurements are computed to come up with an entropy estimate. The first, second, and third order delta is calculated to determine the minimum delta value. The number of bits present in this minimum delta value is the entropy estimate.

When the estimated entropy collected exceeds 320 bits, the collected raw bytes are conditioned (hashed) into 20 bytes (160 bits) of full-entropy strings into srndpool. This is where the FIPS 140-2 mandated continuous RNG test takes place: each newly generated 20-byte block is compared to the previusly generated 20 bytes and depending on FIPS mode, either a system panic is induced or a warning is placed on the syslog if the previous and new bloks are equal.

2.6.1.1 Initialization of swrand

Since physical memory can change size swrand registers with the Solaris DR subsystem so that it can update its cache of the number of blocks of physical memory when it either grows or shrinks.

On initial attach the fips_rng_post() function is run.

During initialization the swrand provider adds entropy from the high resolution time since boot and the current time of day (note that due to the module load system and how KCF providers register these values will always be different from the values that the KCF rndpool is initialized with). It also adds in the initial state of physical memory, the number of blocks and sources described above.

Only after all of the above does the swrand provider register with the cryptographic framework.

2.6.1.2 swrand entropy generation

The swrand_get_entropy() is where all the real work happens when the KCF random pool calls into swrand. This function can be called in either blocking or non blocking mode. The only difference between blocking and non blocking is that the later will return EAGAIN if there is insufficient entropy to generate the randomness, the former blocks indefinitely.

A global uint32_t entropy_bits is used to track how much entropy is available.

When a request is made to swrand_get_entropy() we loop until we have the available requested amount of randomness. First checking if the number of remaining entropy in srndpool is below 20 bytes, if it is then we block waiting for more entropy (or return EGAIN if non blocking mode).

Then we determine how many bytes of entropy to extract, it is the minimum of the total requested and 20 bytes. We then update the output buffer and continue the loop until we have generated the requested about.

2.6.1.3 Adding to the swrand pool>

The swrand_seed_entropy() function is used to mix entropy from an external source via the KCF random_add_entropy() call. It xors the input into srndpool without touching the pointers, so although it changes subsequent output from the pool, no new entropy is added by this call.

2.6.2 n2rng random provider

This applies only to SPARC processors with either an S2 core (T2, T3, T3+) or to S3 core (T4, T5, M5, M6) both CPU families use the same n2rng driver and the same on chip system for the RNG.

The n2rng driver provides the interface between the hyper-privilged access to the RNG registers on the CPU and KCF.

The driver performs attach time diagnostics on the hardware to ensure it continues operating as expected. It determines that it is operating in FIPS 140-2 mode via its driver.conf(5) file before its attach routine has completed. The full hardware health check in conjunction with the hypervisor only when running in the control domain. The FIPS 140 checks are always run regardless of the hypervisor domain type. If the FIPS 140 POST checks fail the driver ensures it is deregistered with KCF.

If the driver is suspended and resumed it reconfigures and re-registers with KCF. This would happen on a suspend/resume cycle or during live migration.

2.6.3 intelrd random provider

This applies only to x86 processors that support the RDRAND instruction.

The intelrd driver uses the RDRAND (or RDSEED if that is also supported by the processor) instruction to provide entropy for KCF.

The driver produces the entropy in 20-byte (160-bit) chunks using the SHA-1 algorithm to condition 1023 (when using RDRAND) or 5 (when using RDSEED) 64-bit values returned by the respective instructions, into 160 full-entropy bits. The FIPS 140-2 continuous RNG test is done on these 160-bit chunks.

3. FIPS Internals

3.0 FIPS approved DRBG

In FIPS mode, the cryptographic framework employs a deterministic random bit generator (DRBG) described in NIST SP 800-90A. We are using the Hash_DRBG with SHA512 as the underlying hashing algorithm.

In userland, the libucrypto library uses a DRBG for servicing random_get_bytes() and another one for servicing random_get_pseudo_bytes(). The former is initialized with prediction resistance requested, which means it is reseeded after each request. The 256-bit entropy for the initialization and reseed is obtained from the getentropy(2) system call.

In the kernel, the random_get_bytes() function is using the DRBG, it is initialized with prediction resistance requested, and the entropy for the initialization and reseed (both of 256-bits) comes from kcf_rnd_get_bytes() called with KCF_RND_BLOCK, i.e. blocking until enough entropy is collected from the system

320 bits are collected and those are fed into the FIPS 186-2 Appendix 3.3 algorithm as X_SEED (two 160-bit values are computed) then the first 256 bits of the resulting 320 bits are used as the seed for the DRBG.

3.1 FIPS 186-2: fips_random_inner()

It is a completely internal to Solaris function that can't be used outside of the cryptographic framework.

fips_random_inner(uint32_t *key, uint32_t *x_j, uint32_t *XSEED_j)
It computes a new random value, which is stored in x_j; updates XKEY.XSEED_j is additional input.In principle, we should protect XKEY, perhaps by placing it in non-paged memory, but we aways clobber XKEY with fresh entropy just before we use it and step 3d irreversibly updates it just after we use it. The only risk is that if an attacker captured the state while the entropy generator was broken, the attacker could predict future values. There are two cases:

  1. The attack gets root access to a live system. But there is no defense against that that we can place in here since they already have full control.
  2. The attacker gets access to a crash dump. But by then no values are being generated.

Note that XSEED_j is overwritten with sensitive stuff, and must be zeroed by the caller. We use two separate symbols (XVAL and XSEED_j) to make each step match the notation in FIPS 186-2.

All parameters (key, x_j, XSEED_j) are the size of a SHA-1 digest, 20 bytes.

The HASH function used is SHA1.

The implementation of this function is verified during POST by fips_rng_post() calling it with a known seed. The POST call is performed before the swrand module registers with KCF or during initialization of any of the libraries in the FIPS 140 boundary (before their symbols are available to be called by other libraries or applications).

4.0 /dev/urandom

This is a software-based generator algorithm that uses the random bits in the cache as a seed. We create one pseudo-random generator (for /dev/urandom) per possible CPU on the system, and use it, kmem-magazine-style, to avoid cache line contention.

4.1 Initialization of /dev/urandom

kcf_rnd_init() calls rnd_alloc_magazines() whichsetups up the empty magazines for the pseduo random number pool (/dev/urandom). A separate magazine per CPU is configured up to the maximum number of possible (not available) CPUs on the system, important because we can add more CPUs after initial boot.

The magazine initialization discards the first 20 bytes so that the rnd_get_bytes() function will be using that for comparisons that the next block always differs from the previous one. It then places the next 20 bytes into the rm_key and next again 20 bytes into rm_seed. It does this for each max_ncpus magazine. Only after this is complete does kcf_rnd_init() return back to kcf_init(). Each of the per CPU magazines has its own state which includes hmac key, seed and previous value, each also has its own rekey timers and limits.

The magazines are only used for the pseduo random number pool (i.e. servicing random_get_pseduo_bytes() and /dev/urandom

4.2 /dev/urandom generator

At a high level this uses the FIPS 186-2 algorithm using a key extracted from the random pool to generate a maximum of 1310720 output blocks before rekeying. Each CPU (this is CPU thread not socket or core) has its own magazine.

4.3 Reading from /dev/urandom

The maximum request size that will be services for a single read(2) system call on /dev/urandom is 133120 bytes.

Reads all come in via the kcf_rnd_get_pseduo_bytes() function.

If the requested size is considered to be large, greater than 2560 bytes, then instead of reading from the pool we tail call the generator directly by using rnd_generate_pseudo_bytes().

If the CPU's magazine has sufficient available randomness already, we use that, otherwise we call the rnd_generate_pseudo_bytes() function directly. rnd_generate_pseduo_bytes() is always called with the cpu magazine mutex already locked and it is released when it returns. We loop through the following until the requested number of bytes has been built up or an unrecoverable error occurs. rm_seed is reinitialized by xoring in the current 64 bit highres time, from gethrtime() into the prior value of rm_seed. The fips_random_inner() call is then made using the current value of rm_key and this new seed.

The returned value from fips_random_inner() is then checked against our previous return value to ensure it is a different 160-bit block. If that fails the system panics when in FIPS 140-2 mode or returns EIO if FIPS mode is not enabled. Before returning from the whole function the local state is zero'd out and the per magazine lock released.

5.0 Randomness for key generation

For asymmetric key generation inside the kernel a special random_get_nzero_bytes() API is provided.It differs from random_get_bytes() in two ways, first calls the random_get_bytes_fips140() function which only returns once all FIPS 140-2 initialization has been completed. The random_get_bytes() function needs to be available slightly earlier because some very early kernel functions need it (particularly setup of the VM system and if ZFS needs to do any writes as part of mounting the root filesystem). Secondly, it ensures that no bytes in the output have the 0 value, those are replaced with freshly extracted additional random bytes, it continues until the entire requested length is entirely made up of non zero bytes.

A corresponding random_get_nzero_pseduo_bytes() is also available for cases were we don't want 0 bytes in other random sequences, such as session keys, nonces and cookies.

The above two functions ensure that even though most of the random pool is available early in boot we can't use it for key generation until the full FIPS 140-2 POST and integrity check has completed, e.g. on the swrand provider.

6.0 Userspace random number

Applications that need random numbers may read directly from /dev/random and /dev/urandom. Or may use a function implementing the FIPS 186-2 rng requirements.

Starting with Solaris 11.3 the getrandom(2) system call is available for application use. For applications or libraries that build their own randomness subsystem but want entropy input they should call getentropy(2) instead of getrandom(2).

The cryptographic framework libraries in userspace provide the following internal functions:

  • pkcs11_get_random()
  • pkcs11_get_urandom()
  • pkcs11_get_nzero_random()
  • pkcs11_get_nzero_urandom()

The above functions are available from the libcryptoutil.so library but are Private to Solaris and MUST not be used by any 3rd party code - see the attributes(5) man page for the Solaris interface taxonomy. Similar to the kernel space there are pkcs11_get_nzero_random() and pkcs11_get_nzero_urandom() variants that ensure none of the bytes are zero. The pkcs11_ prefix is because these are Private functions mostly used for the implementation of the PKCS#11 API.

I hope this is useful and/or interesting insight into how Solaris generates randomness.

Update 2013-09-12 I was asked about how this applies to Illumos: To the best of my knowledge [ I have not read the Illumos source the following is based on what I remember of the old OpenSolaris source ] most of what I said above should apply to Illumos as well. The main exceptions are that the fips_random_inner(), POST and some of the continuous checks don't exist, neither does the Intel RDRAND support. The source or the n2rng driver, random(7D), kcf and swrand were available as part of OpenSolaris. Not that Illumos may have changed some of this so please verify for yourself.

About

Darren Moffat-Oracle

Search

Categories
Archives
« May 2016
MonTueWedThuFriSatSun
      
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
     
Today