X

News, tips, partners, and perspectives for the Oracle Solaris operating system

Solaris Random Number Generation

Darren Moffat
Senior Software Architect

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 href="http://docs.oracle.com/cd/E26502_01/html/E29043/attributes-5.html">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.

Join the discussion

Comments ( 5 )
  • guest Wednesday, September 18, 2013

    Is it just me or is mdb's rnd_stats dcmd broken on Solaris 11?

    echo ::rnd_stats | mdb -k

    Random number device statistics:

    5904199250313759140 bytes generated for /dev/random

    15918401109740712482 bytes read from /dev/random cache

    8562249233582938557 bytes generated for /dev/urandom


  • Darren J Moffat Wednesday, September 18, 2013

    Yes the mdb dcmd is indeed broken I'll log a bug and ensure it gets fixed. Thanks.


  • guest Friday, April 25, 2014

    Seems like the "echo ::rnd_stats | mdb -k" is fixed in Solaris 11.2


  • guest Friday, May 9, 2014

    Hi Darren,

    we want to read from /dev/random with Java SecureRandom (we never write to it). It is true, that /dev/random always returns high quality random numbers and blocks when no entropy is available? We use Solaris 10 8/11.

    Thanks

    Nils


  • Darren J Moffat Friday, May 9, 2014

    Nils, yes /dev/random will block if it believes there is insufficient entropy in the pool to return the requested amount of random bits.


Please enter your name.Please provide a valid email address.Please enter a comment.CAPTCHA challenge response provided was incorrect. Please try again.Captcha
Oracle

Integrated Cloud Applications & Platform Services