Pseudorandom vs. True Random

Question

Proper security algorithms demand true random numbers. For instance, secret keys & initialization vectors should never not be true random.

However, generating numbers using Java's Random library or C's srand() initialization & then rand() are only able to generate pseudorandom numbers. From what I understand, since functions like srand() gather the seed from some source such as system time, and the 24 hours time is cyclical, it is not truly random. Please correct me if this assumption is flawed.

Also, an example of a truly random number would be if we use a seed from let's say an audio file, and picked a pseudorandom place in the file and then get the audio frequency at that location. Since only the location was pseudorandom but the frequency at that location was not, the value is truly random. Please correct me if this assumption is flawed.

Finally, apologies for compounding the question further, exactly how vulnerable would it really leave systems if pseudorandom values are used? I have learned that AES 128 is actually enough to secure systems (Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers?). For military standards, 192 & 256 were adopted (Why most people use 256 bit encryption instead of 128 bit?). Is using true random values also akin to following such baseless standards, or is it actually crucial?

Answer 1

There is a (common) misconception in this question that there is such a thing as “true” randomness and that this matters for security. In fact, whether “true” randomness exists is a philosophical question (physics gives a partial answer), which is not relevant for security.

There are many notions of randomness. What is relevant for security is unpredictability. Security is defined as protecting against adversaries. A value is “random”, for security purposes, if your adversary cannot find or guess it.

In the context of security, “true random” is sometimes used to mean a value is based on some physical process that no adversary can reproduce. For example, a coin flip is generally truly random in that sense. But not if the coin is too heavily biased, and not if the adversary can see the result of the coin flip. Performing 128 coin flips in front of a camera will not give you a secure 128-bit random number. (It does give you a value that cannot be predicted in advance, which is good for a few things but not good, for example, as a cryptographic key.)

Conversely, a value which is calculated in a deterministic way by a cryptographically secure pseudorandom generator (CSPRNG) is perfectly fine as a random value, as long as adversaries cannot learn the seed or the internal state of the random generator. The fact that only deterministic physical processes were involved other than the generation of the seed, and that the same seed was used to generate other random values, do not compromise the security of the random value (assuming that the CSPRNG was correctly designed and implemented — an assumption that holds for any secure processing).

“True” randomness is necessary for security because you have to seed the CSPRNG somehow. You can seed a CSPRNG with the output of a CSPRNG, but ultimately, you have to start somewhere with a non-deterministic or non-sufficiently-precisely-modeled physical process.

A random value is only good enough if it's sufficiently unpredictable. If I tell you that I picked my secret key at random between 12729af5a51075a68db9d4b05ce7981a and fc42099f25ee1eb5a8dc1178c35868b8, that's not good for me: I did in fact generate those two values randomly, and you don't know which one it is, but you can still find it in at most two guesses. The measure of unpredictability or unknownability of a value is called entropy (beware that there are many related, but distinct concepts called entropy). A fully known value has an entropy of 0. A value which has equal chances of being one of two known possibilities has an entropy of 1. By telling you that my key is one of these two values, I've reduced its entropy to at most 1 bit, no matter how randomly those two values were generated.

An audio file may or may not have a large amount of entropy. At one extreme, if the adversary has the same file, the entropy is 0. If the adversary has a different recording of the same sound, there may be artifacts due to the microphone quality and placement, but audio compression would tend to remove these artifacts. Microphone white noise can be a decent source of entropy, but you should get it directly from the hardware: by the time you get a recording, it's hard to make sure that the noise has been preserved and that the same noise hasn't been copied somewhere else.

The problem with rand() functions in the standard library of most programming languages is not that they're pseudorandom, but that they're not cryptographically secure for two major reasons:

• The adversary can find the seed. For example srand(time()) is mostly predictable (depending on how precisely the adversary knows when your application ran – this has nothing to do with time-of-day being cyclical). And even if the adversary doesn't know the seed, if the seed is a 32-bit number, it's easy for the adversary to try all possible seeds by brute force. If it's a 64-bit number, it's costly but still doable.
• Outputs are not independent: given enough outputs from rand(), it's possible to calculate other outputs.

Secure random generators, such as /dev/urandom or CryptGenRandom, have neither of these flaws: they use a CSPRNG algorithm (which guarantees independent outputs) from a secure seed (which, in modern computers, can be generated from a component in the main CPU).

Answer 2

With regard to:

Also, an example of a truly random number would be if we use a seed from let's say an audio file, and picked a pseudorandom place in the file and then get the audio frequency at that location. Since only the location was pseudorandom but the frequency at that location was not, the value is truly random. Please correct me if this assumption is flawed.

It seems like this approach would produce 'random' values with very little entropy. For example, if the audio file is sampled at 44.1 KHZ, and the audio is 5 minutes (300 seconds) long, this means that there are only 13,230,000 possible values (44100 * 300 = 13230000) in the space that this 'random' number generator produces. An attacker who understands how your 'random' number generator works could easily iterate through all ~13 million values in short order, applying each one as the key in your encryption algorithm, until it finds the correct key that decrypts the ciphertext. See Write a Python or C program to guess the key for an (albeit somewhat contrived) example of how this can be done. Also, programs like hashcat and john the ripper can be used to automate this process.

With regard to your last paragraph: yes AES-256 (and even AES-128) are considered to be strong encryption algorithms - but their strength is contingent on a strong key. If you generated a key by doing: echo -n 'iloveyou123' | sha256sum, then an attacker can find your key very quickly, again using a program like hashcat or john the ripper.

Java has a built-in function SecureRandom(). On the page linked to above, it reads:

This class provides a cryptographically strong random number generator (RNG).

You might want to consider using this function.

Answer 3

Your first assumption is incorrect, as usually system time is pulling from a real time clock which tends to output a unix timestamp which doesn't technically cycle. Pseudorandom number generators like those in popular programming languages (usually the mersenne twister) do cycle, however, due to their nature as deterministic functions. If the generator is initialized with the right parameters, the length of the 'period' or time before the "pattern" of the numbers generated starts repeating is great (2^19937 – 1).

Your second assumption is also not entirely correct as the 'random' number generated is still pseudorandom (debatably) as you are just "whitening" the algorithm by introducing more randomness. True randomness is generated by pulling data from physical phenomena such as radiation and atmospheric noise, and in the case of /dev/random hardware events.

Pseudorandom number generators are technically hackable given (in the case of the mersenne twister) 624 consecutive numbers generated from the seed [https://github.com/kmyk/mersenne-twister-predictor/blob/master/mt19937predictor.py], however that is not an easily exploitable vulnerability in the context of encryption

Answer 4

True random is always better. Unfortunately, it is much harder. The commonly used technique is that at boot time, the system tries to gather as much random values as it can: the date and time (not random at all but it allways changes, and it is to guess at what time (with millesecond precision) the random subsystem asked it, optionally, it can try to gather random values from the network, from the disk, or from the operator if the system can only be manually booted.

From that, it initializes its own system seed. Application that do nor require reproducible sequences can just rely on that system sequence.

Giving a seed is mainly of interest for tests. If you want to control the output of an algorithm using random values, using a specific seed allows to always receive the same sequence, and because of that to alway get the same output value which can then be easily controled. But for production code, you should never give yourself a seed.

Answer 5

In matters of security asking the right questions is extremely important, as is asking clear and precise questions. Learning how to ask these questions is difficult so I will try to restate your questions in more precise terms as well as answer some questions that I think will help further your understanding.

1. Does the fact that the time-of-day seed overflows create a security vulnerability?

Basically no. I don't know of any modern system whose random seed overflows every 24 hours. Some old BASIC implementations did this. The main attack I can think of is to cause the program to run at the same time the next day, and you will get the same sequence of random numbers.

2. Does the fact that the time-of-day is used as a seed create a security vulnerability?

Absolutely. If a program runs srand(time(NULL)) and you know it started 2 hours ago, plus or minus 2 minutes, you know that it got seeded with one of 240 possible values, and you can easily brute force all 240 values, and if you can observe a couple of outputs you can quickly determine which of these seeds was the actual one and how far along in the sequence it has gone.

If this program happens to be one that is generating keys based on that seed alone, you can re-run the program with each of those 240 values and one of them will give the exact same keys.

3. So what if we give a "true" random seed to a pseudo-random generator?

This is definitely better but is not necessarily good enough. Some PRNGs are "stronger" than others, but if you observe enough outputs of the PRNG you can eventually deduce the internal entropy value and begin predicting future values. PRNGs are usually designed to be efficient to execute, rather than be cryptographically secure. However there are exceptions.

4. If we select a pseudorandom location in an audio file, does that give us "true" randomness?

No. The audio file can be considered part of your seed. If you run the same program with the same PRNG seed and the same audio file you will get the same sequence of numbers. Alternatively you can consider the audio file as a "secret" part of your algorithm, which is then security through obscurity.

There's more. An audio file is not random at all (unless it's white noise!) If you exploit some other weakness in the system to guess the outputs of the PRNG, then you can start to build a picture of what is in this audio file, which will let you make guesses when you get a sample that is quite close to a previous sample, but also, you might be able to guess what is in the audio file. For example if you reconstruct enough to guess that it is a recording of a human voice this will make it easier to guess some of the statistical properties within the file.

Even if you don't know what the PRNG is doing, you will still be able to observe a non-uniform distribution in the values of the frequencies in the audio.

5. OK, forget the audio file. Let's just say we have a giant table of 10 million truly random numbers that we got somewhere. And we use a PRNG to index into it. Is that random?

What advantage does that have over just using the numbers in the table in the original order? Are you hoping to be able to re-use the table for a longer period of time? The longer you use it for, the more likely some weakness in the PRNG will be exploited to your detriment. Better to have each entry in the table have a fixed lifespan: single use only. In this case adding a PRNG does not make it any more random. Rather than storing big tables which might be leaked, you might as well get the numbers from a hardware generator exactly when you need them, then discard them.

6. exactly how vulnerable would it really leave systems if pseudorandom values are used?

This depends hugely on the precise combination of application, seed source, PRNG algorithm, and threat model. If the seed source is time(NULL), and the attacker has access to the binary, it's like leaving your keys in the front door. If you at least pull the seed out of /dev/random you might be making an attack infeasible, or it might just need the attacker to observe your program for a few weeks to get enough info to make some deductions.

If the attacker doesn't have your binary but correctly guesses you are using srand(time(NULL)) then they can potentially collect enough observations to make their move.

An attacker could potentially launch a DDoS attack or something to crash your server or cause more instances to spin up, thus guaranteeing that they get their PRNG seed from a reasonably predictable timestamp.

If, however, you use a PRNG that doesn't make it easy to infer the hidden state, seed it with hardware entropy rather than a timestamp, and use the numbers in a way that doesn't leak a lot of information, it will not be easy to attack.

As with all things security though, just one mistake can completely compromise you, which is why it is advisable not to rely on all those assumptions about your seed, PRNG and application when you can instead simply use a sequence of one-time random values derived from hardware entropy.