Schneier on Security
A blog covering security and security technology.
« "In Case of Terrorist Attack, Do Not Discard Brain" |
| ID Cards for Port Workers »
October 21, 2008
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 AM
• 77 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
I think his basic statement is valid:
IF "quantum computing becomes commonplace" THEN "hackers will use the technology to crack conventional encryption".
If the premise never comes true (and its certainly not anytime soon) then the branch never gets taken.
But I believe that the following analagous statement would still be true:
IF "*.* becomes commonplace" THEN "hackers will use the technology to crack conventional encryption".
Simply replacing the wildcard with QC does not alter its validity, merely narrows the scope (stipulating that since the original subject was computing we are still talking about computing). It could be any noun in the wildcard; "electronic dancing zebras" or "pistachio flavored microprocessors" but as long as they have come into common use (in computing) then I foresee no way that hackers would not use them to break encryption.
So basically what we see here is the seminal disingenuous politicians statement: A string of phonemes which cause camera/reporter time to be dedicated to them and with cursory glance they appear to have said something but when analyzed semantically its a null statement.
I have been reading some past presentations lately by Roger Schell, a leading contributor to the TCSEC Orange Book. He is a staunch advocate for the need for assurance at the system/network levels, echoing your comments about crypto being the strongest link in the chain. Without them, he describes cryptography as an "opiate of the naive".
We do not know if quantum encryption makes evesdropping impossible. Because it's claims are based on our knowledge of physics, which might never be complete. Also, it is possible to evesdrop on some bits without disturbing them.
See this article on quantum cloning:
Here’s one thing I don’t understand about quantum crypto:
Surely it’s susceptible to denial of service attacks? Whenever there’s eavesdropping going on, the channel is compromised and cannot be used. So, all Eve has to do is flood the channel with as much eavesdropping noise as she can muster, thus rendering the channel unusable?
"Surely it’s susceptible to denial of service attacks?"
All media are susceptible to DoS attacks.
"Whenever there’s eavesdropping going on, the channel is compromised and cannot be used."
No, the channel is not compromised. The bits that were eavesdropped, however, are unusable and must be retransmitted.
You missed the two biggest Achilles heals of Quantum Cryptography,
1, It has to be point to point (ie you cannot switch it, and the fiber needs to be continuous)
2, It will always have a limited range (due to the laws of physiscs).
The first point means you have to effectivly pull cable from point A to B... which is not something you want to be doing for a number of reasons primarily because of cost and secondly more importantly you may not be allowed to in your juresdiction...
The second point is one that is not mentioned much. Basicaly if you put 100 photons into a fiber at some distance only 50 of them will make it to the end of the fiber. If the fiber is double that length then only 25 photons get there and so on. this goes by various names but is usually called transmission loss. You can improve it quite a lot but at the end of the day it is always going to limit your transmission range.
It has a secondary effect, that is it is random in nature as to which photons dissapear in transit. Which means that you cannot tell the difference between transmission loss and somebody randomly stealing your photons (or injecting them under certain conditions).
Which qives rise to a secondary problem,
In a QCrypt system that uses a true random bit generator at both ends to set the state of the polarisers random sampaling by Eve would be an inconveniance that reduces the bandwidth between Alice and Bob.
But what happens when your random number generator is not truly random?
What if it used a deterministic algorithm?
In this case Eve can (theoreticaly) break the system in that it is weekend to the detectability of the two random generators. If Eve guesses their sequence then it enables her to spoof the system at a low level.
Quantum transmission makes undetected eavesdropping impossible. Since what gets transmitted safely is the one-time pad, detected eavesdropping has no effect.
Wiesner claimed that there might be a way to eavesdrop on more information than the initial paper suggested, by dealing with multiple photons as a unit.
Surely the whole point of encrypting your data is that you no longer care whether there's an eavesdropper?
Well, first of all, bob:
IF quantum computing becomes commonplace" OR "some mathematical advance in number factorization takes place" THEN...
Second, Clive Robinson:
1. You don't need a single fiber from A to B, you just need an optical path.
2. Its range is limited... until the development of quantum repeaters.
By the way, there are two more companies selling quantum key distribution devices: idQuantique and SmartQuantum.
"Security is a chain; it's as strong as the weakest link."
Security is not something that you just dump something on. It's not a big truck. It's a series of tubes. And if you don't understand, those tubes can leak and if they leak, when you put your message in, it comes back out and it's going to be readable by anyone; enormous amounts of material, enormous amounts of material will be leaked.
@bob (first post): I like your logic analysis, but I must say that *.* is so MS-DOS.
With the way the modern media works, you are NOBODY until the media misquote you. Be grateful Bruce!
QE tries to solve the key exchange problem. ie replace the public key system. As noted above it can't become common place due to the physical limitations.
Also quantum computers appear to make some problems easier to solve. But making the computer becomes "np-hard". There are plenty of papers (well a few) that claim even if its all sunshine and roses then Mores law for quantum computing will be linear (in qbits) at best. Some have even claimed that Quantum decoherence will give a finite upper bound on the number of qbits possible.
Time will tell
"1. You don't need a single fiber from A to B, you just need an optical path."
True, but problem 2 is generaly worse for the Earths "pure air" than it is for good graded index glass. Also there is the problem of less predictable changes in polarisation etc.
I know there have been experiments with modified laser diode sources up to high altitude aircraft some years ago and I assume the SatRecon bods and friends will have tried an experiment or two either from LEO or GSO (in theory that mirror stuck up on the moon back during a moon walk would work).
Sat to sat has some interesting possibilities but even in what constitutes as GSO, range is still limited by the fact that space is neither a vacum or devoid of matter of various sized chunks (and then there is the "non point radiator" issue of the photon source).
But at the end of the day commercial use is going to be ground based and limited to 50K or so as the crow flies at the moment due to various practical issues and the effective bit rate dropping with distance (not sure what the companies claim the distance/rate is currently).
I cannot deny that now the distance is a problem, but as I said quantum repeaters (possible in theory and very difficult in practice with today's technology) will end with this restriction.
In Vienna currently there is an experimental link of more than 80 km (if I remember well). In the air, I remember the Canary Islands (Spain) experiment, with entangled sources over 144 km. I should have the references somewhere...
I recommend everybody to see the video from the SecoQC presentation:
Well, nobody could say that it is the perfect solution, but anyway is a valid solution for key growing.
> Eavesdropping via spyware or Trojan
> or TEMPEST would still be possible
... and is more common nowadays anyway, unless you're the NSA.
You can't have a quantum repeater. The best you could have would be a quantum relay; A and B use one encrypted channel, B and C use another. A repeater is, by definition, an eavesdropper.
And (more to the point) if you have a relay, you have a weak point that pretty much makes the whole shebang as secure as non-quantum cryptography. Suborning the relay gives you a way to slurp plaintext out of the stream.
edit that last and start the first sentence with, "As far as I understand it..."
I'm no expert on qc.
@ Pat Calahan
A quantum repeater is not an eavesdropper. Based on quantum entanglement you can have untrusted repeaters.
See for example:
With today's technology the most we can get is a trusted relay, with the problems we all know.
Correct me if I'm wrong, but I seem to recall seeing a news article just in the past week (possibly in New Scientist, I don't recall for sure) describing a MITM attack by which Chuck can listen in on Ava's and Brian's quantum-encrypted conversation without their knowledge by disrupting their initial handshake and stepping in himself. Ring any bells...?
(The regular cast are on vacation this week.)
It was even worse when it was reported that a quantum encryption system had made a Swiss election more secure:
Elections get rigged in lots of ways, but most of them probably don't involve tampering with communication between polling stations and central tabulation centres. Even if some attacks use that vector, adding quantum encryption only strengthens overall security by a small increment. Paying more people to watch ballot boxes and ballot counters would probably have a greater security impact.
Good point. The point is not if quantum Crypto works, but if its a good allocation of cash.
No competent Rovian will allow the problem to even get to the ballot box and cast a vote to begin with.
In this mad American system where you can become ineligible to vote for so many reasons and onerous requirements to be "registered", and no legal mandate to vote (like Singapore or Australia), all it takes is pre-emptive challenges to a voter's eligibility, and a reasonably run voter suppression campaign.
Nothing like mailing known (name your party) voters you are working against mildly threatening cards asking if they are really qualified (convicted of crimes, etc.), and then, just see which one comes back as undeliverable, and challenge them.
Or just have someone dressed in what looks like police / law enforcement officials at the booth pre-emptively challenge every single black male in front of TV cameras, (statistically, the odds of them being ineligible to vote is pretty good) accusing them of being.....
Who needs to interfere with the voting booth transmission link?
American is probably the only place in the world that advertises itself as a "democracy" when probably 60%+ of all black males of legal age are either ineligible or not registered to vote, or do not turn up to vote at all.
There are other developments in quantum physics that are far, far more important.
Poke your head in nwdocfinder.com/7126 to see what terrible shape the whole field of security is in. These gurus don't even realize how bad they sound. I have attended several security related functions this year and came away with a solid impression security is almost devoid of innovation. It is the same old stuff over and over and over again. Booths manned by talking heads who couldn't care less about anything but keeping their jobs.
How many use complaince as the beginning and end of everything? Then there are all the ten ton policy-based solutions. And most is simply added on and has to be incorporated into another something that is actually trying to enable people to do their jobs. In other words security isn't inherent.
I'm trying to count in my head the number of sales people who wanted me to think that owners are always aware of data breaches having occurred. Yeah, right. And how many spit out encryption this and encryption that to make it sound good. And there are the micro improvements that are rebundled and repackaged to produce a new product.
But more than anything else, this is all anyone knows. Without exception, everyone thinks the current state of affairs is just the way it is and there is nothing else. So, just deal with it. Can I show you our new appliance that starts at $20,000 and you only have to hire two more IT people. No? How about our new enterprise Email software that assumes the guy in IT that controls it all can ALWAYS be trusted, but NONE of my remote workers can ever be trusted. No? How about the black box that moves all passwords and keys to a single Fort Knox server? Yeah, passwords controlling passwords controlling passwords. Just don't forget to pick a good one ... say, twenty characters long and then change it every couple days. Now, be sure and don't forget what it is.
I worked as part of a team to evaluate the benefits of quantum crypto a couple of years ago. What most people forget is that quantum crypto uses a side channel to transmit which parts of the key exchange it was able to receive. That side channel is protected by normal crypto. A Swiss research team a year ago found one of the quantum crypto manufactures wasn't even bothering to encrypt this side channel, making it trivial to figure out what the key was.
Then there is the cost factor. As mentioned above, the transmission problem is really hard to solve, so it will probably remain a lot more cost effective to just send a trusted courier with a stack of CDs, (or BlueRay if you want to get fancy), filled with AES keys to the remote site, and then just cycle through the different keys periodically.
In short, quantum crypto is probably LESS secure than traditional crypto, and costs more. Not a good combination...
You can actually see a much longer write-up at my blog http://reusablesec.blogspot.com/2008/10/...
Keith Harrison is either clueless or monstrously misquoted. I don't see how this could possibly help consumers "know their own transactions and daily business is [sic] secure."
Is every consumer going to have a dedicated optical channel going to every possible vendor? I can't even get the local telco or cable provider to run one multiplexed fiber to my house.
Someone's been in the lab too long.
"(In the 80s, the NSA broke Soviet one-time-pad systems because the Soviets reused the pad.)"
Wouldn't reusing the pad make it no longer a one-time pad by definition?
My main problem with quantum cryptography is the name. "Quantum transmission" would be a much better description. Cryptography is about communicating securely over an insecure channel; quantum 'crypto' is an extremely high-tech way of creating a secure channel. They are almost polar opposites of each other.
The freedom of democracy also includes the freedom not to exercise your rights, and absention from voting is effectively the same thing as voting with the winning party.
That said, the biggest problems in voting is establishing a one-to-one correspondence between voter and vote. So far, I have yet to see a solution that does not involve people verifying identities manually, and with humans being the weakest link in virtually all security systems, this bothers me. However, it bothers me less than allowing computers to determine voting results without human intervention. Even assuming that humans are making 2% error rates, the results of most elections are not in that much doubt.
S: How about our new enterprise Email software that assumes the guy in IT that controls it all can ALWAYS be trusted, but NONE of my remote workers can ever be trusted.
Preach it brother. I had the head of IT tell me that his vpn solution was better than mine because it was an "enterprise" solution! I barely kept from laughing in his face.
There are people who seriously think that a huge network with an "enterprise" ssl connection from the outside --- using passwords common to email, databases, etc, --- with an it department full of folks with passwords to it, which is usable from kiosks, without any internal firewalls is safer than a small network with a properly setup ipsec certificate solution with only a few point of entry, because of the magic word "enterprise" -- i.e., it's someone elses problem!
Anyone who even uses the word "enterprise" as meaningful should be condemned to life in the dungeons of Cobol.
Quantum transmission solves a narrow problem: *passive* eavesdropping. Sure, if you shine a light that's weak enough, the eavesdropper can only intercept *all* of the light (at any given time), and so cannot listen without being detected.
This of course does nothing to protect against *active* eavesdropping. The attacker simply needs his own reveiver and transmitter. To defeat that, Quantum transmission falls back on pre-existing shared secrets, which hardly makes it a breakthrough in key exchange.
Skorj: that's not actually true. A big part of the point is that because it's not possible to measure both of two parameters of the photon, only one or the other, then it's impossible for your "active" eavesdropper to reproduce the signal correctly once they've received it. No pre-existing shared secret needed; the necessary agreement on which measurements to keep can be made over an authenticated but not secret public channel after the fact.
You say you can't see any commercial value in it, but that's because you are thinking as a security professional, and not a salesman. This product allows companies to truthfully claim to have an product with unbreakable encryption, and have no chance of a lawsuit for false advertising. While people's perceptions of the situation are poor, companies can still take advantage of the situation to make a dollar (which lets face it, that's the only reason most companies exist). If I may be so bold, I would suggest that it is more accurate to say there is no current technical necessity for such a product, since accurately-implemented encryption products are not tractable at the moment.
The side channel does not need to be encrypted, just authenticated. The key distillation process is public.
The courier with DVDs has a huge problem: you have to securely store these keys until they are used. The quantum key "grows" before its use.
Quantum cryptography just replaces the key distribution problem. After that, you have to use one-time-pad (if you don't need high throughput) or another symmetric conventional algorithm (AES...). It is in an early stage of development, so talking about expensive devices, IMHO, is not a good argument. Of course, this problem was solved more than 30 years ago with PKI, but based on mathematical "speculations". The big deal with QKD (QKG, from Quantum Key Growing, is a more accurate name) is that you can actually have a well defined and measurable security threshold. Maybe it will not replace PK, but I think that it deserves some money for research.
"cryptography is already sufficiently secure"
cool. i like that much better than how you said it in this post:
"the encryption algorithm is not particularly relevant to security"
much better now. thanks!
"cryptography is already sufficiently secure"
I'm tempted to say that AES in a properly designed system is likley to be more secure than the overall security of the QCrypt systems currently available.
The actuall QCrypt system I have looked at with test kit and some others I've seen system design notes for just don't give me confidence.
For instance a QCrypt main channel is used to establish an OTP cipher between the parties.
An OTP is at the end of the day just another stream cipher irespective of how you "grow it and communicate it".
And it is known that stream ciphers have issues with bit flipping and lack of MAC etc.
Then there is the side channel which although not required (in the current versions of QCrypt) to be secure does require to be 100% authenticated.
Therefore you have one (theoreticaly) 100% secure but un-authenticated and un-reliable channel, and one (theoreticaly) 100% authenticated, reliable but in-secure side channel.
That is the two channels are effectivly the oposit of each other and at best are only loseley connected with each other.
And in the case of the main channel the QCrypt system has additional issues to do with timing and data loss.
But the two almost unrelated channels are used to communicate an OTP that will have some further unspecified protocol encrypted by it...
I've yet to see a convincing argument that,
1, the same problems that face conventional OTP/stream cipher systems do not apply to the QCrypt system.
2, Further that there "can be no way" that Eve can exploit the differences in the communications paths to her advantage either by weakening the 100% secure or 100% authentication aspects of the individual channels.
3, And fianaly having potentialy gained a small advantage, that Eve cannot then multiply the effects of the small advantage due to a poor choice of (un-specified) protocol...
My gut just has a bad time of beliving that a practical QCrypt system is going to address more than one or two of these areas, let alone all of them.
If the above is not clear please blaim it on the fact that I've been up and about for the last 21hours and may not be as coherant as I might otherwise be 8(
Just curious but how big is the key storage problem? For someone to gain access to the keys, it seems like they would either have to have an attacker on the inside, or have already compromised the system. In either case, Quantum Crypto doesn't sound like it would mitigate the problem as you are already pretty screwed...
And Edit, You were right, I should have said authentication, not encryption when it comes to the side channel.
There is a difference in technicalities here.
I fundamentally agree with you that there is (and should be) a right to cast an abstention as a ballot.
The difference is, in systems like Singapore and Australia, your option to do that is done after you show up to vote, go into the voting booth, and at that point, can either destroy the ballot, or deface it, or do whatever you want including voting for any or all of the candidates.
However, to show up, to receive a ballot and make it inside the booth is mandatory with very few exceptions.
By forcing such participation, it ensures that tactics that are widely practiced in the US - voter suppression / turnout, denying people the vote, etc. are not used.
I think that this research at IBM from years ago shows that a man in the middle attack is at least theoretically possible against quantum computing. They overcame the uncertainty principle. This was done 15 years ago.
I should have written against 'Quantum Cryptography' not 'quantum computing'.
That is the point. You cannot measure the security in the DVD courier scenario. If the Q-key is obtained just before it is used, you can minimize this problem (although not completely avoid it).
@Martin Duffy & others
An eavesdropping is possible in QKD. You can have different attacks based on quantum phisics principles. The benefits of quantum key distribution is that you can measure the limit of information that Eve can have of the key, and then make a privacy amplification on this key to extract the entropy shared between Alice and Bob.
Once more, I have to say that I don't think that QKD is a perfect solution to the key distribution problem. But it can't be denied that it is better than PKI in some aspects and worse in other (maybe too many). But saying that QC does not deserve to be researched is like saying that is stupid to research in car security because the biggest problem is driving under the alcohol effects.
@Seth Breidbart: if you can transmit a pad that way why wouldn't you transmit the message itself duh ! One time pad in this case is thoroughly useless.
@ Martin Duffy,
"They overcame the uncertainty principle. This was done 15 years ago"
From the article you linked to the essential argument is,
"In brief, they found a way to scan out part of the information from an object A , which one wishes to teleport, while causing the remaining, unscanned, part of the information to pass, via the Einstein-Podolsky-Rosen effect, into another object C which has never been in contact with A"
Which has a diagram which shows two information paths, particles BC being "quantum entangled" and "the scan of particle A".
The question is does "the scan of particle A" provide Eve with all the information required (and as presented it's the only information Eve can duplicate) to break QCrypts main channel?
I think you will find on reflection that Eve needs another piece of information which is the state of Alice's polariser...
Which according to the original QCrypts model is not available to Eve untill after Bob has measured the photon, by which time it is to late.
The only two gaurenties that Eve can not know the state of Alice's polariser are,
1, Alice must use a truly random state selection process (ie 100% non determanistic).
2, The state information cannot be leaked to Eve befor Bob has scaned the photon (ie a "side channel" / TEMPEST attack is 100% not possible).
And it is on those two assumptions that the original QCrypt model rests.
Both of which are very unsound assumptions,
As we know TEMPEST side channels occur in just about every bit of classic crypto kit and even with all the TEMPEST protection for "known side channels" there are new side channels being discovered all the time (black swan anybody?)...
True random number generators (TRNGs) are bassed on the noise in physical processes such as "Thermal noise", "Galactic Background noise", "time between particals in radioisotope decay", "time differences between movment of physical objects". And all practical implementations have one thing in common, they are "Oh so Slow".
That is the true random bit rate from a TRNG is orders of magnitude below anything vaugely usefull in a communications network. So how do you get the desired bit rate of random data?
Simple you take your True Random bits from your TRNG and use them to perturb a pesudo random but 100% determanistic generator (PRNG). That is you "spread your entropy" across many pesudo random bits which gives rise to the notion of "entropy spread ratio" that is the number True to Pesudo bits.
It sounds good but it cannot in reality work Shannon amongst others has shown that beyond doubt.
You cannot manufacture entropy with a determanistic process as a simple thought excercies will show,
What you are doing is taking a 100% "known data" stream and mixing it with a 100% "unknown data" stream. The easiest way to do this is by bit inversion of the "known data" stream.
That is, your "entropy spreader" is effectivly a simple stream cipher.
Shannon showed that the only secure stream cipher (the One Time Pad) must have as much "unknown data" (key) as "known data" (message) to be 100% secure.
Therefore the only two things an attacker needs to know to 100% break an "entropy spreader" is the state and method of the PRNG.
Kerkhoff's principle states "The enemy knows the system" so the whole security of an "entropy spreader" relies on the attacker not knowing the state of the "entropy pool" or "State array" etc of the PRNG.
Worse because in the "entropy spreader" each TRNG bit is used more than once and the attaker knows the PRNG used the state of the PRNG becomes 100% known.
That is any "entropy spreader" takes a 100% unknown or True random bit source and makes it 100% known to the attacker...
The only real way to up the bit rate of True random bit generators is to run multiple ones in at the same time and mix their outputs together in some manner where the failiure of one TRNG does not effect the others.
But there is a gotcher, nothing works in true isolation. In a practical implementation you run the risk of the TRNGs influencing each other or falling into synchronisation.
That is via an implementation side channel such as the powersupply, the "noise energy" from one TRNG effects the other TRNGs or "noise energy" from another source affects the TRNGs.
And if going down the radio active decay path as one researcher once joked "at modern data rates you'd need your own personal mini sun"
As Bruce is only to well aware all crypto systems quantum included have an "elephant in the room". That is their security relies an a source of True Randomnes and a bunch of assumptions only and nothing else.
Lose or break the True Randomnes and you have only assumptions of security...
@Nyhm: True, but "*" is very hard to read and I dont believe it makes the "Im a universal wildcard" statement quite as intensely.
@n: So? Thats probably about the same percentage, or higher, as white males, or black females who vote in the US. Isnt an average turnout here something like 21% of eligible?
And frankly I dont care how many people vote, or what color they are. Quality is more important that quantity. We dont get better candidates just because more people vote. If anything the opposite is true.
"Go Vote Right NOW!" drives are counterproductive. If you are so uninterested in the political process that someone has to tell you to vote and you are too lazy to go to register ONCE as a separate trip, or even if you dont know where the library is (back when I registered you could ONLY do it at the library or the BoE) then its very likely that you are NOT aware of the issues or any given candidate's ACTUAL position (rather than what the guy driving your bus told you his position is because he gets paid to deliver votes) on said issues and consequently your presence probably doesnt significantly increase the value of the process; more likely it decreases it.
Similarly, if you are not intelligent enough to poke a pre-perforated hole out of a piece of cardboard with a sharp implement designed for the purpose while the cardboard is held in a jig also designed for THAT purpose, then you probably aren't the one who should be deciding the future of the country anyway.
Robert Heinlein suggested that rather than age/race/gender/other as determining factors for who should get to vote, perhaps have a quadratic equation pop up on the screen and you have to solve it within one minute. So the smart 13 year old black girl gets to vote while the 52 year old white guy who inherited his position as CEO and cant balance a checkbook without an accountant does not. I'd rather see that as a franchise determinant than simply the fact that you were on the earth while it completed 18 orbits without you contributing anything at all to the process.
@ Martin Duffy,
Oh one thing I forgot to ask / mention.
In the IBM article (you mentioned,) only one set of quantum bits (Qbits) where entangled (and would have come from Eve in the attack).
Ask yourself the following,
1, What would the effect be if Alice used a pair of entangled Qbits AA´ and retained A´ for her own use?
2, What would be the effect of Eve using a pair of entangled Qbits EE´ to measure alices sent Qbit A?
This is the field of play QCrypt has moved into since the original QCrypt model.
So as Sherlock Holms used to say "Watson! the game is still afoot!".
One of the few joys ot the UK National Health Service's endemic "hurry up and wait" system is you have plenty of time to do little else but think or sleep.
And you daren't do the latter as you might miss your name being called, "Sorry Nurse was that my name?"...
"So the smart 13 year old black girl gets to vote while the 52 year old white guy who inherited his position as CEO and cant balance a checkbook without an accountant does not."
Appears to be a nice idea however it has a problem,
The 52 year old CEO does not care if he votes or not!
Because unlike the smart 13 year old, he has the knowledge and money to buy the politicians opinion after the election...
Which is what I realy realy hate about "representational democracy", it just positivly encorages corruption by politicians who know that the only punishment the "representational democracy" system reserves for them is the posibility they won't get re-elected. And your smart politician has already by the process of largess / pork (sorry networking) ensured that they have a nice position on a board of directors of one or more of the favoured companies should they not be re-elected...
@ Clive Robinson
IdQuantique's TRNG is a pci card (or usb) that gives up to 16 Mbps of random bits. The basis is that you polarize one photon at, let's say, 90º and send it through a 45º polarized mirror. Quantum physics principles say that the photon will go through or will be reflected with a probability of 0.5, giving a random bit of information. This bit ratio is enough for today's QKD.
With today's quantum devices, nevertheless, if you want a reasonable encrypted bandwith you cannot use one-time-pad (idQuantique uses AES, I think).
I can do better, Uncle Bob, there need to be a head tax of about $10,000 a year (adjusted for inflation every 3 months) that must be paid in order to qualify to vote. Sure don't want those people who can't have a dime to their name and pay no taxes to vote.
Then there must be a property qualification, that anyone who votes must own at least a house of 2,000 square feet (or a 1,500 square feet apartment) that is well maintained, and current on all fees, taxes, building codes and bylaws, etc. Can't let people who live on sewer grates vote.
Quadratic equation? What kind of a test is that? There have to be a qualification test (substantially tougher than the citizenship test and covering more topics and in more depth and with more current subjects) that take, say, 2 hours or so to complete that must be done by every voter. Can't allow them nits that can't even tell you what the 13th Amendment is to vote.
Oh, then there has to be other tests, have you paid up all your taxes? etc. etc. etc.
Then there have to be exclusions, anyone who lobbies government surely can't vote --- conflict of interest. Those who work for government or contractors or are related to government, or work for press, media, blogs, websites, political parties, interest groups...
Now, that is a real democracy.
"The basis is that you polarize one photon at, let's say, 90º and send it through a 45º polarized mirror. Quantum physics principles say that the photon will go through or will be reflected with a probability of 0.5, giving a random bit of information."
Ouch that's going to produce one heck of a lot of bias in a practical implementation.
What method do they use to remove the bias in something like 12.5% of the bits that system would be expected to produce?
@ Clive Robinson
Yep, it should produce a lot of bias. I do not know how they remove the bias.
Anyway, why do you expect a bias around 12.5%?
"Anyway, why do you expect a bias around 12.5%?"
Because that is about the minimum level I found when doing something not to disimilar after moving it from an optical test bed to a functional prototype several years ago.
In reality you find you dont't get half silvered mirrors, polarisers do not produce truly polarised light, neither are opticaly flat. Then photodetectors don't, light sources are less predictable than candles and a whole host of other oddities.
And that's before you start considering how to put it all together in a reliable way and testing it...
At the end of the day broad band thermal noise in a microwave system proved to be easier to get working in a repeatable and testable way and certainly a lot less costly.
However since then optics have moved on in leaps and bounds due to CD/DVD etc technology so the cost of manufacturing equation has probably changed (but then MMICs etc are now dirt cheap as well)...
@n: No that wouldn't be an improvement. Having money is not guarantee of not being ignorant (although there is probably on average a negative correlation; ie the more ignorant you are the less money you make). Ditto property, but I might concede that as a good criterion for being allowed to vote on property taxes.
Quadratic equation too simplistic? I agree with you there as well, it focuses only on math which does not guarantee you're a good citizen; I was merely using a pre-existing example (RAH died in '88) of a test. As far as a full citizenship test every time? Excellent idea, you get a major candidate to present it and I'll vote for him/her.
As far as democracy, not sure whether a true democracy (ie every voter weigh in personally on every issue); is even feasible but this isn't one; its a republic.
But one thing is certain. If everyone votes only in self-interest at the expense of everyone else, we will be going the same place Rome went ("bread AND circuses").
And the downhill slope will steepen asymptotically when more than 50% of the population pays less than or equal to zero income tax. And I read that in the US currently around 48% of the population pays no tax OR gets back MORE than they paid in, so all it will take is just a little more "soak the rich, reward the lazy" and the "great experiment" will collapse.
Well, you seem to have more experience than I have in optics, but anyway I don't think that the bias is too high. Moreover, I think they use a phase coding scheme instead of using polarization. The principles involved are the same, but its easier to manage.
But even using the polarization scheme I don't reckon that the error is that high, because air experiments of QC that use the polarization scheme would not have been possible. A quantum bit error rate over 11% does not allow you to distille a secure key.
@ Matthew Skala
Yes, that was sort of my point: Quantum Transmission guards against an attacker who has the ability to be a man-in-the-middle on a secure link, but lacks the ability to intercept email. Not really useful IMO.
This is the same argument we have over whether HTTPS is really secure against a man-in-the-middle attack. Sure, it's secure if the attacker can't also perform a man-in-the-middle attack on the email-based cert process (but of course such attacks have been demonstrated).
"... I don't reckon that the error is that high, because air experiments of QC that use the polarization scheme would not have been possible. A quantum bit error rate over 11% does not allow you to distille a secure key."
As I indicated it falls down to the quality of the (optical) components you use.
And when it comes to manufacturing what consumer cost point and market size the end product is aimed at.
If you are making mil spec grade equipment then you will either buy in mil spec parts from a catalogue, or get them manufactured for you (which is often less expensive than buying in catalogue parts). Importantly the spec puts quality / reliability over price.
If however you are looking at a limited production run in a cost sensitive market things are a lot different.
If you only have mass produced Consumer Off the Shelf Technology (COST) grade parts available in your price range. Which are designed for a FMCE market product and not specificaly designed for what you are doing then you are constrained by the old "you get what you pay for" issue.
These days the parts available for (mass) production are considerably better and the FE manufactures are also much happier to do custom short runs than they where a few years back (which is why consumer manufacturing in WASP countries is effectivly dead).
Also the market has changed due to US and other legislation and consiquently matured a lot. And has thus moved from a few "lab rat" geeks to significant numbers of profesionals with a "real need to scratch" and a budjet to match. So the equation has changed considerably.
As for my level of experiance in optics no it's not my area, mine is at much lower frequencies, and in "getting product out the door".
You could say I was saddled with a thoroughbred who was tasting pastures new, and I had to try very hard to keep the "stirups short" and the "blinkers on" ;)
'...Quantum Transmission guards against an attacker who has the ability to be a man-in-the-middle on a secure link, but lacks the ability to intercept email.'
That is not correct. Quantum Key Growing is based on the fact that Eve cannot read a photon without modifying its state, and what is more important, without having the certainty that she read the correct value, so she cannot reproduce again the quantum bit. Bob does not know either the correct result of the measurement, but that is where the authenticated channel plays a role, so Alice can say which bases she used to prepare the bits and Bob can then be sure of 50% of his measurements. That is: an intercept-resend strategy will produce an error of 25%, so it can be easily detected.
@ Clive Robinson
Well, at least by now I don't reckon anybody thinks of selling QKD devices to households but to big companies (banks...), so the high cost should not be a major problem.
@ Matthew Skala
The protocol actually needs a secret shared between Alice and Bob so they can authenticate the first public communication. After that, they can use the generated keys to send encrypted information and to authenticate protocol messages.
It would make eavesdropping on the communications channel .... an easy Denial Of Service feature
@bob: I'm pleased that you took the time to refute my snarky comment regarding your wildcard syntax. My motivation for commenting was my shared (and immediate) recognition of DOS 8-dot-3 filename wildcarding. I was amused how its quaint (and even nostalgic) meaning could bleed into (infect?) other contexts. It's at the same time a concise and overarching comment on the cultural landscape of computing.
"Having money is not guarantee of not being ignorant "
Um... maybe we have different goals.
I want them to be ignorant as long as they are my ignoramuses.
What I can't take are people who don't follow orders and training to vote right (for me every time).
So all the education, financial, testing is aimed to produce a reliable voter that will do the right thing inside the booth.
My goal is to quietly video what they do, and those who don't vote right can have their houses, money, etc. taken away and disqualified next time.
"Well, at least by now I don't reckon anybody thinks of selling QKD devices to households but to big companies (banks...), so the high cost should not be a major problem."
Hmm not sure Banks have any money these days unless their Gov has subbed them a few billion to cover directors bonuses and a few other incidental expenses...
On a more serious note True Random number generators should be of interest to any communications network operator / provider if only to protect the engineering channels from unwelcome intrusion.
So for that matter anyone who needs to generate keys for third parties (yes I know it should be a security no no but would you trust an employee to make their own...)
Although the potential market is quite large, most people end up using a bit of freeware from some Open Source provider. As Sun and others did.
Tis a shame that a bug caused only 16Bits of entropy in their PK certificates....
Yep, QKD is very sensible to DoS.
@ Clive Robinson
'Hmm not sure Banks have any money these days unless their Gov has subbed them a few billion to cover directors bonuses and a few other incidental expenses...'
Hmmm... 'touché' ;-)
@Peter and Clive:
Don't get confused with the specs of optical components in the QKD/TRNG systems, or the complexity of the whole contraption - most of them are actually mass market components, or at least could be if there *were* a market for it. The specs are not really that tight, you don't want to have that in the first place as the security there should not (and typiclly does not) rely on a manufacturer keeping their specs. I think it is also fair to compare the complexity of any of these systems to that of a CD player, with probably a similar cost/quantity relationship.
As for removing a bias in TRNGs, I don't know what the idquantique chaps do but you could simply use hashing to remove it, or use a 'compressed' version of the raw sequence where the redundancy due to imbalance is reasonably well removed.
But at the moment, there *is* no market for the QKD systems; as far as I know, none of the companies offering their first models are making any money out of them, and that is a pretty good measure wether it solves or at least makes an institution look like to solve an existing problem.
Not sure if this would be different if the whole area would not have been that overhyped, and less irresponsible claims had been made (the worst of all in my mind still being that 'unconditionally secure' slogan). I like the term of 'QKG', that really expresses what it can offer.
Perhaps there will be a niche where this is useful.
But by en large, I tend to agree with the assessment in the main article that there are much, much weaker links in usual security chains than those which could be strenghened by QKD - or QKG 8)
"As for removing a bias in TRNGs, I don't know what the idquantique chaps do but you could simply use hashing to remove it, or use a 'compressed' version of the raw sequence"
Sorry that's a mistaken assumption a lot of people make. The bias just goes throught to the ouput of the hash and lossless compression functions.
A one way function does not remove bias nor can many compression functions, only a lossy function can (ie it discards the biased bits).
Basicaly you have to test and reject bits as they come out of the generator. One way to do this is on the probability of particular bit patterns.
The simplist is read two bits from the generator at a time, you then do,
00 = no output
01 = output 0
10 = output 1
11 = no output
Then read the next to bits and repeate the test (never never just throw one bit away).
Which is obviously grossly inefficient.
It also has another issue which is very important in data communications, which is you do not know when a bit will be output.
It is this last issue which causes all the problems which is why things like entropy pools and hash functions have found popularity with engineers.
Esurnir, the trick is that when sending the pad, it doesn't matter that some of the bits are compromised. (After the initial transmission, the parties randomly pick some bits, and reveal how they measured them and the results. If the results all match for those measured the same way, there was no eavesdropping. If there was eavesdropping, the message is never sent.) Since you lose over half the bits, and can only detect eavesdropping after the fact, attempting to send the message that way is a very bad idea.
Peter, the bias is removed by an error-correcting code.
@ Seth Breidbart,
"Peter, the bias is removed by an error-correcting code."
Would you care to amplify on that as in what sort of error correcting code and how?
I would be very worried if the error corecting code either bit stuffed or bit flipped the output of the quantum generator.
The thing that bothers me most about quantum crypto is the notion that if someone were to eavesdrop, the signal gets mangled, which makes it remarkably easy for someone to just continuously destroy your communication channel. Maybe your goal isn't to eavesdrop but to make it so that the victim cannot use quantum crypto in order to get any message across. It seems the biggest challenge (aside from actually getting quantum crypto to real life specs) is back to the same problem of creating a secure channel where nobody can access the line and derail your train.
@ Sleep Deprivation Ninja,
" ...back to the same problem of creating a secure channel where nobody can access the line and derail your train."
If you think about a Shannon Communications Channel it does not exclude total communications disruption as an attack vector.
So from the point of creating a secure channel yes that is possible using either conventional or quantum cryptography.
But denial of service attacks will work against both conventional and quantum cryptography, there is little you can do to stop it. Conventional cryptography has the advantage though in that you can use multiple channels in different domains. With quantum cryptography you are effectivly stuck with just the one channel.
The only extra thing the quantum communications channel brings to the Shannon model is the possability to detect evesdroping.
However it is a threashold issue if Eve goes about it the right way then she can due to the deficiencies of the equipment go a long way in not being detected yet still gain some information.
The question is, is she able to use the information she obtains. And that is still a very open question.
Any way it's gone the witching hour in the UK so it's time to sleep on it.
Clive, the original paper (QC II) gives the details. (I don't remember them.)
Sleep Deprivation, if someone can intercept the photons of a QC channel, they can intercept the photons of an ordinary channel and just not retransmit them. Blocking a communication link when you have physical access is easy.
Clive, QC can limit the amount of information Eve can get without detection to a vanishingly small fraction (for a given probability of detection, a fixed number of bits).
"Surely the whole point of encrypting your data is that you no longer care whether there's an eavesdropper?"
If quantum cryptography means no more eavesdroppers then you don't need to bother encrypting your message.
As far as I know:
1) There is no such thing as quantum cryptography. There is a mechanism which, somewhat incorrectly, is named Quantum Key Distribution (QKD).
2) A comment suggests that if secure key distribution is possible, there is no need to use secrets as one time pads; one can as well communicate securely the message
Without getting into details let me say this.
The outcome of the Quantum key mechanism is random and typically 90% of the attempts to send data produce no transmission while 50% of the communicated data are discarded. The randomness of the process precludes meaningful communication of data.
3) A comment writes:
I worked as part of a team to evaluate the benefits of quantum crypto a couple of years ago. What most people forget is that quantum crypto uses a side channel to transmit which parts of the key exchange it was able to receive. That side channel is protected by normal crypto.
QKD uses a side channel that must have integrity and authentication. These are services that do not have the same requirements as confidentiality, hence vulnerable mechanisms can be used provided that the life time of the keys is appropriately short.
4) In additional comments the author writes:
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.
I think that in his haste he overlooked an important consideration. Confidentiality is a service that is provided over a period of time. Thus, even if the current key distribution schemes are safe today, I would not send over the Internet a message that requires secrecy over 30 yrs unless I have some assurance that over the next 30 years one cannot break Diffie Hellman and use recorded exchanges to deduce the key and read the message I sent.
QKD is not the answer to all present or future, real or imagined, problems but may be a nice niche technology for applications that require enhanced key distribution mechanisms.
I really liked the sentence "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." So, I should understand it as even if we have a very strong cryptosystem i.e. quantum crypto, the state of security remains same i.e. insecure. Let me tell you that I am so happy to know that I have views that are similar to someone Big, like you :) Initially (way back in 1998) I started working on Cryptography as a part of my master's thesis (from a small university in India) and currently, I hold PhD with specialization in IDS. My current area of research is vulnearbility analysis and thus my views on security have taken a shape that is similar to what has been expressed in this article. I feel, the same has been conveyed by Michael Howard of MS research- "Security Features != Secure Features." IMO, in SDLC, like QA testing, there should be something like SQA testing. Security (not only cryptography, but safe implementaion) should be a part of software development. Writing a safe code is the most important thing (or one of the most imp. things) which should be followed by a good access control machenism (at various levels- process, host, network).
Quantum Key Distribution = Splendid tool
if it is used at suitable place suitably
as part of a conventional security system
I think I can safely say that no one understands quantum mechanics.” Richard Feynman, Nobel Prize winner in physics and professor at Caltech (Physics Musings).
Can You recommend me some good paper which captures state of the art in computational security which covers quantum aspects?
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.