Cryptography: what are random numbers used for?

Originally, the purpose of cryptography was to allow two speakers (traditionally called Alice and Bob) to exchange messages without another speaker (traditionally called Eve) being able to read them. Alice and Bob are therefore going to agree on a method for exchanging each message M in an encrypted form C. not find the information exchanged without knowing the appropriate secret, which is generally called a key.

It’s a very old exercise, since we speak for example of the “cipher of Julius Caesar”. However, it has become very important in recent years, due to the growing need to exchange information. Cryptography has thus become an essential part of our daily lives. Beyond the exchange of messages, cryptographic mechanisms are used in many everyday objects, to identify and authenticate users and their transactions. These mechanisms are found in telephones, to encrypt and authenticate communications between the telephone and radio antennas, or in car keys, bank cards, etc.

The Internet has also popularized the padlock in browsers, to indicate that communications between the browser and the server are protected by cryptographic mechanisms. To function correctly, these mechanisms require the use of random numbers, the quality of which (more precisely their non-predictability) contributes to the security of the protocols.

Cryptographic algorithms

To transform a message M into encrypted C by means of an algorithm A, keys are used. In so-called symmetric algorithms, we speak of secret keys (Ks), which are shared and kept secret by Alice and Bob. Within the framework of asymmetric algorithms, there are pairs of public (KPu) and private (KPr) keys. For each user, KPu is known to everyone, while KPr must be carefully kept by its owner. Algorithm A is also public, which means that the secrecy of the communication relies solely on the secrecy of the keys (secret or private).

Sometimes the transmitted M-message is not important in itself, and the purpose of encrypting a given M-message is to verify that its correspondent can decrypt it. This proof of the possession of Ks or KPr can be used in certain authentication schemes. In this case, it is important never to use the same message M several times, since this would allow Eve to know information relating to the keys. It is therefore necessary to generate a random message NA, which will change each time Alice and Bob want to communicate.

The best known and probably the most used example of this mechanism is the Diffie-Helman algorithm. This algorithm allows a browser (Alice) and a website (Bob) to obtain an identical secret key Ks, different at each connection, by having exchanged their respective KPu beforehand. This process is executed for example when connecting to a merchant site. This allows the browser and the website to exchange encrypted messages with a key that will be destroyed at the end of each session. This means that you don’t need to keep it (ease of use, security because there is less chance of losing this key). This also implies that we will not encrypt a lot of traffic with the same key, which makes cryptanalysis attacks more difficult than if we always use the same key.

The generation of random numbers

In order for Eve to not be able to obtain the secret key, it is very important that she cannot guess the NA message. In practice, this message is often a large random number used in the calculations defined by the chosen algorithm.

Initially, random generation was used for many simulation works. To obtain relevant results, it is important not to repeat the simulation with always the same parameters, but to repeat the simulation with different parameters, hundreds or even thousands of times. It is then sought to generate numbers which respect certain statistical properties and which do not make it possible to differentiate the sequence of numbers from a sequence which would be obtained by drawing dice, for example.

To generate a random number NA that can be used in these simulations, we generally use so-called pseudo-random generators, which apply a reprocessing algorithm to an initial value, called “seed”. These pseudo-random generators aim to produce a sequence of numbers that looks like a random sequence, according to these statistical criteria. However, by using the same seed twice, we get the same sequence twice.

The pseudo-random generator algorithm is generally public. If an attacker is able to guess the seed, he is able to generate the random sequence, and thus obtain the random numbers used by the cryptographic algorithms. In the specific case of cryptography, the attacker does not even necessarily need to know the exact value of the seed. If he is able to guess a set of values, that is enough to quickly calculate all possible keys and break the cipher.

In the 2000s, programmers used seeds that could be easily guessed, based on time for example, making systems vulnerable. Since, to avoid this ability to guess the seed (or a set of values ​​of that seed), operating systems rely on a mix of physical elements of the system (CPU temperature, connections on the bus, etc.) . These physical elements are impossible for an attacker to observe, vary frequently, and therefore form a good seed source for pseudo-random generators.

What about vulnerabilities?

Although the field is now well understood, random number generators are still sometimes subject to vulnerabilities. Thus, between 2017 and 2021, cybersecurity researchers found 53 such flaws (CWE-338). This represents only a small number of software vulnerabilities (less than 1 in 1000). Several of these vulnerabilities, however, are high or critical, indicating that they can be used quite easily by attackers, and that they are widespread.

An emblematic example in 2010 is Sony’s error on the PS3 software signing system. In this case, the reuse of a random number for two distinct signatures enabled an attacker to find the manufacturer’s private key: it then becomes possible to install any software on the console, including pirated software or malware.

Over the period 2017-2021, flaws also affected physical components: Intel Xeon processors, Broadcom chips used for communications, and Qualcom SnapDragon processors embedded in particular in mobile phones. These flaws affect the quality of the random number generation. For instance, CVE-2018-5871 and CVE-2018-11290 relate to a seed generator whose periodicity is too short, that is to say which repeats the same series of seeds quickly. These vulnerabilities have been corrected and they only affect certain functions of the hardware, which limits the risk.

The quality of the generation of random numbers is therefore effectively a security problem. Operating systems running on recent processors (less than 10 years old) have hardware-based random number generation mechanisms. This generally makes it possible to ensure good quality of these and therefore proper operation of the cryptographic algorithms, even if occasional vulnerabilities may occur. On the other hand, the difficulty is particularly marked on the side of connected objects, whose hardware capacities do not allow the implementation of random generators as powerful as those available on computers and smartphones, and which often prove to be more vulnerable.

We would love to say thanks to the author of this short article for this awesome web content

Cryptography: what are random numbers used for?

We have our social media pages here and additional related pages here.