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

Comments

Quite right

[AaxelB]

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.

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: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: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: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:The U.S. government is VERY corrupt.

[Anonymous Coward]

I rather think that the FBI is quite careful to check that you are not in the house before they go in. They probably have someone trailing you who will warn them if you start heading home or if they lose track of where you are. They are not idiots and have no interest in getting into a firefight unnecessarily.

Basically, stop being stupid. The FBI is not going round breaking into people's houses willy-nilly. They entered those specific houses because they had probable cause to believe that their occupants were hostile agents of a foreign power engaged in illegal espionage, and they had acquired warrants to do so, supported by oath and particularly describing the places to be searched and the things to be seized. Are you seriously complaining because government agents obeyed the Constitution to the letter in the course of exercising their duty to uphold the rule of law?! I can scarcely believe that any American would display such contempt for the principles on which your hard-won freedom is founded.