Slashdot Mirror
Quantum Encryption Explained
angelos writes "New Scientist Magazine has an article discussing the theories of Quantum Encryption. Short and not too complicated an article, but makes for some interesting reading. " Very cool overview of the subject - takes a look at the potential future of encryption and why the curent system of encryption will not last.
It is probably true that random numbers cannot be generated by purely digital means as we have to use less than perfect methods to generate seeds. ANALOG electronics are another matter altogether. A truely random number can be built very inexpensively. A forward biased zener diode will produce white noise. White noise so produced is the result of electrons being forced the "wrong" way over a rather strangely doped p/n junction. I can think of no mathematical way to make this a deterministic system. This white noise should be immediately amplified so we can filter it and apply it to an A/D converter. We then use a spectrum analyzer to find out over what range(s) the noise produced is "flat". This is important because the noise produced may have higher or lower average amplitudes in spots. We then use a steep midpass filter to pass an appropriately large and flat part of the diodes output spectrum. This selectively filtered portion of the noise is then passed to a high quality A/D converter. Lo and behold, we now have a truely random number generator.
No. In space, there is no "up" or "down", so no part of the satellite is the back...
(Score: -1, Unfunny)
--
Xenu loves you!
This encryption scheme sounds pretty good for direct connections, but it is totally useless for Internet communication. The whole idea behind IP is that packets are transmitted, received, and retransmitted from host to host until they reach their destination (hopefully). The problem is that this type of quantum encryption only works if the actual photons that were emitted by the sender are detected by the recipient.
Of course, if every pair of hosts create a one-time pad in this manner for each IP packet that they exchange, it could work, but that would really suck up bandwidth since you need one bit of key for every bit of data. I suppose we could string fiber between all possible pairs of computers on the planet, or maybe just broadcast neutrinos directly. Not this month, though.
Let's not quit working on mathematical encryption algorithms just yet.
That's "Mr. Soulless Automaton" to you, Bub.
The point is there is already an algorithm for a quantum computer that can factor numbers in O(n^3). The problem is it requires 3n quantum bits to use. So, to factor a 512 bit key you would need ~1500 quantum bits. This is a long ways off (largest computation has been done with 5 bits I believe), but there is no way to tell how far off it is. Most researchers in the field believe it is possible.
On the other hand, quantum key distribution, is provably information secure. No amount of computation renders it insecure.
By the way, this is mostly pure research, but there is a group at los alamos that have done quantum key distribution through 50 km of fiber, and 1/2 km of air, both with very small error rates (important for the security proof).
jabber: johnynek@jabber.org
"Your question is answered in the article:"
;)
No, I don't think the quoted piece of the article covers authenticating Bob (or Alice). It deals with the quantum improbability of both intercepting and accurately duplicating the key. If Bob and Alice have a reliable communications channel they can detect Eve intercepting the key with a reliability proportional to the key length. But the protocol seems to be incomplete here -- they do not describe the channel that guarantees that Alice is talking to Bob or that they can detect an imposter. How does Alice authenticate Bob and vice versa? Why is this protocol not vulnerable to a man-in-the-middle attack?
Yes, I understand that Eve can't both intercept the key and derive the values of each bit. That prevents Eve from simply intercepting and retransmitting the key undetected.
My question was how does Alice know she is talking to Bob and not Eve if Eve intercepts the key and pretends to be Bob to Alice and pretends to be Alice to Bob? The article assumes that Alice and Bob have a reliable method to communicate and can know they are talking to each other (the phone call). What is that method? It would seem to be a critical piece of the whole protocol. The article doesn't cover a cryptographically secure method of authentication -- and it wouldn't be fair to use current methods, since the justification for quantum cryptography is presented as current methods being crackable.
Geeky modern art T-shirts
Suppose Alice and Bob want to generate a shared key, and Alice is in NY, and Bob is in CA, and the satellite is over the US. Alice and the satellite generate a key A, and Bob and the satellite generate a key B. The satellite then sends Bob (A XOR B), which Bob uses to compute A. Assuming Bob and Alice can trust the satellite, they can communicate securely with key A.
This technique is also useful for securely rekeying a satellite (e.g. changing the key HBO uses to encrypt their transmissions every month).
I got this info from a presentation given by one of the guys from LANL a couple days ago...
Well, you need the secure channel to be sure that the intended recipient was indeed the person that recieved the transmission on the insecure channel. In this instance, the secure channel isn't a secure channel in the sense of sending communications, but secure in the sense that you are able to dicern who recieved the transmission. A phone call will do, so long as these aren't bank transfers or nuclear launch codes, and you can feel sure about the voice on the other end of the line.
Or the secure channel can be simply the string of dedicated fiber optic cabling running from one building to the next, and therefore you assume that you trust who ever is on the other end of that line.
I'm just saying you need a trust mechanism. PGP helps to provide that infrastructure. This does not, so far as I saw.
This is not saying that John Q Public would never have a computer. This is quantum physics here.
It's simply impossible to send protons positioned as such through a switch or router (or twenty a la the internet) and be assured that they arrive at the other end in the same position that they were in when they left.
If you string together two locations with dedicated lines, that's one thing, but John Q. Public CAN NOT benefit from this in the slightest way shape or form, in regards to e-commerce or other internet based transactions. Unless every vendor or potential vendor strings their own cable to their home, it's just not happening.
The Times of London had a s tory Wednesday indicating an Isreali team has a hendheld quantum device that can crack 512-bit RSA keys in 12 MICROseconds.
Work for Change & GET PAID!
What is called "quantum encryption" is in fact no encryption at all... It is just a powerful and effective key-sharing scheme for an one time pad. An one time pad is the "perfect" cryptosystem, that is it is a cryptosystem that is theoretically unbreakable... obviously there is a price to pay for this, and that is that the key as to be random (in mathematical terms, low out-of-phase correlation, roughly some number of 1's and 0's, and other more technical properties) and as long as the message. The problem is "how to produce/store/share such a beast?" [N.B. constructing a really random sequence is not possible if you are working with electronic devices only] The problem that makes one time pads unpractical for all but diplomatic use is the difficulty in agreeing and transmitting a key to the parties involved. Here it is where quantum mechanics comes to the resque: a quantum state "cannot be cloned" in the sense that it is not possible to take a quantum and get two quanta in exactly the same state (this follows from Heisemberg's indetermination principle). This means that an eavesdropper has to perturb the communication while it is listening to it, whence the possibility of knowing that who wants to communicate and to agree a key is being observed. In this scenario an attacker can only perform a DoS, but is quickly identified, hence the usefulness of using a quantum channel. The message, afterwords is transmitted using an one time pad encryption that is the safest possible in the sense that the only information one might get without the proper key is just the lenght of the message (unless the transmitter adds some padding, just for making also this an useless information).
The breezy assertions at the start of the article that modern cryptosystems are going to be cracked any moment now are totally unwarranted. Progress in solving problems like factorisation, ECDL etc has not been much different from what might have been predicted fifteen years ago, and we have no particular reasons to think that this will change. It's about as worthwhile as speculating that some as-yet-unknown discovery in physics might render quantum cryptography useless.
Quantum crypto requires bizarre quantum properties of your message to be preserved from end to end - there's no possibility of an ordinary routing network. Furthermore, as the Dodger points out, it just pushes the problem into the authentication domain, and that's resting on precisely the same "untrusted" mathematics and a few social problems too. It's an interesting toy, but the public key crypto we already have - that we can do with straightforward hardware and the networks that already exist - will continue to be the workhorse for 99.99% of encrypted world communications, and don't let anyone try and tell you otherwise.
I do wish people wouldn't mutter dark warnings about perfectly good systems in order to sound interesting: the field of security has enough FUD as it is.
--
Xenu loves you!
Actually, if you do a little research, the "quantum" device isn't very quantum. It's simply optoelectronic. It's called "TWINKLE"-- The Weizmann INstitute Key Locating Engine.
The basic premise is this: the quadratic sieve needs to find numbers which are "smooth" (meaning that a number is the multiple of a certain number of primes stored on a list). These numbers are used (well, one of 'em is used, anyway) to figure out the factors of the large number (number theory omitted here, beyond my comprehension).
Anyway, you make up a base of (say) 200000 primes. You assign each of these primes to an LED. You give each of these LEDs a little countdown timer, and hook it all up to a clock running at (say) 10 GHz. You set each countdown timer equal to the prime assigned to its attached LED. When the counter reaches zero, the LED flicks on and the timer resets. It flicks back off the next cycle.
After X pulses (where X is a smooth number), all the LEDs that are supposed to represent the factors of X will turn on. A small photodetector will determine if enough light has been generated to consider the number interesting (has large enough or plain *enough* factors to have a decent probability of being useful). If it is determined interesting, the number is passed on to the computer.
Since it's all running at 10 GHz, and the only outputs are few and far between (relatively speaking), the rest of the calculations can be done on a computer.
I know that this does not even *begin* to cover a number of significant technical details-- please don't flame me.
I also know that I'm not much of a number theory guy, but I think I get the basic premise (though I'm not great at explaining it). Please don't flame me-- I don't take Number Theory until next semester, okay?
"...avoiding...[a man-in-the-middle attack]...is, in my opinion, an implementation detail"
Perhaps, but I would feel so much more comfortable with something that can be automated like contemporary public key protocols, which only require real authentication once and provide for public channel verification thereafter.
That "implementation detail" would seem to be a bit more difficult in a world where current public key cryptography is no longer effective, as in the case where we resort to using quantum cryptography.
Geeky modern art T-shirts
If you have two channels of communication, one secure, and one insecure, you can transmit the key using the secure channel. If it's been intercepted, then the reciever would know and could tell the sender over the insecure channel to resend the key over the secure channel. If there's only one channel, then someone can sit in the middle subsituting messages to there hearts content and no one would evere know.
While this may be a great thing for satelite communications and for closed networks, I don't see how it will ever evolve it's way down to the desktop. How will an electron maintain its' position as it travels through a switch or router? What about sending down a fibre optic line (cable modem) and then having the message relayed through a satelite, then back down to a fibre-optic cahnnel on the other side of the globe?
No... Public key is here to stay. If it's compromised (via improved factoring attacks, TWINKLE, etc...) then we're back to square one... This isn't a subsitute that John Q. Public can use.
ADVISORY: There is an Extremely Small but NonZero Chance that, through a Process Known as "Tunneling," this Post May Spontaneously Disappear from its Present Location and Reappear at any Random Place in the Universe, Including your Neighbor's Domicile. The Poster will Not Be Responsible for any Damages or Inconvenience that May Result.
--
If our understanding of the physics is correct (pretty much certain) then this system is provably secure: no mathematical breakthrough will let you in.
If you can intercept *all* communications between the two parties, direct and indirect, and substitute *all* messages for ones you've written yourself, then nothing at all will stop a MitM attack. You have to have some sort of authentication lever.
However, you're right to say it's a particular weakness of this system, because the system depends on Bob sending Alice an authenticated message of what measurements he took. If Mallet can subvert this channel he can read the secret message. And QC doesn't provide provably secure authentication, since that's impossible - it's a social problem as much as anything else. Perhaps you could prove that the sender of a message knows a particular secret, but how will that help if you can't be sure who holds the secret?
And you're also right that it's totally impractical for real use.
--
Xenu loves you!
The Weizmann institute announced a design for a piece of opto-electronic kit called TWINKLE that could greatly speed factoring, though modern recommended key lengths (eg 1024 bits) are still *way* out of its reach. However, it hasn't been built yet, it's not handheld and it doesn't go at 12 microseconds.
The UK Government are mulling over how to cripple domestic crypto without getting hit over the head at the moment, so scare stories about crypto are appearing all over the press at the moment, especially the Murdoch-owned press; apparently the crypto we all use is worthless, but the Bad Guys are using unbreakable crypto to hold up banks so it must be stopped, and we must go to the GCHQ (our NSA) for "consultancy" on what best to do about it.
--
Xenu loves you!
The problem is that there is no way to know whether the factorization problems are solvable. They are considered "hard", but there is no proof that someone won't come along and render the whole thing obsolete. And maybe someone already has...
The problem of how to break something like RSA is a mathematical one: either some operation is easy to do in one direction and hard to do in another, or it's in fact easy in both directions. Factoring is one example of such an operation.
The proposed quantum scheme relieson the fact that whether a photon will pass through a filter polarized at 45 degrees to the photon's own aligment is random at a quantum level, eg. can't be determined. Eve is screwed at a fundamental physics level. The only thing that could crack this would be major changes in our understanding of particle physics.
It's open to debate whether this is more or less likely than finding a quick factoring method (or in the case of RSA, a quick way to find Phi(n) from n). . .
Most researcher do *not* believe it will happen. The techniques that reached 5 bits can't be extended very much further. No practical demonstrations of any extensible techniques exist at all. It's most likely that decoherence will render it impossible.
--
Xenu loves you!
The conclusions of those "people out there" are not based on anything resembling a fact. If this sort of mindless, groundless pessimism puts even one person off encrypting just one email message with the best tools we have (PGP, GPG etc) then the NSA have done part of their job without spending a single compute cycle.
Learn a little about how modern crypto works (The Cryptogram is a good place to start). Read the descriptions of some of the AES candidates: Serpent, RC6 or Rijndael might be good ones to start with. Even in the supremely unlikely case that the NSA can crack everything we use, it would still cost them something in compute cycles, and encrypting all the world's email would still put a significant barrier in the path of their intelligence-gathering activities.
--
Xenu loves you!
Something the article didn't cover or I missed completely. How does Alice know she is talkin to Bob and not Eve's agent when verifying a valid key was transmitted? In other words, can't Eve simply intercept the entire transmission and emulate Bob to verify the key? While the cryptography logic seemed solid to me, I fail to understand why the phone system is so casually used as an integral part of this system. Note that if something other than the phone call is used to verify the key, the problem remains: how to authenticate Bob in the verification step?
Geeky modern art T-shirts