We have all generated random numbers at one point or another, be it for calculations or HTTP cookies. If you haven’t manually generated one and you are working on a real-life project, there is a high chance somewhere it is being generated for you in "Sumdi" ('Sumdi' is a Marathi word which means to do your work quietly and not let anyone take notice).
In this post, I want to dive into how these random numbers are generated, how random are they actually and what goes behind the scenes. It is really interesting and even though you won’t be "using" this knowledge irl, it will generate a lot of interesting conversations and deepen your understanding of the technology you interact with daily
Most of you might have heard of Cloudflare's Lava Lamps. It's probably the most famous way to generate "truly" random bytes.
It is very well-documented how it works and why they use this, you can read about it here.
In this post, I want to explore how random numbers/bytes are generated in programming languages. I will use Ruby as an example, but pretty much all languages have a similar implementation.
class Random
Okay, before we jump into what happens, it's important to understand the terminology and a few small things to understand and appreciate this subject better.
Let's take the class Random of Ruby and start from there, the introduction covers most of the terms necessary for us to jump-start this journey. Here is what the docs say, read it once, and I will break down the more uncommon terms that we require.
PRNG
"PRNG" means "Pseudorandom Number Generator" which means that a sequence of numbers (bits, bytes...) is produced from an algorithm that looks random, but is in fact deterministic (the sequence is generated from some unknown internal state), hence pseudorandom.
There is another term CSPRNG: Cryptographically Secure Pseudo-Random Number Generator. We will get into this later.
In simple terms, all you need to understand is PRNG is not truly random, and here is where the right question comes in, if it's not truly random, then how random is it?
Mersenne Twister with a period of 219937-1
A Mersenne prime is a prime number that can be written in the form of 2n - 1, where n is an integer. Not all numbers of this form are prime, but when they are, they're called Mersenne primes.
The Mersenne Twister is a type of pseudorandom number generator (PRNG). It's known for providing fast and high-quality random numbers. Its name comes from the fact that its period length is a Mersenne prime. The most common version of the Mersenne Twister, MT19937, has a period of 219937-1.
The period of a PRNG is the length of the sequence of numbers it produces before it starts repeating. The Mersenne Twister with a period of 219937-1 means it can generate 219937-1 numbers before the sequence repeats, an extraordinarily large number.
How Mersenne Twister works is pretty complex and it's above my paygrade. Very interesting nonetheless.
Let's move ahead with the part I want to talk more about!
SecureRandom
As this algorithm is not for cryptographical use, you must use SecureRandom for security purpose, instead of this PRNG.
Okay, this makes sense. For security purposes, we need numbers that are completely unpredictable and Ruby recommends we don't use this class instead use SecureRandom. Let's see what that class definition says.
Here I will focus on /dev/urandom but all three offer more or less the same result.
Okay, so what is /dev/urandom ? How is it more "secure" than the complicated algorithm using large prime numbers?
Now keep in mind we are going to use SecureRandom for generating password tokens and whatnot, we need it to be completely unpredictable! It has to be so unpredictable that even the folks with knowledge of its inner workings are not able to "guess" it.
Computers are very deterministic machines (even if they don’t feel like they are)
Now if you think about it, computers are basically built to always sequentially execute the same set of instructions which we call 'code'. We want the same set of instructions to run in the same way across different computers.
Duh! Seems obvious right?
But here is where we get in trouble, when generating random stuff we want two different computers to do it completely differently. Otherwise, it's not random anymore!
So we understand computers are not unpredictable by nature. So, how or where will they find this "randomness" that we require?
Well, the answer is right there! In the real world, the messy physical world!
Unpredictable events
Every time you type on your keyboard or move your mouse, the disk spins a bit to read some data, it happens in the best case just a little differently.
Now all these events are visible to the kernel. It's the kernel's job to manage these interactions so it keeps track of these events. For example, You move your mouse from (0,1) to (0,3.6).
How wide this range(how spread apart the values are) is what we call entropy.
The more spread apart they are, the harder they are to predict. What they are not is uniform! You are going to move your cursor in a very non-uniform way and the same goes for other events.
Now this is good. We have some unpredictability on our hands, but these are not enough to satisfy our random bytes needs. Enter a CSPRNG.
A CSPRNG is a cryptographic tool that generates a stream of random bytes using all and only the input(our random events) you give to it.
A very simple way to understand how this works is, that we start with a pool just with 0s. Now anytime an event happens
- we convert it into binary
- Hash it with the pool
- Now we have an updated pool.
Rinse and repeat for all events!
We keep doing this and our entropy pool will keep changing. Now for anyone to figure out what my entropy pool is at any point in time, they will have to replicate each and every event of my system, right from mouse movements to hard disk reads in the exact same order with the exact same values! This is pretty much an impossible task!
Now anytime you want say 1000 random bits, we take the entropy pool, hash with 0, 1, 2, 3... (basically a counter). We get some outputs, join them, and voila! We have 1000 bits as random and unpredictable as the pool itself!
Now there are some basic properties of the hash function itself like
- you cant get the input from the output
- all the bits in the input affect all the bits of the output which ensures it is almost impossible to reverse-engineer this!
So back to our question, What is /dev/urandom?
It is exactly this! It's a CSPRNG in the (Linux) Kernel. It looks like a file, you read it like a file. Every time you read some bytes, it will run the CSPRNG and stir the contents of the file. Other OS's have something similar to /dev/urandom.
There is something called /dev/random too. I'll leave it to you to find the difference and what it's use-case is.
Back to SecureRandom
Now the Ruby implementation is pretty much what we talked about. It just reads the file and massages the output in the desired format. Something like...
def self.random_bytes(n=nil)
File.open("/dev/urandom", File::RDONLY) do|f|
f.readpartial(n)
end
end
The current implementation is in C, but you get the idea...
And that is why SecureRandom is considered secure. It still relies on a pseudorandom number generator as we would do in Ruby Land, but it has the benefit of using environmental noise, making it astronomically much more difficult to crack, and technically impossible without gathering the exact same environmental data.
Footnote: There are cases where /dev/urandom has been exploited during the boot sequence. At that time, the system may not have enough entropy available to provide safe random numbers. When the start sequence is being initiated, the system starts from a known state, always the same (particularly true for virtual images), and mostly the same also on any other identical environment. This is also a pretty interesting rabbit hole if you wish to visit it.
Top comments (0)