‘Cryptanalysis of the Random Number Generator of the Windows Operating System’

Summary

‘The pseudo-random number generator (PRNG) used by the Windows operating system is the most commonly used PRNG. The pseudo-randomness of the output of this generator is crucial for the security of almost any application running in Windows. Nevertheless, its exact algorithm was never published.

We examined the binary code of a distribution of Windows 2000, which is still the second most popular operating system after Windows XP. (This investigation was done without any help from Microsoft.) We reconstructed, for the first time, the algorithm used by the pseudo-random number generator (namely, the function CryptGenRandom). We analyzed the security of the algorithm and found a non-trivial attack: given the internal state of the generator, the previous state can be computed in $O(2^{23})$ work (this is an attack on the forward-security of the generator, an $O(1)$ attack on backward security is trivial). The attack on forward-security demonstrates that the design of the generator is flawed, since it is well known how to prevent such attacks.

We also analyzed the way in which the generator is run by the operating system, and found that it amplifies the effect of the attacks: The generator is run in user mode rather than in kernel mode, and therefore it is easy to access its state even without administrator privileges. The initial values of part of the state of the generator are not set explicitly, but rather are defined by whatever values are present on the stack when the generator is called.Furthermore, each process runs a different copy of the generator, and the state of the generator is refreshed with system generated entropy only after generating 128 KBytes of output for the process running it. The result of combining this observation with our attack is that learning a single state may reveal 128 Kbytes of the past and future output of the generator.

The implication of these findings is that a buffer overflow attack or a similar attack can be used to learn a single state of the generator, which can then be used to predict all random values, such as SSL keys, used by a process in all its past and future operation. This attack is more severe and more efficient than known attacks, in which an attacker can only learn SSL keys if it is controlling the attacked machine at the time the keys are used.’

Credit:

‘The information has been provided by Leo Dorrendorf and Zvi Gutterman and Benny Pinkas.
The original article can be found at: http://eprint.iacr.org/2007/419


Details

Conclusions
WRNG design. The paper presents a clear description of the WRNG, the most frequently used PRNG. The WRNG has a complex layered architecture which includes entropy rekeying every 128 KBytes of output, and uses RC4 and SHA-1 as building blocks. Windows runs the WRNG in user space, and keeps a different instance of the generator for every process.

Attacks. The WRNG depends on the use of RC4, which does not provide any forward security. We used this fact to show how an adversary which learns the state of the WRNG can compute past and future outputs of the generator. The attacker can learn future outputs in O(1) time and compute past outputs in O(223) time. These attacks can be run within seconds or minutes on a modern PC and enable such an attacker to learn the values of cryptographic keys generated by the generator. The attacks on both forward and backward security reveal all outputs until the time the generator is rekeyed with system entropy. Given the way in which the operating system operates the generator, this means that a single attack reveals 128 KBytes of generator output for every process.

Code analysis. Our research is based on studying the WRNG by examining its binary code. We were not provided with any help from Microsoft and were only using the binary versions of Windows. To verify our findings we developed a user mode simulator which captures WRNG states and computes future and past outputs of the WRNG. We validated the simulator output against real runs of the WRNG. WRNG versus LRNG. We compared between the pseudo-random generators used by Windows and Linux (WRNG vs. LRNG). The forward security attack on the WRNG is faster by a factor of O(240) compared to the attack on the LRNG. In addition, our findings show that the LRNG has better usage of operating system entropy, uses asynchronous entropy feedings, uses the extraction process as an entropy source, and shares its output between multiple processes. As a result, a forward security attack on the WRNG reveals longer sequences of generator output, compared to an attack on the LRNG.

Recommendations
Forward security. The most obvious recommendation is to change the algorithm used by the WRNG to one which provides forward security. This can be done by making local changes to the current implementation of the generator, or by replacing RC4 with a function which provides forward security. Alternatively, it is possible to use the transformation of [4] which transforms any standard generator to one providing forward security. We believe however that it is preferable to replace the entire algorithm used by the generator with a simpler algorithm which is rigorously analyzed. A good approach is to adopt the Barak-Halevi construction. That construction, suggested in [2], is a simple yet powerful construction of entropy based PRNGs. Its design is much simpler to implement than the current WRNG implementation and, assuming that its building blocks are secure, it provably preserves both forward and backward security. It can be implemented using, say, AES and a simple entropy extractor.

Frequency of entropy based rekeys. The generator should rekey its state more often. We also suggest that rekeys are forced based on the amount of time that has passed since the last rekey. It is important to note that entropy based rekeys are required in order to limit the effect of attacks mounted by an adversary which obtains the state of the generator. (In a good generator, forward security and pseudo-randomness are guaranteed by the function which advances the state, and are ensured even if the generator generates megabytes or gigabytes of output between rekeys.) The risk of an adversary getting hold of the state seems to be more dependent on the amount of time the system runs, than on the length of the output of the generator. It therefore makes sense to force rekeys every some time interval, rather than deciding whether to rekey based on the amount of output produced by the generator.’

Categories: Reviews