ScaDS Logo

COMPETENCE CENTER
FOR SCALABLE DATA SERVICES
AND SOLUTIONS

Random numbers are hard - even harder in virtual machines

Random numbers are an essential element of cryptography and therefore security in general. Like most security aspects, random numbers sound simple but proof to be hard to get right. This text will discuss problems regarding random numbers in computers, especially in virtual machines.

Unpredictability

The most important property of random numbers in cryptographic applications is unpredictability. It should not be possible to predict the next random number from (possibly all) previously used random numbers. If a 16 byte long encryption key is generated in a way that the last eight bytes can be predicted from the first eight bytes the number of possible keys decreases dramatically. If it took 500 billion years to try all possible 16 byte keys, it would take less than a second to try all keys created in that flawed manner.

Sources for randomness

Computers are inherently deterministic devices. The same operation on the same input should always produce the same output. But this crucial characteristic runs contrary to the required unpredictability of random numbers. This conundrum is usually solved by using interactions with the environment as sources for randomness. The most common sources are user interactions like mouse movements and key presses and hardware interactions like the delay during hard disk accesses.

PRNG

The quantity of random numbers generated from interactions with the environment usually doesn't suffice. Therefore pseudo random number generators (PRNGs) are applied. They are deterministic algorithms that take a small amount of random numbers as a seed and generate a large amount of random looking numbers. The unpredictability of the seed is of utmost importance. Therefore, it has to be infeasible to compute the seed from the output.

Common practice and VMs

Since a computer system has usually few interactions during the boot time it is difficult to seed a PRNG early on. Hence, it's common practice to store a small amount of random numbers at shutdown, use them to seed the PRNG at boot time and reseed the PRNG later on when more sources for randomness are available. In virtualized environments this method causes the reuse of the same seed. Virtual machines may be started multiple times from exactly the same disk image. Therefore the same stored random numbers are used to seed the PRNG and the same output is created by the PRNG for a certain amount of time.

Lack of sources for randomness in VMs

The problem is exacerbated by the lack of the most common sources for randomness. Because most virtual machines are servers they have no direct user interaction and the additional abstraction layer provided by the virtualization reduces the direct interaction with hardware components. This shortage of sources for randomness increases the time until a PRNG can be reseeded and in turn the time its output is the same as after previous starts from the same disk image.

Snapshots

Similar problems arise in the context of snapshots. Snapshots capture the whole state of a running virtual machine including the state of the PRNG. A snapshot can be saved and later restored thereby restoring a state of the PRNG whose output was already used before. Since the problems caused by booting from a disk image multiple times and using snapshots are caused by reinstating a former state of the virtual machine they belong to the so called reset vulnerabilities.

TRNG

Reset vulnerabilities are difficult to neutralize because they require the invalidation of the internal state of critical software at an arbitrary point of execution. However, it's possible to attenuate their effects on random numbers by providing additional sources for randomness and enable fast reseeding of the PRNG. Additional randomness can be provided by true random number generators (TRNGs) which provide random numbers based on random physical processes like thermal noise or quantum phenomena.

Summary

This text exemplified why unpredictability the most important property of random numbers. It outlined the common ways to ensure a sufficient supply of random numbers in computer systems and described their problems in virtual machines.