Entries Tagged "quantum cryptography"

Page 2 of 2

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.

Posted on September 22, 2009 at 2:00 PMView Comments

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

Switzerland Protects its Vote with Quantum Cryptography

This is so silly I wasn’t going to even bother blogging about it. But the sheer number of news stories has made me change my mind.

Basically, the Swiss company ID Quantique convinced the Swiss government to use quantum cryptography to protect vote transmissions during their October 21 election. It was a great publicity stunt, and the news articles were filled with hyperbole: how the “unbreakable” encryption will ensure the integrity of the election, how this will protect the election against hacking, and so on.

Complete idiocy. There are many serious security threats to voting systems, especially paperless touch-screen voting systems, but they’re not centered around the transmission of votes from the voting site to the central tabulating office. The software in the voting machines themselves is a much bigger threat, one that quantum cryptography doesn’t solve in the least.

Moving data from point A to point B securely is one of the easiest security problems we have. Conventional encryption works great. PGP, SSL, SSH could all be used to solve this problem, as could pretty much any good VPN software package; there’s no need to use quantum crypto for this at all. Software security, OS security, network security, and user security are much harder security problems; and quantum crypto doesn’t even begin to address them.

So, congratulations to ID Quantique for a nice publicity stunt. But did they actually increase the security of the Swiss election? Doubtful.

Posted on October 29, 2007 at 6:02 AMView Comments

More on Kish's Encryption Scheme

Back in 2005, I wrote about Laszlo Kish’s encryption scheme, which promises the security of quantum encryption using thermal noise. I found, and continue to find, the research fascinating — although I don’t have the electrical engineering expertise to know whether or not it’s secure.

There have been developments. Kish has a new paper that not only describes a physical demonstration of the scheme, but also addresses many of the criticisms of his earlier work. And Feng Hao has a new paper that claims the scheme is totally insecure.

Again, I don’t have the EE background to know who’s right. But this is exactly the sort of back-and-forth I want to see.

Posted on June 11, 2007 at 6:49 AMView Comments

Quantum Computation Research Center in Singapore

Singapore is setting up a $98M research center for quantum computation.

Great news, but what in the world does this quote mean?

Professor Artur Ekert, Director, Research Centre of Excellence, said: “At the moment, you can buy quantum cryptography systems, you can use it in some simple applications but somehow you have to trust companies that sell it to you or you have to test the equipment.

“The kind of quantum cryptography we develop here is probably the most sophisticated that is not available in any other countries so we have some ideas to make it so secure that you don’t even have to trust equipment that you could buy from a vendor.”

Posted on May 10, 2007 at 1:08 PMView Comments

Classical Crypto with Lasers

I simply don’t have the physics background to evaluate this:

Scheuer and Yariv’s concept for key distribution involves establishing a laser oscillation between the two users, who each decide how to reflect the light at their end by choosing one of three mirrors that peak at different frequencies.

Before a key is exchanged, the users reset the system by using the first mirror. Then they both randomly select a bit (either 1 or 0) and choose the corresponding mirror out of the other two, causing the lasing properties (wavelength and intensity) to shift in accordance with the mirror they chose. Because each user knows his or her own bit, they can determine the value of each other’s bits; but an eavesdropper, who doesn’t know either bit, could only figure out the correlation between bits, but not the bits themselves. Similar to quantum key distribution systems, the bit exchange is successful in about 50% of the cases.

“For a nice analogy, consider a very large ‘justice scale’ where Alice is at one side and Bob is at the other,” said Scheuer. “Both Alice and Bob have a set of two weights (say one pound representing ‘0’ and two pounds representing ‘1’). To exchange a bit, Alice and Bob randomly select a bit and put the corresponding weight on the scales. If they pick different bits, the scales will tilt toward the heavy weight, thus indicating who picked ‘1’ and who picked ‘0.’ If however, they choose the same bit, the scales will remain balanced, regardless whether they (both) picked ‘0’ or ‘1.’ These bits can be used for the key because Eve, who in this analogy can only observe the tilt of the scales, cannot deduce the exchanged bit (in the previous case, Eve could deduce the bits). Of course, there are some differences between the laser concept and the scales analogy: in the laser system, the successful bit exchanges occur when Alice and Bob pick opposite bits, and not identical; also, there is the third state needed for resetting the laser, etc. But the underlying concept is the same: the system uses some symmetry properties to ‘calculate’ the correlation between the bits selected in each side, and it reveals only the correlation. For Alice and Bob, this is enough–but not for Eve.”

But this quote gives me pause:

Although users can’t easily detect an eavesdropper here, the system increases the difficulty of eavesdropping “almost arbitrarily,” making detecting eavesdroppers almost unnecessary.

EDITED TO ADD (11/6): Here’s the paper.

Posted on November 6, 2006 at 7:49 AMView Comments

Totally Secure Classical Communications?

My eighth Wired column:

How would you feel if you invested millions of dollars in quantum cryptography, and then learned that you could do the same thing with a few 25-cent Radio Shack components?

I’m exaggerating a little here, but if a new idea out of Texas A&M University turns out to be secure, we’ve come close.

Earlier this month, Laszlo Kish proposed securing a communications link, like a phone or computer line, with a pair of resistors. By adding electronic noise, or using the natural thermal noise of the resistors — called “Johnson noise” — Kish can prevent eavesdroppers from listening in.

In the blue-sky field of quantum cryptography, the strange physics of the subatomic world are harnessed to create a secure, unbreakable communications channel between two points. Kish’s research is intriguing, in part, because it uses the simpler properties of classic physics — the stuff you learned in high school — to achieve the same results.

At least, that’s the theory.

I go on to describe how the system works, and then discuss the security:

There hasn’t been enough analysis. I certainly don’t know enough electrical engineering to know whether there is any clever way to eavesdrop on Kish’s scheme. And I’m sure Kish doesn’t know enough security to know that, either. The physics and stochastic mathematics look good, but all sorts of security problems crop up when you try to actually build and operate something like this.

It’s definitely an idea worth exploring, and it’ll take people with expertise in both security and electrical engineering to fully vet the system.

There are practical problems with the system, though. The bandwidth the system can handle appears very limited. The paper gives the bandwidth-distance product as 2 x 106 meter-Hz. This means that over a 1-kilometer link, you can only send at 2,000 bps. A dialup modem from 1985 is faster. Even with a fat 500-pair cable you’re still limited to 1 million bps over 1 kilometer.

And multi-wire cables have their own problems; there are all sorts of cable-capacitance and cross-talk issues with that sort of link. Phone companies really hate those high-density cables, because of how long it takes to terminate or splice them.

Even more basic: It’s vulnerable to man-in-the-middle attacks. Someone who can intercept and modify messages in transit can break the security. This means you need an authenticated channel to make it work — a link that guarantees you’re talking to the person you think you’re talking to. How often in the real world do we have a wire that is authenticated but not confidential? Not very often.

Generally, if you can eavesdrop you can also mount active attacks. But this scheme only defends against passive eavesdropping.

For those keeping score, that’s four practical problems: It’s only link encryption and not end-to-end, it’s bandwidth-limited (but may be enough for key exchange), it works best for short ranges and it requires authentication to make it work. I can envision some specialized circumstances where this might be useful, but they’re few and far between.

But quantum key distributions have the same problems. Basically, if Kish’s scheme is secure, it’s superior to quantum communications in every respect: price, maintenance, speed, vibration, thermal resistance and so on.

Both this and the quantum solution share another problem, however; they’re solutions looking for a problem. In the realm of security, encryption is the one thing we already do pretty well. Focusing on encryption is like sticking a tall stake in the ground and hoping the enemy runs right into it, instead of building a wide wall.

Arguing about whether this kind of thing is more secure than AES — the United States’ national encryption standard — is like arguing about whether the stake should be a mile tall or a mile and a half tall. However tall it is, the enemy is going to go around the stake.

Software security, network security, operating system security, user interface — these are the hard security problems. Replacing AES with this kind of thing won’t make anything more secure, because all the other parts of the security system are so much worse.

This is not to belittle the research. I think information-theoretic security is important, regardless of practicality. And I’m thrilled that an easy-to-build classical system can work as well as a sexy, media-hyped quantum cryptosystem. But don’t throw away your crypto software yet.

Here’s the press release, here’s the paper, and here’s the Slashdot thread.

EDITED TO ADD (1/31): Here’s an interesting rebuttal.

Posted on December 15, 2005 at 6:13 AMView Comments

News

Last month I wrote: “Long and interesting review of Windows XP SP2, including a list of missed opportunities for increased security. Worth reading: The Register.” Be sure you read this follow-up as well:
The Register

The author of the Sasser worm has been arrested:
Computerworld
The Register
And been offered a job:
Australian IT

Interesting essay on the psychology of terrorist alerts:
Philip Zimbardo

Encrypted e-mail client for the Treo:
Treo Central

The Honeynet Project is publishing a bi-annual CD-ROM and newsletter. If you’re involved in honeynets, it’s definitely worth getting. And even if you’re not, it’s worth supporting this endeavor.
Honeynet

CIO Magazine has published a survey of corporate information security. I have some issues with the survey, but it’s worth reading.
IT Security

At the Illinois State Capitol, someone shot an unarmed security guard and fled. The security upgrade after the incident is — get ready — to change the building admittance policy from a “check IDs” procedure to a “sign in” procedure. First off, identity checking does not increase security. And secondly, why do they think that an attacker would be willing to forge/steal an identification card, but would be unwilling to sign their name on a clipboard?
The Guardian

Neat research: a quantum-encrypted TCP/IP network:
MetroWest Daily News
Slashdot
And NEC has its own quantum cryptography research results:
InfoWorld

Security story about the U.S. embassy in New Zealand. It’s a good lesson about the pitfalls of not thinking beyond the immediate problem.
The Dominion

The future of worms:
Computerworld

Teacher arrested after a bookmark is called a concealed weapon:
St. Petersburg Times
Remember all those other things you can bring on an aircraft that can knock people unconscious: handbags, laptop computers, hardcover books. And that dental floss can be used as a garrote. And, and, oh…you get the idea.

Seems you can open Kryptonite bicycle locks with the cap from a plastic pen. The attack works on what locksmiths call the “impressioning” principle. Tubular locks are especially vulnerable to this because all the pins are exposed, and tools that require little skill to use can be relatively unsophisticated. There have been commercial locksmithing products to do this to circular locks for a long time. Once you get the feel for how to do it, it’s pretty easy. I find Kryptonite’s proposed solution — swapping for a smaller diameter lock so a particular brand of pen won’t work — to be especially amusing.
Indystar.com
Wired
Bikeforums

I often talk about how most firewalls are ineffective because they’re not configured properly. Here’s some research on firewall configuration:
IEEE Computer

Reading RFID tags from three feet away:
Computerworld

AOL is offering two-factor authentication services. It’s not free: $10 plus $2 per month. It’s an RSA Security token, with a number that changes every 60 seconds.
PC World

Counter-terrorism has its own snake oil:
Quantum Sleeper

Posted on October 1, 2004 at 9:40 PMView Comments

News

Last month I wrote: “Long and interesting review of Windows XP SP2, including a list of missed opportunities for increased security. Worth reading: The Register.” Be sure you read this follow-up as well:
The Register

The author of the Sasser worm has been arrested:
Computerworld
The Register
And been offered a job:
Australian IT

Interesting essay on the psychology of terrorist alerts:
Philip Zimbardo

Encrypted e-mail client for the Treo:
Treo Central

The Honeynet Project is publishing a bi-annual CD-ROM and newsletter. If you’re involved in honeynets, it’s definitely worth getting. And even if you’re not, it’s worth supporting this endeavor.
Honeynet

CIO Magazine has published a survey of corporate information security. I have some issues with the survey, but it’s worth reading.
IT Security

At the Illinois State Capitol, someone shot an unarmed security guard and fled. The security upgrade after the incident is — get ready — to change the building admittance policy from a “check IDs” procedure to a “sign in” procedure. First off, identity checking does not increase security. And secondly, why do they think that an attacker would be willing to forge/steal an identification card, but would be unwilling to sign their name on a clipboard?
The Guardian

Neat research: a quantum-encrypted TCP/IP network:
MetroWest Daily News
Slashdot
And NEC has its own quantum cryptography research results:
InfoWorld

Security story about the U.S. embassy in New Zealand. It’s a good lesson about the pitfalls of not thinking beyond the immediate problem.
The Dominion

The future of worms:
Computerworld

Teacher arrested after a bookmark is called a concealed weapon:
St. Petersburg Times
Remember all those other things you can bring on an aircraft that can knock people unconscious: handbags, laptop computers, hardcover books. And that dental floss can be used as a garrote. And, and, oh…you get the idea.

Seems you can open Kryptonite bicycle locks with the cap from a plastic pen. The attack works on what locksmiths call the “impressioning” principle. Tubular locks are especially vulnerable to this because all the pins are exposed, and tools that require little skill to use can be relatively unsophisticated. There have been commercial locksmithing products to do this to circular locks for a long time. Once you get the feel for how to do it, it’s pretty easy. I find Kryptonite’s proposed solution — swapping for a smaller diameter lock so a particular brand of pen won’t work — to be especially amusing.
Indystar.com
Wired
Bikeforums

I often talk about how most firewalls are ineffective because they’re not configured properly. Here’s some research on firewall configuration:
IEEE Computer

Reading RFID tags from three feet away:
Computerworld

AOL is offering two-factor authentication services. It’s not free: $10 plus $2 per month. It’s an RSA Security token, with a number that changes every 60 seconds.
PC World

Counter-terrorism has its own snake oil:
Quantum Sleeper

Posted on October 1, 2004 at 9:40 PMView Comments

Sidebar photo of Bruce Schneier by Joe MacInnis.