Beauty of Random - Discussion & Crypto

The Beauty of Random

Ever wondered how random is random? Think about how random your day could be if you were to ignore your instincts and drop your habits. You could walk out of the door, take a different route, speak to a random stranger and make them smile. Take that thought and think about all the other random going on in the universe. You could be that person who was spoken to by a random stranger today. All of a sudden, your world has changed, in just a small spec of universal time and space.

The events that were subject to infinite possibilities that led you to today, have all been and gone. But isn’t it awe-inspiring to think of the infinite number of randomness that you could have in your lifetime. That, in itself, is beautiful.

Numbers Numbers Numbers…

Have you ever played or heard of the video game Minecraft? If not, don’t worry, I will explain. It’s a 3d block computer game where the objective is simple, build the world as you wan’t it. In Minecraft there is the option to use a PRNG (Pseudo Random Number Generator) to generate a worldmap for you, this is when a word or phrase is used. So that is 232 or 4,294,967,296. That 32bit generated number isn’t that impressive, even on a human scale. Any high school student knows how to read that number aloud. Consider that there are 8 billion earthlings living today, you could give ~half the world population a different world with these numbers. In-fact, any network engineers out there will know that this number is shockingly restrictive in the ipv4 address space. Using some probability theorem we can say that 1 / 4,294,967,296 isn’t that impressive a pool of numbers. That’s right, it can be reduced with the more world seed’s that get generated by a single person or multiple people.

However, even a game like Minecraft has a 64bit number generator. Using the system clock or pre-inputed numbers we can request a 264 number or 18,446,744,073,709,551,616 or in english - eighteen quintillion, fourhundred forty-six quadrillion, sevenhundred forty-four trillion, seventy-three billion, sevenhundred nine million, five hundred fiftyone thousand, six hundred and 16. This number is a lot more attractive in the realm of random. In-fact, in the context of Minecraft or procedural generated worlds such as No Man’s Sky, we can be reasonable and say that it is large enough pool of numbers. It would take the worlds population working from birth until death, visiting a planet every second of their lives, to see every single possible world. In a universal context it is getting impressive because it’s approaching the number scale’s that astrologists currently use to guess the number of stars out there in the universe.

We can in-fact go a step further, if we wan’t even more possible numbers. Using network engineers as an example again, they may have seen 2128 before. This is the number of available ipv6 addresses today. That is 340,282,366,920,938,463,463,374,607,431,768,211,456 or in english - 340 undecillion 282 decillion 366 nonillion 920 octillion 938 septillion 463 sextillion 463 quintillion 374 quadrillion 607 trillion 431 billion 768 million 211 thousand 456. This is a mind boggling number. You could generate a random number for every atom on the earths surface and then do that for another 100+ earths.

It is important to understand that I am just mentioning base numbers and exponents. Not randomness in a core context. Let’s move onto discussing how we can do randomness.

Make it Random But Secure?

The issue with the number generator’s that I have mentioned above, is that they are not cryptographically secure number generators. For example, the Minecraft 2^64 one uses the system clock, unless the consumer generates a number themselves.

Why is the system clock still not random enough from a cryptography perspective? Well, there is a rather interesting story you can read here. As you can see from that article, sometimes, random just isn’t random enough.

We probably shouldn’t leave it to humans to pick numbers. Even from a large pool of numbers. Human’s are creatures of habit and the human brain is well studied. There are easily spotted give aways when a human brain has been involved in generating random. The human brain is lazy and will typically use the limbic system to produce something from memory or habit.

How have we worked out random in the past?

The great mathematician Jon von Neuman once famously said “Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin.”. von Neuman used a simple pseudo-random number generator named Middle Square. The idea behind middle square is you start with some number (called a seed) and square it. You then take the middle four digits of that square to use for your next seed. Middle square is a very primitive random number generator.

There are more useable Pseudo Random Number Generators like the Mersenne Twister where you can start with a 32 bit seed, you initialize this into a state. Every time you then want to generate a random number you pass it through a one-way function g. Then when you need another number you transform the state with the one-way function f. This is because if anyone discovers a state you don’t want them to be able to decipher past states (forward secrecy).

How do we do random now?

When you visit a https website the browser you are viewing this website from will generate 46 random bytes. Like this:-

01111000 10000100 01101101 01110100 01000110 11100000 11111100 11101101
00010101 00101010 01100011 00110000 11111101 11101010 00101100 01101100
10010001 11010010 11111011 11100100 01000001 00110100 01110000 00010101
11000101 10100100 11000010 01011111 00101010 01010001 10001110 11111000
01001101 00011110 00010110 01100001 10011101 11000000 01100000 01010010
01001100 11100100 01000101 10011101 00101000 11011110

This byte sequence is added to a two byte sequence that includes protocol information and this is then encrypted using the websites public key. This is PKI or public key infrastructure. But how does the client generate this random 46 byte sequence? Typically it uses a CSRNG or a cryptographically secure random number generator. This is usually /dev/urandom/, which is a pseudo unix style interface designed to provide randomness from system related events. The level of entropy provided by /dev/urandom/ is often a topic of controversy on many cryptography discussions. There are genuine concerns on some implementations of using /dev/urandom/ but it is used still extensively today.

The concerns with /dev/urandom usually focus on the entropy pool availability around system uptime and whether the interface will block or just provide a poor entropy pool.

How should we do random in the future?

So, picture a world where we have quantum cryptography and we have a true one-time-pad that is impossible to crack. Surely the randomness that allows for these truly elegant transport cryptography techniques to work is still important? Yes, yes it is. We still need a starting point of randomness even in quantum cryptography QKP (Quantum Key Distribution), which is our polorization order of photons and detectors.

In the realms of causality is true random even possible in our universe? This is actually a fair question and a discussion which would go beyond the intentions of this blog post. For now, i’ll leave you with the most important point of random - the next random seed we need to generate cannot be calculated based on knowing the current seed and we should not know how to calculate previous seeds (forward secrecy).

So what is good random for us in the future? The points at which a Radioactive source will decay is completely unpredictable and therefore a perfect true RNG. Atmospheric Noise (ie. lightning storms) are also perfect true RNG and at random.org you can even generate random seeds from an API that use atmospheric noise. There was even a project for lava lamps (the ones you can buy for your home decorations) to provide true RNG via visual point in time captures.

A Random Wrap

I probably mis-sold random at the start of my blog post by mentioning a human instantiated action that could generate random. That is not a good level of entropy.

We need to look at the true RNG achievable from radioactive sources, atmospheric noise and lava lamps.

It seems that true random does indeed come from nature, but not human nature. So that is still beautiful….

Tags// , , ,