The NSA's Backdoor in Dual EC

There was an amazing blog entry which explained it, but can't find it right now.

Edit: I don't think this was the one I read, but it's similar. https://cryptologie.net/article/316/junipers-backdoor/

Basically, Dual EC was chained to another PRNG, so the output should have been robust to crypto vulnerabilities discovered in any of both. The thing is: the second one was never called, because the for's index(a global variable) was set to 32 inside a function call, so the loop never run.

As i understand it, the hackers replaced a magic number Q with a different value than the standards compliant one, where they had pre-computed P.

[1]:https://www.youtube.com/watch?v=nybVFJVXbww

https://dl.acm.org/doi/pdf/10.1145/3266291 goes into it in some detail

Quote: "Addendum: the White House Press Secretary was asked about this story, and their answer is “please stop asking about this story.” h/t " - https://youtu.be/Hfa6bih_gVc?t=1740

That's f*ing hilarious

Now, if the backdoor is in place but no one was using it, no one would know if the public backdoor key got changed. But the attacker gets to decrypt all these sessions. OTOH, if NSA was trying to use the backdoor and noticed it wasn't working, they might start looking into it and find the hack.

So being able to make a very small source code change (32 bytes of public key material in this case) that has this impact is fantastic because that change is small enough that no one might have notice for a long time (which is apparently what actually happened).

But you're right, if you can change the source code then you can add a backdoor anyways, so Dual_EC being backdoored is not what was fatal to the Juniper systems. What was fatal to them is that they had poor internal security.

Still, an intentional backdoor key is plausibly -likely even- easier to replace than a backdoor is to add. So this is a decent argument against intentional backdoors. But it's not really a devastating argument against intentional backdoors.

Intentional backdoors are bad for political reasons too -- or good, maybe, depending on your point of view. Intentional backdoors are bad because the key to the backdoor can leak, and when that happens it can be very hard to fix -- this is devastating to security of the backdoored system, so I think it is a devastating argument against intentional backdoors, especially for a backdoor where exploitation is passive, like Dual_EC.

Dual_EC was a fine covert key escrow system for U.S. government systems, but there was no need to make it covert if it was only for that.

EDIT: But the real problem with Dual_EC is that it's terribly slow. /s

Uhm...isn't the whole basis of modern cryptography the idea that you can have keys that only the good guys know? Every time you use an HTTPS site for example you are relying on the existence of keys that only the good guys know. Every time you use an end to end encrypted messaging system you are relying on the existence of keys that only the good guys know.

The issue with backdoors is not keeping keys secret. It is keeping others from also installing backdoors.

In bridge building you might often ignore questions like "what if that nearby skyscraper fell on the bridge" or "what if there was a 100-year flood every day for a week". They're scenarios that can conceivably happen but they're very unlikely.

In computer security, you wouldn't be so safe because you need to protect your digital bridge from an adversary who has no problems demolishing the nearby figurative skyscraper.

Of course there are real-world situations where bridge building is adversarial, if you're in a war-zone for instance. I think the author is discussing more civil situations like "should we spend an extra $1B to make the bridge asteroid proof".

You don't have to make the bridge more than minimally strong against attack by a foreign military-- or even some wacko with a van full of ammonium nitrate, and you probably can't (or at least it would be utterly budget breaking to make a serious attempt and doing so).

While if you don't make your computer strong against fairly powerful attackers it will get attacked, because the economics of powerful computer attacks make them much less costly to create, almost free to deploy, and relatively low risk of consequences for using them. Fortunately, defending computers from attack also has good economics compared to defending bridges.

Its audience.

Wide reach, and ongoing engagement/discussion.

I read threads like this because the follow-on discussion is often just as or more interesting than the thread itself.

I think a blog post is also a good option here, but most blogs aren’t well suited for having a discussion.

The entire reason I signed up for a Twitter account, after something like 5 years of refusing to do so, was that I asked for some clarification on a post to Full Disclosure, and was told something to the effect of "this has already been discussed at length on Twitter". I had done a bunch of web searches already, and none of them had turned up the thread they linked to, but they were right.

I wouldn't say I'm a fan of Twitter, but because of that situation, I discovered a lot of other discussions in other fields that I wouldn't have seen otherwise, so it seems like a net positive.

That the generator is undetectably backdoorable through choice of constants has never been in question, from what I understand, and has been known outside the NSA (who designed it and chose the constants) via an explicit construction since before the relevant standard was finalized; it’s also so pointlessly slow nobody would normally include it in their own software except maybe out of completionism, which was ANSI’s official motivation for including it as well. (Green’s 2015 blog post[1] has the history and references.)

It’s also long been certain that Juniper included that generator in their software with the standard constant, then were hacked and afterwards for several years their software included in that place a different constant, with no other code changes, and finally an official emergency security update rolled that value back. The presence of the generator was not mentioned in the official documentation neither before nor after the hack, and the code gave the appearance of combining its output with that of another generator (which would have eliminated the backdoorability) while in fact not doing so because of something that looks like a logic bug. (I haven’t gathered the links on this but the surrounding comments here have most of them I think.)

Now, to me this seems like overhelming evidence that Juniper products have had a crippling security vulnerability due to the known backdoorability of Dual_EC_DRBG, without Juniper wanting it so. There is just no other plausible reason to break into Juniper and out of everything you could changing this one apparently pseudorandom string.

To make an argument against standardizing or using backdoorable cryptographic algorithms (Green’s point in the thread under discussion), this is as far as we need to get. The only thing the rest is relevant for is NSA’s reputation, government backdoors, and willing participation in them; but the Juniper story already suggests that the distinction between backdoorable and backdoored (and broken) is at best academic.

* * *

There is also a second place where Dual_EC_DRBG is known to be implemented, and that is the RSA BSAFE library. This library also includes but in most builds does not enable a weird TLS extension from what came to be known as the Extended Random family, though old and uninteresting Internet-connected devices have been spotted with it enabled. Now, the only thing this extension does—the thing it was described to be for by people bearing a US government badge who presented the Internet-Drafts on the IETF mailing lists—is expose more raw randomness from the system’s cryptographic random generator. No cryptographer anywhere has ever (publicly) described or even suggested any way to use this to improve the security of TLS in any configuration, including the authors of the Internet-Drafts. (See Green’s 2017 post[2] and links therein for the details.) However, if you are trying to break the system’s vulnerable random generator, exposing more of its output is immediately useful.

We are now two for two in commercial vendors of security products who implemented Dual_EC_DRBG also exposing its raw output (thus enabling the exploitation of the backdoor if one is configured through the choice of its constant) through ways that are both unusual and unnecessary for the operation of the product (logic bug for Juniper, completely useless and unused experimental TLS extension for RSA).

That when implementing Dual_EC_DRBG in the first place necessitates an explanation. Random generators are essential in a cryptographic systems, but unlike ciphers and such they are a completely opaque implementation detail—somebody you’re communicating with not only mustn’t depend on but actually can’t distinguish which generator you’re using (indeed a generator that can be distinguished is defined to be broken). Thus the choice of generator is a combination of speed (and it’s a speed-critical component) ease of implementation and confidence in the cryptograhy. Not only is the cryptograhy in Dual_EC_DRBG dodgy and known to be so—it’s a choice of 32 data bytes away from being completely and undetectably broken—it’s also hard to implement (elliptic curves in general are Hell on Earth, and while careful choices like in *25519 and *448 can mitigate that somewhat, Dual_EC_DRBG as standardized doesn’t have the necessary structure) and most importantly stupidly slow. It might make sense for ANSI (or, indeed, the NSA) to include it on the list in case it turns out 20 years later that the assumed-intractable problems underlying every other generator aren’t but elliptic curve logarithm still is (this was the official motivation), but as an implementor the one choice you’re going to omit absent an external reason is the generator which requires difficult mathematics and is also two orders of magnitude slower. Dual_EC_DRBG is not “suspicious” as a choice of random generator, it’s stupid.

This, I think, is enough to rule out any non-extraordinary hypotheses on why both Juniper and RSA included Dual_EC_DRBG in their products, and as extraordinary hypotheses go, “NSA paid them to, either directly or by imposing that condition in government contracts, because it did choose a constant enabling the backdoor for the generator it invented” is a pretty good one. It’s also corroborated by (otherwise questionable but plausible) reports of the NSA doing just that for Juniper (in the Yahoo Finance / Bloomberg report under discussion here) and RSA (quite some time ago[3], although it never rose above a rumour and RSA PR tried to run some damage control at the time). This also mostly discharges the questions as to why NSA would create and champion a known-backdoorable algorithm for the standard in the first place, all while dodging the constant choice question in the committee discussions (and even if they birthed this monster for some other reason, they could hardly have missed a freaking patent on the technique filed while standardization still was underway).

All in all, this looks like strong enough evidence to overcome the conspiracy-theoretic penalty and leave me reasonably certain the NSA really did both consciously put this into the standards and spend years pushing it into commercial products.

As to the question of the enemies of the US using this, I can offer two points:

- Cryptography is obscure, the infrastructural importance of computer systems is widely underestimated, and government (or corporate, or diplomatic, or any large organization’s) bureaucracy everywhere is pathologically incapable of staying on top of important details. Nobody ever got fired for buying Juniper firewalls or licensing RSA libraries; it’s the respectable, enterprisey thing to do. (Furthermore, not that many reputable companies make VPN appliances at all; for all we know Cisco weren’t any smarter.)

- National security, intelligence and counterintelligence, state security, secret police, however your place and time of birth call them, have been thoroughly rotten for as long as they have existed, maybe longer. The crossover Crusader / Big Data mentality, “surveil everyone and let God sort then out”, has always been the default. (As well as the old Soviet adage, “give me the man and I’ll find you the charge”, although in more civilized places one is hopefully forced to use blackmail and not the legal system.) There don’t need to be any real enemies of the US (or wherever) in the chosen direction as long as your salary or purpose in life depends on finding them; and, to be fair, it’s not as if the US doesn’t have plenty of enemies within or without.

And that’s a damn shame, because the problem of national security (to use modernity’s chosen term) is not imaginary; it’s just that the solution, even given sincere and well-meaning people as input, always comes out sick.

Finally, regarding suspicion and proof, I don’t really see the distinction you’re trying to make. If “strong suspicion” is to be understood as “weak but not negligible evidence one is struggling to formalize the reasoning for”, I disagree that’s what we have; if instead it means “strong but circumstantial evidence”, I agree, but the boundary between that and “proof” is largely nonexistent, especially in a situation such as this. Unless yet another good person self-immolates specifically to expose the nature of this particular trick in the NSA’s enormous bag, this as strong as support for this hypothesis is going to be, so demanding “proof” as opposed to the current “strong suspicion” seems epistemically counterproductive to me. There’s been enough fire for few enough results that I can’t in good conscience advocate anyone inflict more on themselves; this particular bit of trivia by itself also seems not worth giving up one’s life over.

(Snowden’s factual contribution to this specific story has been vague enough that it’s not particularly worth mentioning—something something working with and/or to compromise vendors, something something breaking “most encryption on the Internet”—except maybe for drawing people’s attention to the points above, all of which are from other and frequently earlier sources. “Lent credence” is right.)

* * *

What part of the “mess with Snowden” do you count as incompetence? The exfiltration approach he describes in his book does sound like run-of-the-mill incompetence if taken at face value, but that’s hardly the part that people were (and, I hope, still are) miffed about.

[1] https://blog.cryptographyengineering.com/2015/01/14/hopefull...

[2] https://blog.cryptographyengineering.com/2017/12/19/the-stra...

[3] https://www.cnet.com/tech/services-and-software/security-fir...

Stuff like this is, on the contrary, evidence that the NSA can't break modern cryptography. If they could, they wouldn't need to try to push through blatant backdoors like this.

If you want to be safe from the NSA, use well-vetted, simple, auditable cryptography tools. The NSA doesn't break real crypto any more, they just find or make software bugs.

The only "thing the NSA has probably broken" that comes to mind in the modern crypto world is when people realized that you could do a one time mass computation for fixed parameters for n-bit Diffie-Hellman and then use the result to decrypt any communications that that used them, efficiently... which was a bit of a problem when tons of software around the world was using default parameters, often 1024-bit, which is in "the NSA can almost certainly break it" range. I remember when that happened, I went through all my servers and re-generated my own dh parameters for OpenSSL, at 4096 bits. But this wasn't a particularly mind blowing idea, it was more like an "oh shit" moment since everyone knew the NSA had the storage/compute budget to actually carry out this attack. But anyone serious about crypto shouldn't have been using 1024-bit DH anyway; it was just a failure of the ecosystem that nobody had proactively deprecated such small sizes.

What are the other options for pure maths people? Academia? Does that really pay any better, plus, depending on your teaching level, there's a good chance you're just a babysitter. A cush gov't job probably sounds pretty good where you will actively be using your skills on a daily basis.

Are there FAANG opportunties for math people at the same level as gov't?

Such a bizarre take. The US government is one of the most belligerent and feared governments in the world, with a known track record of starting wars, toppling democratic governements that are opposed to them, ignoring international law, prioritizing US corporations over any local peoples. China and Russia aren't even half as scary to the vast majority of the planet.