How a Crypto ‘Backdoor’ Pitted the Tech World Against the NSA
Illustration: alengo/Getty Images
In August 2007, a young programmer in Microsoft’s Windows security group
stood up to give a five-minute turbo talk at the annual Crypto
conference in Santa Barbara.
It was a Tuesday evening, part of the conference’s traditional rump
session, when a hodge-podge of short talks are presented outside of the
conference’s main lineup. To draw attendees away from the wine and beer
that competed for their attention at that hour, presenters sometimes
tried to sex up their talks with provocative titles like “Does Bob Go to
Prison?” or “How to Steal Cars – A Practical Attack on KeeLoq” or “The
Only Rump Session Talk With Pamela Anderson.”
Dan Shumow and his Microsoft colleague Niels Ferguson titled theirs,
provocatively, “On the Possibility of a Back Door in the NIST SP800-90
Dual Ec Prng.” It was a title only a crypto geek would love or get.
The talk was
only nine slides long
(.pdf). But those nine slides were potentially dynamite. They laid out a
case showing that a new encryption standard, given a stamp of approval
by the U.S. government, possessed a glaring weakness that made an
algorithm in it susceptible to cracking. But the weakness they described
wasn’t just an average vulnerability, it had the kind of properties one
would want if one were intentionally inserting a backdoor to make the
algorithm susceptible to cracking by design.
For such a dramatic presentation — by mathematicians’ standards — the
reaction to it was surprisingly muted. “I think folks thought, ‘Well
that’s interesting,’ and, ‘Wow, it looks like maybe there was a flaw in
the design,’” says a senior Microsoft manager who was at the talk. “But
there wasn’t a huge reaction.”
Six years later, that’s all changed.
Early this month the
New York Times drew a connection
between their talk and memos leaked by Edward Snowden, classified Top
Secret, that apparently confirms that the weakness in the standard and
so-called Dual_EC_DRBG algorithm was indeed a backdoor. The
Times
story implies that the backdoor was intentionally put there by the NSA
as part of a $250-million, decade-long covert operation by the agency to
weaken and undermine the integrity of a number of encryption systems
used by millions of people around the world.
The
Times story has kindled a firestorm over the integrity
of the byzantine process that produces security standards. The National
Institute of Standards and Technology, which approved Dual_EC_DRBG and
the standard, is now facing a crisis of confidence, having been forced
to re-open the standard for public discussion, while security and crypto
firms scramble to unravel how deeply the suspect algorithm infiltrated
their code, if at all. On Thursday, corporate giant
RSA Security publicly renounced Dual_EC_DRBG,
while also conceding that its commercial suite of cryptographic
libraries had been using the bad algorithm as its default algorithm for
years.
But beneath the flames, a surprising uncertainty is still smoldering over whether Dual_EC_DRBG really is backdoored. The
Times,
crypto experts note, hasn’t released the memos that purport to prove
the existence of a backdoor, and the paper’s direct quotes from the
classified documents don’t mention any backdoor in the algorithm or
efforts by the NSA to weaken it or the standard. They only discuss
efforts to push the standard through committees for approval.
Jon Callas, the CTO of Silent Circle, whose company offers encrypted
phone communication, delivered a different rump session talk at the
Crypto conference in 2007 and saw the presentation by Shumow. He says he
wasn’t alarmed by it at the time and still has doubts that what was
exposed was actually a backdoor, in part because the algorithm is so
badly done.
“If [NSA] spent $250 million weakening the standard and this is the
best that they could do, then we have nothing to fear from them,” he
says. “Because this was really ham-fisted. When you put on your
conspiratorial hat about what the NSA would be doing, you would expect
something more devious, Machiavellian … and this thing is just laughably
bad. This is Boris and Natasha sort of stuff.”
Indeed, the Microsoft presenters themselves — who declined to comment
for this article — didn’t press the backdoor theory in their talk. They
didn’t mention NSA at all, and went out of their way to avoid accusing
NIST of anything. “WE ARE NOT SAYING: NIST intentionally put a back door
in this PRNG,” read the last slide of their deck.
The Microsoft manager who spoke with WIRED on condition of anonymity
thinks the provocative title of the 2007 presentation overstates the
issue with the algorithm and is being misinterpreted — that perhaps
reporters at the
Times read something in a classified document
showing that the NSA worked on the algorithm and pushed it through the
standards process, and quickly took it as proof that the title of the
2007 talk had been right to call the weakness in the standard and
algorithm a backdoor.
But Paul Kocher,
president and chief scientist of Cryptography Research, says that regardless of the lack of evidence in the
Times story, he discounts the “bad cryptography” explanation for the weakness, in favor of the backdoor one.
“Bad cryptography happens through laziness and ignorance,” he says.
“But in this case, a great deal of effort went into creating this and
choosing a structure that happens to be amenable to attack.
“What’s mathematically creative [with this algorithm] is that when
you look at it, you can’t even prove whether there is a backdoor or not,
which is very bizarre in cryptography,” he says. “Usually the presence
of a backdoor is something you can prove is there, because you can see
it and exploit it…. In my entire career in cryptography, I’ve never seen
a vulnerability like this.”
National Security Agency headquarters, Fort Meade, Maryland. Photo: Wikipedia
It’s not the first time the NSA has been accused of installing
backdoors. Crypto trapdoors, real and imagined, have been part of NSA
lore for decades. In some ways the current controversy echoes the
long-ago debate over the first U.S. Data Encryption Standard in the
1970s. The NSA was widely suspected of weakening DES to make it more
crackable by the agency by tinkering with a table of numeric constants
called an S-Box and shortening the algorithm’s key length. In 1994,
though, the NSA was exonerated when it turned out that the agency had
actually changed the S-Box numbers to harden DES against a code-breaking
technique that had been known only within NSA at the time.
In 1995, another case came up that seemed to confirm suspicions about the NSA. The
Baltimore Sun
reported that year that the NSA had inserted a backdoor into
cryptographic machines made by the respected Swiss company Crypto AG,
apparently substantiating longstanding rumors to that effect.
Then in 1999, Microsoft inadvertently kicked off another controversy
when it leaked its internal name for a cryptographic signing key built
into Windows NT. The key was called _NSAKEY, spawning speculation that
Microsoft had secretly given the agency the power to write and sign its
own updates to Windows NT’s crypto engine. Microsoft said this was
incorrect, that the key was an internal Microsoft key only and that it
was called “_NSAKEY” because the NSA was the technical reviewing
authority for U.S. export controls. The key was part of Microsoft’s
compliance with U.S. export laws.
Suspicions about the NSA and backdoors were lingering in 2006 when
Shumow and Ferguson began looking at Dual_EC_DRBG after NIST approved it
for inclusion in
a standard
(.pdf). The standard discussed four federally sanctioned random number
generators approved for use in encrypting government classified and
unclassified-but-sensitive communication.
Each of the four algorithms was based on a different cryptographic
design family. One was based on hash functions, one on so-called HMAC (
hash-based message authentication code),
one on block ciphers and the fourth one was based on elliptic curves.
The NSA had been pushing elliptic curve cryptography for a number of
years, and it publicly championed the last one — Dual_EC_DRBG — to be
included in the standard.
Elliptic curve algorithms are based on slightly different mathematics than the more common RSA algorithm, and the NSA
believes they’re the future of cryptography, asserting that elliptic curve algorithms are smaller, faster and offer better security.
But as Shumow and Ferguson examined the properties of the elliptic
curve random number generator in the standard, to determine how to
incorporate it into the Windows operating system, a couple of strange
things stood out. First, the random number generator was very slow – two
to three orders of magnitude slower than another algorithm in the
standard.
Second, it didn’t seem to be very secure.
“There was a property [in it] that seemed to make the
prediction-resistance of the algorithm not what you would necessarily
want it to be,” the Microsoft manager says. In non-geek speak, there was
a weakness that made the random number generator not so random.
Good random number generation is at the core of encryption, and a
weak RNG can undo the entire encryption system. Random number generators
play a role in creating cryptographic keys, in opening secure
communications between users and web sites and in resetting passwords
for email accounts. Without assured randomness, an attacker can predict
what the system will generate and undermine the algorithm.
Shumow and Ferguson found that the obstacles to predicting what the
random number generator would generate were low. It wasn’t a
catastrophic problem, but it seemed strange for a security system being
promulgated by the government.
Then they noticed something else.
The standard, which contained guidelines for implementing the
algorithm, included a list of constants – static numbers – that were
used in the elliptic curve on which the random number generator was
based. Whoever generated the constants, which served as a kind of public
key for the algorithm, could have generated a second set of numbers at
the same time – a private key.
Anyone possessing that second set of numbers would have what’s known
in the cryptography community as “trapdoor information” – that is, they
would be able to essentially unlock the encryption algorithm by
predicting what the random number generator generated. And, Shumow and
Ferguson realized, they could predict this after seeing as few as 32
bytes of output from the generator. With a very small sample, they could
crack the entire encryption system used to secure the output.
“Even if no one knows the secret numbers, the fact that the backdoor
is present makes Dual_EC_DRBG very fragile,” cryptographer wrote at the time,
in a piece for WIRED. “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.”
No one knew who had produced the constants, but it was assumed that
because the NSA had pushed the algorithm into the standard, the agency
had generated the numbers. The spy agency might also, then, have
generated a secret key.
Schneier called it “scary stuff indeed,” but he also said at the time
that it made no sense as a backdoor, since it was so obvious to anyone
who looked at the algorithm and standard that there was this flaw in it.
As a result, developers of web sites and software applications wouldn’t
use it to help secure their products and systems, he said.
But in fact, many developers did use it.
The U.S. government has enormous purchasing power, and vendors soon
were forced to implement the suspect standard as a condition of selling
their products to federal agencies under so-called FIPS certification
requirements. Microsoft added support for the standard, including the
elliptic curve random-number generator, in a Vista update in February
2008, though it did not make the problematic generator the default
algorithm.
Asked why Microsoft supported the algorithm when two of its own
employees had shown it to be weakened, a second Microsoft senior manager
who spoke with WIRED said that while the weakness in the algorithm and
standard was “weird” it “wasn’t a smoking gun.” It was more of an “odd
property.”
Microsoft decided to include the algorithm in its operating system
because a major customer was asking for it, because it had been
sanctioned by NIST, and because it wasn’t going to be enabled as the
default algorithm in the system, thus having no impact on other
customers.
“In fact it is nearly impossible for any user to implement or to get
this particular random number generator instantiating on their machines
without going into the guts of the machine and reconfiguring it,” he
says.
Other major companies, like Cisco and RSA, added it as well. NIST in fact provides a
lengthy list of companies that have included it in their libraries,
though the list doesn’t say which companies made it the default
algorithm in their library or which products have been developed that
invoke the algorithm.
A Cisco spokesman told WIRED that the algorithm was implemented in its
standard crypto library around mid-2012, a library that is used in more
than 120 product lines, but the algorithm is not the default, and the
default algorithm cannot be changed by users. The company is currently
completing an internal audit of all of its products that leverage the
NIST standard.
RSA, however, made the algorithm the default in its BShare toolkit
for Java and C developers until this week when it told WIRED that it was
changing the default following the renewed controversy over it. The
company sent an advisory to developer customers “strongly” urging them
to change the default to one of a number of other random number
generator algorithms RSA supports. RSA also changed the default on its
own end in BSafe and in an RSA key management system. The company is
currently doing an internal review of all of its products to see where
the algorithm gets invoked in order to change those.
RSA actually added the algorithm to its libraries in 2004 or 2005,
before NIST approved it for the standard in 2006 and before the
government made it a requirement for FIPS certification, says Sam Curry,
the company’s chief technology officer. The company then made it the
default algorithm in BSafe and in its key management system after the
algorithm was added to the standard. Curry said that elliptic curve
algorithms were all the rage at the time and RSA chose it as the default
because it provided certain advantages over the other random number
generators, including what he says was better security.
“Cryptography is a changing field. Some algorithms go up and some
come down and we make the best decisions we can in any point in time,”
he says.”A lot of the hash-based algorithms were getting struck down by
some weaknesses in how they chose numbers and in fact what kind of
sample set they chose for initial seeding. From our perspective it
looked like elliptic curve would be immune to those things.”
Curry says the fact that the algorithm is slower actually provides it with better security in at least one respect.
“The length of time that you have to gather samples will determine
the strength of your random number generation. So the fact that it’s
slower sometimes gives it a wider sample set to do initial seeding,” he
says. “Precisely because it takes a little longer, it actually winds up
giving you more randomness in your initial seeding, and that can be an
advantage.”
Despite the renewed controversy over the algorithm and standard,
Microsoft managers say they still don’t think the weaknesses constitute
an intentional backdoor.
Callas agrees. He thinks it is simply bad cryptography that was
included in the standard to round-out the selection so that there would
be at least one elliptic curve algorithm in the standard.
But one advantage to having the algorithm supported in products like
Vista — and which may be the reason the NSA pushed it into the standard —
is that even if it’s not the default algorithm for encryption on a
system, as long as it’s an option on the system, an intruder, like the
NSA, can get into the system and change the registry to make it the
default algorithm used for encryption, thereby theoretically making it
easy for the NSA to undermine the encryption and spy on users of the
machine.
Schneier says this is a much more efficient and stealth way of
undermining the encryption than simply installing a keystroke logger or
other Trojan malware that could be detected.
“A Trojan is really, really big. You can’t say that was a mistake.
It’s a massive piece of code collecting keystrokes,” he said. “But
changing a bit-one to a bit-two [in the registry to change the default
random number generator on the machine] is probably going to be
undetected. It is a low conspiracy, highly deniable way of getting a
backdoor. So there’s a benefit to getting it into the library and into
the product.”
To date, the only confirmation that the algorithm has a backdoor comes in the
Times story, based on NSA documents leaked by Edward Snowden, which the
Times and two other media outlets saw.
“[I]nternal memos leaked by a former NSA contractor, Edward Snowden,
suggest that the NSA generated one of the random number generators used
in a 2006 NIST standard — called the Dual EC DRBG standard — which
contains a back door for the NSA,” the
Times wrote.
An editorial published by the
Times this weekend
re-asserted the claim:
“Unbeknown to the many users of the system, a different government arm,
the National Security Agency, secretly inserted a ‘back door’ into the
system that allowed federal spies to crack open any data that was
encoded using its technology.”
But all of the quotes that the
Times published from the
memos refer to the NSA getting the standard passed by an international
standards body; they do not say the NSA intentionally weakened the
algorithm and standard, though the
Times implies that this is what the memos mean by tying them to the 2007 presentation by Shumow and Ferguson.
NIST has denied any knowledge of a backdoor and has also denied that the NSA authored its standard. The institute has, however,
re-opened the standard for public comment
as a result of the controversy and “strongly” urged against using the
algorithm in question until the matter could be resolved. The
public comments period will close Nov. 6.
Even without more explicit confirmation that the weaknesses in the
algorithm and standard constitute a backdoor, Kocher and Schneier
believe they do.
“It is extraordinarily bad cryptography,” says Kocher. “If you look
at the NSA’s role in creating standards [over the years] and its general
cryptographic sophistication, none of it makes sense if there isn’t a
backdoor in this.”
Schneier agrees and says the NSA has done too many other things for
him to think, when he sees government-mandated crypto that’s weak, that
it’s just by accident.
“If we were living in a kinder world, that would be a plausible
explanation,” he says. “But we’re living in a very malicious world, it
turns out.”
He adds that the uncertainty around the algorithm and standard is the worst part of the whole matter.
“This is the worst problem that the NSA has done,” Schneier says.
“They have so undermined the fundamental trust in the internet, that we
don’t know what to trust. We have to suspect everything. We’re never
sure. That’s the greatest damage.”
In the midst of confusion over the NSA's spying powers, even
members of Congress who voted for the applicable laws claim surprise at how
they are playing out in practice. With defenders of spying saying to “read the
statute” to understand its privacy protections, I thought I'd do just that.