The Strange Story of Dual_EC_DRBG

Random numbers are critical for cryptography: for encryption keys, random authentication challenges, initialization vectors, nonces, key-agreement schemes, generating prime numbers and so on. Break the random-number generator, and most of the time you break the entire security system. Which is why you should worry about a new random-number standard that includes an algorithm that is slow, badly designed and just might contain a backdoor for the National Security Agency.

Generating random numbers isn’t easy, and researchers have discovered lots of problems and attacks over the years. A recent paper found a flaw in the Windows 2000 random-number generator. Another paper found flaws in the Linux random-number generator. Back in 1996, an early version of SSL was broken because of flaws in its random-number generator. With John Kelsey and Niels Ferguson in 1999, I co-authored Yarrow, a random-number generator based on our own cryptanalysis work. I improved this design four years later—and renamed it Fortuna—in the book Practical Cryptography, which I co-authored with Ferguson.

The U.S. government released a new official standard for random-number generators this year, and it will likely be followed by software and hardware developers around the world. Called NIST Special Publication 800-90 (.pdf), the 130-page document contains four different approved techniques, called DRBGs, or “Deterministic Random Bit Generators.” All four are based on existing cryptographic primitives. One is based on hash functions, one on HMAC, one on block ciphers and one on elliptic curves. It’s smart cryptographic design to use only a few well-trusted cryptographic primitives, so building a random-number generator out of existing parts is a good thing.

But one of those generators—the one based on elliptic curves—is not like the others. Called Dual_EC_DRBG, not only is it a mouthful to say, it’s also three orders of magnitude slower than its peers. It’s in the standard only because it’s been championed by the NSA, which first proposed it years ago in a related standardization project at the American National Standards Institute.

The NSA has always been intimately involved in U.S. cryptography standards—it is, after all, expert in making and breaking secret codes. So the agency’s participation in the NIST (the U.S. Commerce Department’s National Institute of Standards and Technology) standard is not sinister in itself. It’s only when you look under the hood at the NSA’s contribution that questions arise.

Problems with Dual_EC_DRBG were first described in early 2006. The math is complicated, but the general point is that the random numbers it produces have a small bias. The problem isn’t large enough to make the algorithm unusable—and Appendix E of the NIST standard describes an optional work-around to avoid the issue—but it’s cause for concern. Cryptographers are a conservative bunch: We don’t like to use algorithms that have even a whiff of a problem.

But today there’s an even bigger stink brewing around Dual_EC_DRBG. In an informal presentation (.pdf) at the CRYPTO 2007 conference in August, Dan Shumow and Niels Ferguson showed that the algorithm contains a weakness that can only be described as a backdoor.

This is how it works: There are a bunch of constants—fixed numbers—in the standard used to define the algorithm’s elliptic curve. These constants are listed in Appendix A of the NIST publication, but nowhere is it explained where they came from.

What Shumow and Ferguson showed is that these numbers have a relationship with a second, secret set of numbers that can act as a kind of skeleton key. If you know the secret numbers, you can predict the output of the random-number generator after collecting just 32 bytes of its output. To put that in real terms, you only need to monitor one TLS internet encryption connection in order to crack the security of that protocol. If you know the secret numbers, you can completely break any instantiation of Dual_EC_DRBG.

The researchers don’t know what the secret numbers are. But because of the way the algorithm works, the person who produced the constants might know; he had the mathematical opportunity to produce the constants and the secret numbers in tandem.

Of course, we have no way of knowing whether the NSA knows the secret numbers that break Dual_EC-DRBG. We have no way of knowing whether an NSA employee working on his own came up with the constants—and has the secret numbers. We don’t know if someone from NIST, or someone in the ANSI working group, has them. Maybe nobody does.

We don’t know where the constants came from in the first place. We only know that whoever came up with them could have the key to this backdoor. And we know there’s no way for NIST—or anyone else—to prove otherwise.

This is scary stuff indeed.

Even if no one knows the secret numbers, the fact that the backdoor is present makes Dual_EC_DRBG very fragile. If someone were to solve just one instance of the algorithm’s elliptic-curve problem, he would effectively have the keys to the kingdom. He could then use it for whatever nefarious purpose he wanted. Or he could publish his result, and render every implementation of the random-number generator completely insecure.

It’s possible to implement Dual_EC_DRBG in such a way as to protect it against this backdoor, by generating new constants with another secure random-number generator and then publishing the seed. This method is even in the NIST document, in Appendix A. But the procedure is optional, and my guess is that most implementations of the Dual_EC_DRBG won’t bother.

If this story leaves you confused, join the club. I don’t understand why the NSA was so insistent about including Dual_EC_DRBG in the standard. It makes no sense as a trap door: It’s public, and rather obvious. It makes no sense from an engineering perspective: It’s too slow for anyone to willingly use it. And it makes no sense from a backwards-compatibility perspective: Swapping one random-number generator for another is easy.

My recommendation, if you’re in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG.

In the meantime, both NIST and the NSA have some explaining to do.

This essay originally appeared on Wired.com.

Tags: , , , , , , , , , , , ,

Posted on November 15, 2007 at 6:08 AM • 75 Comments

Comments

Lolita stays anonymous • November 15, 2007 7:19 AM

I think you nailed the why. It is not any of the people you listed who pushed for this algorithm with a back door, it is the ones you didn’t mention.

The only sane explanation is some official / person in power who kept on pushing for this, regardless of what the techies said.

n00b • November 15, 2007 7:21 AM

Maybe they are counting on the fact, that most of the programmers don’t have crypto background and will just get the algorithm, test cases and go on implementing it.

Other idea might be to later mandate it’s use in some circumstances and have sort of key recovery mechanism without messy escrow or master keystore.

Matt • November 15, 2007 7:29 AM

I think perhaps you don’t give them enough credit. Have you considered the idea that Dual_EC_DRBG is a red herring, and the real threat remains hidden in one of the other algorithms?

Nostromo • November 15, 2007 7:44 AM

I don’t understand why anyone thinks it is a good idea to use crypto standards defined by the NSA. Of course they have a lot of experience in the field, and it is very valuable to have them review a proposed standard and point out its weaknesses. But they have an obvious interest in promoting the use of crypto that they can break. In the perpetual conflict between the government’s desire to control and the people’s desire to be free, they are simply on the wrong side.

Steve Laniel • November 15, 2007 7:52 AM

Bruce writes: “If you have to use something in SP 800-90 …”.

This suggests that cryptographers shouldn’t use something in SP 800-90. I’m not a cryptographer, so I ask: what should we be using as our PRNG?

NotAllHomers • November 15, 2007 8:06 AM

Elliptic curves is the big clue here.

Pythagoras is well understood by the NSA. They will always try to put a “back door” into public encryption schemes. The flaw in DES is a classic case in point for those in the know so these “new” revaluations are not so new after all. The random number generator problem has been a favorite means to break a secure key for ages. Using the pit controller and reprogramming it to saturation on most home pc motherboards provides a good solution to the problem!

Karellen • November 15, 2007 8:33 AM

NotAllHomers > Huh? You say that the NSA will always try to put back doors in encryption schemes, and then bring up the DES flaw that the NSA fixed?!?

I do take it you’re talking about changes they made to the S-box constants in 1978 before DES was finalised, making it more secure against differential cryptanalysis. Differential cryptanalysis which the NSA invented in 1974 and wasn’t figured out by anyone else ’til 1990?[0]

So make your mind up – are the NSA always trying to make algorithms more secure, or less?

[0] http://en.wikipedia.org/wiki/Data_Encryption_Standard#NSA.27s_involvement_in_the_design

Nicholas Weaver • November 15, 2007 9:05 AM

I think it may be a “all your eggs in one basket” thing, that Dual_EC_DRBG proves to be computationally equivelent to the elliptic curve problem for public keys, so if there is an algorithmic breakthrough whith bones the pRNG, it also bones the public key operations as well. So if you have to do crisis management, it doesn’t make the problem any worse.

And because its something they have probably used for a LONG time, they want to make sure that all the old systems still apply to the “standard”, rather than having to replace them.

Matt • November 15, 2007 9:05 AM

Re: Karellen

They only fixed it because it was widely known. Wheels within wheels man, take the red pill and follow the rabbit hole.

John • November 15, 2007 9:12 AM

Oops. RNGs have more uses than cryptography. In my time (long ago) linearly congruential generators were in common use. They were no good for cryptography, but quite good for statistical purposes. They also had the advantage of generating pseudo-random sequences that could be reproduced (a big point).

But, in those days there was also a dearth of literature on non-linear generators (like nothing, a deafening silence), and some of my math friends suspected NSA influence.

So, the latest NIST standard may prove excellent for general use, but remain suspect for crypto.

That is nothing new.

Crypto is a specialized field. I believe that to be used effectively in the private sphere, we would need Corporate Security Agencies (CSAs) analogous to the NSA for the Government. I have yet to see that happen.

Nyhm • November 15, 2007 9:15 AM

This is not directly related to RNG, but some other references regarding the U.S. gov’t involvement in algorithm design from Bruce:

Regarding prime number choices for DH and DSA standardization: Practical Cryptography (Ferguson,Schneier) Ch 12.9, pp.220-222: “Other parts of that same U.S. government (e.g., NSA, CIA, FBI) have a vested interest in being able to break into private communications.”

Somewhere (could not find the reference), Bruce stated that the U.S. gov’t (NIST,NSA) would logically have stronger interest in providing strong digital signature functions (vs. strong encryption), which would imply producing good hash algorithms. (Please double-check this, as I have no reference.)

Dave Walker • November 15, 2007 9:32 AM

It’s interesting to compare and contrast this case, to the famous case of the NSA requesting the contents of the S-boxes be changed in the prototype which eventually became DES. The fame, here, came when differential cryptananalysis was discovered in the non-NSA world, and the prototype was found to be particularly vulnerable whereas production DES was rather less so.

Yesterday, the NSA was making crypto stronger, without us knowing about it. Now, they might be introducing back doors.

How times change.

Andrew • November 15, 2007 9:45 AM

What about true hardware random number generators? They are becoming more common on various processors these days. The TI Omap series of ARM processors have them, as do the Cavium (and other) network processors. Given that some of these processors sell for only a few $, how hard can it really be for the big guys to add them to, say, an x86?

greg • November 15, 2007 9:55 AM

I thought that any algo with constants should use a public method to generate them or move them out of control of the designer. (aka n digits of pi or e).

But more impressive is that insisting on published algorithm’s is working. A hats of to the code breakers…NSA can’t be that far head of the published literature any more.

Clive Robinson • November 15, 2007 10:11 AM

As Bruce says’

“Generating random numbers isn’t easy”

“Problems with Dual_EC_DRBG were first described in early 2006. The math is complicated, but the general point is that the random numbers it produces have a small bias.”

Even non determanistic or True RNGs based on such things as radioactive decay have bias, that can be sufficiently predictable to weaken a system where it has not been taken into acount.

Likewise Noise Resistors and diodes can be subject to external signals which would add bias to their output.

And even interferance on the power cables in a building can have an effect on the output of any poorly designed physical RNG.

Oh and all physical sources of randomness usually produce very little in the way of random bits in any given time frame.

The usual suggestion for getting rid of bias and upping the bit rate is hashing a pool of entropy… Which unsurprisingly (due to complexity of the problem) has little real reasearch behind it, it just “feels right”.

Hashing has it’s own problem, if your source of randomness goes wrong and becomes predictable after it has been hashed it will not be obvious to the casual or unskilled observer.

And an entropy pool likewise has problems if an attacker can get access to any input to it (say via hitting the hard disk controler with lots of file access requests) they can eventually poison it to their advantage.

So even when designing in a True Random Generator you need to be very carefull with what you use/buy.

Barney • November 15, 2007 10:15 AM

It’s not really a backdoor, it’s more a flaw.

The recommendation to use other generators is, of course, relative.

If you really have to save the extra hour (in NSA time) it takes to break, then you just infiltrate the process.

UNTER • November 15, 2007 10:24 AM

Bruce,

This sounds like the old Heisenberg ploy. Someone at the NSA got orders from folks higher up to make a back-door PRNG. The mathematician thought this was absolutely imbecilic, useless, and dangerous, but he was under orders.

So he does what Heisenberg did with A-bomb work in Germany – he does the job poorly and slowly. “Yup, I’ve got it!” So it’s slow – that would dissuade good engineers who don’t have the maths to see it. It’s obvious – that dissuades the mathematicians who don’t care about efficiency.

The only people screwed are those who don’t think about the problem at all, much like the manager who demanded the back door. Probably a Bush political hack, I bet.

sooth_sayer • November 15, 2007 10:50 AM

There might be a simpler and more human explanation.

The person in-charge or his/her protege did the work the DRBG’s .. sometimes such motivations drive people. Who hasn’t heard of Edison frying someone with AC to push DC.

I don’t understand why the source of constants has to be explained if the algorithm to generate them is provided.

The back-door scenario will be troublesome if it were proven for any set constants. That would be even a bigger back door than the one implied in the article.

FP • November 15, 2007 10:54 AM

@Andrew: “true hardware random number generators”

Most true random number generators are too slow for cryptography or other real-world applications.

When many random numbers are needed, and a true random number generator is available, it is usually only used to seed a pseudo-random number generators.

A good PRNG, when seeded with random input, produces “infinite” amounts of pseudo-numbers that are indistinguishable from “truly random” numbers.

anurag • November 15, 2007 11:28 AM

it seems more likely, given that the impl is slow, that there are problems with the other approaches that NSA is aware of, and they want something in the standard that is still viable that they can advise people to use. Ditto for choice of Q.

Its hard to see how they benefit from forcing a slow, complex, broken mechanism into the standard. A slow, complex, only known safe mechanism, I would understand.

That said, the fact that everyone else is placed in a position of just having to trust is certainly problematic.

Clive Robinson • November 15, 2007 11:30 AM

@FP,

“A good PRNG, when seeded with random input, produces “infinite” amounts of pseudo-numbers that are indistinguishable from “truly random” numbers.”

If only that where true…

It’s not, a very simple thought experiment disproves it. “Infinite” includes all numbers therefore their length is also infinite, a PRNG is limited to the size of numbers it produces by the size of it’s internal state (in bits).

Also You have the problem of how often you re-seed the PRNG. It depends on the unisity distance of the one way function of the PRNG. A bad example using DES then you would have to re-seed about every two block outputs to be theoreticaly secure…

ace • November 15, 2007 11:45 AM

Looking in 800-90: there are P-256, P-384 and P-521. Are they all broken? It sounds so? Then it’s more than unlucky coincidence.
Second, there is the recipe for alternatives in Appendix. It probably doesn’t mention the “prime order” condition? Otherwise it would be too obvious?
Third, if when somebody doesn’t know of such condition, and make his own constants, what’s the probability that he’ll make the same error as Dual_EC_DRBG authors? The Appendix expects alternative constants to be “hard-wired” in the source code or the hardware.

aze • November 15, 2007 11:48 AM

I have a better theory. There’s only one reasonable reason to have a slower algorithm. That’s because it’s stronger than all the others. NSA knows secret weakness(es) in all other commercial crypto systems. So; the NSA have published this because they want to have decent commercial crypto available off the shelf for their own use. (I know this doesn’t sound very paranoid.. please just wait :-). All they have to insist on is full implementation of the standard and they get their own RNG which is actually secure.

Whatever weakness the other systems have that this doesn’t have, is dependent on the keying of the special constants. If you choose randomly you get a weak system. If you choose according to some rule that only they know you get a strong system. If you take the constants they give, you get a strong system with a backdoor.

This would also match with the way that Russian crypto systems are much slower and more conservative than most western ones. Maybe they know something about NSA crypto that we don’t know.

(now I get to find out why you should know more about crypto before commenting on Bruces blog.)

David (Toronto) • November 15, 2007 11:51 AM

Deja-DES-vu indeed.

Magic numbers, it even sounds like the S-box controversy all over again.

@Karellen & Dave Walker – Yes the NSA made the DES S-boxes stronger. However, somewhere along the line the key length got halved. DESCHAL and EFF wouldn’t have broken 112 bit DES in – my god that was 10 years ago. Nor today for that matter.

Maybe they are weakening it, maybe not. If they are and the parrallel holds, the magic numbers are a red-herring. So, what are we missing?

Having a fallback method is an interesting idea, but unless it’s just in case – the implications may be a bit of a worry.

Anonymous • November 15, 2007 12:00 PM

@ Clive Robinson

“‘Infinite’ includes all numbers therefore their length is also infinite, […]”

Wouldn’t that only be true if I were attempting to create an infinitely long series of UNIQUE numbers? If I allow for any given number to be used an indefinite number of times, shouldn’t I be able to create an infinite series of numbers that doesn’t include all numbers?

Greg Alexander • November 15, 2007 12:15 PM

Dear Mr. Schneier,

Why did you cite the Gutterman/Pinkas/Reinman paper? It picks nits and it only suggests three exploits:
* if you have access to kernel memory on a stopped system, you can determine the previous random number generated. Newsflash: if you have access to kernel memory on a stopped system, you already won. Did you know that if you strace the program reading from /dev/urandom, you can see what numbers it is currently reading? Wow!
* if you know the root password then you know certain attributes of the user’s first interaction with the computer which may help you predict entropy pool contents. In actuality, if you know the root password you already won. Even if you hadn’t, vaguaries in the way that it is typed (time of boot, time of login, speed of typing, typos, etc.) provide enough entropy to make this attack infeasible. As they note in the paper!!
* if you know the complete set of network events going into a WRT router, you know its entropy pool. Since WRTs almost never contain private keys (and if they do, knowing the state of LRNG is of limited utility), you may as well replace the WRT with your own device if you have this kind of complete hardware access to the network. Further, at worst this is a weakness in a special case application of the LRNG rather than a general weakness in the LRNG.

It rounds out with a bunch of gnashing of teeth about documentation and open source development ideology, and a neither-here-nor-there whinge about a denial of service attack.

Frankly, if The Bruce Schneier is going to say that the LRNG is “flawed”, I’d hope you’d cite something a little bit less retarded. Or does your authority mean so little to you?

Savik • November 15, 2007 12:23 PM

The NSA is after all a government agency with a mission to protect national assets — meaning it helps business and individuals protect their assets. How? By providing secure encryption algorithms and best practices for securing systems, etc.

Just because they have the capability to perform nefarious activities does not mean that they do. And really — where is the evidence that they have?

Why so quick to jump to conspiracies all of the time?

Bryan Feir • November 15, 2007 12:27 PM

@ David (Also in Toronto):

The explanation I heard for NSA and their handling of the DES keys (which was more along the lines of ‘this is the only thing that really makes sense’, since the NSA is understandably unwilling to provide official answers):

Remember that part of the push for DES was a standard encryption system to be used by even the American government. (For Classified documents, at least; Secret and up were to use other methods.) So the NSA wouldn’t want it to be too easily broken.

Also emember that NSA has a large, classified budget. They have long been one of the biggest investors in supercomputer technology, and almost certainly had and still have access to a lot of high-end computing resources.

So basically, with DES they wanted a system that had no weaknesses that the Russians could exploit to crack it… but which was had a short enough key that the NSA could brute-force it themselves in a reasonable length of time.

DES was never supposed to be the be-all and end-all of encryption; even when it was first adopted, it was given a ‘shelf life’ of how long it would be considered useful before something stronger was needed.

There are all sorts of interesting bits about DES that tell you what its designers were thinking. Such as the initial permutation which shuffles the bits around and then shuffles them back. This has absolutely no effect on the actual cryptographic strength of the algorithm, and doesn’t affect hardware implementations at all… but it slows down purely software implementations.

Greg Alexander • November 15, 2007 12:28 PM

More details…. The previous post was about the “Analysis of the Linux Random Number Generator.” I decided to read “Cryptanalysis of the Random Number Generator of the Windows Operating System” from Dorrendorf/Gutterman/Pinkas, for contrast. I find it odd that the flaws in the Windows generator are described as “a flaw” while the FUD about the Linux generator is described as “flaws”. Let me compare and contrast:

  • Entropy:
    • Linux: maybe predictable, if the moon lines up just right and you squint
    • Windows: only used every 128kB, not used for seed, and therefore mostly irrelevant
  • forward-security attack:
    • Linux: possible to go back one value if there is no intervening entropy and if you have full access to kernel, O(2^64) or harder
    • Windows: possible to go back up to 128kB values with just access to user memory, O(2^23)
  • backward-security attack:
    • Linux: O(1) iff there are no entropy events occurring whatsoever
    • Windows: O(1) for 128kB no matter what

The vulnerabilities are not even in the same realm. The Windows vulnerabilities are the sort of things that can and will be exploited in The Real World we all Know And Love. The Linux vulnerabilities are grasping at straws.

Bruce, whyfor behavest thou so disrespectfully towards facts?

Karellen • November 15, 2007 12:39 PM

David (Toronto) > The NSA did not halve the DES key length, it was originally 64 bits before they reduced it to 56 bits.

Anonymous • November 15, 2007 1:40 PM

anyone thought of the NSA inisisting on this rather obvious flaw to be included in the standard to divert attention from the other more subtle ones???? call me an unbeliever but not trusting agencies like the NSA has proved to be good practice throughout history 🙂

Anonymous • November 15, 2007 2:12 PM

Good to read your website/blog Bruce, critical issues.
Previous posters, some need to read about DES…

Dual_EC_DRBG: DES S box history seems a good starting point, see BS’s book, Applied Cryptography. Some ideas I’m pondering:
With Trusted Computing and DRM coming around, privacy rethink, Donald Kerr recent news, I’m glad the NSA puts up the target ballon of Dual_EC_DRBG. Mainstream needs crypto issues put up, to keep people honest. What happened with S boxes and those in the know, beyond reported in Applied Cryptography? Idea is, how proactive is the NSA to keep crypto from being a used as a hostile measure?
Trap doors and time to break seem critical design issues, unique keys in each hardware, with other crypto magic?
The NSA must be getting VERY good at crypto today, although others outside are too. Dual_EC seems to have a good bad and ugly nature. Hopefully, the movie ends right, ahhhhhhhhh!

Jeremy • November 15, 2007 2:13 PM

@Anonymous
“If I allow for any given number to be used an indefinite number of times, shouldn’t I be able to create an infinite series of numbers that doesn’t include all numbers?”

Yes.

However, pseudo-random algorithms still can’t do this, because their internal state has finite size (required to run on a computer with finite memory). This means that, after some finite number of outputs, the generator has to enter a state that it’s been in before. At that point, the generator has entered a loop (though possibly a very long one). All outputs after that point are cyclic, and can be predicted knowing only the previous outputs and the cycle length.

Anonymous • November 15, 2007 3:04 PM

Andrew: “how hard can it really be for the big guys to add them to, say, an x86?”

They’ve been in VIA processors, and Intel/AMD chipsets, since the Socket 370/Socket A days.

RC • November 15, 2007 3:45 PM

The main problem with this deliberate vulnerability is that it proves the NSA is willing to act in this manner, casting doubt on all the other standards in which they have been substantially involved.

David (Toronto) • November 15, 2007 4:13 PM

@Karellen – I believe you are mistaken.

  1. Wikipedia mentions both a 64 and 128 version of Lucifer predating DES, but is unclear which went forward.

  2. Biryukov is clearer (in “Block Ciphers and Stream Ciphers: The State of the Art”) … “The structure of Lucifer was significantly altered and since the design rationale was never made public and the secret key size also went down from 128-bit to 56-bits this resulted in controversy, and distrust among the public.”

Paul Wayper • November 15, 2007 5:31 PM

Even if this is an obvious backdoor, there’s one way I can think of that they can still get to easily exploit it.

If all US Government servers were set up so that they used the Dual_EC_DRBG method, then no matter what random bit generation method you use the NSA already knows something about your encrypted data. Maybe this only allows them to decrypt the server’s side of the conversation. Maybe they can only break the encryption easily if both sides are using Dual_EC_DRBG. But forcing the hand of one party is a good start. And if you can get two Government machines to talk to eachother, you have a guaranteed ability to break their encryption.

So regardless of whether it’s slower, uglier and smells of fish, it may still give the powers that be a chance to listen in. Once it’s in the standard it’ll be very hard to shift.

Filias Cupio • November 15, 2007 7:31 PM

You could run two of the PRNG algorithms and XOR their output. In this case, someone would need to break both algorithms to break your PRNG.

Is this a sensible strategy? Would you get more cryptographic value for your cpu cycles/memory by using just one algorithm but with more rounds and/or longer keys?

Paran0id • November 15, 2007 8:01 PM

“My recommendation, if you’re in need of a random-number generator, is not to use Dual_EC_DRBG under any circumstances. If you have to use something in SP 800-90, use CTR_DRBG or Hash_DRBG.”

Oh Bruce!

You risk antagonising the Power.

Watch out for Black Helicopters.

David Thomas • November 15, 2007 10:25 PM

@Greg Alexander

… aren’t we sensitive! Bruce didn’t say the LRNG “is flawed,” he said that the paper “found flaws.” This is true – as much as they are not of practical concern, they are flaws. Appropriate discrimination between the Windows 2000 RNG and the Linux RNG was not the point of the article. What was Bruce’s recommendation? “Don’t use the LRNG”? No, it was “Don’t use Dual_EC_DRBG,” as it gives every indication of deliberate sabotage. Were the paper a survey of RNGs more generally, more details would be required. The point was how easy it is for RNGs to stray from ideal when you’re trying to make ’em work right, and that, in this case, they may not have been trying.

Matthew Skala • November 15, 2007 11:00 PM

Filias Cupio: I think my PRNG is pretty good, but I want extra security, so I’ll XOR it with the output twice.

I agree with RC: regardless of why the NSA would suggest this PRNG with an obvious problem, the fact that they’re willing to do so is itself an important piece of information.

As for what their inscrutable reasons might be, I’m reminded of a comment about the old Soviet GOST block cipher, which I think I read in Bruce’s AC2: the cipher had selectable S-boxes, and it was speculated that the people in charge of crypto would give secure S-boxes to the people they wanted to have secure S-boxes, and insecure S-boxes to the people they wanted to have insecure S-boxes. I could see something like that coming into play here. If everyone implements the standard and the standard includes an insecure option among the secure ones, then someone who knows about that and wants to control whether a party’s communications are secure or not, just has to influence the party to choose the right option. The benefits of standardization, and of people you want to be secure and people you don’t want to be secure using the same software and probably not noticing that they’re using different settings for it, are huge.

Anonymous • November 16, 2007 1:20 AM

“The main problem with this deliberate vulnerability is that it proves the NSA is willing to act in this manner, casting doubt on all the other standards in which they have been substantially involved.” RC

Good point. So why do they push ECC so much? They have provided the curves more or less. Maybe like other curves the recommended curves will map to a group that the normal Index calculus can be used. Now the security of ECC is no better than other DL based PK methods. Problem is you use ECC because we think its safe to assume that the sub exponential Index methods don’t apply.

Q • November 16, 2007 5:44 AM

All artithmetic generated random numbers suffer from this problem. If you maintain a list of all known used arithmetic random generators, then with an algoritm like C4.5 (search for “C4.5” with Google) you can easily discriminate which arthimetic random generation algorithm is used to produce the random numbers and therefore easily break the used computational secure algorithm.

The Information-Theoretic provable secure low-cost PC-based FreeMove Quantum Exchange Proof-of-Concept System therefore uses true Quantum Randomness instead of pseudo arithmetic randomness. By the way: This was already predicted in 1951 by John von Neumann.

More Information on this Research Proof-of-Concept can be found on the URL http://picasaweb.google.com/freemovequantumexchange

Clive Robinson • November 16, 2007 6:00 AM

@Matthew Skala,

“people in charge of crypto would give secure S-boxes to the people they wanted to have secure S-boxes, and insecure S-boxes to the people they wanted to have insecure S-boxes.”

Actualy there is a history of this happening. During WWII the U.S. issued a small field machine cipher based on a coin counting mechanism. It is now known that something aproaching 80% of the keys where relativly insecure. The argument given at the time was that if it was captured and copied the chances are that the adversery would not know about the relative security of the keys, and would in all probability end up predominantly using the relativly insecure keys. Likewise the possability of weakness in other Crypto AG ciphers suposedly put in by the NSA has been debated on numerous occasions.

It has been surmised that the NSA did not know about either Differential or Linear cryptanalysis at the time IBM made their original submission for DES.

It is known that the designers of DES actually discovered the weaknesses in the S-Boxes after developing their own “new” attack (T or tickle) which was later re-discovered by people playing around with early versions of FEAL. The level of involvment of the NSA in actually strengthaning the S-Boxs has never been released and is still something of a controversy (see Don Coppersmiths and others comments on the “T-Attack”). It has been further suggested that the NSA had no input other than to tell the IBM design team to keep their mouths shut for the sake of National Security.

Oddly the NSA assumed that DES would only be put in hardware and that they could control the technology supply to banks and the like. It has been said that it was one of their biggest (publicaly known) mistakes, it realy was responsible for kick starting the computer security industry and Universities delving into Crypto research

Later as we know the NSA tried to push a DES replacment which they tried to keep the internals of secret (Skipjack / CapStone / clipper) it was soundly rejected by just about everybody. In June 1998 they declasified the Skipjack algorithm and interestingly although it is secure in the implimentation the NSA released it is very brittle in that even very minor changes to the algorithm can weaken it greatly.

Inglorion • November 16, 2007 6:45 AM

While on the subject of PRNGs, I’d like to point people at my
deadbeef random number generator (http://inglorion.net/software/deadbeef_rand/).
While I made it as a kind of joke, I have the feeling that it
can be useful in practice, as it’s simple and seems to
perform fairly well. I don’t have the background to perform
a good analysis of it, but maybe someone here can help with that.

John • November 16, 2007 8:18 AM

There were a couple of comments on DES peculiarities that I want to add to.

  1. The Initial Permutation. The DES designers never explained its purpose. It was widely believed that its purpose was to make software implementations costly, and thus prefer hardware.

However, somebody (I forgot his name, sorry – David Hoye?) came up with a clever scheme of boolean operations that achieved the IP quickly and cheaply.

  1. Why the NSA preference for hardware?

My guess is purely legal. The Arms Import and Export Act began in 1954 with a different name, the Military something Act. At that time, effective crypto meant hardware. The ITAR, which implemented the law, listed crypto hardware (legally “devices”). Nobody thought of software.

Now, a law to be enforceable has to be fairly specific. If crypto is equipment, it could be argued that software isn’t equipment and thus is exportable without permission. It was a gap in the law.

Sometime in the early 80s somebody recognized the same gap I did, and software crypto was added to ITAR. Further, the Munitions Control Board extended the definition of cryptographic devices and software to include cryptanalytic devices and software in one of its bulletins.

But at the time of DES, NSA’s General Counsel feared that its legal authority did not extend to software implementations. At least, that is my surmise. Thus, the insistence on hardware.

Rick • November 17, 2007 7:28 PM

Is this sort of bias something that the NSA might
expect the research community to detect? Or,
looking at it another way, was this a “test” to
see if the non-NSA community would detect
a backdoor?

IN_the_Surf • November 18, 2007 7:19 PM

Bruce,

For as much as you lament the current administration’s “fear tactics,” you sure do a great job yourself when it appears to benefit a point that you are making.

“…we have no way of knowing whether the NSA knows the secret numbers that break Dual_EC-DRBG. We have no way of knowing whether an NSA employee working on his own came up with the constants—and has the secret numbers. We don’t know if someone from NIST, or someone in the ANSI working group, has them. Maybe nobody does.”

Bruce, the absence of proof is not proof of wrongdoing in this case. You are however presenting this lack of knowledge as if it were proof that wrongdoing is occurring.

I have no problem with you questioning the veracity or safety of such things; however, you should try and give some evidence to support your claims as well as be “open” enough to allow for others to do such things as well. You have a tendency to think that your questions, opinions, and worries are the rational ones. You are, by far, not the only “authority” on security topics.

Rangan • November 19, 2007 6:20 AM

Bruce

Why should we worry about contraversial PRNG – Dual_EC_DRNG?
We should think in a new line. Like, computing DRNG from Pi infinite series that will give a good entropy.

Rangan • November 19, 2007 6:32 AM

Bruce

Sometimes, DRNGs won’t be useful other than crypto applications. We should design DRNGs should be useful for multiple applications such as Information Security, Image processing, Digital Signal processing.

I don’t know CTR_DRNG / Hash_DRNG that will be useful for multiple applications. Give me some DRNGs that we can use for many things.

Brian • November 19, 2007 8:40 AM

Being completely ignorant of the math involved with ECs and PRNGs, has anyone tried factoring the constants from Appendix A of the NIST publication? Would that help in determining the secret numbers?

_Anonymous • November 21, 2007 5:36 PM

One can only hope that Quad_EC_TFHA might be declassified someday in order to put an end to this conspiracy.

(TFHA = Tin Foil Hat Algorithm)

Stromseal • December 1, 2007 11:10 PM

The spooks already have the backdoor, frontdoor, sidedoor and the basement key. Oh, and there’s the secret trapdoor that they have told you about too.

Mike • July 31, 2008 3:30 AM

IN_the_Surf:

You are however presenting this lack of knowledge as if it were proof that wrongdoing is occurring.

I don’t at all see how Bruce is saying that. He even writes: “We don’t know if someone from NIST, or someone in the ANSI working group, has them. Maybe nobody does“. He is highlighting a valid concern, but asking for more proof simply highlights that you don’t understand this problem at all. There cannot be any proof given about this, neither that this is not the case, so Bruce is asking to be cautious, and since there are other and better alternatives, it is a no-brainer to use them instead.

That you have to point out that Bruce is not the only authority on security topics (although I fail to see why it is relevant to mention that) tells me that this is more of a personal problem you have with Bruce, than anything else.

HUCK • September 17, 2008 1:43 PM

Has anyone from ANSI / NSA / etc. commented on this potential backdoor since this article was posted?

Thanks for keeping encryption sane for us all, Bruce.

Dennis • July 6, 2013 8:45 AM

Intel includes a hardware random number generator starting with the Ivy Bridge chip. It produces 800 megabytes/second, using the hardware randomness as input to a cryptographic function. Google brings up plenty of articles, such as this.

Kernel Kurtz • July 6, 2013 7:22 PM

Who developed the constants? I’d start looking at car wrecks around that time. They lo-o-o-o-v-e car wrecks.

sapien_red • July 7, 2013 11:01 AM

i have a nagging doubt , i suspect a double bluff.

they what people far far away from ecc and any crypto implementation based on it.

give a bad example with obvious flaws to scare them off
“its a trap”

i will be looking into ECC with renewed interest because of this 😉

Clive Robinson • July 8, 2013 6:35 AM

@ Dennis,


    Intel includes a hardware random number generator… It produces 800 megabytes/second, using the hardware randomness as input to a cryptographic function.

I would be very very cautious about the Intel RNG system.

One major issue is you cannot test it reliably because of the crypto function.

As I’ve repeatedly said in the past crypto/hash functions do not add entropy to the output of the basic entropy generator, using such systems are the equivalent of “sprinkling magic pixie dust” thinking.

Further the basic entropy generator is very likely to be subject to significant bias and noise that is not actually unpredictable (think powersupply noise it is mainly dependent on the input source and load conditions all of which are either measurable or influanceable).

If you cannot get directly at the output of the basic entropy generator than you cannot check it, thus all bets are off as to if it’s actually giving you any entropy at all…

Hussam • January 21, 2015 2:44 AM

You are really awesome Schneier as stated above in the comments in fact it is a backdoor for the NSA!

Nick P • January 22, 2015 12:46 AM

You were right to worry. Good advice too. Yet, it makes perfect sense if they think they can pay major crypto providers a lot of money to use it. And then they have easy access to so many communications. What doesn’t make sense for technical reasons can sometimes make sense for operational reasons in tradecraft. Just like marketing winning over technical superiority in commercial sector.

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.