Random number generation is a very important topic in Cryptography. It is the technique that helps us avoid brute force attacks.
A brute force attack is when the attacker tries all possible keys to try to decode an encrypted message. If the attacker can predict how the key was generated, then the number of keys to try will be considerably less. However, if the keys are randomly generated, and the number of possible keys is big enough, then a brute force attack will be unfeasible.
Anyone who attempts to generate random numbers by deterministic means is, of course, living in a state of sin.
John von Neumann
Let’s start with some definitions to get a better understanding of the topic.
Table of Contents
- Random number generators
- Some applications of random numbers in cryptography and network security
- Sources of entropy for Random Number Generators
- Summary
Random number generators
We can have two types of random number generators:
- True random number generator
- Pseudorandom Number Generator
A True Random Number Generator takes as input an effectively random source. Some sources examples are atmospheric noise, thermal noise, photoelectric effect, etc. These are physical phenomena that are unpredictable. The number generator translates the physical effect into a number.
We also refer to the input source as Source of Entropy.
We can use other physical sources that are related to the computer we use. For instance keystrokes, mouse movements, etc.
One of the application of this type of generator is on protocols like TLS.
In some cryptographic applications, you can find the use of certain deterministic algorithms to generate random numbers. Because the algorithms are deterministic the sequence of numbers is not truly random.
Therefore, we call them Pseudo-Random Number Generators (PRNG). Even though the sequence is not truly random, the use of some of these algorithms is generally accepted in cryptography.
This type of number generation has the advantage that is faster than the true random number generators. They use an initial value called the seed.
Requirements for cryptographically secure PRNG
The basic requirement for using a Pseudo-Random Number Generator for cryptographic purposes is that an attacker not knowing the seed, cannot determine the pseudo-random number.
One way of choosing a seed can be to use a True Random Number Generator. Once we have a random seed, then we generate pseudo-random numbers.
Also, every sequence of random numbers needs to have the following properties:
- Randomness
- Unpredictability
We define the Randomness characteristic in statistical terms.
For such a definition, we can say that the sequence of 1s and 0s should follow a uniform distribution. In other words, the frequency of appearance of 1 and 0 should be around the same value.
The second criterion for a random number sequence is independence. This means that having a subsequence of the random number (1s and 0s), you cannot infer the whole sequence (the random number).
Unpredictability is the characteristic that knowing one random number from a sequence, you cannot predict other numbers from that sequence.
Some applications of random numbers in cryptography and network security
Find below some applications of random numbers:
- Key distribution. Usually, some applications generate nonce to prevent replay attacks.
- Reciprocal authentication schemes
- Session key generation
- Generation RSA key pairs.
- Generation of bitstreams for use in stream ciphers
Sources of entropy for Random Number Generators
The document Randomness Requirements for Security RFC 4086, establishes sources of entropy that we can use on a computer to generate a True Random Number.
See the sources found on the document as well as their description below.
Sound/Video Input
“Many computers are built with inputs that digitize some real-world analog source, such as sound from a microphone or video input from a camera.
The “input” from a sound digitizer with no source plugged in or from a camera with the lens cap on is essentially thermal noise. If the system has enough gain to detect anything, such input can provide reasonably high-quality random bits.
This method is extremely dependent on the hardware implementation.
If you are using a Unix-based system, you can try the following command:
cat /dev/audio | compress – >random-bits-file”
Disk drives
“Disk drives have small random fluctuations in their rotational speed due to chaotic air turbulence [DAVIS, Jakobsson].
The addition of low-level disk seek-time instrumentation produces a series of measurements that contain this randomness.
Such data is usually highly correlated, so significant processing is needed, as described in Section 5.2 of RFC 4086.
Nevertheless, experimentation a decade ago showed that, with such processing, even slow disk drives on the slower computers of that day could easily produce 100 bits a minute or more of excellent random data.”
Summary
In cryptography, we use both True Random Number Generators and Pseudo-Random Number Generators.
The requirements for a cryptographically secure pseudo-random number generator are:
- If an attacker does not know the seed, you cannot infer the random sequence.
- Randomness.
- Unpredictability.
Random numbers are extensively used in Cryptography. Therefore, it is important to know which generators are cryptographical secure so we can use them in applications that require secrecy.
Related post: