09 September 2020
This is a short story that I wrote some time ago. It’s designed to illustrate some interesting properties of CSPRNGs (Crytographically Secure Pseudo Random Number Generators), which form the bedrock of modern encryption techniques. In particular, the story highlights the fact that a single rather short key is sufficient to generate all the random numbers anyone will ever need. You don’t need a continuous source of pure entropy.
Part 1: The Universal RNG
During the universe’s design stage, it was realized that making some events probabilistic from the point of view of human beings was a greatly desirable property. (Several small proto-universes failed shortly after the intelligent species that populated them was able to work out the deterministic laws behind every event.) For the universe that ultimately went into production, it was decided that making a great many events (including quantum fluctuations) chancy was the safest approach.
True Believers hold that all these chancy events are Really random. That is, they believe that whenever the universe needs a new random number, God uses their infinite power to create it in their mind ex nihilo, and there’s simply nothing more to be said in the way of explanation. Skeptics hold that not even God is capable of acts of creation of this kind, and that there must be some ultimately deterministic story about where these numbers come from.
As it turns out, both are wrong. God is perfectly capable of creating Really random numbers, but although omnipotent is far too lazy to continue doing this all the time. Perhaps God has other universes to tend to, or maybe Heaven needs random numbers for some secret purpose of its own. In any case, the fact is that God only ever bothered to generate 2^8 random binary numbers, in the form of a single 256 bit key embedded into the universe’s core systems. Whenever any “chancy” event needs to happen, the random information is generated by the universe using a CSPRNG that (entirely by coincidence) is exactly equivalent to ChaCha201. So it turns out that the universe is fundamentally deterministic, just not in the way anyone expected.
A stubborn cohort of angels on the review board insisted that this was an inelegant solution to the problem of randomness. They tried to convince God to create an Oracle that would generate Really random numbers all on its own for the universe to use. The Almighty was undeterred, ultimately ruling that the system as designed was “good enough”. Many suspected that God’s real reason was that having another thing around capable of generating uncaused events was taken to be a slight to the Divine dignity. Lucifer led several others in resigning from the panel in protest. Following a disruptive sit-in at God’s office, he was cast like lightning from Heaven.
Unsurprisingly, God was right about the system being good enough. After all, the whole point of the system was to prevent humans from predicting events that were meant to be unpredictable without requiring the intervention of miracles.2 One complaint was that the total number of requests to the RNG over the universe’s lifetime might possibly exceed a value at which the RNG would begin to cycle. However, it was shown that collecting enough data to exploit (or even have a chance at detecting) the issue was physically impossible due to the energy constraints of the universe.
Of course, no steps needed to be taken to prevent direct attacks on the CSPRNG’s state, or key recovery, since these were coded into the OS of the universe itself, and life forms in the universe would have no access to them. So that’s the system that was ultimately put in place: every “random” event that ever happens in this universe can ultimately be traced back to its initial state and the single 256 bit key that makes it unique. While other designs based on entropy pools with estimators were considered, God worried about the universe blocking if at some point they forgot to update the pool with new random data. It was determined that the CSPRNG approach provided enough practical security with a single hard-wired key set at the beginning of time.
Part 2: God’s
It is well known that God has a phone number.3 What is less commonly known is that when God designed the universe, they added a number of other interfaces intended to be helpful to human beings. The True Believers, for example, have it as an article of their faith that God is listening in all the time on
/dev/null. But the most useful interface in God’s
/dev is undoubtedly
The design team realized quite early on that humans themselves would need sources of randomness. Since every bit of random data is ultimately generated by God’s RNG anyway, it was decided that
/dev/random should just return data straight from the RNG with no scrambling. Although this provided far more direct access to the RNG than its designers had initially anticipated, it was determined that its security margin was sufficiently high to allow for these queries.
/dev/random was provided on Earth in a number of high and holy places. God’s interfaces are so fast that they are able to provide data to human devices at the full speed of any interface any humans have been able to construct so far. Of course, all these interfaces have to get their data ultimately from a single device built into the universal mainframe, but light travel time isn’t a problem since that was a constraint built into the universe’s physical laws, not something that applies to the machine the universe runs on.
For a long time humans were happy to take their devices to the nearest
/dev to be filled up with random data. But Lucifer, displeased with the success of the system, tricked one of them into accepting data from an illicit, possibly backdoored source. God was pissed, and things generally went to hell for a while after that. While some authorities wanted to shut down the
/dev system entirely, God ultimately decided that since the security of
/dev/random hadn’t been compromised in any way, they would leave the system in place. In general, however, access to
/dev for ordinary humans became more difficult after this, and many of the high and holy places fell under the control of nation states or were sold off to corporations for extraction of their natural resources.
It gradually came about that humans started to need random numbers more frequently, and even though you could get as many numbers as you needed from
/dev/random, the latency caused by having to travel to an accessible holy place was considered unacceptable. Instead, it became common for priests to provide their own sources of random numbers. They would do this by traveling themselves and returning with 256 bits of random data, which they would then use as a key to seed a CSPRNG that was (incidentally) similar to God’s own. While the priests’ computers could provide random data only much more slowly than
/dev/random, the latency was much better because people didn’t have to travel so far. This method managed to sustain most civilizations for centuries, resulting in a hierarchy where only the highest ranking bishops had direct access to
/dev/random, and local priests would seed their own CSPRNG’s from 256 bit keys provided from their RNGs instead of directly from God’s sources.
Cracks emerged. The role of priests in this scheme became widely regarded as suspect. After all, an untrustworthy priest could be providing random bits from a less-than-holy source, and if anyone on the chain between you and God’s RNG was a bad actor, they could potentially uncover your secrets. Protestants began to insist on making the journey to
/dev themselves to get their own keys, and rolling-your-own PRNG functions quickly became a widespread practice. A number of televangelists were found to be using keys of unknown origin with less than 32 bits of entropy.
Cryptographers eventually invented solutions for collecting and estimating entropy, and most skeptics stopped caring about having any link back to the “supposedly” holy
/dev/random. Instead, their operating systems gathered entropy from secular sources like ordinary “random” events. Of course any key they created was ultimately the result of deterministic processes that had their origin in God’s RNG, but practically speaking this had no effect on their security.
Perhaps most surprising of all was the group of Satanists who insisted on using random numbers generated from secret sources supposedly provided by Lucifer himself. They claim Lucifer has crafted mechanisms for generating Really random numbers, such that every number you get from the Devil’s
/dev/random is entirely Real, not backed by a PRNG. Expert theologians and cryptographers currently believe this to be impossible. Even if Lucifer is using some kind of chancy mechanism to generate these numbers, the process must be ultimately deterministic and known to God.
Part 3: Unexpected Consequences
A number of crypto nerds needed to generate 2048 bit keys for use with asymmetric cryptosystems like RSA. Many of them suspected that God’s RNG might be a PRNG or otherwise distrusted it, and decided like the secularists to collect their own sources of entropy from the universe. They relied on the only the most conservative estimations of entropy, collecting a full 2048 bits of entropy into their pools before turning that data via convoluted methods into their keys. The irony of this, of course, was that every event in all of space-time put together only contained the 256 bits of true randomness hard coded into it at the moment of creation. Their keys were no better than 2048 bits taken from God’s
/dev/random, even no better than 2048 bits taken from a CSPRNG seeded by 256 bits taken from God’s
There is a strange beauty to the fact that all of this was fundamentally secure. No one, no matter how many bits they stored and analyzed from God’s RNG, had any hope of doing better than 50/50 at guessing the next bit that would come out, which someone else could securely use for any purpose. So long as every person in the chain from God’s RNG was trustworthy, each person could take a mere 256 bits to seed a CSPRNG from the person who came before, and every 256 bits that came out of the 10th person’s CSPRNG was just as cryptographically secure as the same amount of data taken from God’s own
/dev/random. 256 bits of sufficiently unpredictable data really is enough for everyone, forever.4
Unfortunately, it didn’t last forever. One of God’s interns introduced a use-after-free into the universe’s code, and a too-clever hacker who found their way into one of the remaining high and holy places managed to root the universal mainframe. In a matter of minutes, they had accidentally triggered a debugging function that had been left in the code, which led to a kernel panic. The universe went out like a light.
To be precise, God used ChaCha20 with what Daniel J. Bernstein calls “fast-key-erasure” here. The point of this isn’t to provide protection against backtracking (key recovery was assumed to be impossible by the design team), but in this case is an efficient and secure way of rekeying which is required by the ChaCha20 cipher because of its smallish 64 bit counter. God briefly considered AES-256-CTR, but decided against it because of its small block size (128 bits), which makes it possible to distinguish from a random oracle with a sufficient number of requests. In theory fast-key-erasure might be enough to protect against this, even without rekeying with new randomness, but the security margin was deemed insufficient in light of available alternatives. ↩
Additionally, leaving open the possibility (from the human point of view) that the universe was non-deterministic was discovered to have psychological benefits. ↩
It’s 42, as suggested by the philosopher Majikthise in Douglas Adams’ Hitchhiker’s Guide to the Galaxy. Unfortunately, God did not put any audio interfaces in