Slashdot Mirror
Loophole in Windows Random Number Generator
Invisible Pink Unicorn writes "A security loophole in the pseudo-random number generator used by Windows was recently detailed in a paper presented by researchers at the University of Haifa. The team found a way to decipher how the number generator works, and thus compute previous and future encryption keys used by the computer, and eavesdrop on private communication. Their conclusion is that Microsoft needs to improve the way it encodes information. They recommend that Microsoft publish the code of their random number generators as well as of other elements of the Windows security system to enable computer security experts outside Microsoft to evaluate their effectiveness. Although they only checked Windows 2000, they assume that XP and Vista use similar random number generators and may also be vulnerable. The full text of the paper is available in PDF format."
No, but they might use it for encrypting windows passwords.
Give me Classic Slashdot or give me death!
Whoops -- it's not rand, it's CryptGenRandom.
Now if only we had a plan for getting a girlfriend. And I don't mean Flargina the Elf, because from what I hear, shes packing something and its not a bow.
-The world would be a better place if everyone had a hoverboard
Looks like if you can use their method to find the current state fast enough, windows doesn't do a great job of reseeding very quickly: I read through the PDF and found this comparison of the LRNG to WRNG (p. 18) - "Reseeding timeout. The LRNG is feeding the state with system based entropy in every iteration and whenever system events happen, while the WRNG is reseeding its state only after generating 128 KBytes of output. Synchronization. The collection of entropy in the LRNG is asynchronous: whenever there is an entropy event the data is accumulated in the state of the generator. In the WRNG the entropy is collected only for a short period of time before the state is reseeded. In the long period between reseedings there is no entropy collection. Security implication: The impact of the previous four properties is that forward and backward security attacks are more severe when applied to the WRNG. The attacks are more e±cient by twelve orders of magnitude. They reveal the outputs of the generator between consecutive reseedings, and these reseedings are much more rare in the case of the WRNG. In some cases, reseeding the LRNG happens every few seconds, while the WRNG is reseeded every few days, if it is reseeded at all."
Quiz: True or False -- On a scale of 1 to 10, what is your middle name?
No, Intel no longer provides a hardware RNG on most chipsets. The last is the i810.
Some AMD64 chipsets still do though. You generally don't find hardware RNG on any chipset below the "Major Enterprise Purchase" mark.
Which could be bettered, easily.
http://www.microsoft.com/technet/archive/security/topics/issues/fipseval.mspx?mfr=true
You'll note that Windows 2000 passed FIPS-140-1.
Like the VIA C3 processor?
)9TSS
That sort of attack could probably be used against online Nethack servers such as nethack.alt.org. You could predict what set of items you'd get if you generated a character at a specific value of time(NULL). You'd also be able to predict the future for that character. You'd try out sequences of moves on your PC, and then send the sequence that got you the best results.
/dev/urandom. (They might already be doing that.)
Unfortunately extra non-determinism would be introduced by bones files, and you'd get a new random sequence if you logged out. The server admin could also stop this attack quite easily by sourcing random data (or just the seed) from
>north
You're an immobile computer, remember?
The Commodore had one too, on the sound chip. The old P3 i810 and VIA C3 chipsets had RNGs built in. They relied on thermal noise. Some AMD chipsets still have it. But for the most part, no modern motherboard comes integrated with a hardware RNG.
Win 2K is a very legacy product and its crypto functionality is very limited compared to 2K3 and Vista.
...it's Tommy Tutone.
They use thermal noise.
http://en.wikipedia.org/wiki/Thermal_noise
This sounds *really* wrong. You can say white-hats should have waited for a few days or even a few weeks after notifying the vendors before disclosing problems, but they should be disclosed eventually, and should be disclosed after giving vendors a reasonable amount of time. There bound to be people not upgrading their Windows, and there bound to be people not upgrading their Redhat or Fedora or Ubuntu or SuSE or FreeBSD or whatever operating system you name (not to mention whatever Firewalls, protocols, applications, etc, etc you name). So we shouldn't be disclosing any vulnerability about any of those?! Who, then, know that their software is vulnerable to black-hats and needs upgrading, and who, then, know which software vendor is more trust-worthy for providing secure software or providing rapid response to security issues? And, more importantly, how developers can learn from the others' mistakes and start writing secure code?
Shot noise in diodes under reverse breakdown is a typical way to generate noise.
Well your wish has been granted. The Windows Vista cryptography API (CNG) provides just this kind of functionality.
From the MSDN page on CNG features:
It seems that the CNG is very extensible. You can add new RNGs, encryption providers, hashing algorithms, etc.
Windows RNG collects "entropy" (that is, non-pseudo-randomness) from many sources, including drive timing, network timing, keyboard and mouse timing, temperature information, etc. However, there are only so many "really random" bits per second available.
Any good RNG combines sources of entropy with a cryptographically secure PRNG. The researchers are attacking the PRNG portion of the Windows RNG. If you only generate keys (or other random numbers) infrequently, this is a non-issue, as the hardware sources of entropy provide enough "really random" bits to generate a "really random" number.
However, if you generate a fast series of keys (or other random numbers), you quickly use up all of the "really random" bits that the RNG has cached, and you only have the PRNG on your side, and therefor the key is merely "pseudo random". TFA is an attack on the "psuedo random" portion of the Windows RNG.
Interestingly, the much-reviewed TrueCrypt engine seems to slow to a crawl if you create a bunch of files (and therefore keys) in a hurry - presumably it has an RNG that actually blocks waiting until it has enough new "really random" bits for each new key. This is a cool idea for a crypto library, but not usable for a general-purpose RNG, which suggests that the system libraries should probably provide *two* RNGs.
Socialism: a lie told by totalitarians and believed by fools.
http://en.wikipedia.org/wiki/Urandom
Technology tips and tricks.
I've seen resistors (thermal noise) and zener diodes (junction breakdown noise) used as noise sources. The trick is to keep external non-random signals out of the circuit.
Mea navis aericumbens anguillis abundat
IMO the attack is not so severe as they make it sound. While this is a nice piece of reverse engineering and cryptanalysis, in practice the security implications are small.
The bottom line is that every process has its own copy of the RNG state. That means that breaking into one process will not help you deduce the random numbers being used by another. (The authors comment that there may be similarities between the two states, but they don't have any way to turn that into a practical attack.) So the only thing this does is it lets an attacker who compromises a certain process or program, such as IE, be able to learn the random number state. From that he can deduce old random numbers that were used, as well as deduce new random numbers that will be created in the future.
That second part is hard to avoid, but the first part, running the state backward (confusingly called forward security by cryptographers), is a sign of bad design of the RNG. Okay, Microsoft messed that up. But what are the security implications?
The implication is that if someone breaks into your computer, here is something more he can do. Not only can he take over going forward, he can learn a certain amount of data about the past. If you had an SSL protected session in the past, then he could go back and figure out what they keys were back then and decrypt the data.
But how bad is this, really? Compared to the harm he can already do by breaking into your computer? Given that he's there, he can learn all of your future SSL keys anyway. Anywhere you go in the future, your bank, paypal, ebay, any site he can learn all of your passwords and account numbers. He doesn't need to compromise the RNG for this, he can just watch your keystrokes. Basically, you are totally screwed if this happens.
Given the enormous magnitude of the security lost, the additional harm from being able to decrypt a few old requests is quite small. You are basically owned from then on. If you have insecure software that is vulnerable to such attacks, you're screwed anyway. A weakness in the RNG state means you are slightly more screwed, that's all. It's not a major change in the security equation.
The bottom line is that most of the damage comes from the break-in. Again, not to take anything away from these guys' work, but the attack they describe is at worst just the icing on a very nasty cake. Microsoft should fix it, and it sounds like they probably have in Vista, but nobody needs to change their security practices because of this flaw.
Is that the NSA secret surveillance access?
--
U.S. Government corruption TimeLines
Example: Complete 911 Timeline, 3895 events
I'm surprised nobody posted this one yet:
As John von Neumann joked, "Anyone who considers arithmetical methods of producing random digits is, of course, in a state of sin."
One of the fundamental tenets of good cryptography is that if you can't see the algorithm, then it is not secure. That means all of the algorithm, including the RNG, if you use one. If you can't cryptanalyze it, you can't make any judgements about security. The fact that the Windows RNG is closed source and proprietary automatically excludes it from use in cryptographic functionality, and I'm quite surprised to discover that it is actually being used this way. (Actually, I'm not surprised; I'm surprised that some people consider it secure.)
And after the various faults with RNGs in the past on UNIX and Mainframes, I'm surprised that anyone is so naive as to believe that Windows had a good one. Microsoft's past history is so poor that only the most naive of programmers would assume that their RNG could be used for security purposes. It might be fine for simulations and gaming purposes, but that's it.
Considering that any cryptographer worth a Google search would know that almost all PRNG's have been broken, I'm wondering why anyone is making an issue of this; I thought all cryptographers just assumed that the host OS RNG is insecure by default. Or could it be that we have a lot more naive Windows developers than previously thought?
The society for a thought-free internet welcomes you.
(P)RNGs are *crucial* to any cryptographic operation that draws it's entropy from it. Since it is such a basic functionality and so important to security, it is critical to do this right. The DNS cache poisoning attack http://www.securiteam.com/securitynews/5VP0L0UM0A.html is all about bad implementation of PRNG.
The big problem that I see is, that it seems that Microsoft did not give the correct implementation of PRNG the importance it should have.
Windows NT uses several formats: SYSTEMTIME (field separated structure), FILETIME (64-bit NTFS time timestamps), 64-bit posix-like timestamps, etc., all of which are fine *far* beyond the 2048 32-bit Posix boundary. Just because the value you found doesn't have leading zeros doesn't mean it is processed as smaller than 64-bits.
Maybe you should read some formal documentation before posting.
sigh
The paper makes reference to a O(2^23) time to compute the previous state, given any current state. Maybe I am being a bit pedantic, but any undergraduate CS major familiar with big-O notation could tell you that O(2^23)=O(1); authors should just drop O() when they want to communicate the static (input-independent) run time of an algorithm.
An unjust law is no law at all. - St. Augustine
I Browse at +4 Flamebait
Open Source Sysadmin