Cryptanalysis of the windows random number generator

ABSTRACT

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 on-trivial attack: given the internal state of the generator, the previous state can be computed in O(2²³) work (this is an attack on the forward-security of the generator, an O(1) attack on backward security is trivial). The attack on the 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. As a result, 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.

REFERENCES

• 1: AIS 20: Functionality classes and evaluation methodology for deterministic random number generators. Application Notes and Interpretations of the Scheme (AIS) Version 1, Bundesamt für Sicherheit in der Informationstechnik, Dec. 1999.
• 2: Boaz Barak , Shai Halevi, A model and architecture for pseudo-random generation with applications to /dev/random, Proceedings of the 12th ACM conference on Computer and communications security, November 07-11, 2005, Alexandria, VA, USA [doi>10.1145/1102120.1102148]
• 3: D. Beaver and S. Haber. Cryptographic protocols provably secure against dynamic adversaries. In EUROCRYPT '92, pages 307--323, 1992.
• 4: M. Bellare and B. S. Yee. Forward-security in private-key cryptography. In M. Joye, editor, CT-RSA '03, volume 2612 of Lecture Notes in Computer Science, pages 1--18. Springer, 2003.
• 5: Theo de Raadt , Niklas Hallqvist , Artur Grabowski , Angelos D. Keromytis , Niels Provos, Cryptography in OpenBSD: an overview, Proceedings of the annual conference on USENIX Annual Technical Conference, p.33-33, June 06-11, 1999, Monterey, California
• 6: Scott R. Fluhrer , Itsik Mantin , Adi Shamir, Weaknesses in the Key Scheduling Algorithm of RC4, Revised Papers from the 8th Annual International Workshop on Selected Areas in Cryptography, p.1-24, August 16-17, 2001
• 7: I. Goldberg and D. Wagner. Randomness in the netscape browser. Dr. Dobb's Journal, January 1996.
• 8: Peter Gutmann, Software generation of practically strong random numbers, Proceedings of the 7th conference on USENIX Security Symposium, p.19-19, January 26-29, 1998, San Antonio, Texas
• 9: Z. Gutterman and D. Malkhi. Hold your sessions: An attack on java session-id generation. In CT-RSA '05, volume 3376 of LNCS, pages 44--57. Springer, 2005.
• 10: Zvi Gutterman , Benny Pinkas , Tzachy Reinman, Analysis of the Linux Random Number Generator, Proceedings of the 2006 IEEE Symposium on Security and Privacy, p.371-385, May 21-24, 2006 [doi>10.1109/SP.2006.5]
• 11: Michael Howard , David E. Leblanc, Writing Secure Code, Microsoft Press, Redmond, WA, 2002
• 12: J. Kelsey. Entropy and entropy sources in x9.82. http://csrc.nist.gov/CryptoToolkit/RNG/Workshop/EntropySources.pdf, July 2004.
• 13: John Kelsey , Bruce Schneier , David Wagner , Chris Hall, Cryptanalytic Attacks on Pseudorandom Number Generators, Proceedings of the 5th International Workshop on Fast Software Encryption, p.168-188, March 23-25, 1998
• 14: Mark R. V. Murray, An implementation of the Yarrow PRNG for FreeBSD, Proceedings of the BSD Conference 2002 on BSD Conference, p.6-6, February 11-14, 2002, San Francisco, California
• 15: D. A. Osvik. personal communication, 2007.
• 16: T. Ts'o. random.c - linux kernel random number generator. http://www.kernel.org.

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection

General Terms:
Security

Keywords:
cryptanalysis, pseudo random number generator (prng), windows operating system