That resulted in an internal random generator which had to rely on whatever was provided by the operating system and the administrator, and that, in several cases was insufficient to seed a cryptographic PRNG. As such, an advanced PRNG was selected, based on Yarrow, which kept a global per-process state, and was aggressively gathering information, including high precision timestamps and process/thread statistics, to enhance a potentially untrusted pool formed from the system random generator or EGD. That, also meant locks for multi-threaded processes to access the global state, and thus a performance bottleneck, since a call to the PRNG is required even for the simplest of crypto operations.
Today, however, things have changed in operating systems. While Linux used to be a pioneer with /dev/urandom, now all operating systems provide a reliable PRNG, even though there are still no standardized APIs.
- Linux provides /dev/urandom, getrandom(), getentropy()
- Windows provides CryptGenRandom()
- *BSD provides /dev/urandom, getentropy()
- MacOSX provides /dev/urandom, getentropy()
- Solaris: /dev/urandom, getentropy(), getrandom().
Some of the interfaces above are provided as system calls, some others as libc calls, and others as file system devices, but for the application writer, that shouldn't make significant difference. These devices or system calls, provide access to a system PRNG, which is in short doing what was GnuTLS doing manually previously, mixing various inputs from the system, in a level and way that a userspace library like GnuTLS could never do, as the kernel has direct access to available hardware and interrupts.
Given the above, a question that I've been asking myself lately, is whether there is any reason to continue shipping something advanced such as a Yarrow-based PRNG in GnuTLS? Why not switch to simple PRNG, seeded only by the system device? That would not only provide simplicity in the implementation, but also reduce the performance and memory cost of complex constructions like Yarrow. In turn, switching to something simple with low memory requirements would allow having a separate PRNG per-thread, further eliminating the bottleneck of a global per-process PRNG.
The current PRNG
To provide some context on GnuTLS' PRNG, it is made available through the following function all:
int gnutls_rnd(gnutls_rnd_level_t level, void *data, size_t len);That takes as input an indicative level, which can be NONCE for generating nonces, RANDOM for session keys, or KEY for long term keys. The function outputs random data in the provided buffer.
There was (a partial) attempt in GnuTLS 3.3.0 to improve performance, by introducing a Salsa20-based PRNG for generating nonces, while keeping Yarrow for generating keys. This change, although it provided the expected performance improvement for the generation of nonces, it still kept global state, and thus still imposed a bottleneck for multi-threaded processes. At the same time, it offered no improvement on the memory consumption (in fact it was increased slightly by a Salsa20 instance - around 64 bytes).
For the yet-unreleased 3.6.0, we took that enhancement several steps further, ensuing the elimination of the locking bottleneck for multi-threaded processes. It was a result of a relatively large patch set, improving the state of the internal PRNG, and rewriting it, to the following layout.
The new PRNG
The Yarrow and Salsa20 PRNGs were replaced by two independent PRNGs based on the CHACHA stream cipher. One PRNG is intended to be used for the NONCE level (which we'll refer to it as the nonce PRNG) and the other for KEY and RANDOM levels (the key PRNG). That reduces the memory requirements by eliminating the heavyweight Yarrow, and at the same time allows better use of the CPU caches, by employing a cipher that is potentially utilized by the TLS protocol, due to the CHACHA-POLY1305 ciphersuite.
To make the state lock-free, these two generators keep their state per thread by taking advantage of thread local data. That imposes a small memory penalty per-thread --two instances of CHACHA occupy roughly 128-bytes--, albeit, it eliminates the bottleneck of locks to access the random generator in a process.
Seeding the PRNG
The PRNGs used by GnuTLS are created and seeded on the first call to gnutls_rnd(). This behavior is a side-effect of a fix for getrandom() blocking in early boot in Linux, but it fits well with the new PRNG design. Only threads which utilize the PRNG calls will allocate memory for it, and carry out any seeding.For threads that utilize the generator, the initial seeding involves calling the system PRNG, i.e., getrandom() in Linux kernel, to initialize the CHACHA instances. The PRNG is later re-seeded; the time of the re-seed depends both on time elapsed and the amount of bytes generated. At the moment of writing, the nonce PRNG will be re-seeded when 16MB of is generated, or 4 hours of operation, whichever is first. The key PRNG will re-seed using the operating system's PRNG, after 2MB of data are generated, or after 2 hours of operation.
As a side note, that re-seed based on time was initially a major concern of mine, as it was crucial for a call to random generator to be efficient, without utilizing system calls, i.e., imposing a switch to kernel mode. However, in glibc calls like time() and gettimeofday() are implemented with vdso something that transforms a system call like time(), to a memory access, hence do not introduce any significant performance penalty.
The data limits imposed to PRNG outputs are not entirely arbitrary. They allow several thousands of TLS sessions, prior to re-seeding, to avoid re-introducing a bottleneck on busy servers, this time being the system calls to operating system's PRNG.
Defense against common PRNG attacks
There are multiple attacks against a PRNG, which typically require a powerful adversary with access to the process state (i.e., memory). There are also attacks on which the adversary controls part of the input/seed to PRNG, but we axiomatically assume a trusted Operating System, trusted not only in the sense of not being backdoored, but also in the sense of doing its PRNG job well.I'll not go through all the details of attacks (see here for a more detailed description), but the most prominent of these attacks and applicable to our PRNG are state-compromise attacks. That is, the attacker obtains somehow the state of the PRNG --think of a heartbleed-type of attack which results to the PRNG state being exposed--, and uses that exposed state to figure out past, and predict future outputs.
Given the amount of damage a heartbleed-type of attack can do, protecting against the PRNG state compromise attacks remind this pertinent XKCD strip. Nevertheless, there is merit to protecting against these attacks, as it is no longer unimaginable to have scenarios where the memory of the PRNG is exposed.
Preventing backtracking
This attack assumes that the attacker obtained access to the PRNG state at a given time, and would need to recover a number of bytes generated in the past. In this construct, both the nonce and key PRNGs re-seed based on time, and data, after which recovery is not possible. As such an attacker is constrained to access data within the time or data window of the applicable generator.Furthermore, generation of long-term keys (that is, the generator under the KEY level), ensures that such backtracking is impossible. That is, in addition to any re-seed previously described, the key generator will re-key itself with a fresh key generated from its own stream after each operation.
Preventing permanent compromise
That, is in a way the opposite of the previous attack. The attacker, still obtains access to the PRNG state at a given time, and would like to recover to recover all data generated in the future. In a design like this, we would like to limit the number of future bytes that can be recovered.Again, the time and data windows of the PRNGs restrict the adversary's access within them. An attacker will have to obtain constant or periodic access to the PRNG state, to be able to efficiently attack the system.
No comments:
Post a Comment