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 and hardware interactions like the delay during hard disk accesses. Examples for user interactions include mouse movements and key presses.
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. With this, they 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 Virtual Machines
A computer system has usually few interactions during the boot time. Because of that, 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. The same output is created by the PRNG for a certain amount of time.
Lack of sources for randomness in Virtual Machines
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.
Random Numbers in Virtual Machines
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. Furthermore, it described their problems in virtual machines.
Check out more news about ScaDS.AI Dresden/Leipzig at our Blog.