Flaw in the Windows 2000 Random Number Generator

Posted November 21, 2007 in Programming, Security, Windows

The article is called “”http://eprint.iacr.org/2007/419.pdf">Cryptanalysis of the Random Number Generator of the Windows Operating System". I haven’t read the whole thing yet, but from a short glance it looks very interesting.

In my 2002 article about “”http://erngui.com/articles/rng/“>Secure Random Numbers” I
mentioned that it wasn’t clear how CryptGenRandom really works internally, since different sources disagreed on it, but ended-up recommending it for people on Windows wanting an “easy way out”…

Well, I don’t recommend it anymore. The authors of the above article have reverse-engineered it and found it to be extremely weak.

A very simple RNG would just use a secret key and a symmetric crypto algorithm like AES to encrypt a timestamp every time the user needs some random data. The weakness is that it totally relies on the secrecy of the key. So you’re better off replacing the key frequently. Plus you really don’t need to know what the key is to start with, so why no use some “random” value for the key itself? This brings us to the general design of a secure RNG:

  1. Entropy sources, i.e. somewhere in the computer that produces data that is hard-to-guess (as much as possible)

  2. An entropy pool or distiller that takes the “random” input from different sources and mashes them together cryptographically to make sure that we at least have a small amount of very hard-to-guess data.

  3. An entropy stretcher, i.e. a crypto algorithm that uses the hard-to-guess value from the previous step as secret key and produces as much secure random data as the user needs.

From a brief skim of the article, the entropy stretcher is bad (it uses RC4 which meant it was always suspicious) and the key for the “stretcher” is only changed (with data from steps 1 and 2) every 128K of output.

Further reading:

[Via CodeProject Insider and Computerworld’s Gregg Keizer.]