An army of researchers recently published a short study of a weakness that NSA is alleged to have introduced into a public security standard. Joseph Menn of Reuters gave the study lengthy and largely uncritical coverage; here's the gist:
Security industry pioneer RSA adopted not just one but two encryption tools developed by the U.S. National Security Agency, greatly increasing the spy agency's ability to eavesdrop on some Internet communications, according to a team of academic researchers. Reuters reported in December that the NSA had paid RSA $10 million to make a now-discredited cryptography system the default in software used by a wide range of Internet and computer security programs. The system, called Dual Elliptic Curve, was a random number generator, but it had a deliberate flaw - or "back door" - that allowed the NSA to crack the encryption. A group of professors from Johns Hopkins, the University of Wisconsin, the University of Illinois and elsewhere now say they have discovered that a second NSA tool exacerbated the RSA software's vulnerability.
The allegation that NSA weakened the dual elliptic curve random number generator has been floating around for some time, and it has already had some policy impact. The President’s Review Group was reacting to the story when it declared that the US Government should "fully support and not undermine efforts to create encryption standards [and] not in any way subvert, undermine, weaken, or make vulnerable generally available commercial software."
A careful reading of the actual study, though, suggests that there’s been more than a little hype in the claim that NSA has somehow made us all less safe by breaking internet security standards. I recognize that this is a technical paper, and that I’m not a cryptographer. So I welcome technical commentary and corrections.
With that disclaimer, however, it seems to me that the paper makes two points that take a lot of the air out of the "NSA wrecks internet security" balloon:
1. If there’s a backdoor in the standard, no one has found it.
It’s an article of faith among academic cryptographers (and something the Reuters article just assumes) that there is a backdoor in the dual elliptic curve standard. In 2007, some Microsoft researchers explained how a backdoor might have been implanted in the standard. Researchers have been looking for ways to exploit the backdoor – and thus prove its existence – ever since. Yet the paper concedes that the researchers can’t confirm the existence of a flaw. Instead, the researchers had to make up a different flawed protocol and show how quickly they could exploit that vulnerability. The artificiality of that exercise probably should have made Reuters a little more skeptical about the study's results, but there's a more important point in the researchers' concession.
Seven years is a lifetime in cryptanalytic attacks, so it’s quite a surprise that no backdoor has been proved in all this time. It raises the possibility that there really is no flaw – or that NSA has introduced a flaw that only NSA can exploit. That’s important because the press and a lot of cryptographers have been saying that NSA weakened internet security for everyone. But if there is no flaw, or if it’s a flaw only NSA can exploit, then at worst internet security has been weakened for adversaries and intelligence targets of the United States.
Call me old-fashioned, but that sounds like a good thing to me. Of course, academic cryptographers may still argue that it's not, but only by flirting with a moral relativism that most Americans don’t share.
2. If there’s a backdoor in the standard, it’s had no discernible effect on internet security.
Talk about burying the lede. After measuring how fast their fake standard’s contrived flaw could be exploited, the researchers decided to go looking for examples of the flawed elliptic curve standard in the wild. What they found seems to cast doubt on the news value of the whole flap.
It turns out that you can scan more or less every public-facing server on the internet in less than an hour. A company called Zmap will do it for you for free. The researchers used ZMap, and they found a total of 21.8 million servers offering secure http connections of the sort that the controversial elliptic curve standard is accused of subverting. And how many of those 21.8 million servers were clearly using the controversial standard?
Let me say that again. 720 out of 21,800,000 secure servers used the standard that is accused without conclusive proof of weakening security on the internet.
In a fit of understatement. the researchers note that this is “much less than 1%.” Well, yes. In fact, it is less than one percent in the same way that the weight of your cat is less than that of a bull African elephant – three orders of magnitude less.
Put another way, only .0003% of the secure servers on the internet were identified as running code that is subject to the famous flaw, if it is a flaw. And it’s likely that the vast majority of those servers are of no interest to the United States government, so the backdoor would never be used for them. If you assume that NSA has a real interest in maybe 1% of internet traffic, that’s 72 servers on the internet whose security might be put at risk by the standard -- and then only if they harbor information of intelligence interest to the United States government.
Big whoop. That's not even table stakes in the world of computer security.
When other researchers went looking for devices on the internet that were open to attack because of flawed plug and play protocols, they found 40 or 50 million online devices with the security flaw, a flaw that some manufacturers have simply refused to fix. And there are between 300 and 500 million computers running Windows XP that will get their last security updates from Microsoft this weekend; after that, it's open season on those machines.
So when it comes to weakening internet security, there are a lot of people and companies that are way, way ahead of NSA. Though you wouldn't know it from the credulous press coverage given to academic cryptographers' attack on the elliptic curve number generator.
Academic cryptographers have seen NSA as their adversary for fifty years, and press coverage so far has simply treated their worst assumptions about the agency as received truth. Despite that, the academic cryptographers' campaign against NSA's role in standards has not attracted widespread public support or serious legislative proposals. Nor did the Obama expert’s group recommendation gain much traction inside the administration.
If I’m right about the two lessons to be learned from this academic paper, that is just about the right response.
Notes: When I did my calculations, I didn’t count SChannel servers, which account for 12% of secure servers. That’s because the researchers admit that, while the controversial protocol is an option in SChannel, it is not the default. Similarly, ZMap could only identify servers running the Java version of the controversial protocol, not the C++ version. But even assuming that there are twice as many, or ten times as many, C++ implementations as Java implementations, the possible flaw in the protocol is dwarfed in its impact by many known security flaws that no one seems to be especially exercised about – suggesting that the flap over NSA’s role in the standard grows out of an agenda other than security.
UPDATE: Dropped an erroneous zero from my percentage calculation. There's no greater honor than having Dorothy Denning correct your math.
Hello Mr. Baker- First, there is no such thing as "a flaw only NSA can exploit." That doesn't make sense, because a flaw can be exploited by anyone who discovers it, or has downloaded code written by someone else who did. Second, you say that "it’s quite a surprise that no backdoor has been proved." If a backdoor was "proved," that would be the end of that backdoor. Computer security is concerned with backdoors that have been discovered by black hats, but not white hats. Once a backdoor is found, the software is fixed and the backdoor is closed.
Backdoors introduced by anyone, including the NSA, can be used by black hats (bad guys) to do bad guy stuff.
Posted by: LinuxFan2718 | Apr 04, 2014 at 06:29 AM
Thank you for this thought-provoking article.
I think the article you cite does not quantify the number of potentially backdoored servers well at all; it could be 720, or 720 + 12%, or any larger number. Certainly the media has exaggerated the threat, as they always do.
Zmap is not a company that scans servers. It is a program you can download and run on your own system to scan the Internet. And only if you have a very fast Internet connection (gigabit) can it do so in an hour.
Posted by: Sambowne | Apr 04, 2014 at 04:19 PM
The reason it is a flaw that only the NSA can exploit, is because the alleged flaw in the protocol requires knowledge of two secret parameters that are used to generate a number built into the protocol.
If someone has knowledge of these two secret parameters - according to the 2007 paper by Microsoft research - the NSA would be able to quickly predict the numbers outputted by Dual_EC_DRBG. Without knowledge of the secret parameters, Dual_EC_DRBG is a fairly safe algorithm to use for key generation.
So that tells us that if the NSA kept hold of these two secret parameters, they can break it easily - but a better question is can someone who ISN'T the NSA find out what the secret numbers are to break it easily?
The answer here is a categorical no: using the power of math we can show that deducing the secret parameters given the public number in Dual_EC_DRBG is equal to a problem called the Discrete Log Problem - a provably hard problem to solve. In fact, if you can find a fast algorithm to find the secret numbers in Dual_EC_DRBG, that same algorithm will find you Gmail's private key equally fast (because Gmail uses Elliptic Curve Cryptography, which is based on the same hard problem).
This is why this is a flaw "only the NSA can exploit". If the NSA kept a hold of those secret parameters, they can break Dual_EC_DRBG. But if you're not the NSA, you need to solve the Discrete Log Problem on the public number in Dual_EC_DRBG to get the secret parameters to break it, a problem equally hard as breaking Gmail's private key.
Posted by: Pwnallthethings | Apr 06, 2014 at 06:34 PM