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."

31784

[FooAtWFU]

129775, 80123133, 5580012. 6740091, 6558, 42!

Re:

[Spokehedz]

All I get on mine is '8675309'

Damn you Johnny Two-Tone!

Ummm.... Re:31784

[sharper56]

...it's Tommy Tutone.

Re:

[jejones]

RANDU! Save us, RANDU!

Oh, wait, that was Landru.

NSA access?

[Futurepower(R)]

Loophole in Windows RNG.

Is that the NSA secret surveillance access [heise.de]?

--
U.S. Government corruption TimeLines [cooperativeresearch.org]
Example: Complete 911 Timeline, 3895 events

Re:

[l1gunman]

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."

Re:

[xenocide2]

The first entry on wikiquote for Neumann:

On mistaking pseudorandom number generators for being truly "random" -- this quote is often erroneously interpreted to mean that von Neumann was against the use of pseudorandom numbers, when in reality he was cautioning about misunderstanding their true nature while advocating their use. From "Various techniques used in connection with random digits" by John von Neumann in Monte Carlo Method (1951) edited by A.S. Householder, G.E. Forsythe, and H.H. Germond [wikiquote.org]

Sounds pretty reasonable, or a very long lasting urban legend...

Comment removed

[account_deleted]

Comment removed based on user account deletion

Re:Hardware RNG

[$RANDOMLUSER]

Now why would you assume Microsoft would use the hardware RNG when they have thier own, much better, proprietary RNG available?

Re:Hardware RNG

[defnoz]

Now why would you assume Microsoft would use the hardware RNG when they have thier own, much better, proprietary RNG available?

After all, they spent so much time perfecting it in Excel 2007!

Re:Hardware RNG

[thePsychologist]

It might only be a problem for 2000 users:

According to the researchers, who have already notified the Microsoft security response team about their discovery, although they only checked "Windows 2000" (which is currently the third most popular operating system in use) they assume that newer versions of "Windows", XP and Vista, use similar random number generators and may also be vulnerable.

Re:Hardware RNG

[thePsychologist]

This is classic behaviour on Slashdot. I point out this might not be a big of a problem as it seems (as they only tested Windows 2000, and not XP or Vista, both combined are far more used than 2000), and I'm modded as troll, only because (I presume) that I'm providing evidence that a problem with Microsoft isn't as serious as it seems (i.e. I'm getting in the way of MS bashing).

Re:Hardware RNG

[somersault]

Yeah because every time Windows is updated, it's a really high priority to write a new random number generator? XP is based off of 2000 even if Vista was meant to be a rewrite.

"Hey guys, I dont think the random number generator is random enough today - it came up with 2 prime numbers in a row! Anyone feel like taking a few days to rewrite it, test it, introduce a few bugs, document it, seal off the documentation to make sure nobody finds it, and go take it up to Steve? I hear he's out of chairs right now so it should be okay".

Re:Hardware RNG

[Tim Browse]

Unfortunately, some people might believe that's really how it happens. Cryptographically secure RNGs are a widely known issue in the field (hell, even I know about it, and I'm not in the field), and you can be sure that the Crypto programmers at MS are at least aware of the issue. It wouldn't surprise me, at any rate, if implementing a new RNG had been considered a priority for XP or Vista if they had discovered the existing one to be vulnerable.

If they had time in between cocking up all the WGA stuff, that is.

Re:

[Bert64]

A new RNG is not really a selling point, the only way it will help their bottom line is if enough people know about flaws in the old one that it's profitable to replace it.
Look at it from a business perspective, microsoft will.

Re:Hardware RNG

[thebdj]

A new RNG is not really a selling point, the only way it will help their bottom line is if enough people know about flaws in the old one that it's profitable to replace it.

Actually it can be, since it would be necessary to use a FIPS compliant PRNG to perform certain operations, they would need to have one. I suspect (see my other posts) that this is from a deprecated cryptographic service provider that MS no longer providers (DSS_BASE). If you check out the information on the CMVP website for the RNG Validation Lists [nist.gov], you will see they implement FIPS 186-2 PRNGs, which the paper itself admits (Appendix B) has some forward security and is not the PRNG they are attacking here.

Re:Hardware RNG

[yukk]

What makes you think that MS has "Crypto programmers" ? I'm sure that part of development went something like this.
Okay, module 14537r Random Number Generator. Teams, who wants do do this ? No, it's not boring. Come on. Okay, draw straws. Jones, you win. Yes, sure you can get the intern to write it. You carry on with the Clippy enhancements.

Why should MS crypto programmers be aware?

[EmbeddedJanitor]

I don't share your optimism. I have dealt closely with MS on three very different areas of computing (certain low-level kernel stuff and some client server stuff). In all cases I was shocked at how poorly the people understood their subject matter.

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.

Re:Hardware RNG

[Goaway]

What is this, "proof by sarcasm"?

Re:

[MrAnnoyanceToYou]

This is the Internet. Proof by sarcasm is the most defensible kind.

Re:Hardware RNG

[somersault]

I prefer to call it Sarca'm's Razor

the number of affected users enbiggens the problem

[doti]

only tested Windows 2000, and not XP or Vista, both combined are far more used than 2000

Still, 2000 has more (desktop) users than Linux. By your logic, if there were a similar problem in Linux, it would be less of a problem?

Re:Hardware RNG

[Belial6]

You actually didn't provide any evidence that the problem doesn't affect XP or Vista, you just suggested that the two newer version should be trusted immediately after finding out that 2000 has a bug in an unlikely to be updated part of the system. The non-troll way of highlighting this information would be:

That is a problem. I am eagerly awaiting the tests of XP and Vista to see if this was fixed for them.

You could probably even slip a little bias in there without being called a troll with:

They are going to test with XP and Vista aren't they? After all, it should be trivial to test this on the newer systems if the cryptography hasn't been changed. I mean what kind of security researcher just assumes the functionality of a security system?

Of course, it would be a little silly to assume that this does not affect at least XP, as 2000 was still under maintenance when XP was released, so if the bug was found during the development of XP, it should have been fixed in 2000. It would look far worse for Microsoft if they KNEW about a security hole in 2000 while it was still under maintanace, and did not bother to back port the fix from XP.

Why bother!

[Arivia]

Why bother checking the other versions: after all, anything that matters is on Windows 2000 already!

Re:

[operagost]

I recently discovered that Windows is not Y2K compliant! Although I only checked Windows 3.1, I assume that newer versions of Windows, 2000, XP, and Vista, use similar 2-digit dates and may also be vulnerable.

Re:

[Bert64]

Funny you should mention that, windows has a really kludgy way of handling dates beyond 2000... It basically still uses a 2 digit date, and defines an arbitrary split point, eg:
Dates below 70 are considered in the year 2000, over 70 are considered in the 1900s.

Excel also has some stupid bugs to do with dates, which microsoft are now trying to enshrine in the ooxml format.

Re:

[Anonymous Coward]

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

Re:

[Schraegstrichpunkt]

No. Read the paper, which states, inter alia (yes, I just learned that phrase this week):

We analyze the way in which the operating system uses the WRNG and note that a different copy of the WRNG is run, in user-mode, for every process, and that typical invocations of the WRNG are seldom refreshed with additional entropy. Therefore, the backward and forward security attacks, which only work while there is no entropy based rekeying, are highly effective. Furthermore, we also found that part of the state of the generator is initialized with values that are rather predictable.

Re:Hardware RNG

[lgw]

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.

Re:Hardware RNG

[EsbenMoseHansen]

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.

Brilliant idea! Let's call one of them /dev/urandom and the other one /dev/random. ;)

Re:

[mashade]

Brilliant idea! Let's call one of them /dev/urandom and the other one /dev/random.

/dev/urandom is the PRNG while /dev/random is the true RNG. In other worse, exactly the same as on Windows, save for device names.

http://en.wikipedia.org/wiki/Urandom [wikipedia.org]

Re:

[Burz]

Don't know about Windows' implementation, but the PRNG's I'm familiar with do not use up all of the cached entropy in one gulp. The entropy is used as seed values for the psuedo-random algorithm, giving you more "random" bits then you started with.

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 isn't how TC behaves on Linux at all, and I would doubt that description anyway. Generating new keys as files are written? I don't think so.

Re:

[Keith_Beef]

Like a strong Brownian motion producer (say, a cup of hot tea)?

Beef.

Re:

[larry bagina]

intel's fpu is a random number generator (unintentionally).

Re:

[operagost]

What is this, 1997? They had an FPU bug in the Pentium 60-90 MHz processors. I guess you still make jokes about exploding Pintos and wheelbarrows full of Weimar Deutchmarks, too.

Seed time

[EaglemanBSA]

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.

Re:Seed time

[EaglemanBSA]

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."

Re:

[Tacvek]

What Linux RNG are they talking about? My understanding is that the output of /dev/random is fully random under the condition that the kernel has not overestimated the entropy of any of the inputs, and the mixing function works properly.

Re:

[Schraegstrichpunkt]

If somebody reads your RNG state today via /dev/kmem, you don't want them to know what its output was an hour ago, or what it will be in an hour.

Huh?

[mrseigen]

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.

Re:Huh?

[Hatta]

No, but they might use it for encrypting windows passwords.

Re:Huh?

[mrseigen]

Whoops -- it's not rand, it's CryptGenRandom.

Re:Huh?

[Mantaar]

From TFA:

Date: received 4 Nov 2007

Old indeed. 8 days. That's a lot, Microsoft might have already fixed it, you see, they fix things fast!

Re:

[InvisblePinkUnicorn]

Considering that Windows 2000 is still used by at about as many people as use Vista, I don't think it matters whether they've fixed it in XP or not. They've still got to answer to all the 2000 users.

Re:

[plague3106]

No they don't; they EOLed Windows 2000 a while ago, IIRC.

Re:

[morgan_greywolf]

Y4h!! rand() i5 st00p1d!!! my pwn3d SSL add5 up a77 t3h numb3rz in t3h d4t3st4mp!!!

Where's the white noise generator?

[tjstork]

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.

Re:

[account_deleted]

Comment removed based on user account deletion

Re:Where's the white noise generator?

[palladiate]

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.

Re:Where's the white noise generator?

[OrangeCowHide]

A white noise generator? Bah... What systems need are pop-o-matic bubbles with m * 2^n sided dice to generate m * n bits. It could even put a window up saying, "The entropy pool is depleted. Please press the pop-o-matic bubble to generate more."

That would be awesome

Re:Where's the white noise generator?

[ConceptJunkie]

Perhaps you could pour hot tea into it instead.

Re:

[pesc]

Like the VIA C3 [via.com.tw] processor?

Re:Where's the white noise generator?

[palladiate]

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.

Re:

[CarpetShark]

Put white noise hardware and real random number hardware on PCs, and this whole problem goes away.

How do these work? Electromagnetics? Background radiation? Quantum unknowns? Even without being a physicist, I can imagine flaws in systems based on most of these.

Re:

[cheese_wallet]

They use thermal noise.

http://en.wikipedia.org/wiki/Thermal_noise [wikipedia.org]

Re:

[mkendall]

How do these work? Electromagnetics? Background radiation? Quantum unknowns?

Shot noise in diodes under reverse breakdown is a typical way to generate noise.

Re:

[Detritus]

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.

Re:

[Ephemeriis]

I know that there are plenty of machines out there that come with hardware RNG at reasonable prices... But is that even necessary?

I've seen software that tracks mouse movements for a while when generating random numbers, couldn't something similar be done through the OS itself? Couldn't you use mouse movement, keyboard input, sound and video output, etc. as your RNG? Wouldn't that be almost as good as a truly random number generator?

Or is there some obvious flaw in such a scheme which keeps it from being

Re:

[Darkforge]

Mouse movements and keystroke latency are OK for consumer grade encryption keys (though, note that they are normally just a seed for a pseudo-randomizer) you can't really use them on headless servers, which is where most of the important (i.e. high financial value) encryption takes place.

USB Hardware RND

[CustomDesigned]

Buy one of those $25 toy digital cameras. Keep the lens cap on, or put black tape over the lens. Connect to USB port. Add script to snap a "picture" every few minutes to prng. (Is there a way for userland to feed entropy to kernel based /dev/random?) With no light, digital cameras return thermal noise - which looks like "snow" on an analog TV. I've done this with a toy camera I bought for my daughter. The camera feeds raw pixels to the linux driver, and the post processing done by the Windows software was never implemented in Linux, making it useless as a camera (plus it has 256M ram, but no flash memory). But it works great for this application. I haven't done a mathematical analysis of exactly how much entropy is in the signal. I'll leave that for the stat geeks.

I got the idea from a project that used a webcam snapping pictures of a Lava Lamp® as a hardware RNG.

Re:

[Niggle]

Back when I was doing astronomy, a completely "black" picture didn't show purely random noise. You also get a faint fixed pattern. IIRC, that was mostly determined by tiny variations in the size of the detector pixels.

That was a decade ago though. Modern chips might be a lot more uniform. Also, a digital camera on your desktop is unlikely to be liquid nitrogen cooled, so the thermal noise will be higher anyway.

The Vista RNG

[Anonymous Coward]

Although they only checked Windows 2000, they assume that XP and Vista use similar random number generators and may also be vulnerable.

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.

Re:The Vista RNG

[eln]

Yes, but that 4 was generated via a fair dice roll, and is guaranteed to be random. You can't say that about the numbers the Vista RNG spits out. So you see, what the WNGB lacks in quantity it makes up for in quality.

Re:

[DreamerFi]

Sounds like the same one Dilbert [k12.va.us] is using.

ob XKCD reference

[wren337]

http://xkcd.com/221/ [xkcd.com] // chosen by fair dice roll // guaranteed to be random

Re:The Vista RNG

[secPM_MS]

The random number generator for XP and 2K3 server was substantially improved over that of Win 2000. Additional work was done for Vista. These systems are used in highly secure military deployments and due to its importance to system security, the random number generator was subjected to extensive analysis and was updated to deal with issues uncovered. When evaluating "random number generators" you need to consider not only the "random number" generator, but entropy harvesting from the system and other issues relating to usage. I assume the bulk of the readers are not MS developers, but if you need a good random number on a Windows platform, call CryptGenRandom. Equivalent functionality is provided for managed code as well.

Win 2K is a very legacy product and its crypto functionality is very limited compared to 2K3 and Vista.

Re:

[John Hasler]

> The random number generator for XP and 2K3 server was substantially improved over that
> of Win 2000.

You know this, of course, because you have reviewed the source code.

Re:The Vista RNG

[secPM_MS]

I didn't, but I know the people who did the enhancements, and they are very competent and well known cryptographers.

Re:

[Tim C]

A newly registered guy, even if they're named secPM_MS, doesn't buy much.

Why does it matter how long he's had an account here? I've been here for years and have the UID to prove it (well, if you believe I registered this account rather than buying it), but what does that say about how much I know about any given topic?

Novell

[Anonymous Coward]

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.

What is the scope of potential attacks?

[argent]

The abstract made me think that this was akin to the sequence number prediction problems in older TCP implementations, but it doesn't seem that this provides much opportunity for a remote attack. What is teh actual scope of the problem, how could this be practically used in an exploit?

Spearmen

[Anonymous Coward]

So that's why my tanks and battleships always lose to spearmen.

Fixed in Vista?

[adonoman]

http://msdn.microsoft.com/msdnmag/issues/07/07/Security/default.aspx [microsoft.com] has the new API, including a RNG

that meets Federal Information Processing Standards (FIPS) for use with the Digital Signature Algorithm (DSA).

There's a lot I don't like about Vista, but for security researchers to "assume that XP and Vista use similar random number generators and may also be vulnerable" without a basic google search is a bit much!

Re:Fixed in Vista?

[Anonymous Coward]

Actually go further back;

http://www.microsoft.com/technet/archive/security/topics/issues/fipseval.mspx?mfr=true [microsoft.com]

You'll note that Windows 2000 passed FIPS-140-1.

Re:Fixed in Vista?

[CastrTroy]

Just because they have a new API for getting the random numbers, it doesn't mean that they are using different algorithms for generating those random numbers. Also, they much still have the old APIs in there, otherwise, a lot of programs would fail to work. Since most of the software out there was written pre-Vista, and written to run on Vista, XP, and 2000, it's conceivable that applications on these operating systems are using the vulnerable code.

Publication iffy

[cdrguru]

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.

Re:

[IkeTo]

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,

Does this mean...

[physicsphairy]

That it will be possible to predict what values Excel will give us in our spreadsheets?

Don't newer cpus have TRNG builtin?

[jmichaelg]

I thought that True Random Number Generators had been built into all newer CPUs. It appears, after a quick Google search, that's not the case. Via provides a TRNG on their C3, AMD provides one on their Geode processor, and Intel provides one on their "Firmware Hub." What's not clear to me is why, given the obvious need for a TRNG, Intel and AMD haven't incorporated one into the mainstream x-86 architecture.

Re:

[palladiate]

You're slightly mistaken.

Intel only provided RNG on the 810 series of chipsets, and that was the Pentium 3 generation. The VIA C3 is of the same generation of chipsets, nothing faster than a 1.4 ghz processor. AMD does provide a path, but it's an optional part of the chipset, and not universally supported.

There used to be more ubiquitous hardware RNG.

Here's the thinking in Redmont

[Frantactical Fruke]

Um, our programmers are all in conference negotiating the next shutdown dialog, but we have plenty of spare lawyers, so we'll fix this problem with a DMCA law suit in 5, 4, 3, 2...

Similar but different?

[QuietLagoon]

I wonder if this [coredump.cx] is a similar problem?

Re:

[QuietLagoon]

Linux was in the one [coredump.cx] published the prior year.

Is there a list of slots machines that run windows

[Joe The Dragon]

Is there a list of slots machines that run windows?

Solution

[PPH]

Use Excel. Its solutions appear to be far less predictable than the current RNG.

Hardware RNG

[SamMichaels]

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 [fourmilab.ch]? After all, in 1985 plutonium should be available in every corner drugstore [wikipedia.org].

Vista is safe!

[LingNoi]

<sarcasm>Don't worry! I spoke to a MS rep and they told me that Windows Vista was the most secure operating system available!</sarcasm>

Oblig Dilbert

[BlueParrot]

Troll: "nine,nine,nine,nine,nine,nine,nine,nine,nine,nine,nine..."
Dilbert: "Are you sure that is random?"
Troll: "That's the thing with random numbers, you can never be sure... nine,nine,nine,nine,nine..."

Might not extend past W2K

[thebdj]

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 [nist.gov] 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.

Not so severe

[SiliconEntity]

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.

Re:

[Tom]

Ok, in that case I misread. Then it's not much of a danger, few windos machines stay up for more than a day or so.

I can't believe this is an issue...

[gillbates]

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?

Tin foil hat: "Reflections on Trusting Trust"

[mlwmohawk]

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.

Re:

[secPM_MS]

Everything I have heard in the security community within Microsoft says that there are no backdoors. Since my observation is not evidence to the paranoid, consider the following:

The Common Criteria evaluators have essentially full access to the Windows source code and all supporting documentation. They look for issues that would enable backdoors or security vulnerabilities. Once and a while, they find something interesting. Microsoft then fixes it as a security bug.

Windows platforms are used by numerous

Re:

[mlwmohawk]

Everything I have heard in the security community within Microsoft says that there are no backdoors.

I have never heard anything other than, "It could be, if you knew...."

The Common Criteria evaluators have essentially full access to the Windows source code and all supporting documentation. They look for issues that would enable backdoors or security vulnerabilities. Once and a while, they find something interesting. Microsoft then fixes it as a security bug.

Funny how people who are not "Common Criteria eva

O(2^23)=O(1)

[omnirealm]

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.

Re:

[kurt555gs]

WTF? does this mean that in Vista you just pray for a random number?

Re:

[roguetrick]

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.

Re:

[Cheesey]

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.

Unfortunately extra non-determinism would be introduced by bones files, and you'd get a new random sequence if you logged out. The server ad

Re:

[Tetsujin]

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."

And what happens when we make assumptions? we make an ass of me, and you make more money [google.com]

Uh, no... When you make an assumption, you make an ass of you and Mption...