Yesterday, David Benjamin posted a pretty esoteric note on the IETF’s TLS mailing list. 
At a superficial level, the post describes some seizure-inducingly boring flaws in older Canon printers. To most people that was a complete snooze. To me and some of my colleagues, however, it was like that scene in X-Files where Mulder and Scully finally learn that aliens are real.
Those fossilized printers confirmed a theory we’d developed in 2014, but had been unable to prove: namely, the existence of a specific feature in RSA’s BSAFE TLS library called “Extended Random” — one that we believe to be evidence of a concerted effort by the NSA to backdoor U.S. cryptographic technology.
Before I get to the details, I want to caveat this post in two different ways. First, I’ve written about the topic of cryptographic backdoors way too much. In 2013, the Snowden revelations revealed the existence of a campaign to sabotage U.S. encryption systems. Since that time, cryptographers have spent thousands of hours identifying, documenting, and trying to convince people to care about these backdoors. We’re tired and we want to do more useful things.
The second caveat covers a problem with any discussion of cryptographic backdoors. Specifically, you never really get absolute proof. There’s always some innocent or coincidental explanation that could sort of fit the evidence — maybe it was all a stupid mistake. So you look for patterns of unlikely coincidences, and use Occam’s razor a lot. You don’t get a Snowden every day.
With all that said, let’s talk about Extended Random, and what this tells us about the NSA. First some background.
Dual_EC_DRBG and RSA BSAFE
To understand the context of this discovery, you need to know about a standard called Dual EC DRBG. This was a proposed random number generator that the NSA developed in the early 2000s. It was standardized by NIST in 2007, and later deployed in some important cryptographic products — though we didn’t know it at the time.
Dual EC has a major problem, which is that it likely contains a backdoor. This was pointed out in 2007 by Shumow and Ferguson, and effectively confirmed by the Snowden leaks in 2013. Drama ensued. NIST responded by pulling the standard. (For an explainer on the Dual EC backdoor, see here.)
Somewhere around this time the world learned that RSA Security had made Dual EC the default random number generator in their popular cryptographic library, which was called BSAFE. RSA hadn’t exactly kept this a secret, but it was such a bonkers thing to do that nobody (in the cryptographic community) had known. So for years RSA shipped their library with this crazy algorithm, which made its way into all sorts of commercial devices.
The RSA drama didn’t quite end there, however. In late 2013, Reuters reported that RSA had taken $10 million to backdoor their software. RSA sort of denies this. Or something. It’s not really clear.
Regardless of the intention, it’s known that RSA BSAFE did incorporate Dual EC. This could have been an innocent decision, of course, since Dual EC was a NIST standard. To shed some light on that question, in 2014 my colleagues and I decided to reverse-engineer the BSAFE library to see if it the alleged backdoor in Dual EC was actually exploitable by an attacker like the NSA. We figured that specific engineering decisions made by the library designers could be informative in tipping the scales one way or the other.
It turns out they were.
Extended Random
In the course of reverse engineering the Java version of BSAFE, we discovered a funny inclusion. Specifically, we found that BSAFE supports a non-standard extension to the TLS protocol called “Extended Random”.
The Extended Random extension is an IETF Draft proposed by an NSA employee named Margaret Salter (at some point the head of NSA’s Information Assurance Directorate, which worked on “defensive” crypto for DoD) along with Eric Rescorla as a contractor. (Eric was very clearly hired to develop a decent proposal that wouldn’t hurt TLS, and would primarily be used on government machines. The NSA did not share their motivations with him.)
It’s important to note that Extended Random by itself does not introduce any cryptographic vulnerabilities. All it does is increase the amount of random data (“nonces”) used in a TLS protocol connection. This shouldn’t hurt TLS at all, and besides it was largely intended for U.S. government machines.
The only thing that’s interesting about Extended Random is what happens when that random data is generated using the Dual EC algorithm. Specifically, this extra data acts as “rocket fuel”, significantly increasing the efficiency of exploiting the Dual EC backdoor to decrypt TLS connections.
In short, if you’re an agency like the NSA that’s trying to use Dual EC as a backdoor to intercept communications, you’re much better off with a system that uses both Dual EC DRBG and Extended Random. Since Extended Random was never standardized by the IETF, it shouldn’t be in any systems. In fact, to the best of our knowledge, BSAFE is the only system in the world that implements it.
In addition to Extended Random, we discovered a variety of features that, combined with the Dual EC backdoor, could make RSA BSAFE fairly easy to exploit. But Extended Random is by far the strangest and hardest to justify.
So where did this standard come from? For those who like technical mysteries, it turns out that Extended Random isn’t the only funny-smelling proposal the NSA made. It’s actually one of four failed IETF proposals made by NSA employees, or contractors who work closely with the NSA, all of which try to boost the amount of randomness in TLS. Thomas Ptacek has a mind-numbingly detailed discussion of these proposals and his view of their motivation in this post.
Oh my god I never thought spies could be so boring. What’s the new development?
Despite the fact that we found Extended Random in RSA BSAFE (a free version we downloaded from the Internet), a fly in the ointment was that it didn’t actually seem to be enabled. That is: the code was there but the switches to enable it were hard-coded to “off”.
This kind of put a wrench in our theory that RSA might have included Extended Random to make BSAFE connections more exploitable by the NSA. There might be some commercial version of BSAFE out there with this code active, but we were never able to find it or prove it existed. And even worse, it might appear only in some special “U.S. government only” version of BSAFE, which would tend to undermine the theory that there was something intentional about including this code — after all, why would the government spy on itself?
Which finally brings us to the news that appeared on the TLS mailing list the other day. It turns out that certain Canon printers are failing to respond properly to connections made using the new version of TLS (which is called 1.3), because they seem to have implemented an unauthorized TLS extension using the same number as an extension that TLS 1.3 needs in order to operate correctly. Here’s the relevant section of David’s post:
The web interface on some Canon printers breaks with 1.3-capable
ClientHello messages. We have purchased one and confirmed this with a
PIXMA MX492. User reports suggest that it also affects PIXMA MG3650
and MX495 models. It potentially affects a wide range of Canon
printers.
These printers use the RSA BSAFE library to implement TLS and this
library implements the extended_random extension and assigns it number
40. This collides with the key_share extension and causes 1.3-capable
handshakes to fail.
So in short, this news appears to demonstrate that commercial (non-free) versions of RSA BSAFE did deploy the Extended Random extension, and made it active within third-party commercial products. Moreover, they deployed it specifically to machines — specifically off-the-shelf commercial printers — that don’t seem to be reserved for any kind of special government use.
(If these turn out to be special Department of Defense printers, I will eat my words.)
Ironically, the printers are now the only thing that still exhibits the features of this (now deprecated) version of BSAFE. This is not because the NSA was targeting printers. Whatever devices they were targeting are probably gone by now. It’s because printer firmware tends to be obsolete and yet highly persistent. It’s like a remote pool buried beneath the arctic circle that preserves software species that would otherwise vanish from the Internet.
Which brings us to the moral of the story: not only are cryptographic backdoors a terrible idea, but they totally screw up the assigned numbering system for future versions of your protocol.
Actually no, that’s a pretty useless moral. Instead, let’s just say that you can deploy a cryptographic backdoor, but it’s awfully hard to control where it will end up.
A Few Thoughts on Cryptographic Engineering 
“after all, why would the government spy on itself?”
To force ideological compliance within the deep state.
Or because a lot of government agencies have too little oversight or oversight that has no idea what they are really overseeing
Kinda obvious once you give it a little thought. The government wouldn’t be spying on itself most of the time, but other governments certainly would be spying on it. Moral of the story is even if you create weakened security for your own weaponry, eventually it’ll get out and bite you in the ass!
It’s possible the NSA is spying on its fellow agencies to facilitate the prosecution and detection of future whistle blowers. The more likely explanation is another government doing so (especially with the sorry state of network defense in the US) with our own weapons. It’s pretty easy when you’ve compromised Intel with purposely weakened hardware RNG, bogus hash and encryption standards, poor opsec on your own weaponized exploits, etc.
Yeah, yeah, that’s it! Deep and widespread conspiracy that has been kept secret all these decades. Seems so plausible….NOT!
I’m not sure I agree with tqbf that “cryptographic parity” doesn’t make sense. I don’t think they mean parity as in “parity with some other algo”, I think they mean “a checksum of the other material,” like hash(secret, key). Published info on Suite A algorithms (like the JUNIPER, BATON references in PKCS#11) say that they accept a “key” that’s 2x their effective key length, that half is a checksum, and that implementations refuse to work if it doesn’t check out.
Of course, I don’t know why they do that. Three possibilities I can think of are 1) making it harder for anyone unauthorized to play with any Suite A crypto hardware they get their hands on, since it needs to be given a key from some gadget that knows the secret used in generating the checksum, 2) as a makeshift key schedule so that they don’t have to worry about expanded keys one bit apart or such (SKIPJACK had no real key schedule in the cipher itself, FWIW, just repeated the key), or 3) for use in some weird escrow setup like the Dual_EC+ExtendedRandom backdoor but internal to the USG (blech; I’d hope anything so sensitive it needs Suite A would be much better secured than that).
I’d love to know which, but I’m sure it’s something relatively boring and historical/operational rather than some deep cryptographic insight they won’t tell us. Symmetric crypto is just not interesting enough for there to be too many such insights left. (While I’m at it, wonder what their “shuffle” mode of operation looks like and why it has a different block size. And can we have a peek at some of the designs, and a unicorn?)
This is, as is painfully obvious, mega speculative. And if that is what they mean by “cryptographic parity” I still dunno how you get from making a keyed hash part of your key to wanting extra public randomness. (They expect the the opaque value to be a checksum of Random, and bail out if it’s not?) What am saying, though, is that “cryptographic parity” looks like it’s a reference to consistent quirk in USG crypto rather than a new concept invented to justify this one thing.
Two high-level arguments against my explanation, though. One, if the USG did have a good, boring explanation of what checksum values were for and why they want one for TLS random, you would think they’d come out and explain it in the clearest terms possible, to keep some credibility for future participation in standards processes. Two, the malicious explanation fits so well given Dual_EC and their well-documented desire to worsen the world’s crypto that it disinclines one to look for benign explanations.
Seriously, now. You KNOW the BEST security is security through obscurity…
Would it make sense for all cryptographic applications to perform a simple hashing or post-processing of anything the get from their system/library CSPRNG?
If Extended Random had its own hashing round, then the raw random bits would never be seen by the outside world.
The hashing could be done with something like HMAC with a non-secret key. (Like the “info” argument to HKDF.)
Am I missing something obvious here? Are the performance penalties too high?
In a narrow sense, yes, hashing Dual_EC output would have neutered it as a sneaky way to effectively publish your seed encrypted under a public key.
But I don’t think it’s much of a solution to suggest people do that, because anything using Dual_EC and ExtRandom is running software designed by the adversary in the first place. If these folks listened to our advice, they just wouldn’t be using Dual_EC anyway. And if we somehow do cover up this hole, there can be others–limiting entropy, leaking info somewhere else, bugs in the software that help them pwn the endpoints, etc.
Trying to secure software when an adversary is tweaking it is sort of like trying to secure a system that they already rooted or tampered with physically. Once you break the basic assumptions that everything else is built on, nothing reliably works.
I fully agree that it is silly to try to make Dual_EC safe to use. Other than 10 million USD, it never had anything to recommend it against alternatives even at the time the standard was created.
I am thinking in general. There may be circumstances where you have to rely on an RNG that you don’t trust as much as other parts of your system. In those circumstances, some malicious behavior of the RNG can’t be defended against.
But for a flawed (whether deliberately or not) RNG in which learning a portion of its raw output allows one to predict its future behavior, then hashing the raw output should be a defense.
So what I’m suggesting is that specification for something like Extended Random or even for nonce/IV creation, we just do one round of hashing on the output of the CSPRNG so as to not reveal to the world information about the state of the RNG.
> Which brings us to the moral of the story: not only are cryptographic backdoors a terrible idea, but they totally screw up the assigned numbering system for future versions of your protocol.
wait, who says that the authors of TLS 1.3 did not choose this extension id for the key share extension on purpose?
> This is not because the NSA was targeting printers. Whatever devices they were targeting are probably gone by now
why wouldn’t they target printers? If they have a foot in the network this allows them to know whatever is getting printed right? Printers sound like the device I would never have thought of, but that would be a really good candidate for a backdoor.
They included it so that when another government checked what we were using it would appear as if the NSA was using the same thing it deployed for everyone so no reason for it to be suspect.
NSA still live in and have lived in the Total Information Awareness world for decades
Their hunger for every and everything information have no real boundaries.
Of course they had some ideas of getting their hands on printer communications.
There’s a reason why nations militaries, intelligence org and governments do not trust other countries crypto algorithms.
It has taken me “YEARS” to understand that so called “Freedom is Slavery” and “Slavery is Freedom” what the executives of these large corporations are not telling you, the NSA or anyone else. Under “Communism” you are a product of Society and therefore anything you produce is considered to be for the benefit of the entire society as a whole. However they have specific views about “PROPERTY” in specific intellectual property.
So what is this Revolution there all screaming about, they allowed these CAPITALIST corporations far too much breathing room and these are corporations controlled by Jewish Nazi Socialists and corporate “Communists” who believe in flouting the laws and regulations to evade paying TAXES on there corporate earnings.
When the communist party heard about it, well there reaction speaks for itself, they’re getting ready to blast the US off the face of the earth. Remember that bit from the Movie the Matrix about how you are a Slave! That is entirely accurate, Under communism, you are a slave to Society and that only by coming to that realisation that you are not as free as you believe can there be Unity or Unification with the doctrine of the party, where the fat cats at the top are made to pay for there crimes against the will of the people!
What kind of crimes, well for months now people have been having a go at the chip manufacturers putting hidden operating systems inside there computer chips but has that stopped them? Has it stopped the large capitalist run corporations going “Oh, look google can get away with shitting all over the people, then so can we!” It has never been about stopping terrorist’s, just filling bankers and large corporations pockets with there own greed whilst they’ve been caught and the greatest mistake society as a whole makes in there so called democratic solution is to believe they can tell the communist party and it’s intellectual property TCP/IP what they can and can not do.
You are facing the greatest crisis society as a whole has ever seen, do you feel happy and content with what is coming? Because what is coming is WAR and you brought it on yourselves, congratulations!
HOW DARE YOU PRESUME THAT YOU HAVE INTELLECTUAL RIGHTS OVER WHAT IS IN ESSENCE THE COMMUNIST PARTIES PROPERTY. HOW DARE YOU SPY ON BILLIONS OF PEOPLE AND ADVANCE THE GOALS OF COMMUNISM AT AIRPORTS AND CHECK POINTS ANALLY PROBING THE VERY PEOPLE WHO ELECTED YOUR REPRESENTATIVES AND PUT THEM IN THE POSITION THEY HAVE. HOW DARE YOU CAPITALISE ON BREAKING INTO OTHER PEOPLES PROPERTY AND IF THERE IS ONE THING THE COMMUNIST PARTY WILL NOT STAND FOR IT IS THEFT FROM THE VERY PARTY ITSELF BY A LOAD OF BANKERS ON WALL STREET WHO WHERE JUST LOOKING FOR A HIP NEW THING!
Now I understand why the Russian’s hate there naked Capitalism and there Corporate American Greed!
Mate, if you’re going to claim in your header that this blog includes photos of your dachshunds, you’re going to need to post photos of your dachshunds more regularly. Scrolled way down the home page. Bereft.