11.6 Random Number Generators

About the generators

GnuTLS provides two random generators. The default, and the AES-DRBG random generator which is only used when the library is compiled with support for FIPS140-2 and the system is in FIPS140-2 mode.

The default generator - inner workings

The random number generator levels in gnutls_rnd_level_t map to two CHACHA-based random generators which are initially seeded using the OS random device, e.g., /dev/urandom or getrandom(). These random generators are unique per thread, and are automatically re-seeded when a fork is detected.

The reason the CHACHA cipher was selected for the GnuTLS’ PRNG is the fact that CHACHA is considered a secure and fast stream cipher, and is already defined for use in TLS protocol. As such, the utilization of it would not stress the CPU caches, and would allow for better performance on busy servers, irrespective of their architecture (e.g., even if AES is not available with an optimized instruction set).

The generators are unique per thread to allow lock-free operation. That induces a cost of around 140-bytes for the state of the generators per thread, on threads that would utilize gnutls_rnd. At the same time it allows fast and lock-free access to the generators. The lock-free access benefits servers which utilize more than 4 threads, while imposes no cost on single threaded processes.

On the first call to gnutls_rnd the generators are seeded with two independent keys obtained from the OS random device. Their seed is used to output a fixed amount of bytes before re-seeding; the number of bytes output varies per generator.

One generator is dedicated for the GNUTLS_RND_NONCE level, and the second is shared for the GNUTLS_RND_KEY and GNUTLS_RND_RANDOM levels. For the rest of this section we refer to the first as the nonce generator and the second as the key generator.

The nonce generator will reseed after outputting a fixed amount of bytes (typically few megabytes), or after few hours of operation without reaching the limit has passed. It is being re-seed using the key generator to obtain a new key for the CHACHA cipher, which is mixed with its old one.

Similarly, the key generator, will also re-seed after a fixed amount of bytes is generated (typically less than the nonce), and will also re-seed based on time, i.e., after few hours of operation without reaching the limit for a re-seed. For its re-seed it mixes mixes data obtained from the OS random device with the previous key.

Although the key generator used to provide data for the GNUTLS_RND_RANDOM and GNUTLS_RND_KEY levels is identical, when used with the GNUTLS_RND_KEY level a re-key of the PRNG using its own output, is additionally performed. That ensures that the recovery of the PRNG state will not be sufficient to recover previously generated values.

The AES-DRBG generator - inner workings

Similar with the default generator, the random number generator levels in gnutls_rnd_level_t map to two AES-DRBG random generators which are initially seeded using the OS random device, e.g., /dev/urandom or getrandom(). These random generators are unique per thread, and are automatically re-seeded when a fork is detected.

The AES-DRBG generator is based on the AES cipher in counter mode and is re-seeded after a fixed amount of bytes are generated.

Defense against PRNG attacks

This section describes the counter-measures available in the Pseudo-random number generator (PRNG) of GnuTLS for known attacks as described in [PRNGATTACKS]. Note that, the attacks on a PRNG such as state-compromise, assume a quite powerful adversary which has in practice access to the PRNG state.

Cryptanalytic

To defend against cryptanalytic attacks GnuTLS’ PRNG is a stream cipher designed to defend against the same attacks. As such, GnuTLS’ PRNG strength with regards to this attack relies on the underlying crypto block, which at the time of writing is CHACHA. That is easily replaceable in the future if attacks are found to be possible in that cipher.

Input-based attacks

These attacks assume that the attacker can influence the input that is used to form the state of the PRNG. To counter these attacks GnuTLS does not gather input from the system environment but rather relies on the OS provided random generator. That is the /dev/urandom or getentropy/getrandom system calls. As such, GnuTLS’ PRNG is as strong as the system random generator can assure with regards to input-based attacks.

State-compromise: Backtracking

A backtracking attack, assumes that an adversary obtains at some point of time access to the generator state, and wants to recover past bytes. As the GnuTLS generator is fine-tuned to provide multiple levels, such an attack mainly concerns levels GNUTLS_RND_RANDOM and GNUTLS_RND_KEY, since GNUTLS_RND_NONCE is intended to output non-secret data. The GNUTLS_RND_RANDOM generator at the time of writing can output 2MB prior to being re-seeded thus this is its upper bound for previously generated data recovered using this attack. That assumes that the state of the operating system random generator is unknown to the attacker, and we carry that assumption on the next paragraphs. The usage of GNUTLS_RND_KEY level ensures that no backtracking is possible for all output data, by re-keying the PRNG using its own output.

Such an attack reflects the real world scenario where application’s memory is temporarily compromised, while the kernel’s memory is inaccessible.

State-compromise: Permanent Compromise Attack

A permanent compromise attack implies that once an attacker compromises the state of GnuTLS’ random generator at a specific time, future and past outputs from the generator are compromised. For past outputs the previous paragraph applies. For future outputs, both the GNUTLS_RND_RANDOM and the GNUTLS_RND_KEY will recover after 2MB of data have been generated or few hours have passed (two at the time of writing). Similarly the GNUTLS_RND_NONCE level generator will recover after several megabytes of output is generated, or its re-key time is reached.

State-compromise: Iterative guessing

This attack assumes that after an attacker obtained the PRNG state at some point, is able to recover the state at a later time by observing outputs of the PRNG. That is countered by switching the key to generators using a combination of a fresh key and the old one (using XOR), at re-seed time. All levels are immune to such attack after a re-seed.

State-compromise: Meet-in-the-Middle

This attack assumes that the attacker obtained the PRNG state at two distinct times, and being able to recover the state at the third time after observing the output of the PRNG. Given the approach described on the above paragraph, all levels are immune to such attack.