Slashdot Mirror
Quantum Cryptography Leaving the Lab
Theodore Logan writes "More than a year ago, MagiQ announced the world's first commercial quantum cryptography system (pdf), with ID Quantique following closely in their footsteps. Currently, the technology is limited to offering point-to-point connections up to a maximum distance of around 50 km, but this is likely to be greatly improved on in coming years. The systems available today are prohibitely expensive for the average Joe (MagiQ's are priced at more than $50,000 per unit), but one could envision a future in which they are built into the infrastructure by non-end user actors. Does this spell the end of the field of cryptography? Will systems like this ever become commonplace, or will they be reserved for sensitive financial transactions and military applications? What impact will quantum cryptography have on society? Good articles available from International Herald Tribune, EE Times and CNET."
Since they make a point that they "Rely on the laws of physics", they're bound by them too (maths is far more forgiving
OTOH, it's the first generation of these devices, and perhaps IPv8 will somehow encode an encryption hierarchy (packets get encrypted sequentially in one direction, and decrypted on the way back, assuming the same route is taken, each node only needs to know the encryption to the next one worked ok to guarantee the encryption was ok. You'd still want to be in control of all the nodes along the way though...)
As for price - if they can solve the networking issue, that'll come down dramatically - it'll be onboard in the equivalent of the BIOS that we have in ten years time (when we all have fibre to the home. Possible optimistic
Simon
Physicists get Hadrons!
Does this spell the end of the field of cryptography?
Uh, no. Quantum key distribution is completely useless unless you have a cryptographic algorithm and protocol using that key for encryption. I suppose you could just send the message over quantum channels, but a quantum channel for key distribution is probably many orders of magnitude too slow for the acutal data.
Reading datas alter them. So the man in the middle will be detected. I'm not a professional, but I understood that you have to destroy the photon to read its information.
The key is sent with a single photon for a bit. A simple way of looking at it is that by measuring (spying) the photon, you unavoidably change it (randomly flip the bit), causing checksums in the protocol to fail and alarm bells to go off. Heisenberg's Uncertainty Principal or something.
The purpose of cryptography is to transmit information in such a way that access to it is restricted entirely to the intended recipient. Originally the security of a cryptotext depended on the secrecy of the entire encrypting and decrypting procedures; however, today we use ciphers for which the algorithm for encrypting and decrypting could be revealed to anybody without compromising the security of a particular cryptogram. In such ciphers a set of specific parameters, called a key, is supplied together with the plaintext as an input to the encrypting algorithm, and together with the cryptogram as an input to the decrypting algorithm.The encrypting and decrypting algorithms are publicly announced; the security of the cryptogram depends entirely on the secrecy of the key, and this key must consist of any randomly chosen, sufficiently long string of bits.
Read more here
Too bad quantum crypto and quantum computing have absolutely nothing in common.
Quantum crypto is a misnomer, it isnt even crypto at all. It's an intrusion detection system. Quantum crypto works by sending sensitive photons through a tight channel as bits which will get disturbed by an eavesdropper. Where as electrical signal on a wire expects static, and a wiretap isnt noticed.
Quantum computing however, works on electron entanglement, and is pretty far off.
Essentially, Quantum Cryptography works because of Heisenberg's Uncertainty Principle and a thought experiment known as Schrodinger's cat. Basically, when one of these devices transmits a bit, it does so as a single photon with a known "spin." By observing that photon, you modify the very physical properties of that photon and corrupt the data. The man in the middle has no way to reconstruct the data because he has no way of knowing the given properties of a photon in the seqence. Further, that serves to DOS the connection (becuase the man in the middle cannot retransmit the same quantum sequence), thus causing the units to switch off and declare an alarm.
It's similar to Schrodinger's cat: Schrodinger comprised a thought experiement where a cat was put into a sealed box with a poison and a radioactive atom. In the course of 1 hour, the atom has a 50/50 chance of decaying, thus killing the cat. At the end of the hour, the cat is neither dead or alive, but in a state of flux. It's not until you observe the system that you fix the state of the cat as being dead or alive.
Q: "Why do sound techs say 'check 1, 2'?"
A: "Cause if they could count any higher they'd be lighting techs."
Here is a whitepaper from MagiQ on their technology.
Quantom theorys are already out of the lab and in the real world. Old computer hardware is based on NAND and XOR gates but Toffoli and Fredkin gates are useful in the modern world and because you can revser them, once you start building DES/AES/RSA engines out of them, you can start to short circut some of the brute force attaces in very interesting ways. Combined with the real world ability to pre-compute and store data sets in the order of 3e12 bytes at a time, there are many crypt attacks now open to anyone with a good collection of hard drives.
"OK.. sorry for summarising.. but quantum computers can crack conventional encryption in a single cycle. They make it trivial to factor things down to prime numbers, no matter how large. And since this is the basis of most current cryptography, they will obsolete our current cryptography."
This is bullshit. First off, you have to assume that
a) non-trivial Quantum computers can be constructed at all [who says there are not limits?]
b) The time per solution is not greater than a brute force attack.
I mean sure a single cycle AES cracker would be cool. But if the machine took 2^100 years to build who gives a shit?
This type of hype always pisses me off.
To boot as I understand it, QC only "attacks" in sqrt time by meet-in-the-middle approaches. So AES-256 would provide all the security ya need.
Tom
Someday, I'll have a real sig.
Sort of. It's part of a negotiation sequence. Read Xeo 024's qubit.org link, it explains it pretty well.
(Based on memory of Bruce Schneier's description in Applied Cryptography)
/, and \.
Alice sends Bob a series of polarized photons.
There are four possibilities: -, |,
Bob sets up his polarization detector randomly so that each "qbit" is measured either for horizontal/vertical polarization or diagonal polarization. If a - or | photon hits the detector and it was set up for horizontal/vertical, he gets a good bit, otherwise a bad bit. And if a / or \ photon hits the detector and it was set up for diagonal polarization, same story. The key point is this: if the detector was set one way and the photon is polarized the other, it is in principle impossible to know its true polarization.
So Bob has a sequence of photons, some of which he knows, and some he doesn't, and he knows which are which. He sends Alice a clear-text message saying which ones he knows. Alice then encrypts the true plaintext by XOR'ing it with the values of the photons that Bob knows, using some convention like "- and / are 0, | and \ are 1".
Example:
Alice sends...: - \ - | / - | (random)
Bob's detector: + + X + X X + (random)
Bob's result..: - ? ? | / ? |
Bob's response: 1 0 0 1 1 0 1
Key...........: 0 1 1 1
If Eve tries to listen in on the photons Alice sends to Bob, she perturbs them irrevocably.
A bad description -- go buy Bruce's book for a better one.
"Skill shows through where genius wears thin." -Wittgenstein || Religion: uniting aviation and architecture.
The reason most encryption works is because when you linearly increase key size, you exponentially increase the amount of time required to crack the key if you have no special knowledge, meaning it is much more difficult (impossible for practical purposes) to decrypt without a key than encrypt or decrypt with the necessary keys.
Doubling the key size may only double the work of the one encrypting and decrypting using a key but exponentially increases the work of the one trying to break it without a key. Almost no matter how easy it is to crack a short key, you can increase key size until the advantage of linear versus exponential is overwhelming.
But quantum computing -- encoding the problem into the quantum matrix, not to be confused with the quantum encryption described in this article -- threatens to be able to solve such problems in linear time instead of exponential time.
This means that when the user doubles the size of his key instead of exponentially (enormously) increasing the amount of work to solve the problem, it only doubles the amount of work required to crack it, which would make decryption a simple footrace even if you do not have the key, if the amount of work required to crack the key is proportional to the amount of work required to encrypt / decrypt instead of an exponential relationship.
Primes would not seem to be adequate at all, if quantum computing allows them to be solved linearly. At best, if you could find something that had the difficulty of non-quantum primes under quantum computing, then perhaps you could use that.
However, quantum cryptography does not rely on large numbers that are hard to factor, but on the fact that it is impossible (according to currently known physics, as correctly pointed out) for someone to eavesdrop without being detected.
www.qubit.org has this explanation:
The basic idea of cryptosystems (B) is as follows. A sequence of correlated particle pairs is generated, with one member of each pair being detected by each party (for example, a pair of so-called Einstein-Podolsky-Rosen photons, whose polarisations are measured by the parties). An eavesdropper on this communication would have to detect a particle to read the signal, and retransmit it in order for his presence to remain unknown. However, the act of detection of one particle of a pair destroys its quantum correlation with the other, and the two parties can easily verify whether this has been done, without revealing the results of their own measurements, by communication over an open channel.
So to use this for safe communication, you would send some random data through the connection, and once you are sure there were no eavesdroppers, you can use this random data as the key for normal symmetrical encryption. And if the random key is as large as the data you encrypt with it, even normal symmetrical encryption can't be cracked with a quantum computer.
You are thinking in terms of classical physics. On the quatum level, the properties that are to be measured do not actually exist until an attempt is made to measure them. All that exists is a wave function representing the combined probablities of the various properties momentum, spin, location, etc.
Furthermore, in accord with the Heisenberg uncertainty principle, you cannot determine all of the properties, of, for example, an electron. Knowing (measuring) one property makes the others unknowable (NOT unmeasurable). For example, if you measure the postion of an electron, then you cannot also know the energy that electron has at that instant, and vice versa. Thus, what property you choose to measure determines what you can know.
Back to crpto - the system uses spin as the property measured, because pairs of particles with opposite spins can be created and sent to different places. No one can know the spin of each particle until the measurement is made. At that point, the other particle must have the opposing spin (you now know this because of conservation of spin).
If someone intercepts the particle, they must first know which property to measure. Once it is measured, though, they are exposed and the information is, essentially destroyed.
The universe is nothing more that probability. See Douglas Adams for further elaboration.
Molecular Mechanic
I have written this book partly to correct a mistake.
Seven years ago I wrote another book: Applied Cryptography. In it I described a mathematical utopia: algorithms that would keep your deepest secrets safe for millennia, protocols that could perform the most fantastical electronic interactions-unregulated gambling, undetectable authentication, anonymous cash-safely and securely. In my vision cryptography was the great technological equalizer; anyone with a cheap (and getting cheaper every year) computer could have the same security as the largest government. ...I went so far as to write: "It is insufficient to protect ourselves with laws; we need to protect ourselves with mathematics."
It's just not true. Cryptography can't do any of that.
It's not that cryptography has gotten weaker since 1994, or that the things I described in that book are no longer true; it's that cryptography doesn't exist in a vacuum.
Cryptography is a branch of mathematics. And like all mathematics, it involves numbers, equations, and logic. Security, palpable security that you or I might find useful in our lives, involves people: things people know, relationships between people, people and how they relate to machines. Digital security involves computers: complex, unstable, buggy computers.
Mathematics is perfect; reality is subjective. Mathematics is defined; computers are ornery. Mathematics is logical; people are erratic, capricious, and barely comprehensible.
The error of Applied Cryptography is that I didn't talk at all about the context. I talked about cryptography as if it were The Answer(TM). I was pretty naïve.
The result wasn't pretty. Readers believed that cryptography was a kind of magic security dust that they could sprinkle over their software and make it secure. ... A colleague once told me that the world was full of bad security systems designed by people who read Applied Cryptography.
Since writing the book, I have made a living as a cryptography consultant: designing and analyzing security systems. To my initial surprise, I found that the weak points had nothing to do with the mathematics. They were in the hardware, the software, the networks, and the people. Beautiful pieces of mathematics were made irrelevant through bad programming, a lousy operating system, or someone's bad password choice. ...
Any real-world system is a complicated series of interconnections. ... No system is perfect; no technology is The Answer(TM).
This is obvious to anyone involved in real-world security. In the real world, security involves processes. It involves preventative technologies, but also detection and reaction processes, and an entire forensics system to hunt down and prosecute the guilty. Security is not a product; it itself is a process. And if we're ever going to make our digital systems secure, we're going to have to start building processes.
A few years ago I heard a quotation, and I am going to modify it here: If you think technology can solve your security problems, then you don't understand the problems and you don't understand the technology.
This book is about those security problems, the limitations of technology, and the solutions.
"She's a scientist and a lesbian. She's not going to let it slide." Orphan Black
I think that's a little too simple. The quantim crypto part is used to transmit a one-time pad, which is probably unbreakable. However, one-time pads suffer from key-distributions problems, which is where the quantum bit--no pun intended*--comes in. So it makes for a nice marriage between the two.
* A desparate punster submitted ten puns to a local newspaper to try to win the grand punster prize. His hopes were dashed, however, to find out that not only did he not win the prize, but no pun in ten did.
Have fun: Join D.N.A. (National Dyslexics Association)
That's not at all true. First of all, the quantum part is seperate from the cryptography part. It's primary purpose is to provide you a conduit over which you can send data and be absolutely sure that if someone other than your recipient saw it, the recipient will know.
The one-time pad, which is only feasable by quantum cryptography, is impossible to decrypt without the key. Or rather, impossible to know which decryption is correct, as you can easily decrypt it into whatever you want.
You have no idea whether:
"5preio2309d91kcn2s02ia"
actually means:
"al-Qaeda strikes again" or
"Hi there, how are you?" or
"ZekdjEs322SKE#aap2MZal"
and so on. You can say it means whatever you want, but you'll never really have any idea if that is what it meant or not unless you have the key.
Yes, someone may break quantum cryptography, but to say that it will happen because is has happened before is silly.
Random and weird software I've written.
Shamir has already described how to attack quantum key exchange. His attack, which I've talked about before here, is like Alexander the Great's attack on the Gordian Knot. You don't try to solve a problem designed to be unsolvable: instead you step back and figure out what the *real* problem is and solve that.
Besides the Shamir attack, there's always the wait-for-your-opponent-to-screw-up attack. One time pads are theoretically unbreakable, with mathematically provable security. This didn't stop the US from reading the Venona intercepts. The Soviets had used one time pads two times, and that mistake destroyed the security.
a) non-trivial Quantum computers can be constructed at all [who says there are not limits?
/. headlines or other one-line summaries of the technology. Contrary to popular belief, it's really not all that confusing. It's just an interesting way to exploit something that was observed in nature (like most other inventions). Try something like "The Feynman Processor". It's kinda old now (everything is "in the future"), but it's all explained so that my cat could understand it given enough time.
/. reader.
OK, why would you assume some arbitrary limit on the number of quantum gates that can be linked together? You only need to link as many gates as the bits of encryption you're trying to crack. I know that currently quantum computers are only factoring numbers like 15, and that the methods that are used to link the gates are not easy, but there is no reason that the exact same methods can't be used to link more gates.
b) The time per solution is not greater than a brute force attack.
OK, now I know you're just a complete dumbass! Do you know anything about quantum computing? I don't know how long you think it takes an electron to change state, but in case you're wondering, it's not very long. All of the work in a quantum computer is actually done before you ask for the solution. The actual work side also takes virtually no time. You'll simply be asking it the same question every time, and it calculates all the answers for you (over simplified to the point of being wrong, but at this point it seems quite necessary) and you simply tell it which answer you'd like. The time it takes for all this to happen is short enough that I doubt it could be measured. Even if the different gates in your computer are miles or light years apart, the quantumly linked actions are (were last time I read) considered to be instantaneous (yes, faster than light). The slowest part of the system will be where you want to interface your quantum computer with the "real" world.
This type of hype always pisses me off.
Why don't you read some literature the explains quantum computing and then read your comments again. If you haven't read anything about how it actually works, then you can only depend on the
I fear that I've greatly over-estimated the average
The "standard" use of these devices is for point-to-point communication. Put one end in the White House and the other in the Pentagon (about 40km away) and you have a communications channel that can not be sniffed without detection. So far, so good.
But this doesn't scale well. Talking from DC to Moscow would probably require some sort of relay system, just as a relay system would be required if we wanted to have this enter people's homes (otherwise you'd need direct fiber connections between you and everyone you ever want to talk to). So now the relays need to be "trusted", and the possibility of a MITM attack is introduced.
As you have discovered, QC protects the security of the link, not the endpoints, relays, etc.
Disclaimer: IAAPP (I *am* a particle physicist)
To address your first paragraph.... Why do you assume there is no limit? Maybe circuit building is a O(n^10) process?
To address your second paragraph.... "time per solution" meant the time it takes to make the actual device. If it takes 2^100 years to design an AES cracker I don't care.
Overall... I never said QC is impossible. I just hate how people spin [forgive the pun] things to no logical ends.... OMG they can factor the number 15. That means the technology works. Doesn't mean it will scale. Factoring 15 and a 1000-bit composite are not the same order of magnitude.
Similarly AES is not a trivial algorithm. Designing a QC for AES may prove to be intractable. Which means all the QC hype in the world won't break AES.
Who knows. Keep an open mind and don't make stupid conclusions like "crypto is dead" or "your mother is a whore".
Tom
Someday, I'll have a real sig.
Why don't you read some literature the explains quantum computing...
Last I heard, there is still a ton of comp-sci problems that are hard, even in the quantum world. NP problems will still be NP problems---quantum computers don't help with those.
Also, unless some really major innovations come up, we won't see quantum computers anytime soon (and I mean in centuries, not years).
"If anything can go wrong, it will." - Murphy
Transmitting a large one time pad to an agent in the field can allow them to use that one time pad _later_.
"Who is the Journal of Quantum Physics going to believe?" --Stephen Hawking
>This is true for a passive attack, i.e., one were the attacker can only eavesdrop on a connection.
>However, in a man-in-the-middle attack, the attacker can also arbitrarily modify data.
But the point of quantum crypto is that there's no such thing as a passive MITM attack. Quantum MITM can't help but be active. So after the transmission of the qubits, Alice should have guessed the right polaraization for about half of the qubits. For these qubits, Alice and Bob should have measured the same bits. Alice and Bob now pick some subset of these bits and announce publicly what they each got.
If their bits agree here, then they of course are sacrificed, but if the bits disagree, then Alice and Bob know that there must have been an eavesdropper listening.
Actually the whitepaper (http://www.magiqtech.com/registration/MagiQWhiteP aper.pdf) appears to imply that they detect this thanks to an out of band communication channel. Page 13: "Alice and Bob verify the integrity of the quantum channel by revealing a random subset of the key bits and checking the error rate using the public communication channel."
Thus if an attacker (Eve) were to also Man in the Middle the out of band communication I think they could be successful in their nefarious goals.
Informally, it's impossible to observe say the spin of a photon without pretty much destroying it. So you'd have to reconstruct a photon w/ the same spin. However photons also have other properties which you cannot measure at the same time (Heisenberg's uncertainty principle), so basically the man-in-the-middle attack fails because the man in the middle cannot get all the information required to retransmit the photon exactly as is. There are ways using entanglement to test and make sure the photon is exactly what Alice sent (I don't know specifics off the top of my head).
Basically, no way to recreate the bit you receive in such a way that Bob wont know it was modified.
The random number can be generated in many ways. Computers have PRNGs, Pseudo-Random Number Generators which can rely on several different sort-of random data: system time, memory contents, disk contents, mouse movements, etc. The problem with such PRNGs is that they usually use reproducable data to generate the random number - mouse activity can be guessed (activity patterns), system time can be guessed (the range of possible values for the system timer, time is global after all), memory contents can be guessed (operating system and programs running, etc) - it is at the very least easier to guess these and try all possible combinations than guessing cosmic radiation patterns, for example, which are truely random. This "guessing" is what cuts down possibilities and makes brute-forcing in a smaller field of possibilities an option. To beat this, real RNGs (i.e. non-pseudo) rely on truely (theoretically) random occurences, such as atmospheric noise (http://www.random.org).
Thermal noise can not be easily detected from afar (afaik), and if you're close physically - you might as well just take the data by physical force. But guessing the possible thermal noise based on know patterns makes guessing the pseudo-random number that much easier.
Spins don't enter into it. A photon with spin +/-1 is means it is circularly polarised. In this matter all photons are spin 0, what you measure is the angle of polarisation. In one system an angle of 0 means the bit is zero and an angle of 90 degrees means the bit is one. In the other system the angles are 45 and 135 degrees. If you know a photon has an angle of 0/90, you would pass it through a filter which blocks, say, the photons with an angle of 0 and then put a detector behind the filter. If it blips then you've read a one.
If you don't know what system the photon was encoded in, you will have to guess. When you guess incorrectly, the result of your measurement will be 0/1 randomly (indepentantly, of course, of what the photon was representing in the correct system), this is what the 45 degrees are about. When she guesses correctly, Eve can manufacture a new photon which is sufficiantly identical to the original to fool Bob. However, half (on average) of her incorrect guesses will give her away.
Using RSA as an example, here's a less-than-six-step process for finding the private key given the public key (exponent e and modulus m=pq):
(1) Factor m into p and q (both distinct primes).
(2) Calculate phi(m) = (p-1)(q-1).
(3) Find the reciprocal of e in this new modulus phi(m). That's the private key.
Once you have step 1, the rest takes a very short amount of time (less than a second). And you don't even need a sample message....
The problem is you can solve for the third thing, but some things are harder to solve for than others. All of the security of public key cryptosystems depend on the "hardness" of the "third thing" you need to solve for.
To give an easy example of how one way can be harder than the other, try doing this problem by hand:
Given y = x^3 - x^2 + 5x - 4,
(1) Find y given x=3.
(2) Find x given y=10.
Why is one way harder than the other? Because it's easy to multiply things together, but not so easy to factor. It's the same thing with cryptosystems. So, I doubt anyone will find a simple algorithm to make them equally "easy." The best factoring algorithms in the world are still nowhere as simple as multiplication.
OTOH, quantum computing can do exponential time problems in something like linear time, so a quantum computer could just factor and we'd be done with it. No need for a fancy mathematical algorithm. We already know how to do it -- it's built right into the cryptosystem.