Entries Tagged "encryption"

Page 33 of 56

Ed Felten on the NSA Disclosures

Ed Felten has an excellent essay on the damage caused by the NSA secretly breaking the security of Internet systems:

In security, the worst case—the thing you most want to avoid—is thinking you are secure when you’re not. And that’s exactly what the NSA seems to be trying to perpetuate.

Suppose you’re driving a car that has no brakes. If you know you have no brakes, then you can drive very slowly, or just get out and walk. What is deadly is thinking you have the ability to stop, until you stomp on the brake pedal and nothing happens. It’s the same way with security: if you know your communications aren’t secure, you can be careful about what you say; but if you think mistakenly that you’re safe, you’re sure to get in trouble.

So the problem is not (only) that we’re unsafe. It’s that “the N.S.A. wants to keep it that way.” The NSA wants to make sure we remain vulnerable.

Posted on September 12, 2013 at 6:05 AM • View Comments

The NSA's Cryptographic Capabilities

The latest Snowden document is the US intelligence “black budget.” There’s a lot of information in the few pages the Washington Post decided to publish, including an introduction by Director of National Intelligence James Clapper. In it, he drops a tantalizing hint: “Also, we are investing in groundbreaking cryptanalytic capabilities to defeat adversarial cryptography and exploit internet traffic.”

Honestly, I’m skeptical. Whatever the NSA has up its top-secret sleeves, the mathematics of cryptography will still be the most secure part of any encryption system. I worry a lot more about poorly designed cryptographic products, software bugs, bad passwords, companies that collaborate with the NSA to leak all or part of the keys, and insecure computers and networks. Those are where the real vulnerabilities are, and where the NSA spends the bulk of its efforts.

This isn’t the first time we’ve heard this rumor. In a WIRED article last year, longtime NSA-watcher James Bamford wrote:

According to another top official also involved with the program, the NSA made an enormous breakthrough several years ago in its ability to cryptanalyze, or break, unfathomably complex encryption systems employed by not only governments around the world but also many average computer users in the US.

We have no further information from Clapper, Snowden, or this other source of Bamford’s. But we can speculate.

Perhaps the NSA has some new mathematics that breaks one or more of the popular encryption algorithms: AES, Twofish, Serpent, triple-DES, Serpent. It wouldn’t be the first time this happened. Back in the 1970s, the NSA knew of a cryptanalytic technique called “differential cryptanalysis” that was unknown in the academic world. That technique broke a variety of other academic and commercial algorithms that we all thought secure. We learned better in the early 1990s, and now design algorithms to be resistant to that technique.

It’s very probable that the NSA has newer techniques that remain undiscovered in academia. Even so, such techniques are unlikely to result in a practical attack that can break actual encrypted plaintext.

The naive way to break an encryption algorithm is to brute-force the key. The complexity of that attack is 2n, where n is the key length. All cryptanalytic attacks can be viewed as shortcuts to that method. And since the efficacy of a brute-force attack is a direct function of key length, these attacks effectively shorten the key. So if, for example, the best attack against DES has a complexity of 239, that effectively shortens DES’s 56-bit key by 17 bits.

That’s a really good attack, by the way.

Right now the upper practical limit on brute force is somewhere under 80 bits. However, using that as a guide gives us some indication as to how good an attack has to be to break any of the modern algorithms. These days, encryption algorithms have, at a minimum, 128-bit keys. That means any NSA cryptanalytic breakthrough has to reduce the effective key length by at least 48 bits in order to be practical.

There’s more, though. That DES attack requires an impractical 70 terabytes of known plaintext encrypted with the key we’re trying to break. Other mathematical attacks require similar amounts of data. In order to be effective in decrypting actual operational traffic, the NSA needs an attack that can be executed with the known plaintext in a common MS-Word header: much, much less.

So while the NSA certainly has symmetric cryptanalysis capabilities that we in the academic world do not, converting that into practical attacks on the sorts of data it is likely to encounter seems so impossible as to be fanciful.

More likely is that the NSA has some mathematical breakthrough that affects one or more public-key algorithms. There are a lot of mathematical tricks involved in public-key cryptanalysis, and absolutely no theory that provides any limits on how powerful those tricks can be.

Breakthroughs in factoring have occurred regularly over the past several decades, allowing us to break ever-larger public keys. Much of the public-key cryptography we use today involves elliptic curves, something that is even more ripe for mathematical breakthroughs. It is not unreasonable to assume that the NSA has some techniques in this area that we in the academic world do not. Certainly the fact that the NSA is pushing elliptic-curve cryptography is some indication that it can break them more easily.

If we think that’s the case, the fix is easy: increase the key lengths.

Assuming the hypothetical NSA breakthroughs don’t totally break public-cryptography—and that’s a very reasonable assumption—it’s pretty easy to stay a few steps ahead of the NSA by using ever-longer keys. We’re already trying to phase out 1024-bit RSA keys in favor of 2048-bit keys. Perhaps we need to jump even further ahead and consider 3072-bit keys. And maybe we should be even more paranoid about elliptic curves and use key lengths above 500 bits.

One last blue-sky possibility: a quantum computer. Quantum computers are still toys in the academic world, but have the theoretical ability to quickly break common public-key algorithms—regardless of key length—and to effectively halve the key length of any symmetric algorithm. I think it extraordinarily unlikely that the NSA has built a quantum computer capable of performing the magnitude of calculation necessary to do this, but it’s possible. The defense is easy, if annoying: stick with symmetric cryptography based on shared secrets, and use 256-bit keys.

There’s a saying inside the NSA: “Cryptanalysis always gets better. It never gets worse.” It’s naive to assume that, in 2013, we have discovered all the mathematical breakthroughs in cryptography that can ever be discovered. There’s a lot more out there, and there will be for centuries.

And the NSA is in a privileged position: It can make use of everything discovered and openly published by the academic world, as well as everything discovered by it in secret.

The NSA has a lot of people thinking about this problem full-time. According to the black budget summary, 35,000 people and $11 billion annually are part of the Department of Defense-wide Consolidated Cryptologic Program. Of that, 4 percent—or $440 million—goes to “Research and Technology.”

That’s an enormous amount of money; probably more than everyone else on the planet spends on cryptography research put together. I’m sure that results in a lot of interesting—and occasionally groundbreaking—cryptanalytic research results, maybe some of it even practical.

Still, I trust the mathematics.

This essay originally appeared on Wired.com.

EDITED TO ADD: That was written before I could talk about this.

EDITED TO ADD: The Economist expresses a similar sentiment.

Posted on September 6, 2013 at 6:30 AM • View Comments

The NSA Is Breaking Most Encryption on the Internet

The new Snowden revelations are explosive. Basically, the NSA is able to decrypt most of the Internet. They’re doing it primarily by cheating, not by mathematics.

It’s joint reporting between the Guardian, the New York Times, and ProPublica.

I have been working with Glenn Greenwald on the Snowden documents, and I have seen a lot of them. These are my two essays on today’s revelations.

Remember this: The math is good, but math has no agency. Code has agency, and the code has been subverted.

EDITED TO ADD (9/6): Someone somewhere commented that the NSA’s “groundbreaking cryptanalytic capabilities” could include a practical attack on RC4. I don’t know one way or the other, but that’s a good speculation.

EDITED TO ADD (9/6): Relevant Slashdot and Reddit threads.

EDITED TO ADD (9/13): An opposing view to my call to action.

Posted on September 5, 2013 at 2:46 PM • View Comments

Detaining David Miranda

Last Sunday, David Miranda was detained while changing planes at London Heathrow Airport by British authorities for nine hours under a controversial British law—the maximum time allowable without making an arrest. There has been much made of the fact that he’s the partner of Glenn Greenwald, the Guardian reporter whom Edward Snowden trusted with many of his NSA documents and the most prolific reporter of the surveillance abuses disclosed in those documents. There’s less discussion of what I feel was the real reason for Miranda’s detention. He was ferrying documents between Greenwald and Laura Poitras, a filmmaker and his co-reporter on Snowden and his information. These document were on several USB memory sticks he had with him. He had already carried documents from Greenwald in Rio de Janeiro to Poitras in Berlin, and was on his way back with different documents when he was detained.

The memory sticks were encrypted, of course, and Miranda did not know the key. This didn’t stop the British authorities from repeatedly asking for the key, and from confiscating the memory sticks along with his other electronics.

The incident prompted a major outcry in the UK. The UK’s Terrorist Act has always been controversial, and this clear misuse—it was intended to give authorities the right to detain and question suspected terrorists—is prompting new calls for its review. Certainly the UK. police will be more reluctant to misuse the law again in this manner.

I have to admit this story has me puzzled. Why would the British do something like this? What did they hope to gain, and why did they think it worth the cost? And—of course—were the British acting on their own under the Official Secrets Act, or were they acting on behalf of the United States? (My initial assumption was that they were acting on behalf of the US, but after the bizarre story of the British GCHQ demanding the destruction of Guardian computers last month, I’m not sure anymore.)

We do know the British were waiting for Miranda. It’s reasonable to assume they knew his itinerary, and had good reason to suspect that he was ferrying documents back and forth between Greenwald and Poitras. These documents could be source documents provided by Snowden, new documents that the two were working on either separately or together, or both. That being said, it’s inconceivable that the memory sticks would contain the only copies of these documents. Poitras retained copies of everything she gave Miranda. So the British authorities couldn’t possibly destroy the documents; the best they could hope for is that they would be able to read them.

Is it truly possible that the NSA doesn’t already know what Snowden has? They claim they don’t, but after Snowden’s name became public, the NSA would have conducted the mother of all audits. It would try to figure out what computer systems Snowden had access to, and therefore what documents he could have accessed. Hopefully, the audit information would give more detail, such as which documents he downloaded. I have a hard time believing that its internal auditing systems would be so bad that it wouldn’t be able to discover this.

So if the NSA knows what Snowden has, or what he could have, then the most it could learn from the USB sticks is what Greenwald and Poitras are currently working on, or thinking about working on. But presumably the things the two of them are working on are the things they’re going to publish next. Did the intelligence agencies really do all this simply for a few weeks’ heads-up on what was coming? Given how ham-handedly the NSA has handled PR as each document was exposed, it seems implausible that it wanted advance knowledge so it could work on a response. It’s been two months since the first Snowden revelation, and it still doesn’t have a decent PR story.

Furthermore, the UK authorities must have known that the data would be encrypted. Greenwald might have been a crypto newbie at the start of the Snowden affair, but Poitras is known to be good at security. The two have been communicating securely by e-mail when they do communicate. Maybe the UK authorities thought there was a good chance that one of them would make a security mistake, or that Miranda would be carrying paper documents.

Another possibility is that this was just intimidation. If so, it’s misguided. Anyone who regularly reads Greenwald could have told them that he would not have been intimidated—and, in fact, he expressed the exact opposite sentiment—and anyone who follows Poitras knows that she is even more strident in her views. Going after the loved ones of state enemies is a typically thuggish tactic, but it’s not a very good one in this case. The Snowden documents will get released. There’s no way to put this cat back in the bag, not even by killing the principal players.

It could possibly have been intended to intimidate others who are helping Greenwald and Poitras, or the Guardian and its advertisers. This will have some effect. Lavabit, Silent Circle, and now Groklaw have all been successfully intimidated. Certainly others have as well. But public opinion is shifting against the intelligence community. I don’t think it will intimidate future whistleblowers. If the treatment of Chelsea Manning didn’t discourage them, nothing will.

This leaves one last possible explanation—those in power were angry and impulsively acted on that anger. They’re lashing out: sending a message and demonstrating that they’re not to be messed with—that the normal rules of polite conduct don’t apply to people who screw with them. That’s probably the scariest explanation of all. Both the US and UK intelligence apparatuses have enormous money and power, and they have already demonstrated that they are willing to ignore their own laws. Once they start wielding that power unthinkingly, it could get really bad for everyone.

And it’s not going to be good for them, either. They seem to want Snowden so badly that that they’ll burn the world down to get him. But every time they act impulsively aggressive—convincing the governments of Portugal and France to block the plane carrying the Bolivian president because they thought Snowden was on it is another example—they lose a small amount of moral authority around the world, and some ability to act in the same way again. The more pressure Snowden feels, the more likely he is to give up on releasing the documents slowly and responsibly, and publish all of them at once—the same way that WikiLeaks published the US State Department cables.

Just this week, the Wall Street Journal reported on some new NSA secret programs that are spying on Americans. It got the information from “interviews with current and former intelligence and government officials and people from companies that help build or operate the systems, or provide data,” not from Snowden. This is only the beginning. The media will not be intimidated. I will not be intimidated. But it scares me that the NSA is so blind that it doesn’t see it.

This essay previously appeared on TheAtlantic.com.

EDITED TO ADD: I’ve been thinking about it, and there’s a good chance that the NSA doesn’t know what Snowden has. He was a sysadmin. He had access. Most of the audits and controls protect against normal users; someone with root access is going to be able to bypass a lot of them. And he had the technical chops to cover his tracks when he couldn’t just evade the auditing systems.

The AP makes an excellent point about this:

The disclosure undermines the Obama administration’s assurances to Congress and the public that the NSA surveillance programs can’t be abused because its spying systems are so aggressively monitored and audited for oversight purposes: If Snowden could defeat the NSA’s own tripwires and internal burglar alarms, how many other employees or contractors could do the same?

And, to be clear, I didn’t mean to say that intimidation wasn’t the government’s motive. I believe it was, and that it was poorly thought out intimidation: lashing out in anger, rather than from some Machiavellian strategy. (Here’s a similar view.) If they wanted Miranda’s electronics, they could have confiscated them and sent him on his way in fifteen minutes. Holding him for nine hours—the absolute maximum they could under the current law—was intimidation.

I am reminded of the phone call the Guardian received from British government. The exact quote reported was: “You’ve had your fun. Now we want the stuff back.” That’s something you would tell your child. And that’s the power dynamic that’s going on here.

EDITED TO ADD (8/27): Jay Rosen has an excellent essay on this.

EDITED TO ADD (9/12): Other editors react.

Posted on August 27, 2013 at 6:39 AM • View Comments

Measuring Entropy and its Applications to Encryption

There have been a bunch of articles about an information theory paper with vaguely sensational headlines like “Encryption is less secure than we thought” and “Research shakes crypto foundations.” It’s actually not that bad.

Basically, the researchers argue that the traditional measurement of Shannon entropy isn’t the right model to use for cryptography, and that minimum entropy is. This difference may make some ciphertexts easier to decrypt, but not in ways that have practical implications in the general case. It’s the same thinking that leads us to guess passwords from a dictionary rather than randomly—because we know that humans both created the passwords and have to remember them.

This isn’t news—lots of cryptography papers make use of minimum entropy instead of Shannon entropy already—and it’s hard to see what the contribution of this paper is. Note that the paper was presented at an information theory conference, and not a cryptography conference. My guess is that there wasn’t enough crypto expertise on the program committee to reject the paper.

So don’t worry; cryptographic algorithms aren’t going to come crumbling down anytime soon. Well, they might—but not because of this result.

Slashdot thread.

Posted on August 21, 2013 at 7:01 AM • View Comments

The Cryptopocalypse

There was a presentation at Black Hat last month warning us of a “factoring cryptopocalypse”: a moment when factoring numbers and solving the discrete log problem become easy, and both RSA and DH break. This presentation was provocative, and has generated a lot of commentary, but I don’t see any reason to worry.

Yes, breaking modern public-key cryptosystems has gotten easier over the years. This has been true for a few decades now. Back in 1999, I wrote this about factoring:

Factoring has been getting easier. It’s been getting easier faster than anyone has anticipated. I see four reasons why this is so:

  • Computers are getting faster.
  • Computers are better networked.
  • The factoring algorithms are getting more efficient.
  • Fundamental advances in mathematics are giving us better factoring algorithms.

I could have said the same thing about the discrete log problem. And, in fact, advances in solving one problem tend to mirror advances in solving the other.

The reasons are arrayed in order of unpredictability. The first two—advances in computing and networking speed—basically follow Moore’s Law (and others), year after year. The third comes in regularly, but in fits and starts: a 2x improvement here, a 10x improvement there. It’s the fourth that’s the big worry. Fundamental mathematical advances only come once in a while, but when they do come, the effects can be huge. If factoring ever becomes “easy” such that RSA is no longer a viable cryptographic algorithm, it will be because of this sort of advance.

The authors base their current warning on some recent fundamental advances in solving the discrete log problem, but the work doesn’t generalize to the types of numbers used for cryptography. And they’re not going to generalize; the result is simply specialized.

This isn’t to say that solving these problems won’t continue to get easier, but so far it has been trivially easy to increase key lengths to stay ahead of the advances. I expect this to remain true for the foreseeable future.

Posted on August 19, 2013 at 6:47 AM • View Comments

Protecting E-Mail from Eavesdropping

In the wake of the Snowden NSA documents, reporters have been asking me whether encryption can solve the problem. Leaving aside the fact that much of what the NSA is collecting can’t be encrypted by the user—telephone metadata, e-mail headers, phone calling records, e-mail you’re reading from a phone or tablet or cloud provider, anything you post on Facebook—it’s hard to give good advice.

In theory, an e-mail program will protect you, but the reality is much more complicated.

  • The program has to be vulnerability-free. If there is some back door in the program that bypasses, or weakens, the encryption, it’s not secure. It’s very difficult, almost impossible, to verify that a program is vulnerability-free.
  • The user has to choose a secure password. Luckily, there’s advice on how to do this.
  • The password has to be managed securely. The user can’t store it in a file somewhere. If he’s worried about security for after the FBI has arrested him and searched his house, he shouldn’t write it on a piece of paper, either.
  • Actually, he should understand the threat model he’s operating under. Is it the NSA trying to eavesdrop on everything, or an FBI investigation that specifically targets him—or a targeted attack, like dropping a Trojan on his computer, that bypasses e-mail encryption entirely?

This is simply too much for the poor reporter, who wants an easy-to-transcribe answer.

We’ve known how to send cryptographically secure e-mail since the early 1990s. Twenty years later, we’re still working on the security engineering of e-mail programs. And if the NSA is eavesdropping on encrypted e-mail, and if the FBI is decrypting messages from suspects’ hard drives, they’re both breaking the engineering, not the underlying cryptographic algorithms.

On the other hand, the two adversaries can be very different. The NSA has to process a ginormous amount of traffic. It’s the “drinking from a fire hose” problem; they cannot afford to devote a lot of time to decrypting everything, because they simply don’t have the computing resources. There’s just too much data to collect. In these situations, even a modest level of encryption is enough—until you are specifically targeted. This is why the NSA saves all encrypted data it encounters; it might want to devote cryptanalysis resources to it at some later time.

Posted on July 8, 2013 at 6:43 AM • View Comments

1 … 31 32 33 34 35 … 56

Sidebar photo of Bruce Schneier by Joe MacInnis.