Entries Tagged "QUANTUM"

Page 1 of 2

NSA Plans for a Post-Quantum World

Quantum computing is a novel way to build computers—one that takes advantage of the quantum properties of particles to perform operations on data in a very different way than traditional computers. In some cases, the algorithm speedups are extraordinary.

Specifically, a quantum computer using something called Shor’s algorithm can efficiently factor numbers, breaking RSA. A variant can break Diffie-Hellman and other discrete log-based cryptosystems, including those that use elliptic curves. This could potentially render all modern public-key algorithms insecure. Before you panic, note that the largest number to date that has been factored by a quantum computer is 143. So while a practical quantum computer is still science fiction, it’s not stupid science fiction.

(Note that this is completely different from quantum cryptography, which is a way of passing bits between two parties that relies on physical quantum properties for security. The only thing quantum computation and quantum cryptography have to do with each other is their first words. It is also completely different from the NSA’s QUANTUM program, which is its code name for a packet-injection system that works directly in the Internet backbone.)

Practical quantum computation doesn’t mean the end of cryptography. There are lesser-known public-key algorithms such as McEliece and lattice-based algorithms that, while less efficient than the ones we use, are currently secure against a quantum computer. And quantum computation only speeds up a brute-force keysearch by a factor of a square root, so any symmetric algorithm can be made secure against a quantum computer by doubling the key length.

We know from the Snowden documents that the NSA is conducting research on both quantum computation and quantum cryptography. It’s not a lot of money, and few believe that the NSA has made any real advances in theoretical or applied physics in this area. My guess has been that we’ll see a practical quantum computer within 30 to 40 years, but not much sooner than that.

This all means that now is the time to think about what living in a post-quantum world would be like. NIST is doing its part, having hosted a conference on the topic earlier this year. And the NSA announced that it is moving towards quantum-resistant algorithms.

Earlier this week, the NSA’s Information Assurance Directorate updated its list of Suite B cryptographic algorithms. It explicitly talked about the threat of quantum computers:

IAD will initiate a transition to quantum resistant algorithms in the not too distant future. Based on experience in deploying Suite B, we have determined to start planning and communicating early about the upcoming transition to quantum resistant algorithms. Our ultimate goal is to provide cost effective security against a potential quantum computer. We are working with partners across the USG, vendors, and standards bodies to ensure there is a clear plan for getting a new suite of algorithms that are developed in an open and transparent manner that will form the foundation of our next Suite of cryptographic algorithms.

Until this new suite is developed and products are available implementing the quantum resistant suite, we will rely on current algorithms. For those partners and vendors that have not yet made the transition to Suite B elliptic curve algorithms, we recommend not making a significant expenditure to do so at this point but instead to prepare for the upcoming quantum resistant algorithm transition.

Suite B is a family of cryptographic algorithms approved by the NSA. It’s all part of the NSA’s Cryptographic Modernization Program. Traditionally, NSA algorithms were classified and could only be used in specially built hardware modules. Suite B algorithms are public, and can be used in anything. This is not to say that Suite B algorithms are second class, or breakable by the NSA. They’re being used to protect US secrets: “Suite A will be used in applications where Suite B may not be appropriate. Both Suite A and Suite B can be used to protect foreign releasable information, US-Only information, and Sensitive Compartmented Information (SCI).”

The NSA is worried enough about advances in the technology to start transitioning away from algorithms that are vulnerable to a quantum computer. Does this mean that the agency is close to a working prototype in their own classified labs? Unlikely. Does this mean that they envision practical quantum computers sooner than my 30-to-40-year estimate? Certainly.

Unlike most personal and corporate applications, the NSA routinely deals with information it wants kept secret for decades. Even so, we should all follow the NSA’s lead and transition our own systems to quantum-resistant algorithms over the next decade or so—possibly even sooner.

The essay previously appeared on Lawfare.

EDITED TO ADD: The computation that factored 143 also accidentally “factored much larger numbers such as 3599, 11663, and 56153, without the awareness of the authors of that work,” which shows how weird this all is.

EDITED TO ADD: Seems that I need to be clearer: I do not stand by my 30-40-year prediction. The NSA is acting like practical quantum computers will exist long before then, and I am deferring to their expertise.

Posted on August 21, 2015 at 12:36 PM • View Comments

Detecting QUANTUMINSERT

Fox-IT has a blog post (and has published Snort rules) on how to detect man-on-the-side Internet attacks like the NSA’s QUANTUMINSERT.

From a Wired article:

But hidden within another document leaked by Snowden was a slide that provided a few hints about detecting Quantum Insert attacks, which prompted the Fox-IT researchers to test a method that ultimately proved to be successful. They set up a controlled environment and launched a number of Quantum Insert attacks against their own machines to analyze the packets and devise a detection method.

According to the Snowden document, the secret lies in analyzing the first content-carrying packets that come back to a browser in response to its GET request. One of the packets will contain content for the rogue page; the other will be content for the legitimate site sent from a legitimate server. Both packets, however, will have the same sequence number. That, it turns out, is a dead giveaway.

Here’s why: When your browser sends a GET request to pull up a web page, it sends out a packet containing a variety of information, including the source and destination IP address of the browser as well as so-called sequence and acknowledge numbers, or ACK numbers. The responding server sends back a response in the form of a series of packets, each with the same ACK number as well as a sequential number so that the series of packets can be reconstructed by the browser as each packet arrives to render the web page.

But when the NSA or another attacker launches a Quantum Insert attack, the victim’s machine receives duplicate TCP packets with the same sequence number but with a different payload. “The first TCP packet will be the ‘inserted’ one while the other is from the real server, but will be ignored by the [browser],” the researchers note in their blog post. “Of course it could also be the other way around; if the QI failed because it lost the race with the real server response.”

Although it’s possible that in some cases a browser will receive two packets with the same sequence number from a legitimate server, they will still contain the same general content; a Quantum Insert packet, however, will have content with significant differences.

It’s important we develop defenses against these attacks, because everyone is using them.

EDITED TO ADD (5/14): Detection for QI was recently released for Bro, Snort and Suricata.

Posted on May 4, 2015 at 6:17 AM • View Comments

The Further Democratization of QUANTUM

From my book Data and Goliath:

…when I was working with the Guardian on the Snowden documents, the one top-secret program the NSA desperately did not want us to expose was QUANTUM. This is the NSA’s program for what is called packet injection­—basically, a technology that allows the agency to hack into computers. Turns out, though, that the NSA was not alone in its use of this technology. The Chinese government uses packet injection to attack computers. The cyberweapons manufacturer Hacking Team sells packet injection technology to any government willing to pay for it. Criminals use it. And there are hacker tools that give the capability to individuals as well. All of these existed before I wrote about QUANTUM. By using its knowledge to attack others rather than to build up the Internet’s defenses, the NSA has worked to ensure that anyone can use packet injection to hack into computers.

And that’s true. China’s Great Cannon uses QUANTUM. The ability to inject packets into the backbone is a powerful attack technology, and one that is increasingly being used by different attackers.

I continued:

Even when technologies are developed inside the NSA, they don’t remain exclusive for long. Today’s top-secret programs become tomorrow’s PhD theses and the next day’s hacker tools.

I could have continued with “and the next day’s homework assignment,” because Michalis Polychronakis at Stony Book University has just assigned building a rudimentary QUANTUM tool as a homework assignment. It’s basically sniff, regexp match, swap sip/sport/dip/dport/syn/ack, set ack and push flags, and add the payload to create the malicious reply. Shouldn’t take more than a few hours to get it working. Of course, it would take a lot more to make it as sophisticated and robust as what the NSA and China have at their disposal, but the moral is that the tool is now in the hands of anyone who wants it. We need to make the Internet secure against this kind of attack instead of pretending that only the “good guys” can use it effectively.

End-to-end encryption is the solution. Nicholas Weaver wrote:

The only self defense from all of the above is universal encryption. Universal encryption is difficult and expensive, but unfortunately necessary.

Encryption doesn’t just keep our traffic safe from eavesdroppers, it protects us from attack. DNSSEC validation protects DNS from tampering, while SSL armors both email and web traffic.

There are many engineering and logistic difficulties involved in encrypting all traffic on the internet, but its one we must overcome if we are to defend ourselves from the entities that have weaponized the backbone.

Yes.

And this is true in general. We have one network in the world today. Either we build our communications infrastructure for surveillance, or we build it for security. Either everyone gets to spy, or no one gets to spy. That’s our choice, with the Internet, with cell phone networks, with everything.

Posted on April 24, 2015 at 8:55 AM • View Comments

The Democratization of Cyberattack

The thing about infrastructure is that everyone uses it. If it’s secure, it’s secure for everyone. And if it’s insecure, it’s insecure for everyone. This forces some hard policy choices.

When I was working with the Guardian on the Snowden documents, the one top-secret program the NSA desperately did not want us to expose was QUANTUM. This is the NSA’s program for what is called packet injection—basically, a technology that allows the agency to hack into computers.

Turns out, though, that the NSA was not alone in its use of this technology. The Chinese government uses packet injection to attack computers. The cyberweapons manufacturer Hacking Team sells packet injection technology to any government willing to pay for it. Criminals use it. And there are hacker tools that give the capability to individuals as well.

All of these existed before I wrote about QUANTUM. By using its knowledge to attack others rather than to build up the internet’s defenses, the NSA has worked to ensure that anyone can use packet injection to hack into computers.

This isn’t the only example of once-top-secret US government attack capabilities being used against US government interests. StingRay is a particular brand of IMSI catcher, and is used to intercept cell phone calls and metadata. This technology was once the FBI’s secret, but not anymore. There are dozens of these devices scattered around Washington, DC, as well as the rest of the country, run by who-knows-what government or organization. By accepting the vulnerabilities in these devices so the FBI can use them to solve crimes, we necessarily allow foreign governments and criminals to use them against us.

Similarly, vulnerabilities in phone switches—SS7 switches, for those who like jargon—have been long used by the NSA to locate cell phones. This same technology is sold by the US company Verint and the UK company Cobham to third-world governments, and hackers have demonstrated the same capabilities at conferences. An eavesdropping capability that was built into phone switches to enable lawful intercepts was used by still-unidentified unlawful intercepters in Greece between 2004 and 2005.

These are the stories you need to keep in mind when thinking about proposals to ensure that all communications systems can be eavesdropped on by government. Both the FBI’s James Comey and UK Prime Minister David Cameron recently proposed limiting secure cryptography in favor of cryptography they can have access to.

But here’s the problem: technological capabilities cannot distinguish based on morality, nationality, or legality; if the US government is able to use a backdoor in a communications system to spy on its enemies, the Chinese government can use the same backdoor to spy on its dissidents.

Even worse, modern computer technology is inherently democratizing. Today’s NSA secrets become tomorrow’s PhD theses and the next day’s hacker tools. As long as we’re all using the same computers, phones, social networking platforms, and computer networks, a vulnerability that allows us to spy also allows us to be spied upon.

We can’t choose a world where the US gets to spy but China doesn’t, or even a world where governments get to spy and criminals don’t. We need to choose, as a matter of policy, communications systems that are secure for all users, or ones that are vulnerable to all attackers. It’s security or surveillance.

As long as criminals are breaking into corporate networks and stealing our data, as long as totalitarian governments are spying on their citizens, as long as cyberterrorism and cyberwar remain a threat, and as long as the beneficial uses of computer technology outweighs the harmful uses, we have to choose security. Anything else is just too dangerous.

This essay previously appeared on Vice Motherboard.

EDITED TO ADD (3/4): Slashdot thread.

Posted on March 2, 2015 at 6:49 AM • View Comments

FOXACID Operations Manual

A few days ago, I saw this tweet: “Just a reminder that it is now *a full year* since Schneier cited it, and the FOXACID ops manual remains unpublished.” It’s true.

The citation is this:

According to a top-secret operational procedures manual provided by Edward Snowden, an exploit named Validator might be the default, but the NSA has a variety of options. The documentation mentions United Rake, Peddle Cheap, Packet Wrench, and Beach Head-­all delivered from a FOXACID subsystem called Ferret Cannon.

Back when I broke the QUANTUM and FOXACID programs, I talked with the Guardian editors about publishing the manual. In the end, we decided not to, because the information in it wasn’t useful to understanding the story. It’s been a year since I’ve seen it, but I remember it being just what I called it: an operation procedures manual. It talked about what to type into which screens, and how to deal with error conditions. It didn’t talk about capabilities, either technical or operational. I found it interesting, but it was hard to argue that it was necessary in order to understand the story.

It will probably never be published. I lost access to the Snowden documents soon after writing that essay—Greenwald broke with the Guardian, and I have never been invited back by the Intercept—and there’s no one looking at the documents with an eye to writing about the NSA’s technical capabilities and how to securely design systems to protect against government surveillance. Even though we now know that the same capabilities are being used by other governments and cyber criminals, there’s much more interest in stories with political ramifications.

Posted on October 15, 2014 at 6:29 AM • View Comments

The Security of al Qaeda Encryption Software

The web intelligence firm Recorded Future has posted two stories about how al Qaeda is using new encryption software in response to the Snowden disclosures. NPR picked up the story a week later.

Former NSA Chief Council Stewart Baker uses this as evidence that Snowden has harmed America. Glenn Greenwald calls this “CIA talking points” and shows that al Qaeda was using encryption well before Snowden. Both quote me heavily, Baker casting me as somehow disingenuous on this topic.

Baker is conflating my stating of two cryptography truisms. The first is that cryptography is hard, and you’re much better off using well-tested public algorithms than trying to roll your own. The second is that cryptographic implementation is hard, and you’re much better off using well-tested open-source encryption software than you are trying to roll your own. Admittedly, they’re very similar, and sometimes I’m not as precise as I should be when talking to reporters.

This is what I wrote in May:

I think this will help US intelligence efforts. Cryptography is hard, and the odds that a home-brew encryption product is better than a well-studied open-source tool is slight. Last fall, Matt Blaze said to me that he thought that the Snowden documents will usher in a new dark age of cryptography, as people abandon good algorithms and software for snake oil of their own devising. My guess is that this an example of that.

Note the phrase “good algorithms and software.” My intention was to invoke both truisms in the same sentence. That paragraph is true if al Qaeda is rolling their own encryption algorithms, as Recorded Future reported in May. And it remains true if al Qaeda is using algorithms like my own Twofish and rolling their own software, as Recorded Future reported earlier this month. Everything we know about how the NSA breaks cryptography is that they attack the implementations far more successfully than the algorithms.

My guess is that in this case they don’t even bother with the encryption software; they just attack the users’ computers. There’s nothing that screams “hack me” more than using specially designed al Qaeda encryption software. There’s probably a QUANTUMINSERT attack and FOXACID exploit already set on automatic fire.

I don’t want to get into an argument about whether al Qaeda is altering its security in response to the Snowden documents. Its members would be idiots if they did not, but it’s also clear that they were designing their own cryptographic software long before Snowden. My guess is that the smart ones are using public tools like OTR and PGP and the paranoid dumb ones are using their own stuff, and that the split was the same both pre- and post-Snowden.

Posted on August 19, 2014 at 6:11 AM • View Comments

QUANTUM Technology Sold by Cyberweapons Arms Manufacturers

Last October, I broke the story about the NSA’s top secret program to inject packets into the Internet backbone: QUANTUM. Specifically, I wrote about how QUANTUMINSERT injects packets into existing Internet connections to redirect a user to an NSA web server codenamed FOXACID to infect the user’s computer. Since then, we’ve learned a lot more about how QUANTUM works, and general details of many other QUANTUM programs.

These techniques make use of the NSA’s privileged position on the Internet backbone. It has TURMOIL computers directly monitoring the Internet infrastructure at providers in the US and around the world, and a system called TURBINE that allows it to perform real-time packet injection into the backbone. Still, there’s nothing about QUANTUM that anyone else with similar access can’t do. There’s a hacker tool called AirPwn that basically performs a QUANTUMINSERT attack on computers on a wireless network.

A new report from Citizen Lab shows that cyberweapons arms manufacturers are selling this type of technology to governments around the world: the US DoD contractor CloudShield Technologies, Italy’s Hacking Team, and Germany’s and the UK’s Gamma International. These programs intercept web connections to sites like Microsoft and Google—YouTube is specially mentioned—and inject malware into users’ computers.

Turkmenistan paid a Swiss company, Dreamlab Technologies—somehow related to the cyberweapons arms manufacturer Gamma International—just under $1M for this capability. Dreamlab also installed the software in Oman. We don’t know what other countries have this capability, but the companies here routinely sell hacking software to totalitarian countries around the world.

There’s some more information in this Washington Post article, and this essay on the Intercept.

In talking about the NSA’s capabilities, I have repeatedly said that today’s secret NSA programs are tomorrow’s PhD dissertations and the next day’s hacker tools. This is exactly what we’re seeing here. By developing these technologies instead of helping defend against them, the NSA—and GCHQ and CSEC—are contributing to the ongoing insecurity of the Internet.

Related: here is an open letter from Citizen Lab’s Ron Deibert to Hacking Team about the nature of Citizen Lab’s research and the misleading defense of Hacking Team’s products.

Posted on August 18, 2014 at 11:14 AM • View Comments

The NSA is Not Made of Magic

I am regularly asked what is the most surprising thing about the Snowden NSA documents. It’s this: the NSA is not made of magic. Its tools are no different from what we have in our world, it’s just better-funded. X-KEYSCORE is Bro plus memory. FOXACID is Metasploit with a budget. QUANTUM is AirPwn with a seriously privileged position on the backbone. The NSA breaks crypto not with super-secret cryptanalysis, but by using standard hacking tricks such as exploiting weak implementations and default keys. Its TAO implants are straightforward enhancements of attack tools developed by researchers, academics, and hackers; here’s a computer the size of a grain of rice, if you want to make your own such tools. The NSA’s collection and analysis tools are basically what you’d expect if you thought about it for a while.

That, fundamentally, is surprising. If you gave a super-secret Internet exploitation organization $10 billion annually, you’d expect some magic. And my guess is that there is some, around the edges, that has not become public yet. But that we haven’t seen any yet is cause for optimism.

Posted on May 21, 2014 at 3:29 PM • View Comments

The Continuing Public/Private Surveillance Partnership

If you’ve been reading the news recently, you might think that corporate America is doing its best to thwart NSA surveillance.

Google just announced that it is encrypting Gmail when you access it from your computer or phone, and between data centers. Last week, Mark Zuckerberg personally called President Obama to complain about the NSA using Facebook as a means to hack computers, and Facebook’s Chief Security Officer explained to reporters that the attack technique has not worked since last summer. Yahoo, Google, Microsoft, and others are now regularly publishing “transparency reports,” listing approximately how many government data requests the companies have received and complied with.

On the government side, last week the NSA’s General Counsel Rajesh De seemed to have thrown those companies under a bus by stating that—despite their denials—they knew all about the NSA’s collection of data under both the PRISM program and some unnamed “upstream” collections on the communications links.

Yes, it may seem like the public/private surveillance partnership has frayed—but, unfortunately, it is alive and well. The main focus of massive Internet companies and government agencies both still largely align: to keep us all under constant surveillance. When they bicker, it’s mostly role-playing designed to keep us blasé about what’s really going on.

The U.S. intelligence community is still playing word games with us. The NSA collects our data based on four different legal authorities: the Foreign Intelligence Surveillance Act (FISA) of 1978, Executive Order 12333 of 1981 and modified in 2004 and 2008, Section 215 of the Patriot Act of 2001, and Section 702 of the FISA Amendments Act (FAA) of 2008. Be careful when someone from the intelligence community uses the caveat “not under this program” or “not under this authority”; almost certainly it means that whatever it is they’re denying is done under some other program or authority. So when De said that companies knew about NSA collection under Section 702, it doesn’t mean they knew about the other collection programs.

The big Internet companies know of PRISM—although not under that code name—because that’s how the program works; the NSA serves them with FISA orders. Those same companies did not know about any of the other surveillance against their users conducted on the far more permissive EO 12333. Google and Yahoo did not know about MUSCULAR, the NSA’s secret program to eavesdrop on their trunk connections between data centers. Facebook did not know about QUANTUMHAND, the NSA’s secret program to attack Facebook users. And none of the target companies knew that the NSA was harvesting their users’ address books and buddy lists.

These companies are certainly pissed that the publicity surrounding the NSA’s actions is undermining their users’ trust in their services, and they’re losing money because of it. Cisco, IBM, cloud service providers, and others have announced that they’re losing billions, mostly in foreign sales.

These companies are doing their best to convince users that their data is secure. But they’re relying on their users not understanding what real security looks like. IBM’s letter to its clients last week is an excellent example. The letter lists five "simple facts" that it hopes will mollify its customers, but the items are so qualified with caveats that they do the exact opposite to anyone who understands the full extent of NSA surveillance. And IBM’s spending $1.2B on data centers outside the U.S. will only reassure customers who don’t realize that National Security Letters require a company to turn over data, regardless of where in the world it is stored.

Google’s recent actions, and similar actions of many Internet companies, will definitely improve its users’ security against surreptitious government collection programs—both the NSA’s and other governments’—but their assurances deliberately ignores the massive security vulnerability built into its services by design. Google, and by extension, the U.S. government, still has access to your communications on Google’s servers.

Google could change that. It could encrypt your e-mail so only you could decrypt and read it. It could provide for secure voice and video so no one outside the conversations could eavesdrop.

It doesn’t. And neither does Microsoft, Facebook, Yahoo, Apple, or any of the others.

Why not? They don’t partly because they want to keep the ability to eavesdrop on your conversations. Surveillance is still the business model of the Internet, and every one of those companies wants access to your communications and your metadata. Your private thoughts and conversations are the product they sell to their customers. We also have learned that they read your e-mail for their own internal investigations.

But even if this were not true, even if—for example—Google were willing to forgo data mining your e-mail and video conversations in exchange for the marketing advantage it would give it over Microsoft, it still won’t offer you real security. It can’t.

The biggest Internet companies don’t offer real security because the U.S. government won’t permit it.

This isn’t paranoia. We know that the U.S. government ordered the secure e-mail provider Lavabit to turn over its master keys and compromise every one of its users. We know that the U.S. government convinced Microsoft—either through bribery, coercion, threat, or legal compulsion—to make changes in how Skype operates, to make eavesdropping easier.

We don’t know what sort of pressure the U.S. government has put on Google and the others. We don’t know what secret agreements those companies have reached with the NSA. We do know the NSA’s BULLRUN program to subvert Internet cryptography was successful against many common protocols. Did the NSA demand Google’s keys, as it did with Lavabit? Did its Tailored Access Operations group break into to Google’s servers and steal the keys?

We just don’t know.

The best we have are caveat-laden pseudo-assurances. At SXSW earlier this month, CEO Eric Schmidt tried to reassure the audience by saying that he was “pretty sure that information within Google is now safe from any government’s prying eyes.” A more accurate statement might be, “Your data is safe from governments, except for the ways we don’t know about and the ways we cannot tell you about. And, of course, we still have complete access to it all, and can sell it at will to whomever we want.” That’s a lousy marketing pitch, but as long as the NSA is allowed to operate using secret court orders based on secret interpretations of secret law, it’ll never be any different.

Google, Facebook, Microsoft, and the others are already on the record as supporting these legislative changes. It would be better if they openly acknowledged their users’ insecurity and increased their pressure on the government to change, rather than trying to fool their users and customers.

This essay previously appeared on TheAtlantic.com.

Posted on March 31, 2014 at 9:18 AM • View Comments

Nicholas Weaver Explains how QUANTUM Works

An excellent essay. For the non-technical, his conclusion is the most important:

Everything we’ve seen about QUANTUM and other internet activity can be replicated with a surprisingly moderate budget, using existing tools with just a little modification.

The biggest limitation on QUANTUM is location: The attacker must be able to see a request which identifies the target. Since the same techniques can work on a Wi-Fi network, a $50 Raspberry Pi, located in a Foggy Bottom Starbucks, can provide any country, big and small, with a little window of QUANTUM exploitation. A foreign government can perform the QUANTUM attack NSA-style wherever your traffic passes through their country.

And that’s the bottom line with the NSA’s QUANTUM program. The NSA does not have a monopoly on the technology, and their widespread use acts as implicit permission to others, both nation-state and criminal.

Moreover, until we fix the underlying Internet architecture that makes QUANTUM attacks possible, we are vulnerable to all of those attackers.

Posted on March 14, 2014 at 2:01 PM • View Comments

1 2

Sidebar photo of Bruce Schneier by Joe MacInnis.