Secret documents describing the National Security Agency's surveillance apparatus have highlighted vulnerabilities in outdated Web encryption used by Facebook and a handful of other U.S. companies.
Documents leaked by former NSA contractor Edward Snowden confirm that the NSA taps into fiber optic cables "upstream" from Internet companies and vacuums up e-mail and other data that "flows past" -- a security vulnerability that "https" Web encryption is intended to guard against.
But Facebook and a few other companies still rely on an encryption technique viewed as many years out of date, which cryptographers say the NSA could penetrate reasonably quickly after intercepting the communications. Facebook uses encryption keys with a length of only 1,024 bits, while Web companies including Apple, Microsoft, Twitter, Dropbox, and even Myspace have switched to exponentially more secure 2,048-bit keys.
Eran Tromer, an assistant professor of computer science at Tel Aviv University who wrote his 2007 dissertation on custom code-breaking hardware, said it's now "feasible to build dedicated hardware devices that can break 1024-bit RSA keys at a cost of under $1 million per device." Each dedicated device would be able to break a 1,024-bit key in one year, he said.
"Realistically, right now, breaking 1,024-bit RSA should be considered well within reach by leading nations, and marginally safe against other players," Tromer said. "This is unsatisfactory as the default security level of the Internet."
The NSA's budget is estimated to be at least $10 billion a year.
--Eran Tromer, professor, Tel Aviv University
Facebook declined to comment for this article. A person familiar with the company's encryption development plans, however, said the social network is working on switching over to 2048-bit keys relatively soon.
Encryption that's used to shield the privacy of Web browsing is known as RSA, a form of public key cryptography based on the fact that it is immensely difficult to factor large numbers. As microprocessor speeds continue to advance, however, RSA keys with lengths that were previously viewed as secure have fallen to brute-force attacks.
"Some companies may not feel that intelligence agencies are a threat they care about, so may feel less pressure to upgrade," said Ron Rivest, a professor of electrical engineering and computer science at MIT, and the "R" in RSA. Tromer's published estimates of code-breaking times are "plausible," Rivest said, and it's possible that "additional benefits might be obtained by an intensive research and engineering push."
In 1999, Electronic Frontier Foundation co-founder John Gilmore built a custom machine called "Deep Crack," which performed a brute force attack against a 56-bit DES key (the equivalent of a 384-bit RSA key) in under 23 hours. An RSA key with a length of 768 bits was factored (PDF) in December 2009 by an international team of computer science researchers.
Factoring a 1,024-bit RSA key is about 1,000 times as hard as a 768-bit key -- an expensive but hardly difficult task for the NSA or other well-resourced national intelligence agencies. That's why NIST recommended (PDF) that 1,024-bit RSA keys are no longer viable after 2010, and companies that sell Web SSL certificates began to phase out 1,024-bit RSA keys in favor of 2,048-bit RSA keys a few years ago.
Google also uses 1,024-bit keys, but in 2011 it implemented a clever trick called forward secrecy, meaning a different key is used for each encrypted Web session, instead of a single master key that's used to encrypt billions of them. The company said last month it will switch over to 2,048-bit keys by the end of 2013.
"We would have preferred to move sooner, but operating at the scale we do, client compatibility is always an issue," said Adam Langley, a software engineer at Google. "Everything on the planet seems to connect to us."
Langley added: "We would have totally eaten the cost and the speed years ago -- if we could have done it without worries." As an additional precaution, Langley said, Google usually rotates its RSA keys every two weeks. (Facebook does it once a year, and is also planning to make forward secrecy a default setting for users, which few other companies do. Once Facebook switches to 2,048-bit keys and forward secrecy, its users will be better protected against NSA surveillance than almost any other company.)
Beyond Facebook, other companies still using 1,024-bit encryption keys include Capital One bank and Amazon.com's U.K. and Japan sites. Web sites that have veered in the opposite direction with 4,096-bit RSA keys include Apache.org, Hugedomains.com, Openoffice.org, Phpbb.com, and Shareasale.com.
Classified NSA documents published by the Guardian over the last few weeks have sketched an outline of a massive surveillance system that vacuums up billions of Americans' e-mail messages and other private correspondence. One document prepared by the NSA's Special Source Operations directorate, for instance, said the agency had "processed its one-trillionth metadata record" by December 2012.
Documents that came to light in 2006 in a lawsuit brought by the Electronic Frontier Foundation offer some insight into the spy agency's relationship with Tier 1 providers. Mark Klein, who worked as an AT&T technician for over 22 years, disclosed (PDF) that he witnessed domestic voice and Internet traffic being surreptitiously "diverted" through a "splitter cabinet" to secure room 641A in one of the company's San Francisco facilities. The room was accessible only to NSA-cleared technicians.
The cheap way out
To be sure, even weak encryption is more privacy-protective than no encryption, which is still the default for routine Web browsing.
Chris Soghoian, a senior policy analyst with the ACLU's Speech, Privacy, and Technology Project, said companies that don't use strong encryption are "being cheap" because they can get "more encryption per second per server" with a shorter RSA key.
Tromer, the Tel Aviv University cryptographer, has described in a series of papers (PDF), including some co-authored with Adi Shamir, the "S" in RSA, how technological progress makes custom code-breaking hardware ever faster. Moving to 90-nanometer semiconductor technology that was reached in 2005 brings the cost to $1.1 million for hardware that breaks 1,024-bit keys at the rate of one a year, not counting initial engineering and fabrication, he said. Today's 22-nanometer technology brings a "significant further reduction" in cost, he said.
Another technological approach the NSA or other well-resourced intelligence agencies could use -- putting aside social engineering attacks or intrusions into data centers -- is using off-the-shelf computers in a brute force attack against an RSA key.
"Why use specialized hardware?" asked Arjen Lenstra, a number theorist and professor at the École Polytechnique Fédérale de Lausanne in Switzerland who participated in the successful 2009 effort to factor a 768-bit RSA key. A few "million CPUs for a year suffices for 1,024 RSA," Lenstra said.
Langley, the Google software engineer, said his employer could devote some of its massive computing resources to breaking a 1,024-bit RSA key if it chose to do so.
"It could be done today," Langley said. "We could do it if we really wanted." But, he adds, there are better ways to spend millions of dollars in a way that will "advance the state of cryptography research."