Entries Tagged "cryptography"
Page 37 of 55
Texas Instruments Signing Keys Broken
Texas Instruments’ calculators use RSA digital signatures to authenticate any updates to their operating system. Unfortunately, their signing keys are too short: 512-bits. Earlier this month, a collaborative effort factored the moduli and published the private keys. Texas Instruments responded by threatening websites that published the keys with the DMCA, but it’s too late.
So far, we have the operating-system signing keys for the TI-92+, TI-73, TI-89, TI-83+/TI-83+ Silver Edition, Voyage 200, TI-89 Titanium, and the TI-84+/TI-84 Silver Edition, and the date-stamp signing key for the TI-73, Explorer, TI-83 Plus, TI-83 Silver Edition, TI-84 Plus, TI-84 Silver Edition, TI-89, TI-89 Titanium, TI-92 Plus, and the Voyage 200.
Moral: Don’t assume that if your application is obscure, or if there’s no obvious financial incentive for doing so, that your cryptography won’t be broken if you use too-short keys.
Quantum Computer Factors the Number 15
This is an important development:
Shor’s algorithm was first demonstrated in a computing system based on nuclear magnetic resonance—manipulating molecules in a solution with strong magnetic fields. It was later demonstrated with quantum optical methods but with the use of bulk components like mirrors and beam splitters that take up an unwieldy area of several square meters.
Last year, the Bristol researchers showed they could miniaturize this optical setup, building a quantum photonic circuit on a silicon chip mere millimeters square. They replaced mirrors and beam splitters with waveguides that weave their way around the chip and interact to split, reflect, and transmit light through the circuit. They then injected photons into the waveguides to act as their qubits.
Now they’ve put their circuit to work: Using four photons that pass through a sequence of quantum logic gates, the optical circuit helped find the prime factors of the number 15. While the researchers showed that it was possible to solve for the factors, the chip itself didn’t just spit out 5 and 3. Instead, it came up with an answer to the “order-finding routine,” the “computationally hard” part of Shor’s algorithm that requires a quantum calculation to solve the problem in a reasonable amount of time, according to Jeremy O’Brien, a professor of physics and electrical engineering at the University of Bristol. The researchers then finished the computation using an ordinary computer to finally come up with the correct factors.
I’ve written about quantum computing (and quantum cryptography):
Several groups are working on designing and building a quantum computer, which is fundamentally different from a classical computer. If one were built—and we’re talking science fiction here—then it could factor numbers and solve discrete-logarithm problems very quickly. In other words, it could break all of our commonly used public-key algorithms. For symmetric cryptography it’s not that dire: A quantum computer would effectively halve the key length, so that a 256-bit key would be only as secure as a 128-bit key today. Pretty serious stuff, but years away from being practical.
Here’s a really good essay on the realities of quantum computing and its potential effects on public-key cryptography.
Skein News
Skein is one of the 14 SHA-3 candidates chosen by NIST to advance to the second round. As part of the process, NIST allowed the algorithm designers to implement small “tweaks” to their algorithms. We’ve tweaked the rotation constants of Skein. This change does not affect Skein’s performance in any way.
The revised Skein paper contains the new rotation constants, as well as information about how we chose them and why we changed them, the results of some new cryptanalysis, plus new IVs and test vectors. Revised source code is here.
The latest information on Skein is always here.
Tweaks were due today, September 15. Now the SHA-3 process moves into the second round. According to NIST’s timeline, they’ll choose a set of final round candidate algorithms in 2010, and then a single hash algorithm in 2012. Between now and then, it’s up to all of us to evaluate the algorithms and let NIST know what we want. Cryptanalysis is important, of course, but so is performance.
Here’s my 2008 essay on SHA-3. The second-round algorithms are: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein. You can find details on all of them, as well as the current state of their cryptanalysis, here.
In other news, we’re making Skein shirts available to the public. Those of you who attended the First Hash Function Candidate Conference in Leuven, Belgium, earlier this year might have noticed the stylish black Skein polo shirts worn by the Skein team. Anyone who wants one is welcome to buy it, at cost. Details (with photos) are here. All orders must be received before 1 October, and then we’ll have all the shirts made in one batch.
"The Cult of Schneier"
If there’s actually a cult out there, I want to hear about it. In an essay by that name, John Viega writes about the dangers of relying on Applied Cryptography to design cryptosystems:
But, after many years of evaluating the security of software systems, I’m incredibly down on using the book that made Bruce famous when designing the cryptographic aspects of a system. In fact, I can safely say I have never seen a secure system come out the other end, when that is the primary source for the crypto design. And I don’t mean that people forget about the buffer overflows. I mean, the crypto is crappy.
My rule for software development teams is simple: Don’t use Applied Cryptography in your system design. It’s fine and fun to read it, just don’t build from it.
[…]
The book talks about the fundamental building blocks of cryptography, but there is no guidance on things like, putting together all the pieces to create a secure, authenticated connection between two parties.
Plus, in the nearly 13 years since the book was last revised, our understanding of cryptography has changed greatly. There are things in it that were thought to be true at the time that turned out to be very false….
I agree. And, to his credit, Viega points out that I agree:
But in the introduction to Bruce Schneier’s book, Practical Cryptography, he himself says that the world is filled with broken systems built from his earlier book. In fact, he wrote Practical Cryptography in hopes of rectifying the problem.
This is all true.
Designing a cryptosystem is hard. Just as you wouldn’t give a person—even a doctor—a brain-surgery instruction manual and then expect him to operate on live patients, you shouldn’t give an engineer a cryptography book and then expect him to design and implement a cryptosystem. The patient is unlikely to survive, and the cryptosystem is unlikely to be secure.
Even worse, security doesn’t provide immediate feedback. A dead patient on the operating table tells the doctor that maybe he doesn’t understand brain surgery just because he read a book, but an insecure cryptosystem works just fine. It’s not until someone takes the time to break it that the engineer might realize that he didn’t do as good a job as he thought. Remember: Anyone can design a security system that he himself cannot break. Even the experts regularly get it wrong. The odds that an amateur will get it right are extremely low.
For those who are interested, a second edition of Practical Cryptography will be published in early 2010, renamed Cryptography Engineering and featuring a third author: Tadayoshi Kohno.
EDITED TO ADD (9/16): Commentary.
The History of One-Time Pads and the Origins of SIGABA
Blog post from Steve Bellovin:
It is vital that the keystream values (a) be truly random and (b) never be reused. The Soviets got that wrong in the 1940s; as a result, the U.S. Army’s Signal Intelligence Service was able to read their spies’ traffic in the Venona program. The randomness requirement means that the values cannot be generated by any algorithm; they really have to be random, and created by a physical process, not a mathematical one.
A consequence of these requirements is that the key stream must be as long as the data to be encrypted. If you want to encrypt a 1 megabyte file, you need 1 megabyte of key stream that you somehow have to share securely with the recipient. The recipient, in turn, has to store this data securely. Furthermore, both the sender and the recipient must ensure that they never, ever reuse the key stream. The net result is that, as I’ve often commented, “one-time pads are theoretically unbreakable, but practically very weak. By contrast, conventional ciphers are theoretically breakable, but practically strong.” They’re useful for things like communicating with high-value spies. The Moscow-Washington hotline used them, too. For ordinary computer usage, they’re not particularly practical.
I wrote about one-time pads, and their practical insecurity, in 2002:
What a one-time pad system does is take a difficult message security problem—that’s why you need encryption in the first place—and turn it into a just-as-difficult key distribution problem. It’s a “solution” that doesn’t scale well, doesn’t lend itself to mass-market distribution, is singularly ill-suited to computer networks, and just plain doesn’t work.
[…]
One-time pads may be theoretically secure, but they are not secure in a practical sense. They replace a cryptographic problem that we know a lot about solving—how to design secure algorithms—with an implementation problem we have very little hope of solving.
EFF on Locational Privacy
Excellent paper: “On Locational Privacy, and How to Avoid Losing it Forever.”
Some threats to locational privacy are overt: it’s evident how cameras backed by face-recognition software could be misused to track people and record their movements. In this document, we’re primarily concerned with threats to locational privacy that arise as a hidden side-effect of clearly useful location-based services.
We can’t stop the cascade of new location-based digital services. Nor would we want to—the benefits they offer are impressive. What urgently needs to change is that these systems need to be built with privacy as part of their original design. We can’t afford to have pervasive surveillance technology built into our electronic civic infrastructure by accident. We have the opportunity now to ensure that these dangers are averted.
Our contention is that the easiest and best solution to the locational privacy problem is to build systems which don’t collect the data in the first place. This sounds like an impossible requirement (how do we tell you when your friends are nearby without knowing where you and your friends are?) but in fact as we discuss below it is a reasonable objective that can be achieved with modern cryptographic techniques.
Modern cryptography actually allows civic data processing systems to be designed with a whole spectrum of privacy policies: ranging from complete anonymity to limited anonymity to support law enforcement. But we need to ensure that systems aren’t being built right at the zero-privacy, everything-is-recorded end of that spectrum, simply because that’s the path of easiest implementation.
I’ve already written about wholesale surveillance.
Another New AES Attack
A new and very impressive attack against AES has just been announced.
Over the past couple of months, there have been two (the second blogged about here) new cryptanalysis papers on AES. The attacks presented in the papers are not practical—they’re far too complex, they’re related-key attacks, and they’re against larger-key versions and not the 128-bit version that most implementations use—but they are impressive pieces of work all the same.
This new attack, by Alex Biryukov, Orr Dunkelman, Nathan Keller, Dmitry Khovratovich, and Adi Shamir, is much more devastating. It is a completely practical attack against ten-round AES-256:
Abstract.
AES is the best known and most widely used block cipher. Its three versions (AES-128, AES-192, and AES-256) differ in their key sizes (128 bits, 192 bits and 256 bits) and in their number of rounds (10, 12, and 14, respectively). In the case of AES-128, there is no known attack which is faster than the 2128 complexity of exhaustive search. However, AES-192 and AES-256 were recently shown to be breakable by attacks which require 2176 and 2119 time, respectively. While these complexities are much faster than exhaustive search, they are completely non-practical, and do not seem to pose any real threat to the security of AES-based systems.In this paper we describe several attacks which can break with practical complexity variants of AES-256 whose number of rounds are comparable to that of AES-128. One of our attacks uses only two related keys and 239 time to recover the complete 256-bit key of a 9-round version of AES-256 (the best previous attack on this variant required 4 related keys and 2120 time). Another attack can break a 10 round version of AES-256 in 245 time, but it uses a stronger type of related subkey attack (the best previous attack on this variant required 64 related keys and 2172 time).
They also describe an attack against 11-round AES-256 that requires 270 time—almost practical.
These new results greatly improve on the Biryukov, Khovratovich, and Nikolic papers mentioned above, and a paper I wrote with six others in 2000, where we describe a related-key attack against 9-round AES-256 (then called Rijndael) in 2224 time. (This again proves the cryptographer’s adage: attacks always get better, they never get worse.)
By any definition of the term, this is a huge result.
There are three reasons not to panic:
- The attack exploits the fact that the key schedule for 256-bit version is pretty lousy—something we pointed out in our 2000 paper—but doesn’t extend to AES with a 128-bit key.
- It’s a related-key attack, which requires the cryptanalyst to have access to plaintexts encrypted with multiple keys that are related in a specific way.
- The attack only breaks 11 rounds of AES-256. Full AES-256 has 14 rounds.
Not much comfort there, I agree. But it’s what we have.
Cryptography is all about safety margins. If you can break n round of a cipher, you design it with 2n or 3n rounds. What we’re learning is that the safety margin of AES is much less than previously believed. And while there is no reason to scrap AES in favor of another algorithm, NST should increase the number of rounds of all three AES variants. At this point, I suggest AES-128 at 16 rounds, AES-192 at 20 rounds, and AES-256 at 28 rounds. Or maybe even more; we don’t want to be revising the standard again and again.
And for new applications I suggest that people don’t use AES-256. AES-128 provides more than enough security margin for the forseeable future. But if you’re already using AES-256, there’s no reason to change.
The paper I have is still a draft. It is being circulated among cryptographers, and should be online in a couple of days. I will post the link as soon as I have it.
UPDATED TO ADD (8/3): The paper is public.
iPhone Encryption Useless
Interesting, although I want some more technical details.
…the new iPhone 3GS’ encryption feature is “broken” when it comes to protecting sensitive information such as credit card numbers and social-security digits, Zdziarski said.
Zdziarski said it’s just as easy to access a user’s private information on an iPhone 3GS as it was on the previous generation iPhone 3G or first generation iPhone, both of which didn’t feature encryption. If a thief got his hands on an iPhone, a little bit of free software is all that’s needed to tap into all of the user’s content. Live data can be extracted in as little as two minutes, and an entire raw disk image can be made in about 45 minutes, Zdziarski said.
Wondering where the encryption comes into play? It doesn’t. Strangely, once one begins extracting data from an iPhone 3GS, the iPhone begins to decrypt the data on its own, he said.
SHA-3 Second Round Candidates Announced
NIST has announced the 14 SHA-3 candidates that have advanced to the second round: BLAKE, Blue Midnight Wish, CubeHash, ECHO, Fugue, Grøstl, Hamsi, JH, Keccak, Luffa, Shabal, SHAvite-3, SIMD, and Skein.
In February, I chose my favorites: Arirang, BLAKE, Blue Midnight Wish, ECHO, Grøstl, Keccak, LANE, Shabal, and Skein. Of the ones NIST eventually chose, I am most surprised to see CubeHash and most surprised not to see LANE.
Here’s my 2008 essay on SHA-3. Here’s NIST’s SHA-3 page. And here’s the page on my own submission, Skein.
Sidebar photo of Bruce Schneier by Joe MacInnis.