Entries Tagged "cryptography"

Page 18 of 55

Paris Attacks Blamed on Strong Cryptography and Edward Snowden

Well, that didn’t take long:

As Paris reels from terrorist attacks that have claimed at least 128 lives, fierce blame for the carnage is being directed toward American whistleblower Edward Snowden and the spread of strong encryption catalyzed by his actions.

Now the Paris attacks are being used an excuse to demand back doors.

CIA Director John Brennan chimed in, too.

Of course, this was planned all along. From September:

Privately, law enforcement officials have acknowledged that prospects for congressional action this year are remote. Although “the legislative environment is very hostile today,” the intelligence community’s top lawyer, Robert S. Litt, said to colleagues in an August e-mail, which was obtained by The Post, “it could turn in the event of a terrorist attack or criminal event where strong encryption can be shown to have hindered law enforcement.”

There is value, he said, in “keeping our options open for such a situation.”

I was going to write a definitive refutation to the meme that it’s all Snowden’s fault, but Glenn Greenwald beat me to it.

EDITED TO ADD: It wasn’t fair for me to characterize Ben Wittes’s Lawfare post as agitating for back doors. I apologize.

Better links are these two New York Times stories.

EDITED TO ADD (11/17): These two essays are also good.

EDITED TO ADD (11/18): The New York Times published a powerful editorial against mass surveillance.

EDITED TO ADD (11/19): The New York Times deleted a story claiming the attackers used encryption. Because it turns out they didn’t use encryption.

Posted on November 16, 2015 at 2:39 PMView Comments

Why Is the NSA Moving Away from Elliptic Curve Cryptography?

In August, I wrote about the NSA’s plans to move to quantum-resistant algorithms for its own cryptographic needs.

Cryptographers Neal Koblitz and Alfred Menezes just published a long paper speculating as to the government’s real motives for doing this. They range from some new cryptanalysis of ECC to a political need after the DUAL_EC_PRNG disaster—to the stated reason of quantum computing fears.

Read the whole paper. (Feel free to skip over the math if it gets too hard, but keep going until the end.)

EDITED TO ADD (11/15): A commentary and critique of the paper by Matthew Green.

Posted on October 28, 2015 at 2:11 PMView Comments

Breaking Diffie-Hellman with Massive Precomputation (Again)

The Internet is abuzz with this blog post and paper, speculating that the NSA is breaking the Diffie-Hellman key-exchange protocol in the wild through massive precomputation.

I wrote about this at length in May when this paper was first made public. (The reason it’s news again is that the paper was just presented at the ACM Computer and Communications Security conference.)

What’s newly being talked about his how this works inside the NSA surveillance architecture. Nicholas Weaver explains:

To decrypt IPsec, a large number of wiretaps monitor for IKE (Internet Key Exchange) handshakes, the protocol that sets up a new IPsec encrypted connection. The handshakes are forwarded to a decryption oracle, a black box system that performs the magic. While this happens, the wiretaps also record all traffic in the associated IPsec connections.

After a period of time, this oracle either returns the private keys or says “i give up”. If the oracle provides the keys, the wiretap decrypts all the stored traffic and continues to decrypt the connection going forward.

[…]

This would also better match the security implications: just the fact that the NSA can decrypt a particular flow is a critical secret. Forwarding a small number of potentially-crackable flows to a central point better matches what is needed to maintain such secrecy.

Thus by performing the decryption in bulk at the wiretaps, complete with hardware acceleration to keep up with the number of encrypted streams, this architecture directly implies that the NSA can break a massive amount of IPsec traffic, a degree of success which implies a cryptanalysis breakthrough.

That last paragraph is Weaver explaining how this attack matches the NSA rhetoric about capabilities in some of their secret documents.

Now that this is out, I’m sure there are a lot of really upset people inside the NSA.

EDITED TO ADD (11/15): How to protect yourself.

Posted on October 16, 2015 at 6:19 AMView Comments

SHA-1 Freestart Collision

There’s a new cryptanalysis result against the hash function SHA-1:

Abstract: We present in this article a freestart collision example for SHA-1, i.e., a collision for its internal compression function. This is the first practical break of the full SHA-1, reaching all 80 out of 80 steps, while only 10 days of computation on a 64 GPU cluster were necessary to perform the attack. This work builds on a continuous series of cryptanalytic advancements on SHA-1 since the theoretical collision attack breakthrough in 2005. In particular, we extend the recent freestart collision work on reduced-round SHA-1 from CRYPTO 2015 that leverages the computational power of graphic cards and adapt it to allow the use of boomerang speed-up techniques. We also leverage the cryptanalytic techniques by Stevens from EUROCRYPT 2013 to obtain optimal attack conditions, which required further refinements for this work. Freestart collisions, like the one presented here, do not directly imply a collision for SHA-1.

However, this work is an important milestone towards an actual SHA-1 collision and it further shows how graphics cards can be used very efficiently for these kind of attacks. Based on the state-of-the-art collision attack on SHA-1 by Stevens from EUROCRYPT 2013, we are able to present new projections on the computational/financial cost required by a SHA-1 collision computation. These projections are significantly lower than previously anticipated by the industry, due to the use of the more cost efficient graphics cards compared to regular CPUs. We therefore recommend the industry, in particular Internet browser vendors and Certification Authorities, to retract SHA-1 soon. We hope the industry has learned from the events surrounding the cryptanalytic breaks of MD5 and will retract SHA-1 before example signature forgeries appear in the near future. With our new cost projections in mind, we strongly and urgently recommend against a recent proposal to extend the issuance of SHA-1 certificates by a year in the CAB/forum (the vote closes on October 16 2015 after a discussion period ending on October 9).

Especially note this bit: “Freestart collisions, like the one presented here, do not directly imply a collision for SHA-1. However, this work is an important milestone towards an actual SHA-1 collision and it further shows how graphics cards can be used very efficiently for these kind of attacks.” In other words: don’t panic, but prepare for a future panic.

This is not that unexpected. We’ve long known that SHA-1 is broken, at least theoretically. All the major browsers are planning to stop accepting SHA-1 signatures by 2017. Microsoft is retiring it on that same schedule. What’s news is that our previous estimates may be too conservative.

There’s a saying inside the NSA: “Attacks always get better; they never get worse.” This is obviously true, but it’s worth explaining why. Attacks get better for three reasons. One, Moore’s Law means that computers are always getting faster, which means that any cryptanalytic attack gets faster. Two, we’re forever making tweaks in existing attacks, which make them faster. (Note above: “…due to the use of the more cost efficient graphics cards compared to regular CPUs.”) And three, we regularly invent new cryptanalytic attacks. The first of those is generally predictable, the second is somewhat predictable, and the third is not at all predictable.

Way back in 2004, I wrote: “It’s time for us all to migrate away from SHA-1.” Since then, we have developed an excellent replacement: SHA-3 has been agreed on since 2012, and just became a standard.

This new result is important right now:

Thursday’s research showing SHA1 is weaker than previously thought comes as browser developers and certificate authorities are considering a proposal that would extend the permitted issuance of the SHA1-based HTTPS certificates by 12 months, that is through the end of 2016 rather than no later than January of that year. The proposal argued that some large organizations currently find it hard to move to a more secure hashing algorithm for their digital certificates and need the additional year to make the transition.

As the papers’ authors note, approving this proposal is a bad idea.

More on the paper here.

Posted on October 8, 2015 at 11:44 AMView Comments

Self-Destructing Computer Chip

The chip is built on glass:

Shattering the glass is straightforward. When the proper circuit is toggled, a small resistor within the substrate heats up until the glass shatters. According to Corning, it will continue shattering even after the initial break, rendering the entire chip unusable. The demo chip resistor was triggered by a photo diode that switched the circuit when a laser shone upon it. The glass plate quickly shattered into fragments once the laser touches it.

Posted on September 17, 2015 at 7:17 AMView Comments

Wanted: Cryptography Products for Worldwide Survey

In 1999, Lance Hoffman, David Balenson, and others published a survey of non-US cryptographic products. The point of the survey was to illustrate that there was a robust international market in these products, and that US-only export restrictions on strong encryption did nothing to prevent its adoption and everything to disadvantage US corporations. This was an important contribution during the First Crypto War, and Hoffman testified before a Senate committee on his findings.

I want to redo that survey for 2015.

Here, at the beginning of the Second Crypto War, we again need to understand which encryption products are outside the reach of US regulation (or UK regulation). Are there so many foreign crypto products that any regulation by only one country will be easily circumvented? Or has the industry consolidated around only a few products made by only a few countries, so that effective regulation of strong encryption is possible? What are the possibilities for encrypted communication and data storage? I honestly don’t know the answer—and I think it’s important to find out.

To that end, I am asking for help. Please respond in the comments with the names—and URLs—of non-US encryption software and hardware products. I am only interested in those useful for protecting communications and data storage. I don’t care about encrypting financial transactions, or anything of that sort.

Thank you for your help. And please forward this blog post to anyone else who might help.

EDITED TO ADD: Thinking about it more, I want to compile a list of domestic (U.S.) encryption products as well. Since right now the FBI seems intent on just pressuring the big companies like Apple and Microsoft, and not regulating cryptography in general, knowing what else is out there in the U.S. will be useful.

Posted on September 11, 2015 at 2:08 PMView Comments

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 PMView Comments

Another Salvo in the Second Crypto War (of Words)

Prosecutors from New York, London, Paris, and Madrid wrote an op-ed in yesterday’s New York Times in favor of backdoors in cell phone encryption. There are a number of flaws in their argument, ranging from how easy it is to get data off an encrypted phone to the dangers of designing a backdoor in the first place, but all of that has been said before. And since anecdote can be more persuasive than data, the op-ed started with one:

In June, a father of six was shot dead on a Monday afternoon in Evanston, Ill., a suburb 10 miles north of Chicago. The Evanston police believe that the victim, Ray C. Owens, had also been robbed. There were no witnesses to his killing, and no surveillance footage either.

With a killer on the loose and few leads at their disposal, investigators in Cook County, which includes Evanston, were encouraged when they found two smartphones alongside the body of the deceased: an iPhone 6 running on Apple’s iOS 8 operating system, and a Samsung Galaxy S6 Edge running on Google’s Android operating system. Both devices were passcode protected.

You can guess the rest. A judge issued a warrant, but neither Apple nor Google could unlock the phones. “The homicide remains unsolved. The killer remains at large.”

The Intercept researched the example, and it seems to be real. The phones belonged to the victim, and…

According to Commander Joseph Dugan of the Evanston Police Department, investigators were able to obtain records of the calls to and from the phones, but those records did not prove useful. By contrast, interviews with people who knew Owens suggested that he communicated mainly through text messages—the kind that travel as encrypted data—and had made plans to meet someone shortly before he was shot.

The information on his phone was not backed up automatically on Apple’s servers—apparently because he didn’t use wi-fi, which backups require.

[…]

But Dugan also wasn’t as quick to lay the blame solely on the encrypted phones. “I don’t know if getting in there, getting the information, would solve the case,” he said, “but it definitely would give us more investigative leads to follow up on.”

This is the first actual example I’ve seen illustrating the value of a backdoor. Unlike the increasingly common example of an ISIL handler abroad communicating securely with a radicalized person in the US, it’s an example where a backdoor might have helped. I say “might have,” because the Galaxy S6 is not encrypted by default, which means the victim deliberately turned the encryption on. If the native smartphone encryption had been backdoored, we don’t know if the victim would have turned it on nevertheless, or if he would have employed a different, non-backdoored, app.

The authors’ other examples are much sloppier:

Between October and June, 74 iPhones running the iOS 8 operating system could not be accessed by investigators for the Manhattan district attorney’s office—despite judicial warrants to search the devices. The investigations that were disrupted include the attempted murder of three individuals, the repeated sexual abuse of a child, a continuing sex trafficking ring and numerous assaults and robberies.

[…]

In France, smartphone data was vital to the swift investigation of the Charlie Hebdo terrorist attacks in January, and the deadly attack on a gas facility at Saint-Quentin-Fallavier, near Lyon, in June. And on a daily basis, our agencies rely on evidence lawfully retrieved from smartphones to fight sex crimes, child abuse, cybercrime, robberies or homicides.

We’ve heard that 74 number before. It’s over nine months, in an office that handles about 100,000 cases a year: less than 0.1% of the time. Details about those cases would be useful, so we can determine if encryption was just an impediment to investigation, or resulted in a criminal going free. The government needs to do a better job of presenting empirical data to support its case for backdoors. That they’re unable to do so suggests very strongly that an empirical analysis wouldn’t favor the government’s case.

As to the Charlie Hebdo case, it’s not clear how much of that vital smartphone data was actual data, and how much of it was unable-to-be-encrypted metadata. I am reminded of the examples that then-FBI-Director Louis Freeh would give during the First Crypto Wars in the 1990s. The big one used to illustrate the dangers of encryption was Mafia boss John Gotti. But the surveillance that convicted him was a room bug, not a wiretap. Given that the examples from FBI Director James Comey’s “going dark” speech last year were bogus, skepticism in the face of anecdote seems prudent.

So much of this “going dark” versus the “golden age of surveillance” debate depends on where you start from. Referring to that first Evanston example and the inability to get evidence from the victim’s phones, the op-ed authors write: “Until very recently, this situation would not have occurred.” That’s utter nonsense. From the beginning of time until very recently, this was the only situation that could have occurred. Objects in the vicinity of an event were largely mute about the past. Few things, save for eyewitnesses, could ever reach back in time and produce evidence. Even 15 years ago, the victim’s cell phone would have had no evidence on it that couldn’t have been obtained elsewhere, and that’s if the victim had been carrying a cell phone at all.

For most of human history, surveillance has been expensive. Over the last couple of decades, it has become incredibly cheap and almost ubiquitous. That a few bits and pieces are becoming expensive again isn’t a cause for alarm.

This essay originally appeared on Lawfare.

EDITED TO ADD (8/13): Excellent parody/commentary: “When Curtains Block Justice.”

Posted on August 12, 2015 at 2:18 PMView Comments

1 16 17 18 19 20 55

Sidebar photo of Bruce Schneier by Joe MacInnis.