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."
129775, 80123133, 5580012. 6740091, 6558, 42!
The World Wide Web is dying. Soon, we shall have only the Internet.
I assume this is only a problem for those whose motherboard doesn't have a hardware random-number generator?
How accurate would they have to be with predicting the generator seed times for the keys to work? Would that be a hitch? I'm not an expert in the field, so I honestly don't know.
Quiz: True or False -- On a scale of 1 to 10, what is your middle name?
Maybe it's just me, but I didn't think anyone would be stupid enough to use rand for SSL like the article is implying.
From what I can see, this is an old article anyway.
I am still at a loss to wonder why a PC does not have a white noise generator built into it yet. Even the best random number algorithms are pseudo random, so blasting Microsoft for their algorithm is a little like blasting the kid for not carrying enough of a bucket when the dam is the thing that broke.
Put white noise hardware and real random number hardware on PCs, and this whole problem goes away.
This is my sig.
Your system must meet the requirements to be able to run the Windows Random Number Generator on Vista. Otherwise, you will need to use Windows Number Generator Basic. The only number WNGB can generate is 4.
In other news, Miguel de Icaza said that he believes that the random number generator is a good idea. Linux should have one because Microsoft is going to win anyway, so linux would better be prepared if it doesn't want to be locked out of the future markets, and presented a beta version of the algorithm. Members of the GNOME foundation are participating in the standarization: ''it's better to provide our own insecure random number generator'' said ownen taylor.
So that's why my tanks and battleships always lose to spearmen.
The only benefit that could possibly be derived by publishing algorithms and/or code for Windows security would be if (a) changes proposed would be implemented quickly and (b) everyone planet-wide upgraded.
If both of these did not happen, especially if (b) didn't happen, what you would be doing is exposing all non-upgrading users to the full brunt of whatever flaws their might be. Would this really be productive? Does this remind you of various failures in Linux code that led to rootkits being developed for it. Did the victims of such attacks think it was all for the best because they didn't upgrade in a timely manner?
Yes, relying on people not reverse-engineering code to protect users isn't a great plan. But the current situation - as regrettable as it is - is this is the only plan. There are no fallbacks, there are no alternatives. Most of the running copies of Windows aren't going to be "fixed" in any way whatsoever.
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
http://xkcd.com/221/
That it will be possible to predict what values Excel will give us in our spreadsheets?
When things get complex, multiply by the complex conjugate.
I wonder if this is a similar problem?
Is there a list of slots machines that run windows?
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?
factor 966971: 966971
...it's Tommy Tutone.
You'd think that computers would have built-in hardware based RNGs by now. On-board sound, video, network, etc.......where is the radioactive decay RNG? After all, in 1985 plutonium should be available in every corner drugstore.
I got the idea from a project that used a webcam snapping pictures of a Lava Lamp® as a hardware RNG.
I am willing to bet two things:
1) This does not affect current versions of Windows.
2) This only affects exported versions of Windows. (The PRNG may still be there but may not be default.)
The RC4 implementation screams of a bit-size issue. It also goes to reason since they are in a non-US country. Furthermore, I doubt this affects current versions based on the information available. If you want, go throw the CMVP RNG validation list and find the Microsoft certificates. All of the RNGs that are approved do not use RC4.
I believe there is a lot of hot-air and presumption and in the paper. They published findings and ASSUMED that nothing has been changed with relation to the PRNG. The algorithm certificates shown above clearly shows this is not the case. Furthermore, they do not state which cryptographic provider is used to perform the generation. I believe this PRNG might be from DSS_BASE, which has since been deprecated. This would mean the problem does not exist. They also ask for Microsoft's code, yet I see none of their own. Without their code, how can their paper be reasonably verified.
I say show me some more, before you cry that this is the way all PRNGs since W2K have been implemented.
"Some days you just can't get rid of a bomb."
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
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.
I'm sorry, all this RNG stuff just remines me of NSA key, and all the backdoor crap that Windows has suffered. I am reminded by the paper "Reflections on Trusting Trust."
I honestly have 100% no doubts that "Microsoft" is purposely installing multitudes of access methodologies in the form of bugs with "plausible deniability" for U.S. security officials. The telco's do it, they've been caught and are now asking for immunity. Now whether or not is is actually "Microsoft," or people working within the company secretly for the various security agencies purposely inserting these nearly impossible to find bugs is a different question.
Call me paranoid, but if I told you there was a secret room through which all internet traffic gets directed in all the major internet NOCs, you'd call that paranoid as well.
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
It's official. Most of you are morons.
Now I don't know what the crypto folk are like, but I have yet to see any real evidence to suggest that they'd be any better.
Engineering is the art of compromise.
I don't think those two numbers are that far from each other.