Random numbers in cryptography

In cryptography, randomness is a vital characteristic needed for creating secure encryption keys.

Randomness: What does it mean?

Randomness refers to the impossibility or difficulty of predicting an event or outcome. In cryptography, random numbers are unpredictable and should be uniformly distributed among all possible values.

How to obtain a random number? A convenient but insecure way using LCG (Linear Congruential Generator)

This website uses cookies to enhance the user experience. By continuing to use the site, you agree to the use of cookies. For more information, see our privacy policy.

What is LCG?

LCG (Linear Congruential Generator) is a simple and efficient algorithm for generating random numbers. It is based on the following formula:

X_n+1 = (a * X_n + c) mod m

where:

• X_n is the value of the nth random number
• a is a constant referred to as the "factor"
• c is a constant known as "addition"
• m is a module that restricts the value of printed numbers
• mod is the modulo operator, which returns the remainder of a division

Using LCG

• Start with X_0 having a value that is not divisible by the module m. This initial value is called the seed.
• Calculate the next number X_n+1 using the formula.
• Repeat step 2 to get more random numbers.

LCG illustrative example

Here is an example of LCG's operation to illustrate with small values:

Parameters:

• a = 3
• c = 1
• m = 7

Initial value (seed):

• X_0 = 2

Number generation:

Calculate X_1 = (3 * 2 + 1) mod 7 = 7 mod 7 = 0.

Let's calculate X_2 = (3 * 0 + 1) mod 7 = 1 mod 7 = 1.

Let's calculate X_3 = (3 * 1 + 1) mod 7 = 4 mod 7 = 4.

Calculating X_4 = (3 * 4 + 1) mod 7 = 13 mod 7 = 6.

Let's calculate X_5 = (3 * 6 + 1) mod 7 = 19 mod 7 = 5.

Let's calculate X_6 = (3 * 5 + 1) mod 7 = 16 mod 7 = 2.

Protect your data from cyber threats

Features of LCG

• Fast and efficient: LCG is a very fast and efficient algorithm for generating random numbers.
• Simple: The formula of LCG is simple and easy to understand.
• Predictability: LCG is predictable if the initial value, multiplier, increment, and modulus are known.

LCG is not cryptographically secure

LCG is not intended to be cryptographically secure, and its misuse as such (for example, to create encryption keys or application session tokens) will lead to serious vulnerabilities.

In the case of LCG, the only "secret" is typically the seed value, with which LCG has been initialized. If an attacker obtains it, the attacker is able to predict both all future and all past values that have been generated.

For example, in the case of application session identifiers, this would mean that an attacker could walk back all the session identifiers given to users and log in as any user with a valid session, or wait for the next session identifier to be given to a user and then capture it.

Thought experiment: LCG and lottery numbers

Let's assume that an LCG is used for generating random numbers in a lottery draw. Jaska figures this out and makes a plan to get rich. For the sake of simplification, let's assume that Jaska knows the multiplier (a), increment (c), and modulo (m). These are rarely secrets.

• First, Jaska downloads a list of old lottery rows to his computer.
• Then Jack combines the lottery numbers into one line where there are, for example, the 100 most recent predicted numbers drawn in the lottery.
• Next, Jaska begins using brute force technique to try one seed value after another. 1... 2... 3.. 4.... Jaska uses a tremendous amount of computing power and tries a huge number of different seed values per second.
• Eventually Jaska finds one simulated value: 3827182, which would lead exactly to these 100 numbers that have been predicted in the last lottery draw.
• Jaska still checks that the seed was indeed correct and tries to go back with LCG and make sure that the numbers are the same as the earlier lottery numbers. They are.
• Now Jaska is confident in his success. Jaska moves forward with LCG by 7 numbers. 4, 8, 15, 16, 23, 42, 43. Jaska now knows the winning lottery numbers for the next week.
• Jaska sends the lottery coupon.

Code example: java.util.Random

Here is Java code with a critical vulnerability. Why? Because java.util.Random uses LCG. It is not intended for cryptographic use, but this application still uses it to create session tokens.

import java.util.Random;

public class SessionIDGenerator {
    private Random rng;

    public SessionIDGenerator() {
        // Initialize the Random object without an explicit seed value, in which case the value based on the current time is used by default
        this.rng = new Random();
    }

    public long generateSessionID() {
        // Generate and return a new session ID
        return Math.abs(rng.nextLong());
    }
}

The vulnerability could be fixed like this. Instead of using java.security.SecureRandom class. The difference is that this class uses cryptographically secure PRNG (i.e. CSPRNG) in the background.

import java.security.SecureRandom;

public class SecureSessionIDGenerator {
    private SecureRandom secureRng;

    public SecureSessionIDGenerator() {
        // Initialize the SecureRandom object
        this.secureRng = new SecureRandom();
    }

    public long generateSecureSessionID() {
        // Generate and return a secure session ID
        return Math.abs(secureRng.nextLong());
    }

}

It is good to keep this in mind if you ever do, for example, a security check for an application. Check the application's code to see if random numbers are generated there and how they are used. If they are used for cryptographic purposes, make sure that the PRNG used is cryptographically secure!

PRNG: Pseudo random number generator

LCG belongs to so-called pseudo-random number generators (PRNG, pseudo-random number generator).

PRNG is an algorithm that generates number sequences that appear random, but are not actually random. As you saw, these algorithms are based on mathematical formulas and initial values called seeds. The same seed always leads to the same number sequence.

Pseudorandom number generators are common and efficient, but they have their limitations. Because they are based on algorithms, it is possible to predict future numbers or find weaknesses in the algorithm that weaken randomness.

Pseudo-random number generators (PRNGs) are not actually random but extremely deterministic. True random number generators (TRNGs), on the other hand, are a different story.

TRNG: True Random Number Generator

The TRNG utilizes physical phenomena, such as thermal noise or radioactive decay, to generate random numbers. These processes are inherently unpredictable and produce genuinely random numbers.

TRNGs are more expensive and slower than PRNGs, but they offer a higher level of security. Randomness cannot be predicted or manipulated, making them an excellent choice for cryptographic applications where security is critical.

Entropy

In the context of IT and cryptography, entropy refers to unpredictability or randomness used in security applications, such as creating encryption keys. It is an important concept because a high level of entropy means greater unpredictability, making the system more secure against attacks. Entropy can be collected from various sources commonly considered unpredictable, such as user input timing (e.g. keyboard keystrokes, mouse movements), hardware operation (e.g. disk drive rotation speed, network latency), or even physical environmental phenomena (e.g. temperature fluctuations).

Collecting entropy and using it in pseudorandom number generators (PRNG) or cryptographically secure pseudorandom number generators (CSPRNG) is critical to ensure that the generated random numbers are sufficiently unpredictable and secure. For example, in the Fortuna algorithm (which we will discuss shortly), the collection and management of entropy play a crucial role in its design, allowing the algorithm to produce high-quality randomness, which is particularly important in security-critical applications.

How to obtain a cryptographically secure random number? A better example with Fortuna

Fortuna is a cryptographically secure pseudorandom number generator (CSPRNG) designed by Bruce Schneier and Niels Ferguson. Fortuna is designed to resist various types of attacks and provide a high level of security. It consists of several components, such as collecting entropy from multiple separate sources, an entropy accumulator, and several pseudorandom number generators (PRNG) that produce the final random number. Fortuna is able to continuously receive entropy and is designed in such a way that it does not suffer from certain mathematical problems that can weaken the security of other PRNGs.

Summary

There are different types of randomness for different purposes. When it is needed for cryptographic purposes, it is vital to choose a suitable random number generator for that purpose!