Java Random can be cracked, the random numbers are no longer random and even more unsafe

Java Random random number generation is unsafe. If the first and second random numbers are leaked at the same time, the subsequent random number sequences can be cracked.

The Java Random class uses the Linear Congruential Generator algorithm to generate pseudo-random numbers. The so-called pseudo-random number means that if we use the same seed to generate a random number sequence, the result will be the same.

For example, the following code generates the same random number every time:

Random random = new Random(0)
int cnt = 10
for (int i = 0
   System.out.println(random.nextLong())
}

This means that when we set the seed to 0, the sequence of random numbers we get will be the same every time we run the code. The random numbers generated by the following code are always consistent no matter at any time or on any device. This also means that once a hacker obtains your “seed”, they can predict all the random numbers you generate.

To generate different random number sequences, we need to use different seeds.

Fortunately, the Random class provided by Java does not use the seed value 0 as the initial value of the random number by default. Instead, it takes a more sophisticated approach, using a dynamic random value as the default seed. It combines the current nanosecond time of the system with the initial seed value by performing an XOR operation on seedUniquifier() and System.nanoTime() . By using a nanosecond value to calculate the seed, you can ensure that Random objects built at different times will get different seed values. This ensures that the generated random numbers have higher independence and randomness.

How to generate the initial seed value?

private static final AtomicLong seedUniquifier
    = new AtomicLong(8682522807148012L);
private static long seedUniquifier() {
    
    
    for (;;) {
        long current = seedUniquifier.get();
        long next = current * 181783497276652981L;
        if (seedUniquifier.compareAndSet(current, next))
            return next;
    }
}

This code uses AtomicLong to calculate the seed, which is obviously to ensure that different seed values are generated when multiple Random objects are created in a multi-threaded scenario. In the seedUniquifier method, the AtomicLong.compareAndSet method is used to ensure that a different initial seed value is generated each time the method is executed. Through this method, we can ensure that in multi-threaded applications, when a seed conflict occurs, we can retry through CAS operations (Compare and Swap) to ensure that the Random object created by each thread The initial seed values are different.

In the code, by XORing different initial seed values with the nanoseconds of the current system time, you can ensure that each Random execution will get a different seed. So, does this guarantee that the seed will not be guessed by hackers?

No matter what random seed is used and how carefully calculated and protected it is, there is always a risk that it can be speculated.

The attacker will calculate the seed based on the observed output values. In the case of java.util.Random this is much shorter than 2^48 time. Skeptics can try an experiment where it is shown that the Random output can be predicted in about 2^16 times just by observing two output values. On modern computers, the time to predict the random number output at a given moment is even less than a second.

\# Java Random Security Analysis[1]

The author of this article demonstrates an algorithm for predicting a third random number based on two random numbers! It is strongly recommended that you try this code. If your random numbers are used in high-security scenarios, such as redemption codes, Token generation, etc., be sure to replace them in time! ****

private static final long multiplier = 0x5DEECE66DL
private static final long addend = 0xBL
private static final long mask = (1L << 48) - 1

@Test
public void test6() {
   int a = -117510532
   int b = -1347210525
   int c = 2076362838
   long oldseed = ((long) a << 16)
   for (int i = 0
      long nextseed = (oldseed * multiplier + addend) & amp; mask
      if ((int) (nextseed >>> 16) == b) {
         oldseed = nextseed
         break
      }
      oldseed + = 1
   }
   int next_int = (int) (((oldseed * multiplier + addend) & amp; mask) >>> 16)
   System.out.println(next_int == c)
}

For the nextLong and nextDouble methods, you only need to know any random number to predict the subsequent random number; while for the nextInt and nextFloat, if the first and second random numbers are leaked at the same time, then the subsequent random numbers will also be predictable.

The random number generated by Random is only 48 bits, which means that under random circumstances, with a limited number of attempts and using today’s advanced CPUs, it is possible to crack it in a limited time. For some services, if they are not restarted for a long time, it means that the seed value (seed) is not updated for a long time, so predicting the seed value will become easier.

However, one might question, what’s wrong with predicting seed values and guessing random values? In most cases, such as randomly routing requests to a machine or randomly selecting a userId, there is not much danger even if the seed value is guessed. However, in some scenarios, such as using random numbers to generate passwords, redemption codes, promotion codes, various Tokens, etc., if the application of these random numbers is breached, it may cause immeasurable losses. For example, if the random number in the redemption code pool is successfully guessed, the generated redemption code is no longer safe and reliable, such as redeeming a JD shopping card.

So is there any way to safely use random numbers?

Java provides the SecureRandom random number generation class, which can safely generate random numbers. What are the advantages of SecureRandom compared to Random?

  1. Random generates up to 48 bits of random values, but SecureRandom can generate up to 128 bits of random values.

For the case using Random, it would take about 2^48 attempts to crack it, but thanks to today’s advanced CPUs, it may actually be crackable pretty quickly. For SecureRandom, it takes about 2^128 attempts to crack, which will take many years even with today’s advanced computers. Therefore, SecureRandom provides higher security.

  1. SecureRandom does not use a fixed seed value. Instead, new seed values are continuously obtained from the operating system/dev/random random number file.

The operating system collects all kinds of random data, such as the intervals between key presses. These random data will be stored in files. For Linux and Solaris systems, common file paths are /dev/random and /dev/urandom. Use this random data as a seed to generate random numbers or perform other cryptographic or randomization operations

SecureRandom will obtain the random seed value from the /dev/random file, and each time nextBytes() is called, a different random seed value will be obtained. This way, the attacker cannot infer any information even if he observes the output. Because the random seed keeps changing, unless he can control the contents of the /dev/random file (which is very unlikely)

SHA1PRNG

SHA1PRNG is a pseudo-random number generator algorithm. In Java SecureRandom, it is used as the default random number generation algorithm under Windows. The algorithm is based on the SHA-1 algorithm, but improves randomness by adding extra steps.

The SHA1PRNG algorithm uses a seed to initialize the random number generator. The SHA1PRNG algorithm uses the SHA-1 algorithm to calculate a hash value, which is used to generate random numbers.

The seed used in the SHA1PRNG algorithm is specified at system startup.

NativePRNGBlocking

In Java SecureRandom, the NativePRNG algorithm is the default random number generation algorithm under Linux.

NativePRNGBlocking initializes the internal SHA1PRNG instance using 20 bytes in /dev/random during initial seeding.

When calling nextBytes(), nextInt(), etc.: XOR using the output of the internal SHA1PRNG instance and the data read from /dev/random

NativePRNGBlocking Every time you calculate a random number, you need to get the value from the /dev/random file. When there are insufficient random numbers in /dev/random, NativePRNGBlocking will be blocked. In desktop applications, the /dev/random file is rarely blocked because it can collect user mouse, click, and other events. However, in web programs, due to the high degree of concurrency, there may be insufficient generation of /dev/random data.

For example, someone uses the NativePRNGBlocking algorithm and is always blocked when the online environment service is started. It is because /dev/random has less data that NativePRNGBlocking initialization is blocked.

NativePRNGNonBlocking

In order to avoid being blocked in obtaining random numbers, NativePRNGNonBlocking chooses to obtain random numbers from /dev/urandom.

There are some differences between /dev/urandom and /dev/random.

/dev/random generates random numbers by collecting environmental noise on the system (such as hardware noise, disk activity, etc.). It can only generate high-quality random numbers when there is enough ambient noise on the system.

And /dev/urandom is a pseudo-random number generator device file that uses an internal entropy pool to continuously generate random numbers regardless of the amount of environmental noise on the system. Therefore, /dev/urandom generates random numbers much faster than /dev/random.

To sum up, the random numbers generated by /dev/urandom are of slightly poor quality, but they can be output stably. The random numbers generated by /dev/random are of higher quality, but generating random data is slower when the system is less noisy, which may block some applications.

Therefore, it is recommended that you generally use NativePRNGNonBlocking to read /dev/urandom, which can exchange for stable random data output, although it sacrifices some random number quality.

Using the blocking algorithm may cause online problems. For details, please refer to Using NativePRNGBlocking. The production environment is blocked[2]

SecureRandom is used similarly to Random. When generating an object, just specify the corresponding policy.

SecureRandom secureRandom = SecureRandom.getInstance("SHA1PRNG")
SecureRandom secureRandom = SecureRandom.getInstance("NativePRNGBlocking")
SecureRandom secureRandom = SecureRandom.getInstance("NativePRNGNonBlocking")

secureRandom.nextLong()

SecureRandom is not thread-safe and can be synchronized using the synchronized keyword, or using ThreadLocal to save a SecureRandom instance for each thread.

In a single-threaded environment, loop 1 million times to generate random numbers. The Random algorithm shows the strongest performance and can complete 1 million cycles in only 10 milliseconds. In comparison, the other three SecureRandom algorithms are more than 10 times more time-consuming than Random.

  • In scenarios with high security requirements, it is unsafe to use random numbers generated by Random. If two of the random numbers are obtained, the subsequent random sequence can be cracked.

  • In order to improve security, SecureRandom needs to be used to generate random numbers in some scenarios, such as generating random passwords, redemption codes, and promotion codes.

  • The SecureRandom algorithm uses the system random files /dev/random and /dev/urandom to generate random numbers. Since the random number generated each time will be XORed with the system random file, the random seed is always changing, making the random number unable to be cracked by brute force.

  • In Web systems, it is more suitable to use the NativePRNGNonBlocking non-blocking random algorithm because it provides higher performance.

  • Compared with the other three algorithms, the Random algorithm has the strongest performance. The other three algorithms are more than 10 times more time-consuming than the Random algorithm.

When generating random numbers in business scenarios with higher security, it is recommended to use SecureRandom instead of ~Random~

SecureRandom secureRandom = SecureRandom.getInstance("NativePRNGNonBlocking")
secureRandom.nextLong()

Reference materials

[1]

https://zgjx6.github.io/2019/06/11/Java Random Security Analysis/: https://link.juejin.cn/?target=https://zgjx6.github.io/2019 /06/11/Java%20Random%E5%AE%89%E5%85%A8%E6%80%A7%E5%88%86%E6%9E%90/

[2]

https://cloud.tencent.com/developer/article/1549509: https://link.juejin.cn/?target=https://cloud.tencent.com/developer/article/1549509

The knowledge points of the article match the official knowledge files, and you can further learn related knowledge. OpenCV skill tree Home page Overview 23572 people are learning the system