Schneier on Security
A blog covering security and security technology.
« Homomorphic Encryption |
| Using Agent-Based Simulations to Evaluate Security Systems »
September 25, 2012
Long article on quantum cryptography and cryptanalysis.
Posted on September 25, 2012 at 1:29 PM
• 11 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
QKD is fascinating, but how do they solve the authentication problem?
I think they assume a that Alice and Bob have a small shared secret, and then use a universal MAC to authenticate the keystream.
Of course it's much less useful than asymmetric authentication.
Makes me think how long it would take these super computers being built to crack the algorithm.
QKD is fascinating, but how do they solve the authentication problem?
As in real life you basicaly don't, what you do is limit the scope of the authentication.
In the case of QKD it is (currently) a "point 2 point" system this inherantly gives authentication providing you can ensure the channel is tamper proof.
You then use other methods to extend the scope of the authentication, but unless you include all parts/parties in the authentication process then you are simply "trusting" in human terms (not ITSec terms) that any point outside the suthentication scope is being honest.
In many cases it is not practicaly possible to extend the scope of the authentication process so we just cross our fingers and pretend it's OK.
@ Clive Robinson
So, if you have a tamper proof channel... Why do you need any kind of cryptography? And if your crypto algorithm needs a tamper proof channel, what is it good for?
In reality, the answer is that quantum crypto does not solve the authentication problem, and consequently is useless. All those real quantum crypto products are just snake-oil. Even if somebody gets a way to solve the authentication problem, quantum cryptography will still be way less usefull than assymetric crypto.
A point that did not come across very strongly in the article is that QKD is actually very very limited both geographicaly and in connectivity, and as such it will be constrained as a niche product at best.
That is the range of a QKD link for around a 2Kbit/Sec link is ~100Km, and it has to be a "Point to Point Single fiber". So from a practical perspective if ten parties want to use QKD they all need to be well within 100Km (probably nearer 20Km when you consider physical routing) of each other and have 45 high quality optical links over and above any other comms links.
This might be OK for a small Swiss City with a handfull of "nomes" but what about say London or New York with several thousand financial organisations at 3000 organisations you would be looking at just under 5.5million dedicated high quality optical links.
It's just not practical unless some reliable "physical switch" is developed and even if it is it opens a whole pile of cans of worms.
If you think about it, there are two basic communications charecteristics of a reliable channel that count, "bandwidth and latency". You can never have to much bandwidth or to little latency. But as we know bandwidth cost as does small latency.
If you think about it another way, the QKD link is giving you a 2K B/Sec data rate at best at 100KM which is what you had in the early 1980's with dial up modems. Over a day that gives you 21MByte/day of raw data. You could blow a DVD (4.5Gbyte) and drive it 100KM in a couple of hours, if you did that all day you'd have around two and a half thousand times the bandwidth with a 2 hour latency on the data.
Thus if latency is not an issue it's going to be a lot cheaper, a lot easier and have a much higher bandwidth to use a quantum effect random number generator to blow a few hundred gigabits of raw random data onto a couple of optical disks and get the "mail room boy" to get on his motor bike and hand deliver them.
But QKD is distance limited to ~100KM at 2Kbits/sec What about the international side of informatio? It helps if you remember the old adage of,
Never underestimate the bandwidth of a 747 fully loaded with high density optical disks
Even a large high security bag as used for diplomatic courier has a fairly amazing bandwidth just poor latency.
Appart from two way data comms latency is often not an isssue, take for instance the "back up requirment" given as an example, is latency going to be a significant issue? if not then QKD is not offering an advantage.
What if latency is an issue, you need to be clear what the latency isssue is for. Is it the keymat or the encrypted data? If it's the encrypted data (most likely) then generate the keymat at the remote depository and take it to the sight the data is generated at and encrypt the data and send in real time down an ordinary optical link. It would actually have less latency than the QKD method.
Which begs the question why go QKD to which the answer is probably "because it sounds sexy" not for any real technical reason.
I've yet to be convinced QKD is going to solve any earthly problem better than traditional key distribution methods, so in that respect I regard QKD as a "solution looking for a problem".
And as for "unearthly solutions", a direct range limit of 120KM free space is not going to get you anything other than Low Earth Orbit with orbit times down around 90mins and visability measured in a couple of mins or so if you are lucky.
So, if you have a tamper proof channel... Why do you need any kind of cryptography?
Because "tamper proof" does not mean "eavesdrop proof". It simply means it is not "susceptible to active interferance" without detection.
When we talk about communications channels we mention "path loss" that is the difference between the energy we put into the channel compared to the energy we get out at the far end.
Most people assume that because we say "path loss" we actually mean "lost along the way" rather than "given up to the environment" and this gives rise to a significant misunderstanding in that the lost energy is assumed to be just heat or some other form of incomprehensible noise that does not carry usable information.
Whilst that is "finally" true it is not true initialy, so as with the old fashioned telephone "pick ups" the energy close to the channel is cohearent and information bearing and ripe TEMPEST or EmSec source material.
The purpose of QC as I understand is that you can use the quantum channel to send a message, and you can subsequently tell if that message has been intercepted or not.
So, the message you send could be the one-time-pad for a real message which in itself has no information at all. If it is intercepted, you simply send a new one until you get one through without interception. Once you and your intended listener share a one-time-pad you can send the true message encoded using that pad, which again carries no information (besides length) over any old channel confident that the message can only be decoded by your intended listener (as only they have received the pad needed to decode it).
It would, in theory, be perfect crypto. Assuming of course that upon receipt of the pad, the listener keeps it safe, no one listening to the channels could get any information out of them, the best they could do was intercept all the pads sent over the quantum channel thus preventing communication, they could not intercept any actual information.
In reality, the answer is that quantum crypto does not solve the authentication problem, and consequently is useless. All those real quantum crypto products are just snake-oil.
The commercial quantum-crypto product from ID Quantique also employs the state-of-art classical crypto solutions (e.g. 256 bit AES) along with performing QKD. So to breach the security of such a system, you need to break a computationally-difficult classical encryption technology and a few physically-impossible quantum mechanical primitives.
Whilst any practical-minded vendor shouldn't be foolish enough to claim that they provide a secure communication device merely on the basis of quantum crypto (QC), nonetheless, QC protocols are based on rigorous mathematical and physical security proofs, so calling them snake-oil products would also be a foolish fallacy.
Even if somebody gets a way to solve the authentication problem, quantum cryptography will still be way less usefull than assymetric crypto.
Agreed that QKD has almost no chance of becoming a mainstream technology as public key cryptosystem (PKC), however, calling it (or symmetric encryption, to be more precise) useless compared to asymmetric crypto is narrow-minded and fallacious too. The advances made by quantum computing in last few years suggest that breaking "the principle behind security of assymetric/public key encryption" apart could be achieved in the next decade. In that scenario, not only would all the future security be at stake, but also, any secret data encrypted from the instant when PKC was ushered into realistic deployments, is at a huge risk.
Government/Military (and perhaps, some financial institutions as well) can quite likely not afford such an event.
@ Jay Ann,
The advances made by quantum computing in last few years suggest that breaking "the principle behind security of assymetric/public key encryption" apart could be achieved in the next decade
The next decade? it's unlikely to be in my life time or that of quite a few of the people actually working in the field. The last time I looked we were still will down in the single digits on Qbits and no real likely hood of getting them to work the right way over more than just a handfull of bits, let alone the two to four thousand bits that are quite practical with the RSA algorithm.
Further we are actually designing "quantum computer proof" crypto at a greater rate than we are quantum computing...
As I indicated above Quantum Key Distrubution has a very major issue it's point to point only it cannot be switched between devices such as a telephone can. One of the reasons monorail trains never happened except as curiosities is nobody could work out how to do points so you could switch from track to track. QKD has similar problems in that the only way to switch one endpoint for another is to change the position of the other end of a free space link so it points at a different end point...
Also as I noted we have not got the range up to where QKD can be used to Low Earth Orbit satellites all of which currently limits it's usefulness to most likely users.
Further we have "bright young things" breaking practical implementations almost before the paint has dryed on the first of the latest production device. Even grizzeled old goats such as myself are spotting ways to break the systems almost as quickly as the youngsters can set an experiment up...
At the present time QKD is of very limited range or speed it's actualy probably faster to walk/bike a one time pad on a DVD or other optical media than it is to send it via QKD around a major city...
@ Clive Robinson
Further we have "bright young things" breaking practical implementations almost before the paint has dryed on the first of the latest production device.
And not so surprizingly there are a handful of similar "bright young things" who are:
1. working on notionally very different forms of quantum cryptography, e.g., device independence, usage of semi-trusted repeater nodes, continuous variables etc.
2. sprucing up the practical side of implementations so as to achieve Gbps secret key rates in metropolitan networks (30-50 Kms); or Mbps for ~100 Kms.
3. doing exotic things such as building quantum-public-key cryptographic protocols!
Checkout these links, if you are interested:
Of course, half of these are more or less theoretical proposals and the remaining operate only in research lab testbeds as of now, but remember that the ENIAC weighed around 30 tons, took up 1800 square feet of space, and consumed 150 kW of power (source: wikipedia) ! :-)
From a realistic perspective, chances are quite high that a majority of them would not stand out until the end, however, even if a couple of them deliver, then you just cannot rule out the possibility of a radical breakthrough in practical QKD implementations; and how it would subsequently affect the commercial cryptographic framework.
Finally, breaking practical QKD implementations, in my opinion, is a cycle that any technology has to rigorously brave through, before it provides what-it-is-expected-to on an acceptable and reasonable level. The principle on which QC is based still remains intact and as long as quantum physics is a valid description of nature, one can be sure that a properly implemented QKD system works securely.
Even grizzeled old goats such as myself are spotting ways to break the systems almost as quickly as the youngsters can set an experiment up...
That sounds quite interesting. Could you perhaps share some of your (published/known) exploits ?
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.