Tuesday, October 14, 2008

Quantum Snake Oil

Seeing things like this happen makes me sad about the security industry:

Massive Quantum Network Unveiled

I could devote an entire blog just to debunking Quantum Cryptography. Back in 2005 I worked with a team to evaluate if Quantum Cryptography was a technology that was worth investing in. My recommendation was a resounding no. Since then I have to say that my answer hasn't changed.

First some background. To get a general understanding of Quantum crypto, you need to know that it works on the idea of probability. If Bob sends a message to Alice she will only be able to receive 50% of that message. If Mallory is sitting in the middle and intercepts the message, he also only gets 50% of the message, but due to the fact that Bob is sending photons instead of 1's and 0's Mallory can not resend the entire message to Alice. So the best Mallory can do is send 50% of the message on, and then fill in the other 50% with random gibberish. This means that Alice will only be able to get around 25% of the actual message from Bob, (50% of 50%). If Alice sees her error rate go up, she knows that someone is tapping the line. How does this work? Magic. Honestly, it really doesn't matter due to all the problems with the fundamentals of Quantum Crypto.

First, let's assume that this link is totally unbreakable. That's not true....

Laser cracks 'unbreakable' quantum communications

But still, I'm not ready to argue quantum mechanics with a physics major so I'll give them that. The problem is that quantum crypto also relies on an out of band channel that at best uses traditional crypto to communicate which bits were received on the quantum channel. That channel is still subject to normal attacks. In fact, since the companies making quantum crypto devices are so focused on the "Gee Whiz we're using photons", they have been badly neglecting this side channel, making their implementations much weaker than traditional VPNs

Quantum Cryptography: Researchers Break 'Unbreakable' Crypto

That being said, even if Quantum Crypto was "unbreakable" the costs of it are huge. The boxes themselves are not the problem, but running dedicated fiber lines between the different sites is horribly expensive. A much cheaper solution would be to hire a trusted person to take a stack of Cd's, (or heck spluge on BlueRay), filled with AES keys to the different sites, and just cycle through a new key a minute. I guess what I'm trying to say is traditional crypto has been banged away at for a long time by some really smart people and been found to be secure if used correctly, (admittedly a big if). Quantum crypto has not. Just because it sounds like magic does not mean you should trust it.

As a side note, it annoys me when people say that Quantum Crypto was developed as a response to Quantum Computers. A marketing response yes, but it is not a technology response. Quantum Computers have the potential to break certain algorithms like RSA faster than traditional computers. People realized that, and as Quantum Computers become more mature, you might not want to rely on RSA. Algorithms like AES on the other hand are no more vulnerable to Quantum computing than traditional computing. Quantum Computers, while nice for certain tasks, will not be a win button for crypto breaking.


emonemo said...

hey bro. I briefly looked up AES and it appears that quantum computers will be able to break it. i mean, assuming we are using a 256 bit encryption, it would take a conventional computer 2^256 operations to crack it with a brute force attack. but a 256 bit quantum com could break it in 1 cycle. a 252 bit QC would take 4 operations. and so on. unless key lengths become astronomicaly long QC will crack them exponentially faster than conventional computers. i must admit i do not fully understand quantum cryptography (i understand the physical principle, just not the challenges in its implementation.) i dont see why a global network, much like that used for the net, cant be used. and if interception is detected, the communication can be rerouted.

Matt Weir said...

Hey, thanks for the response. From my understanding, the current proposed quantum attack against AES encryption uses Grover's algorithm. A better write-up of the results of this type of attack can be found at the very bottom of this Wikipedia article on key size. I love Wikipedia ;) What this means is that while traditional cryptography would take O(2^n) to crack AES, the best quantum computers can do is crack it in O(2^n/2), or in AES's case O(2^128). Now while a 128 bit key is not ideal, (aka 3DES's key is effectively only 112 bits long), it still is strong even if we assume that quantum computers are performing operations at a comparable speed to traditional computers. Barring a major breakthrough it will take years for that to happen and the solution is to simply double the key size, (aka create a version of AES that uses 512 bit keys). A much better summary is given is given by Robert Hanson, (no not the spy), here

I admit that I was guilty of an overstatement by saying that AES was "no more vulnerable to Quantum computing vs. traditional computing", since the reduction in key size by half is a significant difference. That being said, I still stand by my belief though that symmetric cryptography can stand up to quantum computing.

Going back to the original point about quantum cryptography, (which is very different from quantum computing), currently it only deals with key exchange, not the encryption of the actual messages. It uses normal symmetric key crypto for that. For augment’s sake, disregarding that, all of the security for quantum crypto is based on the idea that an attacker cannot intercept the data without the error rate going up. There have been numerous demonstrated attacks though that show that's not true. Attackers don't play fair. From shining light down the cable in order to detect the current polarization of the defenders systems, to attacking the authentication and then performing a man in the middle attack, quantum crypto has been shown to be vulnerable to attack. The second attack really is nasty since quantum crypto doesn’t do anything “unbreakable” for authentication. In the best case, just like with the diffie hellman protocol, while you might have a secure connection, without the use of other authentication schemes you have no idea who you are actually talking to.

Also, Quantum crypto is just not scalable. Currently there is no way to switch/route the quantum channel which limits its usefulness quite a bit, (aka you can’t deploy it to do key exchange over the internet unless you had direct line connections between every user of the network). At that point, it just because easier to do a physical key exchange.

Short summary: Quantum Computing = good but not magic. Quantum Cryptography = not worth it

I apologize for this long rambling reply, and I just wanted to say once again thank you for your response. I’ve been wrong about a lot of things before, and quite simply there’s a decent chance I’m wrong about this. Feel free to point me to any additional links/resources which might steer me in the right direction, and please continue to call BS on me in the future.

On a different note, I’m currently working with a master’s student who’s looking for a project, and I’m always on the lookout for new ideas as well. If you have any suggestions of security tools that need updating, (or a demand for a security tool that doesn’t exist), we’d love to hear it. Thanks ;)

emonemo said...

Matt, i read about the 256 divide by 2 thing on wiki after i posted and was like dank! i commented wrongly on that dudes post. (sorry!)

i had the same reaction when i saw a comment made on Mr Schneier's article [http://www.schneier.com/blog/archives/2008/10/quantum_cryptog.html] which pointed out quantum crypto needed point to point connections and also the intensity fell by half after a relatively small distance of transmission . (perhaps these are simply engineering problems?)

also, from what little reading i have done, it appears that so far the only method developed is that of light polarization. but quantum effects become observable on any sufficiently small particle. perhaps entanglement can be used to communicate in the future? or other more secure methods, which have a much simpler and cheaper implementation than thousands of kilometres of optical fibre cables. time will tell i guess.

i have to pretty much agree with what you have said (thanks for your long comment, it cleared up a number of things. and sorry for clicking on the 'disagree' button haha). That wiki article was a major eye opener. i no longer view quantum computers as invincible.

i'm doing an undergrad in electrical engin at imperial college london. I am workin on a project on the future of privacy.

will keep you posted if i come across anything exciting.