Successful Attack Against a Quantum Cryptography System

Clever:

Quantum cryptography is often touted as being perfectly secure. It is based on the principle that you cannot make measurements of a quantum system without disturbing it. So, in theory, it is impossible for an eavesdropper to intercept a quantum encryption key without disrupting it in a noticeable way, triggering alarm bells.

Vadim Makarov at the Norwegian University of Science and Technology in Trondheim and his colleagues have now cracked it. “Our hack gave 100% knowledge of the key, with zero disturbance to the system,” he says.

[…]

The cunning part is that while blinded, Bob’s detector cannot function as a ‘quantum detector’ that distinguishes between different quantum states of incoming light. However, it does still work as a ‘classical detector’ ­ recording a bit value of 1 if it is hit by an additional bright light pulse, regardless of the quantum properties of that pulse.

That means that every time Eve intercepts a bit value of 1 from Alice, she can send a bright pulse to Bob, so that he also receives the correct signal, and is entirely unaware that his detector has been sabotaged. There is no mismatch between Eve and Bob’s readings because Eve sends Bob a classical signal, not a quantum one. As quantum cryptographic rules no longer apply, no alarm bells are triggered, says Makarov.

“We have exploited a purely technological loophole that turns a quantum cryptographic system into a classical system, without anyone noticing,” says Makarov.

Makarov and his team have demonstrated that the hack works on two commercially available systems: one sold by ID Quantique (IDQ), based in Geneva, Switzerland, and one by MagiQ Technologies, based in Boston, Massachusetts. “Once I had the systems in the lab, it took only about two months to develop a working hack,” says Makarov.

Just because something is secure in theory doesn’t mean it’s secure in practice. Or, to put it more cleverly: in theory, theory and practice are the same; but in practice, they’re very different.

The paper is here.

Tags: , , ,

Posted on September 2, 2010 at 1:46 PM • 26 Comments

Comments

James • September 2, 2010 2:10 PM

Ding Ding Ding Ding, the Titanic has sunk!

In all seriousness, nothing is perfect and people seem to forget that. There’s no easy way out for security. It takes hard work and there are no magical pills.

james • September 2, 2010 2:33 PM

“Both IDQ and MagiQ welcome the hack for exposing potential vulnerabilities in their systems”

Wow. Either the company really welcomes it or they’re grinding their teeth. If they do welcome it, maybe some good improvements will come out of this.

Otto • September 2, 2010 2:34 PM

Reading closely reveals that it’s basically an attack upon the technology, not the theory. They exploited a problem with the hardware used to detect single photons. If the hardware didn’t have this fundamental problem with it, then the exploit would not work.

James • September 2, 2010 2:46 PM

@Otto:
I suggest a shirt:
“I cracked Quantum Cryptography and all I got was this lousy pizza”

A job or some research grant would be in order 😀

You’re right that it’s an attack on the practical side, but the reality is that no system can be implemented without practical considerations.

Clive Robinson • September 2, 2010 3:41 PM

Put simply it’s a form of active EmSec or fault injection attack.

As some will remember (and the rest of you can find on previous pages on QCrypto I’ve commented on on this blog) I have very little faith in Qcrypto. Not on the theory side but the implementation side.

The people designing many of these systems appear to compleatly lack the basic crypto designer skill of being able to attack their own systems. Nor infact the simple ability to question what order parts of the system should be in to reduce the attack surface.

Thus I suspect that a very simple modification to the photo detector circuitry to detect either the bias point or standing current will reveal when a photodetector is under a simple attack such as this one.

That said for this particular attack what we need is a semiconductor physicist who is uptodate on modern photodetectors to explain the exact in’s and out’s of this attack and the effects it has on the photodetector.

But the last time I got my hands dirty with such things avalanche photo detectors were the toys of choice. Unfortunatly they have many oddities and failings (for most purposes the worst of all is the recovery time).

So I fully expect to see many more fault injection attacks on Qcrypto which are more sophisticated than this one.

I must admit I’m very tempted to stick my neck out by saying that I don’t think that a 100% secure Qcrypto system is possible with our current technology (and I’m sure there are a few out there who would place a wager on it 😉

As they say time will tell.

However QKD systems like most Qcrypto systems have a fundemental problem that they are “point to point” not “circuit switched” thus like the “monorail” it will be limited to certain niche areas.

DavidE • September 2, 2010 4:33 PM

@ aikimark

In theory, there is no difference between theory and practice.

But, in practice, there is.

Jan L.A. van de Snepscheut

magetoo • September 2, 2010 4:58 PM

“Reading closely reveals that it’s basically an attack upon the technology, not the theory.”

The theory is well established, so that’s not surprising. (Overthrowing everything we thought we knew about quantum physics would be surprising, and presumably reflected already in the headline.) 🙂

As I understand it from not reading that closely, this is similar to what the same group did last year, only now with a practical hack on two commercial products as opposed to doing the same to a research setup.

Doug Coulter • September 2, 2010 6:23 PM

Clive, the problem is, that though I’d take that wager myself — we’d both be on the same side of it, we’d have to find a sucker to wager against ;~)

aikimark • September 2, 2010 6:37 PM

I have a vague memory of an AES attack that was able to deduce internal table caching, based on the response times of many thousand encrypt requests.

moo • September 2, 2010 7:11 PM

@aikimark:
This might interest you:
http://www.rootlabs.com/articles/IEEE_SideChannelAttacks.pdf

Designing and implementing crypto systems is definitely a job for professionals. I cringe whenever I hear about some random programmer implementing his own code for AES or something, or (even worse) making up their own home-brew encryption algorithm without the assistance of an expert. A little bit of knowledge can be a dangerous thing.. for a non-professional, its very easy to create a very insecure system while deluding yourself about how secure it is.

Another example was the comment Bruce posted about skein: by tweaking a single constant value, they made a sophisticated mathematical attack impossible. Most random programmers do not have the maths background required to do something like that. They’ll design something full of potential vulnerabilities and not even realize it.

Clive Robinson • September 2, 2010 10:44 PM

@ aikimark,

“I have a vague memory of an AES attack that was… …based on the response times…”

There are several “timing side channel” attacks against many implementations of AES in software.

And at the risk of starting the misunderstandings again…

It is why I do not recomend using AES “online” if you want “assured security”, unless it is in a verified and certified system.

By “online” I mean using an implementation of AES on a system that is connected to a communications network where an attacker can either passivly monitor or activly provoke timing information that can disclose one or more key or plaintext bits.

And “assured security” is where you can have a reasonable expectation that your plaintext is not recoverable by any currently known practical
attacks.

I am not saying the AES algorithm is broken just that implementations of it are susceptable to timing attacks when in use (it appears more so than other AES candidates).

Thus my view is that AES generated ciphertext is secure BUT during the process of getting to or from ciphertext it may be insecure due to the implementation of the AES algorithm you are using.

This view point is not peculiar to me, the US NSA appear to have it with their AES based inline media encryptor when they carefully say “data at rest” when talking about it’s security clasification. And similar caution has been expressed to me by others when talking about security clasification of products.

So the advice boils down to use AES “offline” to produce ciphertext of information you wish to remain confidential. Then go “online” to send the ciphertext. And importantly even if you are using a supposedly secure channel (SSL etc) assume it is not secure and thus be circumspect in what you say / type / do.

As others have pointed out getting an “assured secure channel” for use in an open and thus hostile environment such as the Internet or HF long haul broadcast is very very expensive.

Nick P • September 2, 2010 10:47 PM

@ Clive and moo

Exactly why I’ve never recommended quantum or immature/homebrew/proprietary encryption to anyone. Existing high assurance approaches to cryptosystem design, like NSA’s Type 1 process or Praxis’ methodology, have proven effective at producing results that match their specifications. For Type 1 systems, this usually means no data leaks from hardware up to the application layer and general unhackability. These are two invariants that we can never be sure we’ve proven, but high assurance designs get very close and inspire a lot of confidence. When was the last time a skilled intelligence agency hacker broke into classified networks by exploiting a remote flaw in the Type 1 link or IP encryptor? AFAIK, never.

If the game is producing flawless systems, then this is the score…

A1/EAL7 classical systems: 8
(off top of my head & no known flaws)

Type 1 classical COMSEC: 30+
(don’t know them all but there’s a lot)

Quantum crypto: 0
(mwahahahahahahaha!!!!!)

Maybe they should just build an EAL7 link encryptor with Type 1 EMSEC and hardware protections. Then they do a cheaper EAL5 augmented certification on it, then brag about the assurance level, NSA pen testing, and the near total data leak prevention. Not only would it sell at least as well, customers would finally have a reason to be confident in their products. As it stands, I look at their offerings this way: their personnel are infected with the Plague, it has spread onto their products, and my clients should stay away to remain in good health. 😉

yt • September 3, 2010 4:47 AM

I’ve always considered quantum science to be one of those things we’re close to understanding, but haven’t quite gotten right. It makes a kind of sense internally, but we’re missing a critical piece of the puzzle to fully put it in context. One day we will look charmingly naive to future scientists.

For reference, see phlogiston theory ( http://en.wikipedia.org/wiki/Phlogiston_theory ), spontaneous generation ( http://en.wikipedia.org/wiki/Spontaneous_generation ), and other obsolete scientific theories ( http://en.wikipedia.org/wiki/Category:Obsolete_scientific_theories ).

l. • September 3, 2010 7:29 AM

First of all, thank you Bruce for linking a thing which is that old (the works were discussed last year, also presented on several confs; here it just was accepted to a peer-reviewed journal). Secondly, for the attack – yup, the APDs suck here and it is not clear wether filtering could solve the problems, last time I spoke with IDQ thay said they are working on some of these… But personally I do think that APDs should not be used here, nor the current photon guns.

Oh, and AES implementations are routinly being cracked and no one touts that AES is crippled, sucks and this is the end. I myself remember a lot of attack papers from this and last year, the one prominent thing is that based on cool single-event errors tied with theory of crypto.

@Clive Robinson: why in fact (at least IDQ) they do try to attack and cripple their own implementations by mounting both practical and theoretical attacks.
It is true that the configurations that are widely known are point-to-point, but that this is the only possible arrangement, that’s not.

John • September 3, 2010 9:00 AM

@moo:

I’ve noticed a lot of “AES can be cracked if implemented wrong” going on, and in fact RC4’s major weakness is a trivial implementation issue (you can make WEP as secure as WPA/AES).

Although I have little encryption experience, I’ve considered implementing my own crypto library. Encryption is simple enough; and really, all I need to do is get some texts (web sites etc) on IMPLEMENTATION and see what usually goes wrong. Then I can develop a strategy for implementing AES, RC4, etc in a secure, carefully designed manner; rather than “oh here’s an easy algorithm, let’s throw it into code.. yep, this fits the standard.”

A programmer wants an AES library that works, so when they wrap it in an SSL library they can get HTTPS and SSH working with it. That programmer should not be writing his own AES library. The programmer writing the AES library should want an AES library that has no severe implementation issues, but have roughly no particular use case for it.

Camfish • September 3, 2010 9:58 AM

I don’t understand why Alice and Bob totally failed to detect the attack.

So, eve, the man-in-the-middle, measures the Alice’s light polarization by positioning the detector in certain position (1 of 2 possibilities). He got about 50% correct bits, and then he blinds the Bob’s detector to turn it into a classic detector, so that Bob will receive the same set of bits as Eve’s.

The Alice and Bob then should agree on a common key through a public authentic channel (to agree on bits when Alice and Bob’s measurement equipments are synchronous). So, assume Bob positioned the detection randomly for each bit received, I think Alice and Bob will find they have only about 75% bits matching (as opposed to a theoretical 100% since the detectors’ positions are Alice’s and Bob’s are synchronous). Why Alice and Bob don’t detect this attack?

I mus have missed something. Please shred some light.

Jack • September 3, 2010 10:15 AM

@Budzeg re:”Milestone recorded. Everything will be hacked… It’s just a matter of time.”

Wrong, because this would mean your statement itself can be broken. If what you say is true, then tell me which number added to 5 is another number? And prove that the number you chose is the correct one. BTW – this problem doesn’t belong to any complexity class because it lacks verifiability. So, go ahead and break it.

David Thornley • September 3, 2010 12:13 PM

Unless we’re very wrong about some fundamentals of quantum mechanics, which is a tremendously successful scientific theory, it is possible to send information such that it cannot be reliably intercepted, and so that any attempt will be detectable. You’ll note that I didn’t say “send information reliably”: the very fragility that provides the security makes it possible for lots of things to disrupt the signal. (There’s also the question whether being able to send a quantum signal reliability would constitute enough control of the transmission so that other security wouldn’t be needed.)

From what Bruce posted, it sounds like the system uses quantum communications when it works, then degrades into a non-quantum channel, and so the plan is to break the quantum channel and watch the security degrade. This may be deliberate or a hardware issue; if Bob’s detector is just looking for photons with certain orientation, then it will receive them either if some photons of that orientation are sent, or twice the number of random photons are sent (for most quantum measurements, a photon can be in one of two states, so half of random photons would be in any detectable state).

The implementation issue is that the receiver must be able to tell if it’s getting quantum signals or not. For example, it can’t just detect whether photons are arriving in one state, it has to detect whether few or no photons are arriving in the other state, and sound the alarm if it’s getting roughly equal results from both.

Steve • September 3, 2010 5:05 PM

A simpler restatement of the clever part I heard recently:

“The difference between theory and practice? In theory, there is no difference.”

Clive Robinson • September 4, 2010 6:57 AM

@ l.,

“why in fact (at least IDQ) they do try to attack and cripple their own implementations by mounting both practical and theoretical attacks”

Well they may well do so but just looking at the photos of their equipment tells me a great deal about. What previous training and experiance they have (and more importantly have not).

I can see a couple of likely routes to investigate just from the photos, thus I predict that there will be more successfull attacks on their equipment as shown.

With regards,

“It is true that the configurations that are widely known are point-to-point, but that this is the only possible arrangement, that’s not”

In theory maybe.

What you require as a minimum is an optical switch which does not degrade in any practical way the properties of the channel or effect in any way the Qbit. But it must be capable of being able to read the “routing info” and ensuring the switched rate is comensurate with the data rate.

Which practicaly means for a non circuit switched system the switch has to read bunchs of photons coming down the fiber that provide the destination address, store this, untill it has made the determination of which way to set the switch, set the switch, inject the routing info down the chosen fiber all before the Qbit comes floating by at close to the speed of light. Not imposssible but not anywhere close to a practical thing to do currently

And yes I have thought of a number of ways you might go about it but the issue boils down to the fact that compared to the equivalent length of fiber the switch is going to add a large amount of channel distortion, this effectivly limits the number of switches you can have in series.

Untill we can find a way to “amplify” the Qbit above the distortion or significantly reduce the distortion at each switching node, the practical limit on the size of the network is not going to be much more than a city block or so (dependant on the number of nodes required for switching).

So not theoreticaly or practicaly impossible just currently limited to a smallish distance for un-switched point to point networks and getting massively reduced in range (say by -3dB or 50%) for each switch added in series.

Clive Robinson • September 4, 2010 9:36 AM

@ Nick P,

Great minds think alike and it appears from your 10:47 and my 10:44 at the same time as well 😉

@ John,

“Although I have little encryption experience, I’ve considered implementing my own crypto libray.”

Don’t bother for several reasons, the first is there are already crypto libraries out there you can use.

However many of those suffer from significant problems because the authors as you note,

“oh here’s an easy algorithm, let’s throw it into code.. yep, this fits the standard.”

But even those that have followed your proposed methodology of,

“Encryption is simple enough; and really, all I need to do is get some texts (web sites etc) on IMPLEMENTATION and see what usually goes wrong. Then I can develop a strategy for implementing AES, RC4, etc in a secure, carefully designed manner”

Have failed to produce a secure library.

The reason for this is “side channels” which have been known about accademicaly since GJ Simmons paper over a quater of a century ago with hsi “prisoner problem” that cave rise to “subliminal channels” and “covert channels” and the more general realisation of “side channels”.

If you follow the link given by @moo above you will get a good idea as to why software on a standard use computer can never realy be considered secure.

For a more indepth look at how one time based covert channel has been implemented and a usefull set of refrences have a look at,

http://web.mit.edu/~greenie/Public/petspaper.pdf

The simple fact is as I keep saying “the more efficient you make it the less secure it is likley to be.

Removing time based side channels on a general PC motherboard and standard OS is as close to impossible as you are likely to get

Even Gus Simmons failed with a protocol for digital signitures he designed that he thought was free of subliminal channels ( http://doi.ieeecomputersociety.org/10.1109/CSFW.1996.503702 ).

But if after all of this you think you can do it please feel free to try you might be the first to succeed.

Robert • September 4, 2010 9:21 PM

@David,
It seems to me that a fragile channel like this must have many viable covert sub channels.

The basic problem is that there is a finite probability of the photon being detected so even a perfect link must assume and overcome channel noise. A simple Covert channel can therefore be coded by intentionally adding channel errors.

The normal fix for this type of suspected covert channel is too “fail long and fail hard” however such a solution for a quantum channel would mean that it never functioned. Adding FEC just creates another level of sub channel working within the FEC algorithm.

Of course all of this ignores the fundamental timing channel that exists within any discrete event system, so you are back to needing ultra-high precision timing TX/RX signal generators for the electronics. But even after this there remains a property of optical Fibers called, polarization mode dispersion, which can be easily manipulated by inducing stress on the fiber. A qbit will not get dispersed but rather an arrival timing jitter will be induced “which creates a great sub channel”

Thinking about it a little more, I’d say that intentional fiber stress to create PM dispersion is probably the best way to create a sub channel. It it very easy to gradually increase the induced timing jitter and thereby infer the RX sample window width.

Nick P • September 5, 2010 10:50 PM

@ Clive Robinson

“Great minds think alike and it appears from your 10:47 and my 10:44 at the same time as well ;)”

I noticed. It was kind of a strange feeling that we were both slamming the topic at the same time. I had the unfortunate experience of a very delayed post. It didn’t appear until way later. May have been moderated for some unknown reason… (or a slow server)

It may have been my statements about the superior appearance of the octopus that put the Schneier regime on full-scale alert, moderating my posts. 😛

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.