How to Sabotage Encryption Software (And Not Get Caught)

  • Andy Greenberg
  • Wired
  • February 27, 2015

In the field of cryptography, a secretly planted “backdoor” that allows eavesdropping on communications is usually a subject of paranoia and dread. But that doesn’t mean cryptographers don’t appreciate the art of skilled cyphersabotage. Now one group of crypto experts has published an appraisal of different methods of weakening crypto systems, and the lesson is that some backdoors are clearly better than others—in stealth, deniability, and even in protecting the victims’ privacy from spies other than the backdoor’s creator.

In a paper titled “Surreptitiously Weakening Cryptographic Systems,” well-known cryptographer and author Bruce Schneier and researchers from the Universities of Wisconsin and Washington take the spy’s view to the problem of crypto design: What kind of built-in backdoor surveillance works best?

Their paper analyzes and rates examples of both intentional and seemingly unintentional flaws built into crypto systems over the last two decades. Their results seem to imply, however grudgingly, that the NSA’s most recent known method of sabotaging encryption may be the best option, both in effective, stealthy surveillance and in preventing collateral damage to the Internet’s security.

“This is a guide to creating better backdoors. But the reason you go through that exercise is so that you can create better backdoor protections,” says Schneier, the author of the recent book Data and Goliath, on corporate and government surveillance. “This is the paper the NSA wrote two decades ago, and the Chinese and the Russians and everyone else. We’re just trying to catch up and understand these priorities.”

The researchers looked at a variety of methods of designing and implementing crypto systems so that they can be exploited by eavesdroppers. The methods ranged from flawed random number generation to leaked secret keys to codebreaking techniques. Then the researchers rated them on variables like undetectability, lack of conspiracy (how much secret dealing it takes to put the backdoor in place), deniability, ease of use, scale, precision and control.

Here’s the full chart of those weaknesses and their potential benefits to spies. (The ratings L, M, and H stand for Low, Medium and High.)

Chart of Weaknesses and Benefits

A bad random number generator, for instance, would be easy to place in software without many individuals’ involvement, and if it were discovered, could be played off as a genuine coding error rather than a purposeful backdoor. As an example of this, the researchers point to an implementation of Debian SSL in 2006 in which two lines of code were commented out, removing a large source of the “entropy” needed to create sufficiently random numbers for the system’s encryption. The researchers acknowledge that crypto sabotage was almost certainly unintentional, the result of a programmer trying to avoid a warning message from a security tool. But the flaw nonetheless required the involvement of only one coder, went undiscovered for two years, and allowed a full break of Debian’s SSL encryption for anyone aware of the bug.

Another, even subtler method of subverting crypto systems that the researchers suggest is what they call “implementation fragility,” which amounts to designing systems so complex and difficult that coders inevitably leave exploitable bugs in the software that uses them. “Many important standards such as IPsec, TLS and others are lamented as being bloated, overly complex, and poorly designed—with responsibility often laid at the public committee-oriented design approach,” the researchers write. “Complexity may simply be a fundamental outcome of design-by-committee, but a saboteur might also attempt to steer the public process towards a fragile design.” That kind of sabotage, if it were found, would be easily disguised as the foibles of a bureaucratic process.

But when it comes to a rating for “control”—the ability to distinguish who will be able to exploit the security weakness you’ve inserted—the researchers label implementation fragility and bad number generation as “low.” Use a bad random number generator or fragile crypto implementation, and any sufficiently skilled cryptanalysts who spot the flaw will be able to spy on your target. “It’s clear that some of these things are disastrous in terms of collateral damage,” says paper co-author University of Wisconsin computer scientist Thomas Ristenpart. “If you have a saboteur leaving vulnerabilities in critical system that can be exploited by anyone, then this is just disastrous for the security of consumers.”

In fact that low “control” rating applies to every other method they considered except one: what the researchers call “backdoor constants,” which they rate as “high.” A backdoor constant is one that can only be exploited by someone who knows certain unguessable values. A prime example of that type of backdoor is the random-number generator standard Dual_EC_DRBG, used by crypto firm RSA and revealed in leaks by Edward Snowden in 2013 to have been sabotaged by the NSA.

Dual_EC’s backdoor required the snooper to know a very specific piece of information: the mathematical relationship between two positions on an elliptic curve built into the standard. Anyone with that knowledge would be able to generate the seed value for its random number generator and thus the random values needed to decrypt messages. But without that information the backdoor would be useless, even if you knew that it existed.

That sort of “backdoor constant” trick can be hard to spot, which is why the paper gives it a “high” score in undetectability. Though cryptographers, including Schneier himself, suspected as early as 2007 that Dual_EC might have had a backdoor, no one could prove it—and it remained in use—until Snowden’s revelations. Once discovered, on the other hand, that sort of backdoor is nearly impossible to explain away, so it gets low marks for deniability. But given that a backdoor like Dual_EC creates the least potential for collateral damage of any method named in the study, Schneier describes the technique as “close to ideal.”

That’s not to say the cryptographers like it. Encryption, after all, is meant to create privacy between two people, not two people and the creator of a perfectly designed, secure backdoor. “This is still a problem for people who are potentially victimized by the NSA itself,” says University of Wisconsin researcher and paper co-author Matthew Fredrikson.

In fact, Schneier attributes Dual_EC’s discretion not to the NSA’s care for internet users’ security, but rather its focus on stealth. “Collateral damage is noisy, and it makes you more likely to be discovered,” he says. “It’s a self-serving criterion, not an issue of ‘mankind is better off this way.'”

Schneier says the goal of the researchers’ paper, after all, isn’t to improve backdoors in crypto. It’s to better understand them so that they can be eradicated. “Certainly there are ways to do this that are better and worse,” he says. “The most secure way is not to do it at all.”

Here’s the full paper:

Surreptitiously Weakening Cryptographic Systems

Categories: Articles, Text

Sidebar photo of Bruce Schneier by Joe MacInnis.