That’s So Random: (Pseudo)Random Data Generation in Kong API Gateway
Kong is the world’s most popular open source API gateway and microservices management layer. Built on top of NGINX, it delivers high performance with easy installation and administration.
Recently we published a release candidate 0.11 for Kong API Gateway. This release features a host of changes, large and small, that dramatically improve the performance, flexibility, and security of Kong. In this blog post, we’ll examine a seemingly innocuous change – an update to how Kong generates random data – and discuss how this change improves the security and flexibility of Kong moving forward.
A quick note on random data: When we talk about “random” data, what we really mean is pseudorandom data. As deterministic machines, computers can never generate “truly” random data. The best we can hope for in a random number generator is unpredictability; the data provided by an RNG should “look” random. This is typically done by initializing a state machine with a “seed” value; the RNG then produces a long stream (and by “long” we mean “never repeating within a reasonable lifetime”) of bits that appear “random”. Because an RNG’s state machine is deterministic, feeding it the same seed in multiple executions will result in an identical string of bits returned.
For the purposes of our discussion, there are two types of random number generators we care about: pseudorandom number generators (PRNGs), and cryptographically secure pseudorandom number generators (CSPRNGs). In actuality, CSPRNGs are a subset of PRNGs; they maintain the same principles as a “regular” PRNG (e.g. generating a stream of pseudorandom numbers generated from an initial seed), but the state machine of a CSPRNG is designed to hold up to scrutiny/attack by an outside observer (e.g., an attacker being able to make assumptions about the RNG’s state based on previous output). CSPRNGs are also designed to have their state “mixed” by feeding in new sources of entropy, to further thwart attacks.
In Linux environments, non-secure PRNGs in various programming languages are typically provided by a built-in PRNG (such as Python’s lib/random.py), or a wrapper around glibc’s rand(). Meanwhile, cryptographically secure PRNGs also fall into two categories- userspace CSPRNGs (such as the RAND_* interface provided by OpenSSL), and the kernel CSPRNG (to which the famed /dev/random and /dev/urandom are associated). The RNG in LuaJIT (which powers Kong), math.random(), is a userspace PRNG (Tausworthe).
Okay, enough theory.
Who cares how Kong is generating random numbers, or whether or not it passes any cryptography tests?
Kong is an API gateway, not a crypto nerd’s playground!
Fair point, but it turns out that Kong needs to be able to generate random data in a secure fashion in a variety of contexts, such as auto-generating API key authentication or OAuth token data. The nature of these tokens is such that strong pseudorandomness is a valuable property.
Historically, random data has been generated using the OpenSSL CSPRNG. OpenSSL’s RNG provides a handful of library functions that Kong leverages to generate cryptographically secure data. In the past, Kong used these functions in a limited context, to seed each Kong process’s random number generator. In reviewing Kong’s use of PRNGs, we saw an opportunity to improve how we create new random strings. This meant switching, where appropriate, to use the kernel’s CSPRNG to provide better quality pseudorandom data generation.
Prior to Kong 0.11, random strings were built by generating a v4 UUID and stripping the hyphens, resulting in a 32 character hexadecimal-encoded string. There were a few problems with this approach: as a lowercase hexadecimal value, the search space for these strings was far smaller than it should have been (only 16 possible characters in each element of the string). Additionally, the UUID generation library used by Kong leverages LuaJIT’s internal random number generator, which, as we previously noted, is not a cryptographically secure RNG. Our solution was to replace the UUID approach with a modified Base64 encoding of kernel CSPRNG data; using the kernel results in strings generated from cryptographically secure pseudorandom data, and changing the encoding format dramatically increases the search space for random strings.
“Wait”, I can hear you say now, “you just said that Kong uses OpenSSL! Why this need for the kernel CSPRNG as well?”.
Excellent question, astute observer!
Remember that Kong leverages OpenSSL’s CSPRNG only to seed the LuaJIT’s RNG. Since Kong should never be generating cryptographically secure data based on math.random() (remember, this function returns data from a PRNG that is not considered cryptographically secure), we only care about generating a unique seed for each worker process. In other cases, such as where Kong generates random strings for fields such as HMAC or key authentication fields, we care much more strongly about generating this data in the most secure fashion. In these cases, we want access to the best quality pseudorandom data that we can get – and this is the kernel’s CSPRNG.
This is not to say that OpenSSL’s CSPRNG is inappropriate here. As a userspace library, generating pseudorandom data from OpenSSL RAND_bytes is faster than reaching to the kernel, because there is no context switch involved to make a syscall. However, recent analyses of OpenSSL’s RNG uncovered a few flaws in its design, and will likely subject it to further scrutiny in the future. At the end of the day, the best CSPRNG in our context is provided by the kernel.
Unfortunately, there’s a small price to pay for calling out to the kernel for this. Historically, access to the kernel CSPRNG was provided through two file descriptor interfaces: /dev/random and /dev/urandom. Currently, the most portable way to access this data is via a read() syscall. In Linux, file I/O of this nature is blocking, meaning that the process has to wait for the kernel to return before it can continue execution. NGINX, the underlying web server that powers Kong, is designed in such a manner that blocking, expensive calls (like this file I/O) can be detrimental to performance: the NGINX process has to sit and wait for this read() call to return, and cannot be used to serve other requests while it waits. This limitation is so stark that NGINX developers have been warned for almost a decade to avoid blocking syscalls and I/O like this.
This is the part of the blog post where we tell you that we found a magic approach/workaround to blocking I/O in OpenResty, and can now serve petabytes of kernel CSPRNG data in a nonblocking fashion, right?
File I/O is still blocking.
We have simply weighed the pros and cons of accessing the best CSPRNG we can, knowing that this access is typically done in a cold code path, and acknowledging that blocking the worker’s event loop for an infinitesimal amount of time to read from the non-blocking urandom file descriptor is an acceptable tradeoff. Kong only needs to read random bytes from the kernel when explicitly asked to by the developer: currently, this is only done when new objects in the Kong Admin API are created with default, secure values, which is done as part of Kong administration, not as a regular part of the request lifecycle.
This doesn’t mean we’re done improving CSPRNG access. Starting with the 3.17 kernel, Linux provides a syscall that wraps around the same CSPRNG that feeds urandom, meaning that we could leverage this syscall in the future to retrieve this data without blocking the working over file I/O. Additionally, recent releases of glibc contain a wrapper for this sycall, further simplifying userspace access. However, not every supported distro uses this kernel in its release, so, for the time being, we need to rely on urandom to fit our needs.
We know that this change in itself isn’t a big or flashy. There are no new shiny interfaces to Kong, no new docs, no groundbreaking discoveries to be made here. But changes like this are important; as engineers, we are committed to creating the best API gateway in the world. Building secure, stable, high-performance software is our goal, and changes like this are just a small part of how we’re continuing to improve Kong for all our users.