Entries Tagged "cryptography"

Page 41 of 55

Quantum Cryptography

Quantum cryptography is back in the news, and the basic idea is still unbelievably cool, in theory, and nearly useless in real life.

The idea behind quantum crypto is that two people communicating using a quantum channel can be absolutely sure no one is eavesdropping. Heisenberg’s uncertainty principle requires anyone measuring a quantum system to disturb it, and that disturbance alerts legitimate users as to the eavesdropper’s presence. No disturbance, no eavesdropper—period.

This month we’ve seen reports on a new working quantum-key distribution network in Vienna, and a new quantum-key distribution technique out of Britain. Great stuff, but headlines like the BBC’s “‘Unbreakable’ encryption unveiled” are a bit much.

The basic science behind quantum crypto was developed, and prototypes built, in the early 1980s by Charles Bennett and Giles Brassard, and there have been steady advances in engineering since then. I describe basically how it all works in Applied Cryptography, 2nd Edition (pages 554-557). At least one company already sells quantum-key distribution products.

Note that this is totally separate from quantum computing, which also has implications for 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. I think the best quantum computer today can factor the number 15.

While I like the science of quantum cryptography—my undergraduate degree was in physics—I don’t see any commercial value in it. I don’t believe it solves any security problem that needs solving. I don’t believe that it’s worth paying for, and I can’t imagine anyone but a few technophiles buying and deploying it. Systems that use it don’t magically become unbreakable, because the quantum part doesn’t address the weak points of the system.

Security is a chain; it’s as strong as the weakest link. Mathematical cryptography, as bad as it sometimes is, is the strongest link in most security chains. Our symmetric and public-key algorithms are pretty good, even though they’re not based on much rigorous mathematical theory. The real problems are elsewhere: computer security, network security, user interface and so on.

Cryptography is the one area of security that we can get right. We already have good encryption algorithms, good authentication algorithms and good key-agreement protocols. Maybe quantum cryptography can make that link stronger, but why would anyone bother? There are far more serious security problems to worry about, and it makes much more sense to spend effort securing those.

As I’ve often said, it’s like defending yourself against an approaching attacker by putting a huge stake in the ground. It’s useless to argue about whether the stake should be 50 feet tall or 100 feet tall, because either way, the attacker is going to go around it. Even quantum cryptography doesn’t “solve” all of cryptography: The keys are exchanged with photons, but a conventional mathematical algorithm takes over for the actual encryption.

I’m always in favor of security research, and I have enjoyed following the developments in quantum cryptography. But as a product, it has no future. It’s not that quantum cryptography might be insecure; it’s that cryptography is already sufficiently secure.

This essay previously appeared on Wired.com.

EDITED TO ADD (10/21): It’s amazing; even reporters responding to my essay get it completely wrong:

Keith Harrison, a cryptographer with HP Laboratories, is quoted by the Telegraph as saying that, as quantum computing becomes commonplace, hackers will use the technology to crack conventional encryption.

“We have to be thinking about solutions to the problems that quantum computing will pose,” he told the Telegraph. “The average consumer is going to want to know their own transactions and daily business is secure.

“One way of doing this is to use a one time pad essentially lists of random numbers where one copy of the numbers is held by the person sending the information and an identical copy is held by the person receiving the information. These are completely unbreakable when used properly,” he explained.

The critical feature of quantum computing is the unique fact that, if someone tampers with an information feed between two parties, then the nature of the quantum feed changes.

This makes eavesdropping impossible.

No, it wouldn’t make eavesdropping impossible. It would make eavesdropping on the communications channel impossible unless someone made an implementation error. (In the 80s, the NSA broke Soviet one-time-pad systems because the Soviets reused the pad.) Eavesdropping via spyware or Trojan or TEMPEST would still be possible.

EDITED TO ADD (10/26): Here’s another commenter who gets it wrong:

Now let me get this straight: I have no doubt that there are many greater worries in security than “mathematical crypography.” But does this justify totally ignoring the possibility that a cryptographic system might possibly be breakable? I mean maybe I’m influenced by this in the fact that I’ve been sitting in on a cryptanalysis course and I just met a graduate student who broke a cryptographic pseudorandom number generator, but really what kind of an argument is this? “Um, well, sometimes our cryptographic systems have been broken, but that’s nothing to worry about, because, you know, everything is kosher with the systems we are using.”

The point isn’t to ignore the possibility that a cryptographic system might possibly be broken; the point is to pay attention to the other parts of the system that are much much more likely to be already broken. Security is a chain; it’s only as secure as the weakest link. The cryptographic systems, as potentially flawed as they are, are the strongest link in the chain. We’d get a lot more security devoting our resources to making all those weaker links more secure.

Again, this is not to say that quantum cryptography isn’t incredibly cool research. It is, and I hope it continues to receive all sorts of funding. But for an operational network that is worried about security: you’ve got much bigger worries than whether Diffie-Hellman will be broken someday.

Posted on October 21, 2008 at 6:48 AM • View Comments

"New Attack" Against Encrypted Images

In a blatant attempt to get some PR:

In a new paper, Bernd Roellgen of Munich-based encryption outfit PMC Ciphers, explains how it is possible to compare an encrypted backup image file made with almost any commercial encryption program or algorithm to an original that has subsequently changed so that small but telling quantities of data ‘leaks’.

Here’s the paper. Turns out that if you use a block cipher in Electronic Codebook Mode, identical plaintexts encrypt to identical ciphertexts.

Yeah, we already knew that.

And -1 point for a security company requiring the use of Javascript, and not failing gracefully for a browser that doesn’t have it enabled.

And—ahem—what is it with that photograph in the paper? Couldn’t the researchers have found something a little less adolescent?

For the record, I doghoused PMC Ciphers back in 2003:

PMC Ciphers. The theory description is so filled with pseudo-cryptography that it’s funny to read. Hypotheses are presented as conclusions. Current research is misstated or ignored. The first link is a technical paper with four references, three of them written before 1975. Who needs thirty years of cryptographic research when you have polymorphic cipher theory?

EDITED TO ADD (10/9): I didn’t realize it, but last year PMC Ciphers responded to my doghousing them. Funny stuff.

EDITED TO ADD (10/10): Three new commenters using dialups at the same German ISP have showed up here to defend the paper. What are the odds?

Posted on October 9, 2008 at 6:44 AM • View Comments

The Doghouse: Tornado Plus Encrypted USB Drive

Don’t buy this:

My first discussion was with a sales guy. I asked about the encryption method. He didn’t know. I asked about how the key was protected. Again, no idea. I began to suspect that this was not the person I needed to speak with, and I asked for a “technical” person. After a short wait, another sales guy got on the phone. He knew a little more. For example, the encryption method is to XOR the key with the data. Those of you in the security profession know my reaction to this news. For those of you still coming up to speed, XORing a key with data to encrypt sensitive information is bad. Very bad.

EDITED TO ADD (9/13): In the comment thread, there’s a lot of talk about one-time pads. This is something I wrote on the topic in 2002:

So, let me summarize. One-time pads are useless for all but very specialized applications, primarily historical and non-computer. And almost any system that uses a one-time pad is insecure. It will claim to use a one-time pad, but actually use a two-time pad (oops). Or it will claim to use a one-time pad, but actually use a stream cipher. Or it will use a one-time pad, but won’t deal with message re-synchronization and re-transmission attacks. Or it will ignore message authentication, and be susceptible to bit-flipping attacks and the like. Or it will fall prey to keystream reuse attacks. Etc., etc., etc.

Posted on September 12, 2008 at 12:05 PM • View Comments

Contest: Cory Doctorow's Cipher Wheel Rings

Cory Doctorow wanted a secret decoder wedding ring, and he asked me to help design it. I wanted something more than the standard secret decoder ring, so this is what I asked for: “I want each wheel to be the alphabet, with each letter having either a dot above, a dot below, or no dot at all. The first wheel should have alternating above, none, below. The second wheel should be the repeating sequence of above, above, none, none, below, below. The third wheel should be the repeating sequence of above, above, above, none, none, none, below, below, below.” (I know it sounds confusing, but here’s a chart.)

So that’s what he asked for, and that’s what he got. And now it’s time to create some cryptographic applications for the rings. Cory and I are holding an open contest for the cleverest application.

I don’t think we can invent any encryption algorithms that will survive computer analysis—there’s just not enough entropy in the system—but we can come up with some clever pencil-and-paper ciphers that will serve them well if they’re ever stuck back in time. And there are certainly other cryptographic uses for the rings.

Here’s a way to use the rings as a password mnemonic: First, choose a two-letter key. Align the three wheels according to the key. For example, if the key is “EB” for eBay, align the three wheels AEB. Take the common password “PASSWORD” and encrypt it. For each letter, find it on the top wheel. Count one letter to the left if there is a dot over the letter, and one letter to the right if there is a dot under it. Take that new letter and look at the letter below it (in the middle wheel). Count two letters to the left if there is a dot over it, and two letters to the right if there is a dot under it. Take that new letter (in the middle wheel), and look at the letter below it (in the lower wheel). Count three letters to the left if there is a dot over it, and three letters to the right if there is a dot under it. That’s your encrypted letter. Do that with every letter to get your password.

“PASSWORD” and the key “EB” becomes “NXPPVVOF.”

It’s not very good; can anyone see why? (Ignore for now whether or not publishing this on a blog makes it no longer secure.)

How can I do that better? What else can we do with the rings? Can we incorporate other elements—a deck of playing cards as in Solitaire, different-sized coins to make the system more secure?

Post your contest entries as comments to Cory’s blog post—you can post them here, but they’re not going to count as contest submissions—or send them to cryptocontest@craphound.com. Deadline is October 1st.

Good luck, and have fun with this.

Posted on September 5, 2008 at 12:01 PM • View Comments

Adi Shamir's Cube Attacks

At this moment, Adi Shamir is giving an invited talk at the Crypto 2008 conference about a new type of cryptanalytic attack called “cube attacks.” He claims very broad applicability to stream and block ciphers.

My personal joke—at least I hope it’s a joke—is that he’s going to break every NIST hash submission without ever seeing any of them. (Note: The attack, at least at this point, doesn’t apply to hash functions.)

More later.

EDITED TO ADD (8/19): AES is immune to this attack—the degree of the algebraic polynomial is too high—and all the block ciphers we use have a higher degree. But, in general, anything that can be described with a low-degree polynomial equation is vulnerable: that’s pretty much every LFSR scheme.

EDITED TO ADD (8/19): The typo that amused you all below has been fixed. And this attack doesn’t apply to any block cipher—DES, AES, Blowfish, Twofish, anything else—in common use; their degree is much too high. It doesn’t apply to hash functions at all, at least not yet—but again, the degree of all the common ones is much too high. I will post a link to the paper when it becomes available; I assume Adi will post it soon. (The paper was rejected from Asiacrypt, demonstrating yet again that the conference review process is broken.)

EDITED TO ADD (8/19): Adi’s coauthor is Itai Dinur. Their plan is to submit the paper to Eurocrypt 2009. They will publish it as soon as they can, depending on the Eurocrypt rules about prepublication.

EDITED TO ADD (8/26): Two news articles with not a lot of information.

EDITED TO ADD (9/4): Some more details.

EDITED TO ADD (9/14): The paper is online.

Posted on August 19, 2008 at 1:15 PM • View Comments

Hacking Mifare Transport Cards

London’s Oyster card has been cracked, and the final details will become public in October. NXP Semiconductors, the Philips spin-off that makes the system, lost a court battle to prevent the researchers from publishing. People might be able to use this information to ride for free, but the sky won’t be falling. And the publication of this serious vulnerability actually makes us all safer in the long run.

Here’s the story. Every Oyster card has a radio-frequency identification chip that communicates with readers mounted on the ticket barrier. That chip, the “Mifare Classic” chip, is used in hundreds of other transport systems as well—Boston, Los Angeles, Brisbane, Amsterdam, Taipei, Shanghai, Rio de Janeiro—and as an access pass in thousands of companies, schools, hospitals, and government buildings around Britain and the rest of the world.

The security of Mifare Classic is terrible. This is not an exaggeration; it’s kindergarten cryptography. Anyone with any security experience would be embarrassed to put his name to the design. NXP attempted to deal with this embarrassment by keeping the design secret.

The group that broke Mifare Classic is from Radboud University Nijmegen in the Netherlands. They demonstrated the attack by riding the Underground for free, and by breaking into a building. Their two papers (one is already online) will be published at two conferences this autumn.

The second paper is the one that NXP sued over. They called disclosure of the attack “irresponsible,” warned that it will cause “immense damages,” and claimed that it “will jeopardize the security of assets protected with systems incorporating the Mifare IC.” The Dutch court would have none of it: “Damage to NXP is not the result of the publication of the article but of the production and sale of a chip that appears to have shortcomings.”

Exactly right. More generally, the notion that secrecy supports security is inherently flawed. Whenever you see an organization claiming that design secrecy is necessary for security—in ID cards, in voting machines, in airport security—it invariably means that its security is lousy and it has no choice but to hide it. Any competent cryptographer would have designed Mifare’s security with an open and public design.

Secrecy is fragile. Mifare’s security was based on the belief that no one would discover how it worked; that’s why NXP had to muzzle the Dutch researchers. But that’s just wrong. Reverse-engineering isn’t hard. Other researchers had already exposed Mifare’s lousy security. A Chinese company even sells a compatible chip. Is there any doubt that the bad guys already know about this, or will soon enough?

Publication of this attack might be expensive for NXP and its customers, but it’s good for security overall. Companies will only design security as good as their customers know to ask for. NXP’s security was so bad because customers didn’t know how to evaluate security: either they don’t know what questions to ask, or didn’t know enough to distrust the marketing answers they were given. This court ruling encourages companies to build security properly rather than relying on shoddy design and secrecy, and discourages them from promising security based on their ability to threaten researchers.

It’s unclear how this break will affect Transport for London. Cloning takes only a few seconds, and the thief only has to brush up against someone carrying a legitimate Oyster card. But it requires an RFID reader and a small piece of software which, while feasible for a techie, are too complicated for the average fare dodger. The police are likely to quickly arrest anyone who tries to sell cloned cards on any scale. TfL promises to turn off any cloned cards within 24 hours, but that will hurt the innocent victim who had his card cloned more than the thief.

The vulnerability is far more serious to the companies that use Mifare Classic as an access pass. It would be very interesting to know how NXP presented the system’s security to them.

And while these attacks only pertain to the Mifare Classic chip, it makes me suspicious of the entire product line. NXP sells a more secure chip and has another on the way, but given the number of basic cryptography mistakes NXP made with Mifare Classic, one has to wonder whether the “more secure” versions will be sufficiently so.

This essay originally appeared in the Guardian.

Posted on August 7, 2008 at 6:07 AM • View Comments

TrueCrypt's Deniable File System

Together with Tadayoshi Kohno, Steve Gribble, and three of their students at the University of Washington, I have a new paper that breaks the deniable encryption feature of TrueCrypt version 5.1a. Basically, modern operating systems leak information like mad, making deniability a very difficult requirement to satisfy.

ABSTRACT: We examine the security requirements for creating a Deniable File System (DFS), and the efficacy with which the TrueCrypt disk-encryption software meets those requirements. We find that the Windows Vista operating system itself, Microsoft Word, and Google Desktop all compromise the deniability of a TrueCrypt DFS. While staged in the context of TrueCrypt, our research highlights several fundamental challenges to the creation and use of any DFS: even when the file system may be deniable in the pure, mathematical sense, we find that the environment surrounding that file system can undermine its deniability, as well as its contents. Finally, we suggest approaches for overcoming these challenges on modern operating systems like Windows.

The students did most of the actual work. I helped with the basic ideas, and contributed the threat model. Deniability is a very hard feature to achieve.

There are several threat models against which a DFS could potentially be secure:

  • One-Time Access. The attacker has a single snapshot of the disk image. An example would be when the secret police seize Alice’s computer.
  • Intermittent Access. The attacker has several snapshots of the disk image, taken at different times. An example would be border guards who make a copy of Alice’s hard drive every time she enters or leaves the country.
  • Regular Access. The attacker has many snapshots of the disk image, taken in short intervals. An example would be if the secret police break into Alice’s apartment every day when she is away, and make a copy of the disk each time.

Since we wrote our paper, TrueCrypt released version 6.0 of its software, which claims to have addressed many of the issues we’ve uncovered. In the paper, we said:

We analyzed the most current version of TrueCrypt available at the writing of the paper, version 5.1a. We shared a draft of our paper with the TrueCrypt development team in May 2008. TrueCrypt version 6.0 was released in July 2008. We have not analyzed version 6.0, but observe that TrueCrypt v6.0 does take new steps to improve TrueCrypt’s deniability properties (e.g., via the creation of deniable operating systems, which we also recommend in Section 5). We suggest that the breadth of our results for TrueCrypt v5.1a highlight the challenges to creating deniable file systems. Given these potential challenges, we encourage the users not to blindly trust the deniability of such systems. Rather, we encourage further research evaluating the deniability of such systems, as well as research on new yet light-weight methods for improving deniability.

So we cannot break the deniability feature in TrueCrypt 6.0. But, honestly, I wouldn’t trust it.

There have been two news articles (and a Slashdot thread) about the paper.

One talks about a generalization to encrypted partitions. If you don’t encrypt the entire drive, there is the possibility—and it seems very probable—that information about the encrypted partition will leak onto the unencrypted rest of the drive. Whole disk encryption is the smartest option.

Our paper will be presented at the 3rd USENIX Workshop on Hot Topics in Security (HotSec ’08). I’ve written about deniability before.

Posted on July 18, 2008 at 6:56 AM • View Comments

1 … 39 40 41 42 43 … 55

Sidebar photo of Bruce Schneier by Joe MacInnis.