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."

CWMike

[pjt33]

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?

Re:Quantum Encryption

[Sir_Sri]

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.

Re:CWMike

[beakerMeep]

Pretty obvious really -- CWMike along with Julie188 have been plaguing Slashdot with this InfoWorld/ComputerWorld tripe for years. The articles are almost always either sensationalism (magic future computing may crack your password, clock is ticking!) or trolling flamebait (is [insert favorite mobile OS] dangerous?). It's bullshit blogspam and Slashdot can do better. I just wish they cared a bit more about weeding out this kind of stuff.

Re:Cracking isn't the problem

[jimicus]

Thing is, much of the time you can be pretty sure that a particular string of plaintext will appear at least somewhere in the decrypted result.

In the case of your credit card number, for example, there's a few things we can do to eliminate most of the apparently valid numbers:

• Mastercard and Visa both allocate the first four digits of card numbers to individual banks. These blocks don't overlap between card types - there's no such thing as a Mastercard that begins with 4547, for instance. If I know where you live, I can take a reasonable guess that your card was issued by a bank in your country and immediately rule out any numbers that weren't allocated to a bank in your country.
• Banks frequently use a predictable pattern to fill the rest of the card number, such as account number (which may itself have a check digit, so you essentially wind up with two check digits in the card number). If you know what patterns the banks in your country use, you can cut down the potential matches further.
• Beyond this, we probably need insider knowledge of the banks own processes - what numbers have/have not been allocated yet? Can we figure out from the card number when the associated account was opened? - if you're 25 years old, it's unlikely you'll have a number indicating a 30 year old account.

Re:And the news here is what?

[Z00L00K]

However not all encryption algorithms can be cracked using quantum computers. The quantum computer cracking of encryption relies on the factorization algorithm and prime numbers but if an encryption is based on another technology the quantum computers aren't a help.

So the Navajo code talkers are still safe.

Re:What exactly is being broken by quantum compute

[dachshund]

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 [wikipedia.org] --- 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 [pqcrypto.org].

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.

Re:Quantum Encryption

[kasperd]

There are some quantum encryption algorithms that are supposed to be safe from decryption by quantum computers.

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.

But quantum computers are required to do the quantum encryption, so there will be a kind of race to install enough of the new machines, before those who get the first few of them, misuse them

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.