Slashdot Mirror
The Clock Is Ticking On Encryption
CWmike writes "In the indictment that led to the expulsion of ten Russian spies from the US in the summer of 2010, the FBI said that it gained access to their communications after surreptitiously entering one of the spies' homes, during which agents found a piece of paper with a 27-character password. The FBI had found it more productive to burglarize a house than to crack a 216-bit code, despite having the computational resources of the US government behind it, writes Lamont Wood. That's because modern cryptography, when used correctly, is rock solid. Cracking an encrypted message can require time frames that dwarf the age of the universe. That's the case today. 'The entire commercial world runs off the assumption that encryption is rock solid and is not breakable,' says Joe Moorcones, vice president of information security firm SafeNet. But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing."
only if you don't actually want to crack it, then quantum encryption will unlock itself, however if you want to crack it you can't.
i thought once I was found, but it was only a dream.
Welcome to 1994, and Peter Shor's discovery of how to factor with quantum computers.
The FBI had found it more productive to burglarize a house...
That kind of behavior, burglarizing houses, committing a crime to stop other crimes, is destructive to the rest of the nation. There are mistakes. There are agents who use their power to cause trouble. There are many other negative consequences, such as the FBI agents acting to support their personal ideas of political action, which has happened numerous times in the past.
Many of us have known it for a long time, but more and more people are waking up to the fact that "cloud computing" is a sham. It's basically 1970s-era mainframe computing revived and renamed, with a layer after layer of marketing bullshit layered on. It has all of the same drawbacks as mainframe computing plus some, and often without many of the benefits.
"Quantum computing" risks becoming the next such mania. Soon enough, some marketing dipshits will come along and relabel some lousy existing technology as "quantum computing" (even when it absolutely isn't). This will get the press going, and soon the buzz will be overwhelming. Every manufacturer will be hard at work putting "Quantum Powered" stickers on the hardware they sell, and all sorts of software providers will be labeling their software as "quantum-compatible".
If it's anything like cloud computing has been, it'll just be a waste of time and money.
Yeah, that's true.
Wait, who didn't know this already? The title is misleading, but the fact that quantum computing breaks RSA is pretty standard knowledge (among people who have heard of quantum computing at all, I guess). Of course, there are other encryption schemes that seem to work just fine (e.g. Elliptic curve cryptography) with quantum computing, and there's not much evidence that algorithms other than RSA are broken. Note: factoring isn't NP-complete! So far there's no reason to believe it's not an "easy" problem, except that we haven't figured out how to do it. More intersetingly, there's a lot of research being done on quantum cryptography, which is really quite cool. In total, quantum computing should probably give us more security than it breaks, except for the idiots who keep using outdated algorithms long after they're broken, but they'd be screwed anyway.
So, the sky is falling! Oh wait, no, that's just the weather changing.
I rely on magic pixie dust found on top of the space elevator. It's easier to get than a useful quantum computer and will be for quite some time.
Anyone prepared to take a bet that the CW of CWMike stands for ComputerWorld, and this is a blatant attempt to drive traffic towards an article he either wrote or published?
It is checking the guessed key is right that is the problem.
Say I take my credit card 4111 1111 1111 1111 and encrypt it with a numeric Caesar cypher, it turns out the encryption is bad but close 90% of the keys you brute force will give you what appears to be a valid answer (assuming mod 10 and 3/4/5 on the 1st digit checks only). If you take the same number with spaces and a EOL and used export grade DES you can try 2^40 keys but only a fraction will result what looks like a credit card number. If you use AES256 then the odds of a good looking result have the right key are even better so not only do you know you have the right key, your confidence in that fact is higher. Deep Crack used a lot of hardware to find out that an attempted key produced useful looking results.
If you want real security, go with a one-time pad and read up on the mistakes the Kriegsmarine made that let their nifty device get cracked.
Sheesh, evil *and* a jerk. -- Jade
Yes it will. Just because the encryption is "quantum" does not mean it's not trivially breakable with rubber hose cryptanalysis.
Admit nothing. Deny Everything. Make Counter-accusations.
Quantum computing is probabilistic, it has a chance to converge on the right answer, and it gets there in the fairly specific case of using a quantum version of a fourier transform to factor large primes. If you base your crypto method on something not vulnerable to to a quantum fourier transform, or if, with your decryption method you absolutely must get the right answer, you can end up back at brute force.
Quantum cryptography is really not related to quantum computing all that much. They both rely on entanglement, but trying to extract some quantum state of two entangled things (nuclear or electron states most likely) isn't really a computational problem that computing, quantum or otherwise exists to solve. There are lots of practical challenges to quantum cryptography, the short version of which is that a single thing in a specific quantum state is hard to pin down, but lots of stuff (polarized light, atoms in excited states etc.) all happen with a distribution of states. If you were to communicate inside a device this limitation isn't really a problem, but if you need to send data from New York to LA it's very hard to send a single photon or atom (at least for the moment), and if you're sending a million photons, in some collection of quantum states it's somewhat harder to guarantee security. I'm being a bit handwavy here, but a few years ago I did a simple demo quantum crypto project with polarized light, for a couple of hundred dollars in hardware borrowed from an optics lab for an afternoon it worked pretty well. Over the length of a table. Scaling up to fibre optics that move any meaningful distance isn't impossible, but if done wrong you end up rapidly defeating your own crypto system.
For those who don't know, a quantum computer can factor products of primes in polynomial time, with a certain probability of success, but right now because you can't build quantum computer which more than a few qubits you are limited to trivial problems. If you could build a multi-million qubit system you could, with a certain probability of success, factor large products primes such as those used in cryptography in polynomial time.
People generally mention that quantum computing will spell the doom for current crypto, but from what I read on different sites, it seems that it's not exactly that. So I would really appreciate if somebody could clarify it. For instance, on Wikipedia there is this:
So, the problem is only for public key crypto, and for AES we just switch to 512 bit keys and no problem? Also if quantum computers don't do all that great against AES, wouldn't be it just a problem of finding somethinig else they have trouble with that could be used for public key crypto?
But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing
At least the number of burglaries will go down
politicians are like babies' nappies: they should both be changed regularly and for the same reasons
Quantum computing could break known asymmetric cyphers, not symmetric. I'm not aware of any quantum solution to breaking any modern popular symmetric algorithms.
Also worth mentioning is that there's really no way the FBI could have known exactly what they'd find. They broke into a home and recovered lots of information, one piece of which proved useful to decrypting messages. If they hadn't found that, who knows what they would have done? Point is don't lower your guard yet - this isn't proof that encryption is rock solid so much as evidence in that direction.
In the end, let's assume unbreakable encryption is readily available. The weakness is in the human factor, since (ultimately) humans have to, at some point, interact with that encryption for it to contain useful information. Looking at the direction England and other countries are going, a government's solution isn't to invest in supercomputers to attack the cryptography; it's to create a set of laws criminalizing a failure to decrypt. Such a failure would be penalized by as much (or more, given the absurd magnitude of criminal damages associated with most modern electronic-targeting laws) as the charges against you for which the cyphertext is relevant. Your information could be protected until the end of the universe while your corpse rots away for some form of electronic obstruction of justice.
There is a pervasive attitude of "If you have done nothing wrong, you have nothing to hide" that seems to be driving a lot of the thrust behind modern laws and solutions. A jury could be (and has been) biased against you just for possession of encrypted material. Why would a legitimate person need to encrypt their documents? Why wouldn't they decrypt them for authorities? "Because they're mine, not yours, and not the government's" isn't something a lot of people sympathize with. I suppose the point I'm trying to make is, while progress on the cryptographic front to stay ahead of authorities (and "bad guys", and the intersection of the two) is critical, it's also critical to enforce a right to innocently encrypt data in the first place.
But sorry to be predominantly negative - overall, a great article that exposes the world of cryptography (and its importance) in terms a layman could understand.
For one, AES is designed to have fixed key sizes, so "just switching to 512 bits" is not as trivial as you may think. Also, not all public key cryptosystems are based on the RSA problem.
Quantum computers can factor the product of two prime numbers in polynomial time, so RSA would be broken. A modification of that algorithm allows certain cases of the discrete logarithm problem to be solved efficiently as well, so DH and ElGamal would be broken also. Luckily, quantum computers are not yet known to be able to solve NP complete problems in polynomial time, so cryptosystems based on NP complete problems (Polly Cracker systems, for example) would still be secure assuming that P != NP. There are also hard lattice problems which quantum computers are not known to be more efficient at solving, which can be used to construct cryptosystems, and there was an early public key cryptosystem based on a group theoretic problem which is known to be secure against quantum computing.
So basically, quantum computing is not really a problem at all, at least not in a theoretical sense. It throws a bit of a wrench into some standard hardness assumptions, but nothing too bad.
Palm trees and 8
Encryptions that rely on the difficulty large integer factorization like RSA are indeed "doomed", because Shor's algorithm will be able to do that in polynomial time. This is a very rare exception. You can literally count the number of quantum algorithms known which can reduce the complexity class of such interesting problems with your fingers. Simply choosing an encryption method that doesn't rely on the difficulty of large integer factorization or one of the other in the "quantum age" no-longer-difficult problems will save traditional encryption.
Grover's algorithm is a good example of what quantum computers may actually be useful for: reduce execution times without reducing the complexity of many problems. The solution for these attacks on classic cryptography will be (as you pointed out) to simply increase the problem size (e.g. key length).
Yep. There's a *very* limited set of tasks that quantum computing can be used for. Factoring numbers just happens to be one of them, that's why it's always dragged out in articles about quantum computing.
To be more specific, a problem needs these properties for a quantum computer to be useful:
1. The only way to solve it is to guess answers repeatedly and check them,
2. There are n possible answers to check,
3. Every possible answer takes the same amount of time to check, and
4. There are no clues about which answers might be better: generating possibilities randomly is just as good as checking them in some special order.
(list lifted from wikipedia)
Even if your problem is quantum-friendly there are still some major obstacles, eg. picking the correct answer out of the mess of results.
And ... even if you can manage all that it only reduces the search time to the square root of brute force. In the case of encryption the other person can simply double the length of his encryption key and you're right back to square one again.
No sig today...
Quantum link encryption is completly unbreakable, according to the mathematics. It's of niche uses, because you need a continuous quantum path from end to end, but useful for those applications where a fiberoptic link needs to be protected from intercepts anywhere along it's length, like connecting military bases. There are implimentation attacks based on things like overwhelming the photon sensors, but the fundamental mathematics has been proven unbreakable.
Can't actually store quantum-encrypted information, though. Not yet. But it does mean that if you have the two endpoints physically secure, and a fiber linking them, you don't have to worry about someone tapping the fiber.
I have an algorithm that lets me factor any number with runtime complexity O(1) with a probability 1/(2^log2(n)) and can run on any system with support for /dev/random. No need for expensive quantum hardware. Preliminary tests have been able to break 4-bit RSA quite reliably. Encryption as we know it is doomed.
Where should I go to collect my grant money?
PS: You can leave the Nobel Prize next to my garden gnome. Thanks.
xkcd is never obligatory. Form your own opinions and speak for yourself rather than simply agreeing with another individual.
And they'll break any law to accomplish the mission. The FBI has murderers and serial killers who are confidential informants. They also have thieves who are confidential informants.
It's a surprise to me that some Russian spies who you'd expect would be trained to deal with counter intelligence would be so careless.
Must contain upper and lower case. Must contain at least one number. Must be EIGHT characters long.
This means my 'Passw0rd' is OK.
Have gnu, will travel.
There are two problems with your statement.
First, the way current Quantum Encryption works is just for a key exchange. In reality, a Quantum Key Exchange is a way to collaborate and cooperatively generate a key, not a way to transmit arbitrary bits. It relies on the fact that if Alice and Bob are exchanging a key, half of the bits Bob gets are going to be wrong, and he won't know which ones until they talk about it afterwards. An intermediary can't intercept the key and still make sure it gets to Bob, because he or she would have to try to regenerate the intercepted bits, and because there has been no exchange yet to determine which bits were "wrong", it can't tell how the particle was actually supposed to be polarized. This is a gross oversimplification (none of the bits are actually wrong, Bob is actually just guessing at which polarization to use to interpret them), but the net result is that the exchange can only be used to exchange keys, at which point classical cryptography schemes are used (and at that point have any weaknesses that the encryption scheme has).
Second, math can say whatever it wants about the security of quantum key exchanges, but there is still always the possibility that we got some portion of the observational physics wrong and the world doesn't work quite like we think it does. At that point, the math would be describing a universe that is not ours and does not do you any good, no matter how well it proves the encryption unbreakable.
You almost always agree with another individual, unless you are suffering from schizophrenia or some other disease of the mind (and probably frequently even then). Very few people get to be the one to synthesize any truly new thought, and there is no shame in giving credit to a fellow human who has already spoken what you were thinking in at least as eloquent a manner as you were likely to come up with.
In fact, I'd wager to say dozens of people have replied to Obligatory xkcd comments with more or less exactly what you have written here just during the course of the relatively short history of slashdotting.
Then you get stupid password systems which state your password must be "at least 6 letters, including 1 upper case and 1 number", about 38 bits. Or even worse "between 6 and 8 characters".
Those systems are generally not trying to protect against people with direct access to the encrypted data files. Instead, they are *login* passwords for systems where attackers do not have direct access to the protected data.
In principle, each of those systems should detect repeat login failures and delay or deny further attempts. In that case, the attacker doesn't get to try countless thousands of guesses. Security holes are very common in those types of systems, but it's not necessarily just because the password is 8 characters long.
Someone has been reading XKCD.
The English word is burgle. The American word is burglarize. It's one of the more amusing Americanisms, but it is valid American.
I am TheRaven on Soylent News
A couple of thousands do (about 5 times the lenght of the number you want to factor). But what you really need is the ability to perform multi-billion gate-operations (while the QFT itself is quadratic, Shor also uses modular exponentiation which makes it a cubic O(n^3) algorithm) within the decoherence time (usually measured in milliseconds or seconds) and with a technical accuracy to the tune of 99.9999999% - a quantum computer is, after all, an analogous device: qubits don't "lock in"; a NOT-gate e.g. thus has to be an exact 180 deg; rotation and neither 179.999 nor 180.001 deg (does not matter for a couple of gates in toy problems but those imperfections add up).
Quantum error correction can somewhat mitigate the former problem (at the cost of about one order of magnitude overhead in both space and time) but not the later. So if it's feasible at all (which is by no means certain as there might be hidden constraints on scalability), we probably won't live to see it.
ignatius
Proper quantum computation (like Shor's Algorithm) isn't probabilistic at all.
Also, you don't need millions of qbits to factor primes. You need on the order of 10x the number of bits in the prime.
256 bit hash, triple blowfish, AES outer envelope, Micro-SDHC card in a hollow coin, in a coin tray on your dresser.
I killed da wabbit -Elmer Fudd
So, the problem is only for public key crypto, and for AES we just switch to 512 bit keys and no problem?
Not necessarily. At present we know of a small number of quantum algorithms for problems such as factorization and database search. There are some brilliant theorists working on these things, but the total amount of (wo)manpower being applied to these problems is constrained by the fact that we don't really have any quantum computers to use this stuff with. A consequence of this is that there are vastly more problems for which we don't have a quantum algorithm than those for which we do.
This has led to a lot of interest in 'post-quantum cryptography' and flood of research papers proposing new public-key cryptosystems based on mathematical problems we don't know how to solve with quantum computers. Another poster mentioned the McEliece cryptosystem, which is based on problems in coding theory. That's a little bit old-school. The new hotness is lattice problems --- go to any top academic crypto conference and you'll see a bunch of papers using these. If you're really interested in this stuff, here's a pretty good intro to a book on the subject of post-quantum crypto.
However, all this talk is good for researchers in non-standard areas, but it shouldn't lead anyone to be overconfident that these problems will stay resistant to quantum solutions. You can more or less bank on there being some future 'golden age of quantum computing theory' which should take off right about the same time useful quantum computers become available. Predictably, the problems that receive the most attention will be the ones most widely used at the time --- including the ones underlying the most widely used cryptosystems.
The one other thing I should mention is that there's a big difference between finding quantum algorithms for fundamental problems such as database search (Grover's algorithm) or number theoretic problems (Shor's algorithm) and finding quantum algorithms for extremely complex specialized systems like AES. Finding an algorithm that solves a major number theory problem is a big contribution --- if you break a particular cryptosystem, people will just shift away from it eventually and your work will become a footnote. Simultaneously, developing an algorithm that attacks AES is enormously harder using the relatively primitive techniques we currently have. So while right now our best approach to breaking symmetric algorithms is to use generic tools like Grover's algorithm, that's not aways guaranteed to be the case.
Of course, crypto's important to us and the chance for a quantum-resistant cryptosystem is better than none at all, so this is still useful work. If you care about your crypto you need to this stuff it all with a little grain of salt, and hope that QCs are far in the future.
Hash functions and symmetric ciphers are somewhat safe against quantum computers. A quantum computer can give a significant speedup, but only to the point of reducing the strength to half the number of bits it would otherwise have. So, just design the algorithms to work with twice as many bits as needed to break them on a classical computer, and they will most likely be secured against a quantum computer as well.
However public key encryption schemes (especially those built on factorization like RSA) can be broken much faster on a quantum computer. For those just increasing the key length isn't sufficient to give you the edge you need to protect against quantum computers. Research is happening in the field of developing public key schemes that are secure against quantum computers, but I don't know what the current state of that is.
There is a major difference. You don't need a quantum computer to do quantum cryptography. You need a device that can send single qubits, and a device that can receive and measure them. But these devices don't need to work on more than one bit at a time, so they are not really quantum computers. The algorithms do involve a lot of computation, but that computation happens on a classical computer which is doing computation on the data before and after it has been in the state of qubits.
There is a method to increase the range at which quantum encryption can work, which involve quantum computers. You cannot use a classical repeater with qubits because the repeater would collapse the quantum state in pretty much the same way an eavesdropper would. Instead you would use devices that takes advantage of entanglement of qubits. Each such device will require a 2-bit quantum computer in order to work. But a 2-bit quantum computer is no use for breaking any sort of encryption. The encryptions that you could break using a 2-bit quantum computer are much easier to break using a classical computer and a lookup table of all the possible keys.
Do you care about the security of your wireless mouse?
probably true that a few thousand would suffice for current cryto systems. But you're then into a trivial cat and mouse game. If it's easy to factor a 4 bit product of primes with a quantum computer, use 16 or 32. If it's easy to build a quantum computer to factor 256 bit RSA with a few thousand gates, well use 1024. If building a crypto system scales more easily than the quantum computer does, well, you're still ahead.
The problem of qubits though is more subtle than just the record being a 7 or 8 qubit system. Without millions in grant money the most complex transistor system you could build in a uni lab would be, frankly, pretty pathetic compared to what can be fabbed by intel. If you want a large scale quantum computer you probably are going to need large scale R&D and manufacturing. That sort of investment wasn't made in quantum computing 4 or 5 years ago, and I haven't touched the topic since so I don't know what's happened since. I suspect that the semiconductor guys are watching the research to try and figure out just how complex and expensive it's going to be to build a system that can factor something more complex than 652133 (719x907). 5 years ago when I was looking into it the big question was which quantum system was most viable, excited electronic, or nuclear states, if so which ones and so on. That's a few steps away from being able to build a scalable system, but it isn't necessarily a huge breakthrough to go from being able to build 100 qubit system(of some time) in a lab to a billion qubit system at intel, though it might be. Depends on a lot of factors.
I'm not well-versed in Shor's algorithm, but since the number of operations required scales polynomially, I suspect that the time that a given machine takes to factor a number scales polynomially with the number of bits. A 1064 bit encryption would just take 4 times longer. That doesn't make moving to longer keys a viable solution.
The trouble right now doesn't lie in whether or not Intel's resources are being thrown at it; Intel can't fab ion traps. Fundamentally new ideas regarding producing and interacting qubits will be needed before it could possibly move to a commercial R&D effort. Some people are working with silicon-based systems because of the possibility of, at least partially, using existing technology to build them but those systems have many limitations.
So if this is the future...where's my jet pack?
Even switching to 512-bit keys is probably an overreaction. AES keys go up to 256-bit mostly to provide safety against these theoretical quantum attacks. Federal standards are only now trying to phase 80-bit equivalent algorithms out of new products, (even though they're still a long way away from being breakable), and while AES-128 isn't considered good enough to protect top secret information, only secret, AES-192 is considered fine for top secret info. Excluding AES-128 is generally seen as an insurance measure against quantum computers.