Quantum Encryption

November 9, 2006 7:25 AM

Quantum Encryption Scientists have created an unbreakable cypher through the use of quantum physics, where a photon is observed and used as the basis for an encryption key. "Uncertainty is the principle we exploit. It's impossible to find the key, because the photon can be measured once and only once. An eavesdropper can't measure it, and so can't get the key." Props to Heisenberg!
posted by PreacherTom (49 comments total)

unbreakable cypher

I know very little about encryption, but this seems like it has to be an overstatement, right?
posted by dead_ at 7:32 AM on November 9, 2006

Quantum mechanics and cryptology. Great. Two subjects that give me a headache separately are now linked.

Tip for investors: Buy Tylenol futures.
posted by mr_crash_davis at 7:38 AM on November 9, 2006 [1 favorite]

Some more readings on Quantum Encryption
posted by falconred at 7:39 AM on November 9, 2006

this seems like it has to be an overstatement, right?

It would be except we don't have quantum computers to break that cypher, so for now, it's unbreakable.
posted by splatta at 7:45 AM on November 9, 2006

quantum computers won't help you break quantum encryption. in fact, nothing will, short of finding a hole in quantum mechanics that no one has noticed yet.
posted by paradroid at 7:47 AM on November 9, 2006

In a stroke of profound unoriginality, I'm going to note that Chuck Norris has already broken this cypher.
posted by horsewithnoname at 7:48 AM on November 9, 2006 [2 favorites]

While I realize this has been written for a not-so-technical crowd, do we really need to open the proceedings with the same goddamned platitudes? Can you ever be absolutely certain, for example, that the e-mail you're sending with some confidential business information attached isn't going to be intercepted and read as it travels the digital highways and byways? No, asshole, you can't, but maybe our digital vehicles, piloted by quantum pioneers, can be secured against information super-pirates!

I also enjoy the veiled indignation: 'Secure as it is, Quantum Crypto is only being slowly adopted by governments and industry.' Yeah, guys, I'm totally sold on its impregnability, based on the strong assurances given by the CEO of MagiQ! The entire history of crypto consists of a series of hubristic statements made by parties with a personal stake in the matter, which are later proven to be laughably wrong by the mathematical community. I see no innate reason to believe this will fall into the 1% that stands up to the attacks, despite the hand-waving of 'it's QUANTUM physics, there doesn't need to be any mathematical soundness!'

I haven't done as much reading on quantum crypto as I'd like to (thanks for the linkage, falconred), but sweet Jesus, presenting it in a fashion that causes the computer science AND quantum physics communities to develop nervous tics is not the way...
posted by Mayor West at 7:50 AM on November 9, 2006 [1 favorite]

Mayor West, this quantum mechanic thinks it is sound.
posted by fatllama at 7:53 AM on November 9, 2006

It is good that quantum encryption seems to be coming into use first, as it would provide a challenge even to a quantum computer. If quantum computers were to arrive before quantum encryption, essentially all the encryption in use today would be useless, and all our sensitive data would be open.

quantum computers won't help you break quantum encryption. in fact, nothing will, short of finding a hole in quantum mechanics that no one has noticed yet.

Would I be wrong in assuming that a quantum computer could still be used to brute force any encryption, quantum or not? Is factoring primes not useful for breaking quantum encryption?
posted by splatta at 7:57 AM on November 9, 2006

Word Up, Mayor West.

There's more to security, and encryption, than the algorithm used. Quantum crypto is very cool, and very interesting. It would be foolish for anyone to use it for Something That Really Mattered today.
posted by These Premises Are Alarmed at 8:01 AM on November 9, 2006

The encryption they'll be using is a one time pad scheme. This means it can decrypt to all plaintexts of the same length as your message, so you cannot decrypt it, no matter how much time you spend - you'll never be sure you decrypted it to the message that was originally sent and not any of the other gazillions of messages they might have sent. OTPs are usable today, but the key exchange problem makes them generally unusable. The quantum bit resolves the key exchange by making sure you know when someone listened in on the connection between you and the person you are communicating with.
posted by edd at 8:04 AM on November 9, 2006 [1 favorite]

Given that most security breaches these days come from exploiting software bugs and human factors, spending oodles of cash on making your links impregnable might not be the best use of your money.
This is only really worth investing in if those who want your data have the resources to tap your fibres and conceivably have the supercomputing power or the mathematical brainbank to conceivably break your conventional crypto. Which basically means the US government. Hence the press-release driven efforts to try to drum um a little uninformed business.
posted by Luddite at 8:06 AM on November 9, 2006

Meh. Too much conception and um is up. Cursed keyboard rot.
posted by Luddite at 8:07 AM on November 9, 2006

The entire history of crypto consists of a series of hubristic statements made by parties with a personal stake in the matter, which are later proven to be laughably wrong by the mathematical community.

I dunno. Most of the actual crypto people I've read are quite insistent that there's no such thing as 'unbreakable' -- just 'hard to break' and 'impractical using current technology.'

My impression is that Quantum Crypto is different because someone breaking it would change the nature of the message itself, at the very least tipping off all the involved parties that something's wrong. That's a big leap in and of itself.

Am I confused? Anyone? Bueller?
posted by verb at 8:08 AM on November 9, 2006

the unbreakability of quantum encryption comes from the fact that you can't observe a quantum state without changing it. so breaking this is not a computational problem, it is a physics problem.

also, we do not know how to break all classical encryption, just ones that relate to factoring, and nobody has a quantum computer large enough or reliable enough (by far) to actually crack anything. yet.
posted by paradroid at 8:08 AM on November 9, 2006

This doesn't solve any crypto problem except where both ends of the communication are physically secure and you have this very special kind of pipe between them. This doesn't begin to cover all the uses for crypto, not even a large subset of them.

By contrast, public key encryption handles the case where only one end of the communication is physically secure, which means it can be used in the field, which this system certainly can't be.
posted by George_Spiggott at 8:10 AM on November 9, 2006

Women have been using one time pads for quite some time. I never knew that was why I couldn't understand them.
posted by srboisvert at 8:14 AM on November 9, 2006 [2 favorites]

On reflection, I overstated that a bit. Even PK encryption does require both ends to be secure, it's just that one end can't reveal the key itself -- it can certainly leak any communication which uses it.
posted by George_Spiggott at 8:19 AM on November 9, 2006

Mayor_West wrote...
The entire history of crypto consists of a series of hubristic statements made by parties with a personal stake in the matter, which are later proven to be laughably wrong by the mathematical community.

Ding ding ding! We have a winner!


As for the "It's physically impossible..." argument, does anyone else remember how Shannon's Limit was used to definitely state that [2400, 9600, 19200, 33k, 56k] baud was the fastest possible modem speed?

Physics wonks do not have a good track record here...
posted by tkolar at 8:19 AM on November 9, 2006

We already have public key cryptography with key sizes long enough to make them "practically unbreakable" for the next hundred years. The issue is not with decyphering the stream, but using social engineering to obtain the key.

The MagiQ system would get around that due to the fact that you'd need to have a custom system set up at each end in order to send anything encrypted. This is its strength, but also its weakness. This system will need to be deployed basically everywhere for you to be able to send messages reliably with it, otherwise you'd need to fall back to an older "less-secure" system when not in base or whatever.
posted by Imperfect at 8:20 AM on November 9, 2006

OK, on further review, I'm willing to cede that this might very well be 'unbreakable,' in the traditional sense: it's effectively a means of solving the distribution problem of one-time pads, which are absolutely secure, assuming your random number generator is up to snuff. But, like George_Spiggott said, I think I'd be happier with public-key crypto that can be used over any communication network, at least until someone demonstrates a quantum computer that can handle more than 3 bits. It sounds like the logistics behind a quantum distribution scheme are godawful, with limitations imposed by physical properties of particles. Once we have the infrastructure in place, and there's reason to believe that the current mechanisms are failing, then sure, quantum entangle away.
posted by Mayor West at 8:22 AM on November 9, 2006

Breaking conventional crypto, Young says, is essentially a mathematical problem that involves factoring very large prime numbers.

I see this "factoring primes" terminology every now and then, and I don't get it. Can someone explain to me what it means to factor a prime? I assume they mean something along the lines of "factoring very large composite numbers" or "finding very large prime factors", but since I know roughly zero about encryption, I'm speculating. Anyone want to throw me a bone?
posted by dilettanti at 8:43 AM on November 9, 2006

It means "given a number known to be a composite of two large primes, what are those primes?"
posted by sonofsamiam at 8:50 AM on November 9, 2006

Anyone want to throw me a bone?

Take two very large primes, and multiply them together. The resulting number is extremely large, and has only two factors, each of which is prime. It would take years of calculations on a supercomputer to factor such a number.

Quantum encryption is different because observation changes the information. If you want a good summary, read The Code Book, by Simon Singh.
posted by weapons-grade pandemonium at 8:52 AM on November 9, 2006

RSA encryption vs. quantum encryption.
posted by weapons-grade pandemonium at 8:56 AM on November 9, 2006

A better way to put it is that breaking quantum encryption is not even theoretically possible, for the reasons that edd noted.

Normal cryptography involves adding "random noise" to your message that is actually anything but. If I know the algorithm and seed that you used to generate your "noise," I can perfectly reproduce your message. I can find your seed value and turn ABCDE FGHIJ KL back into IAMTH EEGGM AN, because I know that your noise is really completely determined by a complex mathematical function. I can also test to see whether there's a different seed value that would turn the plaintext IAMTHE WALRU S1 into ABCDE FGHIJ KL, and I can test other messages to see if the same seed value that decoded this message also decodes other ones into nongibberish.

But if I adding real honest to God pure random noise to my signal, there's no way to decode it unless you happen to have the same random noise that I do. I can't know whether your message is IAMTH EEGGM AN or IAMTH EWALRU S1 or 9MATH OWIES UX, because there is some set of random noise that you can add to each of them to turn them into the ABCDE FGHIJ KL that I see. Quantum cryptography is just a way for you and I to share the same set of random noise with some assurance that other people haven't snooped in on our random noise. It's not quantum cryptography that's not even crackable in theory, it's one-time pads.*

There are still lots of ways I could read your message, including bribing or threatening you, putting software on your machine, Van Eyck phreaking your display, etc. But the transmission itself would be perfectly secure.

*assuming the one-time pads are truly random. If the pad-generating process is not purely random, I might be able to use statistical juju to start guessing at your message.
posted by ROU_Xenophobe at 9:04 AM on November 9, 2006

A few people have already pointed out the real limitation of quantum encryption ---the need for a special link between the two computers. It's also worth noting that it's inherently a transmission scheme, as opposed to a storage scheme. It's too difficult to keep pure quantum states for long periods of time, so there's no practical way to encrypt a file with quantum encryption and save the encrypted file to your hard drive (or do anything similar to that).
posted by Humanzee at 9:22 AM on November 9, 2006

Bah, encryption became too hard for me to crack years ago. Now I just rely on the time honored tradition of convincing one of the parties to give me the key.

And let me tell you; A pair of handcuffs, a wedge of sharp cheddar cheese , a hedge-trimmer, a porcupine, and 2 tubes of KY jelly are more than enough to convince most people.

Though I do get strange looks when I go through the airport.
posted by quin at 9:37 AM on November 9, 2006

As for the "It's physically impossible..." argument, does anyone else remember how Shannon's Limit was used to definitely state that [2400, 9600, 19200, 33k, 56k] baud was the fastest possible modem speed?

Shannon's Law, from my understanding, is absolute. There are NO cases where it has been disproved. Your claim that it somehow didn't hold just means you didn't understand the claims that were made.

The claims as I recall them were: using a carrier on a telco voice signal, there is a maximum number of bits that can be transmitted per second. (I don't remember what the specific number actually is.) By using compression, we can invest CPU time on either end to make it appear that we're sending more bits, but we're not. We're just stripping out extraneous information, and sending only what we need. That's why modems stalled at 53.4K. All the easy gains from compression had already been gotten. Further CPU upgrades would have massively increased modem cost and heat, without giving much benefit in terms of actual throughput. To go further, they needed telco upgrades, and the telcos didn't go that route. So all "56k" modems will do, at best, 53.4K.

If you use a different signal method, like cable or DSL, which are using different frequency bands, then the limits are enormously higher. You appear to be claiming that the existence of DSL disproves Shannon, which is simply wrong. A DSL 'modem' isn't a modem; that's just a shorthand term for a very different technology. They weren't claiming you couldn't send data faster than any arbitrary number; they were saying that you couldn't go faster using that specific type of carrier. And you can't. That's an absolute limit.

As far as quantum encryption goes: this allows you to share bits between two end points that are secured by a special, short-range fiber optic line, and be absolutely certain that you and the recipient are the only people who read those bits. If anyone else eavesdrops, it changes the signal in a detectable way. This doesn't affect copying the bits once they're in the machines, or hacking into the system in some other way. All this technology means is that the bits cannot be invisibly intercepted in transit. Eavesdropping is always detectable.

As far as we understand, this is absolute. If these bits could be read undetectably, it would upend all of physics. An intercepted message would, at a single stroke, disprove quantum mechanics.

Encryption is already very strong, however, so in essence this is making the strong link of the chain absolutely unbreakable. It doesn't affect the things that are likely to actually be attacked. People, for instance, tend to use key passwords that are much weaker than the encryption itself, making their messages fairly easy to crack by a sophisticated entity. Even a one-time-pad system is crackable if you can get the key.

This advance just means attackers can't snoop keys off the wire. They'll have to get them out of permanent storage somewhere.
posted by Malor at 9:52 AM on November 9, 2006

I'm familiar with the theories of quantum cryptography, however I have a question about the system described in the BusinessWeek article:

The two boxes then compare how the photon appeared when it left the first box to how it appears when it arrived at the second. If they match, the photon is used to generate a key, which is used to encrypt the data. If they don't match, the photon is ignored.

How does someone at the receiving end know what the state of the photon was when it left the first box? In other words, how does the recipient know that the photon received was from the sender and not someone who is physically intercepting the original photons and sending their own stream?
posted by justkevin at 10:19 AM on November 9, 2006

There are some interesting alternatives to quantum encryption that may more cheaply provide the same results: a dedicated line which cannot be snooped on.

There are several groups working on using fiber-optic links to try to reproduce the quantum encryption effect, but the one I like the best is Kish's idea: twiddle variable resistors at both ends of the wire and make sure nobody is screwing with the current. It may be more sensitive than QE, too, in that an eavesdropper could be discovered more quickly.

Here are articles which cite Kish's article.
posted by sonofsamiam at 10:27 AM on November 9, 2006

Malor, you're close, but not quite there about the CPU time issue as regarding phone lines. The fact is that Shannon's Law states that you can only send up to a certain bandwidth (I think its 9.6kbaud) on a telephone line no matter what. However, notice I said "baud" instead of "bit". This distinction is important. Baud measures the "symbol rate". So, lets say you can only send at 9,600 symbols per second: would you rather send binary states (0 vs. 1) or, say, hexadecimal states (0 through f)?

This trick requires that you are able to distinguish between sixteen separate states on the line. 56k modems do it by varying both amplitude and phase of the signal. They are imaged as constellation diagrams. Unfortunately that diagram is a little thick for lay readers (hell, I'm an EE, spent several classes learning this stuff and it was thick to me!) — just remember that signals with equal amplitude would fall on a circle and going around the circle delays the phase (i.e. your sine wave could start at 0 and going up to mean "0", 1 and going down to mean "1", 0 and going down to mean "2", and -1 and going up to mean "3").

Is this clear? I do hope so (but unfortunately, I can't say I expect so)!
posted by Xoder at 10:33 AM on November 9, 2006

Of course this will be broken in a few months by some adolescent Latvian hacker working with a 386, a DIY particle accelerator and smallish Bose-Einstein condensate trap made out of a few dozen fifty cent laser diodes.

The upside is that in the process of hacking the QNP this kid will discover how a workable method of teleportation as well as a time machine.

A small - yet long overdue - footnote will be added to history at this point indicating that nothing inspires progress and invention like the challenge brought by any claim of "you can't do this", however, history books quickly became useless with the advent of time-tourism and all that nasty businss of people going back in time to sex up their ancestors. For shame, future humankind, for shame!
posted by loquacious at 10:39 AM on November 9, 2006

Also, if I'm reading/interpreting the Wikipedia entry and the article itself, quatnum encryption is still vulnerable to certain kinds of "man in the middle" and/or interception attacks.

The article mentions daisy-chaining a series of QPNs to increase distance, which is more-or-less exactly one of the methods of doing a "man in the middle" attack on quantum encryption. (Example: A wants to send a quantum-encrypted message directly to B, but both A and B are unaware that their physical link (and/or physical security) have been comprimised by C, who has installed his own pair of compatible quantum encryption devices in between A and B. A transmits to C, who re-encrypts and re-transmits to B, and vice-versa when B transmits back to A through C.

A and B remain unaware that they've been attacked and that they aren't actually receiving each other's true keys - as it is impossible to inspect the true state of the keys without destroying them - and they just assume that they're receiving the encrypted messages as they were sent.

As someone who has previously worked in a supposedly secure data center, that's a whole hell of a lot of faith to be placing on the physical security layer.

At this point, I can only assume it would be more effective to be researching and developing more secure physical locks.
posted by loquacious at 11:11 AM on November 9, 2006

verb writes "Most of the actual crypto people I've read are quite insistent that there's no such thing as 'unbreakable' -- just 'hard to break' and 'impractical using current technology.'"

OTPs, done correctly, are 100% secure in transit, proveably so. You could post a copy of every message you send to the NSA and they still couldn't decypher the plain text. The only attacks are at the encryption/decryption stages (IE: TEMPEST or simple black bag jobs to determine the pad or substitute your good random number generator with a not so random generator). If they haven't compromised your pad, your test is safe.

Imperfect writes "We already have public key cryptography with key sizes long enough to make them 'practically unbreakable' for the next hundred years."

Assuming no one figures out a shortcut to factoring large prime numbers.
posted by Mitheral at 12:30 PM on November 9, 2006

Malor nailed it. The value of a quantum encryption system is not necessarily in unbreakability but in protection from man-in-the-middle attacks *even over otherwise public networks*.

The solution to the problem loquacious poses is entanglement, I think :) Someone is certainly welcome to correct me.

It seems also that timing synchronization could be a solution to that problem. A typical man-in-the-middle attack can be performed just by on siphoning off of a datastream, with no significant delay. Continual re-encryption would be problematic, no?
posted by spiderwire at 12:38 PM on November 9, 2006

Just wanted to second the above suggestion of The Code Book.

Also, two points:

1) quantum computing and quantum cryptography are wholly unrelated.

2) In quantum crypto, you still need some kind of "traditional" cipher. Once a key has been sent, and both parties are satisfied that it has not been observed, messages may be sent under that key. Further, the receiving party will also be aware of the message being observed.
posted by butterstick at 1:34 PM on November 9, 2006

It seems also that timing synchronization could be a solution to that problem. A typical man-in-the-middle attack can be performed just by on siphoning off of a datastream, with no significant delay. Continual re-encryption would be problematic, no?

Well, I'm no cryptologist, I'm just some guy with half a brain, y'know?

But the man in the middle attack as indicated in the Wikipedia entry should be immune to timing problems with this particular form of quantum encryption, which as I read it neither uses entanglement nor precise timing in its encryption scheme.

Keep in mind that this attack uses a method that assumes A) A physical compromise of the physical optical link and B) using identical (or fully compatible) equipment to provide the man-in-the-middle point on the network.

However, even when using techniques of polarization, timing and even perhaps entanglement it may be vulnerable to the "bright light" attack, which floods the optical circuit with light via a physical injection, which may reveal information about the state(s) of the quantum encryption device by way of a very slight reflection.

(In the "bright light" attack on an entanglement-aware cryptosystem, the attack would have to involve passing ones own entangled photons as though they originated at the authorized source. Polarization could be revealed by reflection. Timing could be spoofed by originating the "authorized" signal, or it could also be spoofed by introducing timing lags in the physical layer elsewhere to account for the timing lags on your own compromised leg.)


The bottom line is that any system - especially any system self-touted as "unbreakable" - should be considered breakable. We know how to brute-force break RSA, DES and very nearly any crypto out there - it just takes a non-trivial amount of time. And as time marches on and computers become more powerful, that "non-trivial" amount of time required to break existing mathematical crypto systems becomes shorter.

Which is one reason why we need to keep inventing stronger crypto - the battle is never going to be "won". Ever.

That said, quantum crypto may be strong. On a secured link, it may indeed be unbreakable.

But ultimately - after all is said and done - there is absolutely no such fiction as "secure". It doesn't exist.

If you can make it, it can be broken. If you can make a key and a lock, it can be also be taken apart. If you publish or implement your product, it can be reverse engineered.

If there isn't a theory or axiom for this principle, there should be. There's no such thing as security, computer security or otherwise.

Anything that claims to be "secure" or appears to be "secure" is merely a temporary illusion of security.
posted by loquacious at 1:53 PM on November 9, 2006

loq: entanglement still works. two entangled electrons at the destination locations would be perfectly secure -- the MITM attack you're discussing requires some level of spoofing, which can't be done with an entangled electron -- by that i mean using entangled electrons at different locations to essentially generate perfect OTPs. this is not what the article is discussing though, i think.

as for timing, if you timestamped the transmissions, then unless the circuit was compromised *before* you started timestamping, the time it would take to reencrypt a long key would be noticeable and raise a red flag, i would think. there wouldn't be any way around that. this assumes that the timestamps themselves were encrypted.

the quantum computing point is in that regard *not* unrelated, as you could in theory break "conventional" crypto fast enough that you might be able to avoid any timing-based protection.
posted by spiderwire at 2:53 PM on November 9, 2006

But the man in the middle attack as indicated in the Wikipedia entry should be immune to timing problems with this particular form of quantum encryption, which as I read it neither uses entanglement nor precise timing in its encryption scheme.

i realize that you're aware of the point that i'm trying to make, but timing just seems like a pretty trivial correction to make to account for the objection you're raising, you know? i mean, as long as we've gotten a big quantum-encryption system set up, we'd probably have the resources to incorporate a trivial synch system.
posted by spiderwire at 2:56 PM on November 9, 2006

loquacious: We know how to brute-force break RSA, DES and very nearly any crypto out there - it just takes a non-trivial amount of time. And as time marches on and computers become more powerful, that "non-trivial" amount of time required to break existing mathematical crypto systems becomes shorter.

On the other hand...

Computer science can place some theoretical limits on how an ideal computer would operate. You can't have cycles smaller than Plank time, we know the average minimum number of cycles required to brute-force AES or DES. So it's possible to say that a problem might require more time than we have until the heat death of the universe, or more processing units than atoms in the universe.

Of course, it's possible there might something shorter than a brute force attack.

And, ideal one-time pads have been proven to be unbreakable. The flaw in one-time pads is that it's very difficult to make or securely transport them.
posted by KirkJobSluder at 3:32 PM on November 9, 2006

KJS: that, however, assumes that you're using a Turing machine. again, we don't want to confuse quantum computing and quantum encryption in a thread like this, but those limitations do not apply to quantum computers.

also, as loquacious points out, the computability projections assume a pure brute-force attack. many of the algorithms have been, and more will be in the future, so that's probably an even less reliable assumption.
posted by spiderwire at 3:44 PM on November 9, 2006

Nifty. So technically it’s not really a cypher... or am I missing something.
====================
posted by Smedleyman at 4:01 PM on November 9, 2006

Think of it as a mechanism laid on top of a cipher, like a watermark or a seal. The idea is that if someone looks at the key, the observation changes the key (basic quantum mechanics) in transit and breaks the encoding on the other end.
posted by spiderwire at 4:17 PM on November 9, 2006

Thanks
posted by Smedleyman at 4:52 PM on November 9, 2006

g5s[=-jkgyt76jhlggdy73glki009'/.[yrreewsahiit7e4'#
posted by Joeforking at 5:06 PM on November 9, 2006

Yeah, but it's a nice house.
posted by spiderwire at 7:01 PM on November 9, 2006

That's what she said.
posted by blue_beetle at 1:39 PM on November 10, 2006

Malor wrote...
You appear to be claiming that the existence of DSL disproves Shannon,

[Late response]

No, I'm saying that Shannon's Limit was used inappropriately to make incorrect claims about the maximum speed of modems. Repeatedly.

As you so aptly pointed out, Shannon's Limit was not meant to give a maximum number of bits that a modem can pass over a phone wire. It just sounded close enough that it was subject to repeated misuse.

(And believe me, there was no misunderstanding. People literally claimed that there would never be a modem faster than 2400 baud because of Shannon's Limit.)


More importantly, the history of science is full of people who proved things to be impossible only to find out later that their underlying assumptions were wrong.

Given how little hard data we actually have about quantum phenomena, anyone staking their livelyhood on the idea that we completely understand what's going on at that level is taking a hell of a gamble.
posted by tkolar at 9:32 PM on November 19, 2006