Dual_EC_DRBG Added to Windows Vista

Microsoft has added the random-number generator Dual_EC-DRBG to Windows Vista, as part of SP1. Yes, this is the same RNG that could have an NSA backdoor.

It’s not enabled by default, and my advice is to never enable it. Ever.

EDITED TO ADD (12/18): I should make this clear that the algorithm is available as a program call. It is not something that the user can enable or disable.

Tags: , , , , , ,

Posted on December 17, 2007 at 10:22 AM • 82 Comments

Comments

Eric • December 17, 2007 10:59 AM

You know what would be scary? If they secretly started using this algorithm even if you requested something else. Could anyone tell? What if they only pulled the switch under specific conditions (i.e. Chinese language versions)?

Nick • December 17, 2007 11:21 AM

Or Microsoft could just enable Dual_EC-DRBG to be used sometime in the future after most people forget it’s there.

derf • December 17, 2007 11:48 AM

Either a stealth Windows Update will turn it on, or a future critical security fix will quietly make it the default.

HAL • December 17, 2007 12:11 PM

I got to this point, “When developing Windows Vista, Microsoft set out to provide higher levels of productivity, mobility, and security, with lower costs.” Then my BS Detector went off.

Microsoft lowering costs! Yeah right.

stacy • December 17, 2007 12:21 PM

“[…] and my advice is to never enable it. Ever.”

Are you referring to the RNG or to Vista? 🙂

electron • December 17, 2007 12:23 PM

But Microsoft is lowering costs – the costs of the recording studios.
Microsoft is increasing security – making it possible for the RIAA to check what you’ve got without the owner of the computer knowing.
Microsoft is increasing productivity – that of the lawyers prosecuting the DRM cases for the RIAA.

Everybody else? click ‘n’ wait.

mark • December 17, 2007 12:47 PM

the costs of the recording studios.
Uh no. Actually most recording is HD based and Vista is a performance dog. In the past you’d base your studio around a Windows platform to save money. But with Vista, you need more HW for the same performance and thus the costs go up.

Leave the recording studios out of the record label / DRM madness. We’re victims just like you.

grandma • December 17, 2007 1:08 PM

Anyone who runs Windows is a fscking schmuck and deserves what they get for their poor choice in operating systems.

Jesse Viviano • December 17, 2007 1:09 PM

You should know that the documentation linked to states that the default RNG in Vista SP1 will not be Dual_EC_DRBG, but the RNG based on AES, which is CTR_DRBG, which Schneier recommended in his post warning against Dual_EC_DRBG.

Dual_EC_DRBG is only called when the programmer explicitly calls for it. Therefore, the way to make sure that Dual_EC_DRBG is not used is to perform a source code audit. The auditor must search the source code of the program in question for the constant named BCRYPT_RNG_DUAL_EC_ALGORITHM and the string “DUALECRNG” to make sure that they are either completely absent from the program or used to throw exceptions when their use is detected in runtime, and must make sure that the programmers did not program Dual_EC_DRBG in themselves.

Anonymous • December 17, 2007 1:13 PM

” […] Therefore, the way to make sure that Dual_EC_DRBG is not used is to perform a source code audit”

With Windows you cannot audit the source code.
Use Linux/xBSD instead of Windows.

HAL • December 17, 2007 1:29 PM

“Gartner survey found that 64% of companies planned to begin moving from Windows XP to Windows Vista by the winter of 2008.” via Information Week.

Good news story for security industry insiders.
“Malware authors will step up efforts to attack Windows Vista in 2008, as Microsoft’s latest desktop operating system passes the 10 percent market share milestone, according to security firm McAfee.”

If attacks are going up, why in the world would 64% of biz users being heading in that direction? Nucking futs.

Chris • December 17, 2007 1:46 PM

Um, not to be a spoilsport, but isn’t this in the NIST standard? Why doesn’t the blame belong there, instead of Microsoft implementing it?

Eric • December 17, 2007 1:52 PM

Imagining a Windows system that’s been rigged to always use the backdoored RNG leaves us with lots of interesting posibilities:
1. Inject compromised machines into the supply line for your adversary. I mentioned “Chinese language versions” earlier, but you could probably be more focused than that.
2. If you ever crack your adversary’s machine, modifying the crypto DLL is an extremely subtle attack they’re unlikely to detect.
3. If you can get your adversary to be paranoid about Windows Update, chances are they’ll leave open some other hole for you to exploit.
4. You could probably detect a program signature in order to compromise only certain software. For example, VPN software that’s used by a certain government.

RonK • December 17, 2007 2:26 PM

@ Jesse Viviano

The auditor must search the source code of the program in question for the constant named BCRYPT_RNG_DUAL_EC_ALGORITHM and the string “DUALECRNG”

I get the feeling that you don’t do source code security audits for a living. If I am not mistaken, the BCRYPT_… constant has a numerical value and your method of auditing would certainly miss the use of the value rather than the constant’s name. Not to mention that the value (or the string) could be generated by as complex a calculation as you’d like, rather than just sitting there exposed textually in the source code.

Or am I missing something????

Jesse Viviano • December 17, 2007 2:28 PM

@Anonymous

The source code audit is for the program calling the random number generator library. If the program calls the normal RNG, Dual_EC_DRBG is not going to get called. Instead, CTR_DRBG with AES or the older FIPS 186-2 RNG will get called, depending on which version of Windows is used. Windows Vista SP1 and later will call CTR_DRBG with AES, while older Windows versions will call the FIPS 186-2 RNG which is based on either DES or SHA-1, which have been both broken.

Jesse Viviano • December 17, 2007 2:49 PM

@RonK

You are right. I am just a graduate student that reads this blog and am trying to clear up the confusion caused by people who read this post and fail to check the sources Schneier posted. You would also need to find out what that constant is. That can be done in one line of code in C++ in a test program:
cout << “Constant to avoid: ” << BCRYPT_RNG_DUAL_EC_ALGORITHM << ‘\n’;

By the way, Schneier should have made it clear that it is the programmer’s choice to use this algorithm, not the user’s choice. I would have written the last line of the blog post like this: Fortunately, Dual_EC_DRBG must be explicitly called by the programmer writing a program. Never call it to generate secure random numbers in your programs.

Jeff Craig • December 17, 2007 4:03 PM

@Chris, NIST has already been run over the coals for this algorithm, but to be fair to NIST, the potential vulnerability in it was only discovered well after the NIST report was published. No one can say definitively if NIST or the NSA were aware of this potential backdoor before it was published.

Just because it was in the NIST report doesn’t mean that Microsoft had to implement it. My question is, did they implement it with the seeds published in the NIST document, or did they use their own?

Rob • December 17, 2007 4:23 PM

@Jesse:

The source code validation won’t work, even within MS.

One of the security books from MS gives an example. The tool looked for NULL security descriptors in IIS source code. The programmers dutifully removed those from the source, and replaced them with malloc(-1).

Actually making sure it’s never called with a particular constant is another expression of the halting problem.

Cjhristoph Zurnieden • December 17, 2007 4:47 PM

Based on Microsoft’s long history of “good idea—bad implementation” and the recently found flaws in w2k’s crypto-PRNG I cannot recommend any of the offered crypto-PRNGs in Windows, not even the AES based CTR_DRBG. They all might be implemented badly and the necessary tests would be costly and time-consuming.
Or they followed the aforementioned tradition by heart and implemented the backdoors badly too?

The crypto-API in Windows is not usable for anything serious, as is any other closed source cryptographic algorithm.
I have also trouble finding something that is non-serious but at teh same time in need of weak encryption—movie spoilers perhaps?

CZ

Tina Russell • December 17, 2007 5:06 PM

Bruce, you’ve done tremendous work to help preserve our personal freedom and security so pleeeeease encourage good grammar as well! It should be “never to enable” it, so as to avoid splitting infinitives. (I know some people crow that the split infinitive as an error is so-o-o passé, but I’d still advise avoiding it.)

Sorry, I’m a grammar nut, we’re like this 😀

Me • December 17, 2007 7:44 PM

Tina,

I believe splitting the infinitive is more effective here. “My advice is never to enable it” would say that his advice is never that it should be enabled. This is nuancedly different from saying that he advises someone that this should never be enabled.

Your correction adds ambiguity.

security • December 17, 2007 8:05 PM

To switch off this feature:
You will need a blank cd, cd burner, iso burning software and a some free space on your harddrive.
Goto http://www.ubuntu.com download feisty fawn.
Burn iso to CD
Insert CD
Reboot
Double click icon that installs software

This is all that is needed to ensure a safe OS

Jonathan Allen • December 17, 2007 9:17 PM

Oxford, the Chicago Manual of Style, and the Columbia Guide to Standard English Usage all state that it is acceptable to use split infinitives.

No one really knows why the anti-split infinitive movement started in the 19th century, though Columbia states, “one possibly after-the-fact reason for the objections was that since Latin and Greek infinitives were not (indeed, as single words, could not) be split, neither should English infinitives, even though they often came in two parts, to plus infinitive, and so were vulnerable to being split by adverbs.”

So complaining about split infinitives is not only “passé”, it demonstrates poor grammar.

rob • December 17, 2007 9:49 PM

I think Jesse is right; the second link (to the API documentation) implies that if I’m writing code for Vista I’m allowed to ask for that RNG when creating a struct of type CRYPT_INTERFACE_REG. Its not ‘disabled’ in any way, there just (probably) aren’t any programs that are currently using it.

The real danger of something like this is if it somehow ends up in .NET framework or IE down the road; people programming against the COM interface for IE (or using the browser control in .NET, even old versions) or people writing SSL using the built-ins in .NET could be compromised without knowing it. I think it will be some time before this could happen (keep an eye out to see if its included in XP SP3 next year) but something to keep in the back of one’s mind when writing applications – if you want real security, you simply must write it yourself.

Tom • December 18, 2007 12:19 AM

@Jesse Viviano:

If someone is actively trying to avoid detection there’s always ways around simple source code searches like that. Here’s a trivial example:

#define NEW_SECRET_CONST XXX-1

where XXX is BCRYPT_RNG_DUAL_EC_ALGORITHM+1

Probably better to look for the functions that actually use these constants (though even those could be obfuscated easily)

Arne D H • December 18, 2007 1:06 AM

Would it be possible to create a peer reviewed, opensource tool to alter vista/xp in security conscious ways, for everyone concerned with security? Such a tool could replace the offending code with a dialog box stating that you are about to do unsafe stuff.

Pedant • December 18, 2007 2:48 AM

@marc

Given the tiff earlier over splitting infinitives, perhaps I should point out that you probably mean fewer people, as unless they’ve been puréed first, people are not a continuous quantity.

On topic, given Peter Gutmann’s recent presentation (http://www.cs.auckland.ac.nz/~pgut001/pubs/malware_biz.pdf) , perhaps we should conclude that the Windows OS is irretrievably compromised and that any important information should be processed on hardware dedicated to the job, that has been formally proven to be secure. That probably discounts anything with a general purpose OS – including Linux and BSD.

Pedant

Joachim • December 18, 2007 3:06 AM

Aloha!

Am I the only one that find it interesting that Microsoft is the employer of Niels Ferguson and Dan Shumow, the two researchers that raised the issue of a possible backdoor in the PRNG?

Are Niels and Dan totally out of the loop @ Microsoft? Why on earth were they hired by MS if their competence and receommendations are not used?

Remember that not long ago weaknesses was found in the PRNG in Win2K and WinXP by Leo Dorrendorf, Zvi Gutterman and Benny Pinkas (http://eprint.iacr.org/2007/419.pdf). These weaknesses MS claimed was fixed in Vista and XP by “various changes and enhancements to the random number generator.”

Why on earth does not MS use Yarros/Fortuna when they have Niels on the payroll? And why introduce a new, optional PRNG the same staff members warns about?

Yes, NIST have some explaining to do, but MS behaviour is IMHO really weird.

BTW: Have anybody seen any official response by NIST on the Dual_EC_DRBG issue? Are they following the duck and cover-routine?

SteveJ • December 18, 2007 5:06 AM

I don’t really understand the criticism of MS here. Well, I kind of do, but I don’t think it’s justified.

Have any of the people saying that MS are in the wrong on this, or malicious, or whatever, actually ever implemented a published standard as a software library before? I have. It doesn’t matter whether you think some part of the specification is stupid, or harmful, or that no programmer should ever use it. You still include it, because otherwise you aren’t implementing the standard.

If MS are going to implement a NIST standard, they should do that, not just implement the bits we or they prefer. If anything, it’s good news that, just for once, they aren’t “tweaking” the spec to their own corporate preferences.

It would be even better news if MS documented it with a note that it may be cracked, but ultimately it’s the programmer’s decision whether to use a particular “feature” or not. If your program needs to generate the same sequence of numbers as some other thing which is using Dual_EC-DRBG, then you need an implementation of the algorithm. MS don’t know whether the pseudo-randomness of the sequence is security-critical or not, so why is it their job to try to stop you?

You’ll note that linux distributions still include the “md5sum” utility, despite the fact that MD5 probably should not longer be considered a secure hash function. That doesn’t mean GNU or the distributions are creating security flaws in linux, it just means they think you might some day need to compute an MD5 sum.

Bruce’s advice is spot on – he said not to use the algorithm. He didn’t say freak out and panic that MS are up to something.

I’m sure he’d advise not to use DSA or MD5 or ROT13 either, but I bet there are implementations of those algorithms in several OSs.

SteveJ • December 18, 2007 5:18 AM

Sorry, when I said “DSA” above, I meant to say “the original DSA in FIPS 186”. I didn’t mean to imply that the general algorithm of DSA is ineffective, just the 512-bit keys permitted in FIPS 186 and later deprecated.

greg • December 18, 2007 6:09 AM

@Joachim
MS has a very large R&D department. They produce some fantastic work. But they are pretty much independent of the OS development.

Question to all. Why would someone use windows when security is a high priority? No I don’t mean linux vrs windows flames wars, I mean live update and the general setup where M$ does not trust the user or owner. There are a lot of systems out there all with there benefits and cost. Only use windows where you only need “adequate” security. Example I only use windows to play games.

But lets face it, if NSA is part of our threat model there are far more serious flaws in windows than the RND generator.

Frymaster • December 18, 2007 6:41 AM

a few comments:

Yes, someone could get around a source code audit quite easily if the wanted to use flawed RNG algorithms; they could do that anyway using ANY flawed RNG (or reimplementing the algorithm themselves). Wanting to get round it implies knowing the implications of their action and deliberately choosing to do The Wrong Thing in the face of moral, professional, and managerial objections.

It would be nice if IDEs flagged the use of these things automatically (a bit like “deprecated” classes and methods) but if you’re savvy enough to be choosing your own RNG you can probably google search the name of it and figure this out for yourself

Brian Boyko • December 18, 2007 7:27 AM

Not to put too fine a point on this – but if random number generation is a massively important task for computers to handle, why can’t we hook up a little d20 to a PCMCIA slot and be done with it?

rob • December 18, 2007 8:13 AM

I agree, Microsoft really isn’t to blame for this, NIST is. If there is a question about the algorithm they shouldn’t endorse it.

Any real threat here boils down to a lack of instutitional memory – obviously MS has a lot of smart people on the payroll, and the comment that they were just implementing the spec is valid. The problem is inadequate communication and documentation. Two years from now when someone decides to put a new RNG to put in IE 47.x, who is going to remember that there is a question about this algorithm? And if some sort of doomsday scenario were to happen and I wrote some code where I used a library function to communicate and my security was compromised, I could of course blame microsoft who could blame NIST, but none of that helps anyone.

I poked around my ubuntu system and the web last night looking for references to this RNG in common linux software and the ubuntu dist in particular but couldn’t find much. I did notice that there are some elliptical-curve RNG algorithms in use but could not easily determine if any of them were the one in question. I think the danger is just as present in any other OS as in Vista, though perhaps it will not be present in as short a time.

I also wonder if there’s a way to detect this algorithm in use, and really don’t have the expertise to give a straight answer on that, but my feeling is ‘probably no.’ If it gets implemented in a library function, or gets swapped for the default in TPM, I doubt that your run-of-the-mill developer will notice. I wouldn’t notice, and I write code using Microsoft’s encryption library from time to time.

I guess it may be time to write an open-source SSL implementation for Windows that doesn’t use any built-in functions.

tommy • December 18, 2007 8:37 AM

what kind of national secrets are you all so worried about protecting? i understand snooping is wrong, but what are they going to find out? you’re itunes playlist? your kids soccer schedule??

paranoid nerds!

Carlo Graziani • December 18, 2007 10:15 AM

I wonder what a FOIA request for documents related to the Standard-setting process undergirding Dual_EC-DRBG would show. If there is even one elision from a document, or one document request refused on grounds of National Security, that would pretty much settle the “surreptitious back door” question.

Bruce, do you do FOIA requests? Or, do you talk to people who do?

Garrett G. • December 18, 2007 10:26 AM

Microsoft has (finally!) taken security far more seriously than in the past. I believe this trend began in 2003, when Gates ordered every s/w engineer in the company to attend mandatory security training (how many s/w companies do that?). Vista adds significant security enhancements to the OS, including randomization of library addresses, reduced privs for many services, and many others. Also, why would Ms take the substantial risk of cooperating w/ the NSA, esp given what happen to telecoms that did so? That would be stupid from a business standpoint.

Some of the vents against MS actually contain valid points. But does that mean that MS is culpable in this particular regard (absolving NIST of any responsibility)? I think not.

MrDude • December 18, 2007 10:27 AM

@Carlo Graziani

I like it. A question where “I will not answer that question” answers the question…..

markus • December 18, 2007 10:37 AM

@tommy
OK. Again someone of the “nothing to hide” fraction. Probably your itunes playlist isn’t that interesting, but would you want your bank account to be read by somebody? As you may or may not know, a breakable RNG is not that bad in the random-playback of itunes, as it may make your next song predictable, but come on, do you really think people who implement backdoors in algorithms are interested in that kind of data?

THINK about it!

Greg • December 18, 2007 10:45 AM

@Garrett G.

Of course M$ is taking security seriously. They don’t want us cracking “trusted computing” do they…. They want us, the user, out of the loop.

Karrick • December 18, 2007 10:53 AM

“Anyone who runs Windows is a fscking schmuck and deserves what they get for their poor choice in operating systems.”
— Grandma

I’m still concerned because many people do not voluntarily use said operating system at home, but have no alternate at work. What about schools and libraries? Whether some computer users use the above operating system or not is pointless. Whatever is used by the masses becomes the standard, and interoperability will be the double-edged knife that will bring this back around to haunt those who attempt to stay ahead of the vulnerability curve by using non-main-stream-vendor supplied software.

The adoption of this by the main-stream operating system vendor means that within 5 years it likely will be in other operating systems in one form or another.

This will only result in the systematic weakening of encrypted communications by private parties.

“what kind of national secrets are you all so worried about protecting? i understand snooping is wrong, but what are they going to find out? you’re itunes playlist? your kids soccer schedule??”
— tommy

I will state first hand that most people in government service just want to serve their fellow citizen and make their country better. Indiscriminate use of technology to monitor the day-to-day lives of citizens does not promote individual liberties and human rights. There are many news reports of persons in various countries who are imprisoned and tortured for their beliefs. How long before your beliefs are in opposition to the ruling party of your government? If this question does not make you pause, then I sincerely question the depth of your perspective.

Garrett G. • December 18, 2007 11:31 AM

Oh, I should also add that we should logically think of security (or any specific subject) within a broader context. I.e., rather than thinking about security within the context of security (a narrow focus) or thinking about security within the context of information technology (a slightly less narrow focus), it’s helpful to think about security within the context of everything else (to borrow Thomas Barnett’s terminology).

In the case of Microsoft, they’ve put a large focus on securing their software. Why? The answer is primarily economic. They have a lot (of money) to lose if Microsoft continues to experience s/w holes (like buffer overflow vulnerabilities) on a massive scale. Hence, MS added support for NX/XD (DEP) in SP2 of XP and have added more infrastructure-hardening capabilities in Vista (yes, in addition to the obvious one: UAC). The motivation behind this was primarily business, so it’s helpful to see that perspective as part of the big picture.

I.e., security within the context of everything else (namely business, in this case). Which, by the way, Schneier seems to have a knack for, in my humblest of opinions.

simon • December 18, 2007 11:47 AM

@flamers

If I were Bruce, I’d close comments. Can’t even nerd stuff like PRGNs live without M$/Linux flames and STFU use?
Anyone may avoid it altogeher with the CryptoAPI stuff which is suspicious anyway if you are really concerned (or paranoid). Or permutate the data it outputs until oblivion. MS may not exactly be about choice, but who wants has every possibility.

maelcum • December 18, 2007 11:52 AM

Kool – paying for (nsa) backdoors – M$ just s**ks
I got nothing to hide so i use sidux or debian, its free and modular.
I hope Vista will be the last os out of Redmond, its just bloated slow ugly and too expensive for this code crap. If the government is reading my mails I want to read theirs too!

Garrett G. • December 18, 2007 11:55 AM

@Simon

I agree w/ your sentiment. But turning off comments isn’t the answer, in my view. After all, flamers get the attention, but those with real insight ultimately get respect. With an interactive blog, you get both the good & the bad; the result is, I’d argue, often a “net good”; flamers’ comments are easily skipped (with the apropos sigh) while those with substantial insight are rewarded with readership and interest in their ideas.

Simon • December 18, 2007 12:25 PM

@Garret

You’re very right, it’s not the answer. But it seems skipping those ‘comments’ is easier for you than for me (guess I’ll have to work on that).

d0c0 • December 18, 2007 1:15 PM

Someone wrote:
You know what would be scary? If they
secretly started using this algorithm….

You know what would be even scarier? If it turns out that ANY OF YOU thinks that a packetized communications system — oh, sorry, I mean THE packetized communications system — was designed and developed for ANY REASON other than making it easier for the DOUBLE SECRET POLICE to not only your mail and listen to your conversations, but to control your computers.

But there’s a FUNNY side, too… namely, the fact that you’ve been convinced to PAY FOR IT – the whole frigging thing – out of your own pockets.

Andy P. • December 18, 2007 4:32 PM

Maybe i’ve got something wrong, so please correct me: By writing RNG here is really meant a PRNG, not a true RNG?
I’m remember to be teached, there is no possibilitiy to build a true RNG in software on a deterministic maschine like a standard PC (without an extra RNG in Hardware).
I know, there are PRNGs which cannot hardly distinguished from a true RNG, looking at the output, but looking from the mathematical point of view, there are “only” PRNGs.

Jesse Viviano • December 18, 2007 5:48 PM

@Andy P.
There are ways to write true random number generators for computers. However, this requires a source of chaos, like interrupts generated by the network card, the time it takes your hard disk to send the first byte of a file after a request is made (this depends on the position of the disk being read and the file’s first sector, which the OS has no control of and therefore is a valid source of chaos), the keyboard, and the mouse. The latter two require a human to be using the computer, but without some hardware noise generator, these are the best sources of chaos the computer can use. Using this chaos, a true RNG can be made.

One could argue that a harware RNG would be better, but the only way to ensure that a hardware RNG does not contain some trap the hardware vendor could use to break anything using it is to see the source code, so hardware RNGs are not as trustable as a keyboard and mouse (unless the hardware vendor GPL’s the hardware source like Sun does on some of its CPUs).

Andy P. • December 18, 2007 7:14 PM

@Jesse Viviano
This is what I exactly learned to be a PRNG: an algorithm to spread the few bits of chaotic bits of input (as known as entropy) to create random values, using the avalance effect of i.e. a chiffre. All PRNG have something in common: If you try to get more random numbers from the PRNG that the entropy can substitue either the PRNG is blocked/empty or provide non random numbers. This doesn’t happen per se to a true RNG (i.e. build around a noisy transistor or something similar). I admit that the PRNGs used today are random enough from the practical point of view. But looking from the mathematic POV it is still a deterministic black box with something rare random input. As I learned sometimes long ago as a dogma: “there is no way to implement a RNG in a deterimistic machine”. But maybe this dogma is now proven wrong?
I also admit your concern about the hardware trap, so for practical reasons, an PRNG in OS seems to be the easiest way to produce random numbers today.
Maybe sometimes will simple hardware RNGs be a standard feature of any chipset or CPU: all you need are a few transistors for a CPU-readeable shift register, clocked by FSB and filled by 1bit digitised thermal noise from a PN-border of a semiconductor. Estimated costs: 10 cent. Profit: a true marketing feature. Gain: no hassle about the entropy of PRNGs, because a tricked input is by far more expensive to build than this.

Jesse Viviano • December 18, 2007 11:18 PM

@Andy P.

The difference between a true software RNG and a PRNG is that a PRNG might take some seed data in the beginning and never takes any input after that. RC4, Blum Blum Shub, and a block cipher run in either OFB a.k.a. output feedback mode or CTR mode a.k.a. counter mode. In short, a PRNG will always generate the same sequence of bits if it is given the same initial seed. A true software RNG will use some source of chaos to continuously reseed the algorithm and will block if there is no more chaos to use, resulting in unpredictable output every time.

According to Wikipedia, Linux was the first OS to implement such a true software random number generator in its implementation of /dev/random/, though the first version is considered either weak or broken. I do not know if this has been fixed. Thanks to Schneier’s warning and recommendation, it might be fixed to use CTR_DRBG with AES if it needs fixing. AFAIK, the first version was made more complicated than it should be to avoid formerly overly-strict encryption export laws which have been relaxed.

seb • December 19, 2007 3:42 AM

Is it possible to remove the corresponding file containing the new code or to manually corrupt the section in the file containing the code so that program calls to the weaker RNG would cause an error or a program crash –so at least calls would be noticed?

Ninho • December 19, 2007 6:00 AM

@Andy P : modern PC-chipsets have embedded the kind of RNG you describe, even before the “TPM”. The SiS based PC on which I’m typing has one. It works more or less like you imagined, clocked by the FSB (or optionnaly by the much slower USB clock), shifting 1 bit per clock into a 32-bit register in PCI space.

Only “small” problem, such components are chipset make and model specific, hence difficult to use (other than in the BIOS or motherboard specific drivers).

What is more, the specs are often closely kept by the manufacturers – delivered only on condition of no diclosure, and effectively difficult to reach at for the ordinary programmer/hacker.

And even though I got the programming spec for mine, there is no hint of the physical source of the “random” bits – all I can say is they did well against the standard “diehard” tests.

—
Ninho

Danny • December 19, 2007 6:58 AM

Conspiracy theory: NSA insists on including Dual_EC-DRBG knowing full well that nobody will use it, to drive people towards the that OTHER available PRNG, to which NSA also have a backdoor :).

Like the “pen” example they use in marketing classes: if you have two sorts of pens on the shelf, people will buy the cheaper one. To sell the pricy one, add an even more expensive one to the shelf. You’ll never sell one of those, but sales of the pen now priced “in the middle” will skyrocket.

So by adding a known poor PRNG “underneath”, are we to be driven towards the other PRNG, whose faults are known only to the spooks, maybe ?

Clive Robinson • December 19, 2007 7:29 AM

@Jesse, Rob,

“One of the security books from MS gives an example. The tool looked for NULL security descriptors in IIS source code. The programmers dutifully removed those from the source, and replaced them with malloc(-1).”

This use asside malloc() should never be used in security related software (and what usefull software is not security related these days).

It has been known for a long time that malloc() is a security problem.

Many moons ago SUN had a problem with one of its stock programs. It was reported that it was leaking the tail end of the password file to the user (and others).

What was happening was that the programer had used malloc() to create a buffer into which the password file was read. When that part of the prog had finished it released the memory.

The program then almost imediately called malloc() to create a new buffer and was handed a pointer back to the memory that had been previously used.

Under certain circumstances the buffer was either not or only partialy overwritten with new data, the buffer was then flushed out in it’s entirety thus leaking the tail end of the password file.

The solution was to replace malloc() with calloc(). For more details see the book “Deep C Secrets”.

However you should not use any of the malloc family in this way as they will still not clear the data from the buffer when you free it and there is no gaurenty that other parts of the program (or other programs) will not get handed the memory with the data in it.

The correct thing to do is to clear all alloced memory before you free it (also make sure that compiler does not optimize this step out).

As you can apriciate this is a real problem in Object Orientated programing and code that uses multithreading.

Clive Robinson • December 19, 2007 7:39 AM

@ALL

Under no circumstances write your own RNG be it PRNG or TRNG it might look simple but belive me it is not, most people (even some large electronics corps/comps) get it wrong in one way or another.

IF you don’t accept the above at least please read Ross J Anderson’s book (security Engineering) Bruce and Neils book and Vol 2 of Knuth’s Art of Computer Programing, and then please thing again

Oh and finaly if you still want to do it please do not come running back with tails of woe about how you product was compromised.

Hali • December 19, 2007 12:03 PM

At the moment I am not exactly at the point to see the backdoor clearly.
The call of simple rand() to generate a random number, for example as a password key for AES to be transfered to the client through a DH channel seems to be a bad idea, because the rand() algorithm must be initialisied, and if the initialised number is known, everything is broken.
So most programmes hopefully join more than one scource of random numbers (SHA/MD5), to hope that at least one source is okay (rand() + PIDs + type speed, mouse-position, hardware-generators iv avaliable). In this scenario I don’t see a deep problem of a backdoor as a “weak algorithm”. Even if the backdoor will send the random number to NSA by internet, they will only know one random number before the hash function.

Where exactly is the problem in this case, if nobody really knows if there is backdoor or not.
If there is no backdoor, the source of a new (probably good) random algorithm is born.
If there is a backdoor, this random number has the same worth like a rand() call.

simon • December 20, 2007 6:08 AM

@hali

the provlem is: you can derive the whole iv from looking at few (unabridged) output bytes, and thus predict the wohle sequence (very bad!).
The backdoor is not like in subseven, more like in DES. (If that helps you)

notanyspam • December 20, 2007 3:11 PM

Speaking of encryption and related algorithms, does anyone know of a well-reviewed library implementing symmetric ciphers and chaining modes? There seem to be many libraries (e.g., libtomcrypt, libgcrypt), but precious little information about who’s reviewed them and how.

Adri • December 20, 2007 3:33 PM

This will make me switch to linux/mac, but I got no money for macs, and no time to learn linux codes….

Anonymous • December 21, 2007 4:03 PM

@Adri:
“no time to learn linux codes”

If you can’t use Ubuntu, you’re probably in a coma or cave. Even the elderly are using Ubuntu Linux, get with the program!

rngdev • December 22, 2007 8:42 AM

unix, linux, mac, clones and the like’s, all have had severe issues with RNG’s/PRNG’s .. there are several available distro’s available just now which have issues with their RNG’s/PRNG’s. – There has been just as many bugs and security flaws in the unix clone world as in the world of windows, they are just fixed much faster and have much less impact on the world.

wack • March 30, 2008 1:18 AM

If MS is adding Dual_EC_DRBG just because its a Standard despite its vulnerablility, then MS cryptographic department is stupid.

Either that or they are claiming ignorance for sinister benefits.

And there are stories of USA spying on foreign technology companies and passing on the information to local ones.

reality check • April 8, 2008 4:46 AM

ok..ive been looking at CNG – the suitB support, ecc etc etc…on the face of it, it looks cool…

As usual I im having great issues with finding out exactly how to replace the PRNG (Random number generator) for some of the very reasons highlighted in this blog…

Anyone have experience (if there is such a thing yet of doing this?)

Im trying to replace the windows RNG with a custom one…my idea is to create a .dll that utilises soap which in turn calls my authentication server – running a hardware RNG service (HSM). I have already replaced the windows revocation provider to utilise my own x509 certificate checks but this was with CAPI not CNG.

Any ideas or pointers (MSDN already used, googled, etc..)

roberto • April 23, 2008 9:53 AM

should it not be enough to hexedit the dll or where else the library call is hosted, change a letter in the function call name, save it and do such that the file will not be replaced by the backped one by the system, nor replaced in upgrades. yes, crash of the bad programs will happen, that’s ok.

Hook • May 6, 2008 5:43 PM

Intel was supposed to include a true RNG device in their chipset almost 10 years ago. It was going serial shift quantum noise from a forward biased diode as the above poster talked about.

Why isn’t this a standard part of the IA32/64 instruction set, implemented in hardware using quantum noise?

Nicholas Parimore • November 22, 2008 2:30 PM

Yes, Intel did include RNG on some chips, but VIA has the one you want. Their C7 processors have dual-TRNG’s that can reach Mbit/s speeds. Also have hardware support for AES, SHA1/SHA256, and some RSA and public key ops. Did I mention it comes with those $200 Everex Walmart PC’s? Can anyone say “cheap crypto server?”

VIA Padlock Security Engine: http://www.via.com.tw/en/initiatives/padlock/hardware.jsp

Cryptography Research’s Analysis of VIA TRNG: http://cryptography.com/research/evaluations.html

Clive Robinson • November 23, 2008 11:15 AM

@ Nicholas Parimore,

“Yes, Intel did include RNG on some chips, but VIA has the one you want. Their C7 processors have dual-TRNG’s that can reach Mbit/s speeds. Also have hardware support for AES, SHA1/SHA256, and some RSA and public key ops.”

Yup the c7’s used to be on low cost low power boards as well and i that form where very cost effective in bespoke kit.

Unfortunatly the “atom” appears to be the current favourate flavour, which means big re-work comming over the horizon 8(

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.