The Root of Unpredictability—Random Numbers

1. Why Do We Need Random Numbers?

In the previous articles, many cryptographic techniques were mentioned, and random numbers appear throughout these techniques.

• Generating keys
  Used for symmetric cryptography and message authentication codes
• Generating public-key cryptography
  Used to generate public-key cryptography and digital signatures
• Generating initialization vectors (IVs)
  Used in the CBC, CFB, and OFB modes of block ciphers
• Generating nonces
  Used to defend against replay attacks and in the CTR mode of block ciphers
• Generating salts
  Used in password-based encryption such as PBE

The purpose of using random numbers is to increase the unpredictability of ciphertext so attackers cannot see through it at a glance.

2. What Are Random Numbers?

It is difficult to give a rigorous definition of random numbers. We can only distinguish different types of random numbers by their properties.

• Randomness — There is no statistical bias; the sequence is completely disorderly
• Unpredictability — The next number cannot be inferred from the previous sequence
• Irreproducibility — Unless the sequence itself is saved, the same sequence cannot be reproduced

Random numbers used in cryptography must at least reach the level of unpredictability—that is, they must at least be strong pseudorandom numbers, and ideally true random numbers.

In everyday life, rolling dice produces a sequence of true random numbers, because the sequence it produces is irreproducible and has all three properties: randomness, unpredictability, and irreproducibility.

1. Randomness

Although randomness may appear disorderly, attackers can still see through it. Therefore, it is called weak pseudorandomness.

A pseudorandom sequence generated by a linear congruential generator looks disorderly, but in fact it can be predicted.

2. Unpredictability

Unpredictability means that even if an attacker knows the previously generated pseudorandom sequence, they still cannot predict the next pseudorandom number to be generated. Unpredictability is achieved by using other cryptographic techniques, such as the one-way property and confidentiality of one-way hash functions, to ensure the unpredictability of pseudorandom numbers.

3. Irreproducibility

Using the natural phenomenon of thermal noise, Intel developed hardware devices capable of generating irreproducible random sequences. CPUs include a built-in Digital Random Number Generator (DRNG), and provide the RDSEED instruction for generating irreproducible random numbers, as well as the RDRAND instruction for generating unpredictable random numbers.

3. Pseudorandom Number Generators

A pseudorandom number generator generates a pseudorandom sequence from two things: an externally supplied seed and internal state.

Because the internal state determines the next pseudorandom number to be generated, the internal state must not be known to attackers. The externally supplied seed is used to initialize the internal state of the pseudorandom number generator. Therefore, the seed must also not be known to attackers. In addition, the seed must not use values that are easy to predict; for example, the current time must not be used as the seed.

The comparison between a cryptographic key and a random-number seed is as follows:

There are several algorithms for generating pseudorandom numbers:

• Ad hoc methods
• Linear congruential method
• One-way hash function method
• Cipher-based method
• ANSI X9.17

1. Linear Congruential Method

The linear congruential method multiplies the current pseudorandom value by A, adds C, then uses the remainder after division by M as the next pseudorandom number. As follows.

R0 = (A * seed + C) mod M
R1 = (A * R0 + C) mod M
R2 = (A * R1 + C) mod M
R3 = (A * R2 + C) mod M
R4 = (A * R3 + C) mod M

Rn = (A * R(n-1) + C) mod M

A linear congruential generator is periodic, and future states can be predicted from its period. Therefore, it lacks unpredictability and cannot be used for cryptographic purposes.

Many pseudorandom number generator library functions are implemented using the linear congruential method. For example, the C library function rand and Java’s java.util.Random class both use the linear congruential method. Therefore, these functions cannot be used for cryptographic purposes.

2. One-Way Hash Function Method

A one-way hash function can also generate unpredictable pseudorandom numbers, and they are strong pseudorandom numbers (because its one-way property provides unpredictability).

1. Initialize the internal state, namely the counter value, with the pseudorandom number seed
2. Use a one-way hash function to compute the hash value of the counter
3. Output the hash value as the pseudorandom number
4. Increment the counter value by 1
5. Repeat steps 2 through 4 according to the number of pseudorandom numbers required

The one-way property of the one-way hash function is the foundation that supports the unpredictability of the pseudorandom number generator.

3. Cipher-Based Method

Strong pseudorandom numbers can also be generated using a cipher-based method. This can use either AES symmetric encryption or RSA public-key encryption.

1. Initialize the internal state (counter)
2. Encrypt the counter value with a key
3. Output the ciphertext as the pseudorandom number
4. Increment the counter value by 1
5. Repeat steps 2 through 4 according to the number of pseudorandom numbers required

The confidentiality of the cipher is the foundation that supports the unpredictability of the pseudorandom number generator.

4. ANSI X9.17

Strong pseudorandom numbers can also be generated using the ANSI X9.17 method.

1. Initialize the internal state
2. Encrypt the current time to generate a mask
3. XOR the internal state with the mask
4. Encrypt the result of step 3
5. Output the result of step 4 as the pseudorandom number
6. XOR the result of step 4 with the mask
7. Encrypt the result of step 6
8. Use the result of step 7 as the new internal state
9. Repeat steps 2 through 8 according to the number of pseudorandom numbers required

IV. Other Algorithms

There is a pseudorandom number generation algorithm called the Mersenne Twister, but it cannot be used for security-related purposes. Like the linear congruential algorithm, once its period is observed, the random sequence generated afterward can be predicted.

Java’s java.util.Random class also cannot be used for security-related purposes. For security-related use cases, you can use another class called java.security.SecureRandom.

Similarly, Ruby has two corresponding classes: the Random class and the SecureRandom class. For security purposes, only the SecureRandom class should be used.

V. Attacks on Pseudorandom Number Generators

• Attacks on the seed
  The seed of a pseudorandom number is just as important as the key of a cipher. To prevent the seed from being learned by an attacker, a true random number with non-reproducibility must be used as the seed.

• Attacks on the random number pool
  In general, true random numbers are not generated only at the moment they are needed. Instead, random bit sequences are accumulated in advance in a random number pool file. When needed, a random bit sequence of the required length can be taken directly from the pool and used. (The random number pool itself does not store any meaningful information, yet we still need to protect these meaningless bit sequences. Although this is somewhat paradoxical, it is necessary.)

Reference：

“Illustrated Cryptography”

GitHub Repo：Halfrost-Field

Follow: halfrost · GitHub

Source: https://halfrost.com/random_number/