Where does the randomness come from

Cryptographic random number generators

Cryptographic random number generators or random number generators play an important role in cryptography. Every encryption method requires random numbers to generate digital keys.
A random generator is a method that delivers a random sequence as a result. A random sequence is understood to be a bit sequence of zeros and ones, the sequence of which is random and unpredictable. A random number is an excerpt from a random sequence of limited length.

Random number generators are an often underestimated area in cryptography. An attacker can crack the most secure encryption method if he knows or can even influence the random number when the key is generated.
Any encryption depends on the quality or degree of randomness of such a key.

Coincidence (entropy)

Coincidence or entropy is, in a sense, an event in the present, the outcome of which could not be determined or predicted in the past. But in computers as we know them today, coincidence is not really intended. Logical functions work here, the results of which can be predetermined and understood at any time. And that's right. Because computers are designed so that the same output always occurs when the same input is always made. If a computer adds the numbers 1 and 1, the result should always be 2. That is the condition why computers have prevailed. They always do the same things the same way.
But this is a problem if the result is supposed to be "coincidence". So a function should not always output the same result, but something different every time. But where is this "coincidence" supposed to come from, in a system that always does the same thing and that nothing is left to chance?
In practice, one is content with the definition that "chance should be statistically distributed as well as possible and not be predictable". The randomness of an output random sequence must be verifiable by mathematical means.

Where does the coincidence come from?

A real random number generator requires a physical process that cannot be reproduced. A separate hardware module that generates random numbers from measured values ​​is best suited for this. Voltage fluctuations in resistors and semiconductor components are particularly suitable here. Due to the variance of specimens for these components and complex physical conditions, it can be assumed that the measured values ​​always turn out differently and cannot be generated subsequently. That's the point. However, such hardware modules are not part of the standard equipment of a computer.
Another good source of chance are time differences between events within a computer that arise from mechanically generated information and can be determined without a hardware module.

  • physical noise in components
  • Timing between network packets
  • Hard drive rotation latency
  • Timing of mouse and keyboard inputs

Time differences are not predictable. For example, the time between drive accesses, mouse movements and keystrokes. If you combine several of them with each other, then you can see the result as random and at the same time almost impossible to predict or reproduce.

What sounds so simple is sometimes difficult or impossible to implement in practice. For example in smart cards. There are no input devices or hard drives here. On smartphones, too, chance is only to a limited extent random. These devices are particularly vulnerable if an attacker can manipulate the remaining mechanisms of random generation and thus predict the chance.
In practice this is a real problem because it also affects restarted computers, especially servers. If a device is booted up and the crypto services started, then of course they want to have a chance for temporary keys. This is not a problem with a PC because the user ensures prompt user input using the mouse and keyboard. On a server that has no hard drive (because SSD or network storage) and where no mouse and keyboard inputs are made, the material is only available to a small extent for chance. There isn't much that can be generated by chance.

Pseudo random generator

Every operating system and every programming language provides functions for generating random numbers. But these random functions are not good enough for cryptography. For example, if they are implemented purely in software. Most of these random number generators provide results that an attacker can guess. Therefore, all random number generators that do not require physical measurement are pseudo random number generators.

A pseudo-random generator is a process that processes a starting value, also known as a seed, into a random sequence of any length. An incremental function is applied to the start value as often as required.
In principle, pseudo-random generators only deliver comprehensible random sequences. In addition, they always deliver the same random value with the same starting value. This means that a pseudo-random generator is of little value without a real random seed.
If such a pseudo-random generator is used in cryptography, it has consequences for security. If an attacker knows a random sequence and the increment function, then he can generate all random numbers. For this reason, a random number generator only outputs part of the random number or as a hash value. Another option is to use a key-dependent incremental function.

In order for a random number to be used in cryptography, it must be ensured that an attacker cannot guess or manipulate the start value. The attacker then only has knowledge of the incremental function.
Basically, a pseudo-random generator always delivers predictable results. The result cannot be predicted only if the starting value is not known.

With some random number generators, the output value lies between random and pseudo-random. For example, if the function uses memory areas of the main memory that change frequently. The problem with this is that if this part of the main memory is influenced by software, then it is more of a pseudo-random occurrence. The situation is different if the memory area is directly influenced by hardware.

Prime number generator

If you need two prime numbers according to the RSA method, then you fall back on a prime number generator. Large prime numbers are used so that an attacker cannot guess the numbers. For example with a length of 512 bits, the number of which is of course limited. However, there are 10 of them50. With 1,024 bits it would even be 10100. It is therefore impossible for an attacker to guess the randomly selected prime number.
The way a prime number generator works is quite simple. A random number is simply generated and then checked whether it is a prime number. If not, a new random number is generated and checked again. This is repeated until a prime number is found.
The algorithm that checks the number must of course not take an infinite amount of time. For this reason, one works with an algorithm that recognizes a normal number as a prime number in exceptional cases. This is not a problem, because the RSA method also works with normal numbers, only then is it no longer entirely safe. For an attacker, that would be a hit. But he would also have to first find out that it is not a prime number. Depending on the situation and the attack, the effort involved is too great.
The most important method for generating prime numbers is the Miller-Rabin method. It is easy to implement and there is little chance of getting a wrong prime number.

A good random number generator

To be sure that the random value is as random as possible, several random sources are used. The more the better, the less likely it is that an attacker can guess the coincidence. If an attacker does try, then he has to guess or manipulate the entire pool of chance.
Mixing the random sources is best done with a cryptographic hash function. The output value can then be formed from the hash value.

The point in time at which the random number generator is initialized is important. With a normal PC, this can happen quite early in the boot process. The situation is different with embedded hardware, for example routers. Here chance is more difficult to establish. Here it just takes longer until enough randomness is available.

A good random number generator always draws chance from several sources. It could be that one of the sources is not giving enough randomness. For example because it has been manipulated.

Coincidentally, random number generators aren't all that random

Again and again there are reports about incorrect implementations of random number generators. The result is often insufficient entropy, for example when generating keys.
In an operating system like Linux there is the function "/ dev / random" into which a program can write data in the form of self-generated randomness. That makes sense if you want to limit the influence of outside manipulation. There is a similar function in Windows operating systems, but no data can be passed to it. So a programmer has no control over how random the chance that comes out of it is.
In another case, they had an idea to deal with the problem of limited randomness in freshly started systems. When shutting down, randomness should be generated and saved in order to use it when restarting. This is of course not a good idea because an attacker has access to this coincidence and can also use it. In such a case, the generated key would be easy to determine.

Through the publications by Edward Snowden in mid-2013, it became known that the NSA had back doors built into random number generators. In one case, the random number generator was only able to generate 256 different random numbers, which meant that the NSA was able to reconstruct randomly generated keys.
The mistake could only be found and corrected through openness to the source and the never-ending attention of millions of eyes.
Ordinary users have no chance to check how well a particular implementation is working to identify a bad random number generator. You have to trust your software.

Overview: pseudo random generators

Compared to other cryptographic methods, there are many different methods for random number generators, but only a few of them are standardized. That is understandable too. No interoperability is required with random generators.
Many good pseudo-random generators can be found in the publications of standardization organizations, but this does not correspond to any standardization. This is also not necessary, because if the implementation looks different every time, then an attacker has to deal with it again and again and cannot use a ready-made library. The worst thing that can happen with an implementation is that the output value is not that random. So it doesn't hurt if programmers use good libraries.
Pseudo-random generators are mostly based on other cryptographic methods, such as hash functions or encryption methods.

  • Cryptographic hash functions
  • Key-dependent hash functions
  • Block ciphers
  • Feedback shift registers

Other related topics:

share

Product recommendations

Everything you need to know about networks.

Network technology primer

The network technology primer is a book about the basics of network technology, transmission technology, TCP / IP, services, applications and network security.

I want that!

Everything you need to know about networks.

Network technology primer

The network technology primer is a book about the basics of network technology, transmission technology, TCP / IP, services, applications and network security.

I want that!