Beta
×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

The Clock Is Ticking On Encryption

timothy posted more than 3 years ago | from the promise-that-keeps-on-giving dept.

Encryption 228

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

cancel ×

228 comments

Sorry! There are no comments related to the filter you selected.

Quantum Encryption (1)

neiljt (238527) | more than 3 years ago | (#34598926)

Will quantum encryption be similarly trivial to crack?

Re:Quantum Encryption (4, Funny)

peragrin (659227) | more than 3 years ago | (#34598948)

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.

And the news here is what? (2)

2.7182 (819680) | more than 3 years ago | (#34598958)

Welcome to 1994, and Peter Shor's discovery of how to factor with quantum computers.

Re:And the news here is what? (3, Informative)

Z00L00K (682162) | more than 3 years ago | (#34599808)

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:Quantum Encryption (0)

Anonymous Coward | more than 3 years ago | (#34598950)

Only if you use gigabit encryption. If you want real security, you go with petrabit encryption.

Re:petrabit encryption (1)

TaoPhoenix (980487) | more than 3 years ago | (#34598998)

Rocks are indeed mysterious. However, you probably meant petabit encryption.

Re:Quantum Encryption (3, Insightful)

Black Parrot (19622) | more than 3 years ago | (#34599032)

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.

Re:Quantum Encryption (1)

HungryHobo (1314109) | more than 3 years ago | (#34598964)

I was under the impression that some of the crypto algorithms were safe from quantum computing.

Re:Quantum Encryption (1)

Anonymous Coward | more than 3 years ago | (#34599000)

There are some quantum encryption algorithms that are supposed to be safe from decryption by quantum computers. 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 to destroy the anonymity that is essential for a democracy to work.

Re:Quantum Encryption (5, Informative)

Sir_Sri (199544) | more than 3 years ago | (#34599058)

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:Quantum Encryption (1)

Interoperable (1651953) | more than 3 years ago | (#34599220)

A multi-million qubit system wouldn't really be needed; a few thousand would probably be plenty if the states lasted for a while. I think the record sits at about a seven qubit register using trapped ions and they only last long enough for a proof-of-principle gate operation.

Re:Quantum Encryption (3, Funny)

Anonymous Coward | more than 3 years ago | (#34599566)

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.

Re:Quantum Encryption (1)

Lashat (1041424) | more than 3 years ago | (#34599928)

Exactly what he said. :s

Re:Quantum Encryption (3, Funny)

f3rret (1776822) | more than 3 years ago | (#34599046)

Yes it will. Just because the encryption is "quantum" does not mean it's not trivially breakable with rubber hose cryptanalysis.

Re:Quantum Encryption (2)

wagnerrp (1305589) | more than 3 years ago | (#34600066)

Someone has been reading XKCD [xkcd.com] .

Re:Quantum Encryption (1)

Totenglocke (1291680) | more than 3 years ago | (#34599050)

It doesn't matter - lets see them use raw computing power to generate the missing keyfiles to my TrueCrypt partition.

Re:Quantum Encryption (1)

citizenr (871508) | more than 3 years ago | (#34599066)

Will quantum encryption be similarly trivial to crack?

"quantum encryption" is not an encryption per se, but a method of sending sensitive information

Re:Quantum Encryption (0)

Anonymous Coward | more than 3 years ago | (#34599316)

I've read some time ago something about quantum encryption being already cracked.
btw. if I try to decrypt a quantum encrypted message will it become destroyed ?
Then I don't even need to decrypt it... if the intended recipient can't read it is almost as good as if I read it.

Re:Quantum Encryption (2)

SuricouRaven (1897204) | more than 3 years ago | (#34599546)

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.

Re:Quantum Encryption (2)

cforciea (1926392) | more than 3 years ago | (#34599800)

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.

strange brew that's also good for you. (-1)

Anonymous Coward | more than 3 years ago | (#34598934)

That would be home made Kombucha.

Re:strange brew that's also good for you. (1)

lxs (131946) | more than 3 years ago | (#34598982)

Side effects include turning into a spambot touting the virtues of moldy tea.

The U.S. government is VERY corrupt. (2, Insightful)

Anonymous Coward | more than 3 years ago | (#34598960)

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.

Re:The U.S. government is VERY corrupt. (4, Insightful)

Black Parrot (19622) | more than 3 years ago | (#34599016)

That kind of behavior, burglarizing houses, committing a crime to stop other crimes, is destructive to the rest of the nation.

I don't find it such a bad thing, if they have a warrant from a non-corrupt judicial system.

You can hardly say fighting espionage is inherently corrupt.

Re:The U.S. government is VERY corrupt. (1)

Anonymous Coward | more than 3 years ago | (#34599274)

I don't find it such a bad thing, if they have a warrant from a non-corrupt judicial system.

You can hardly say fighting espionage is inherently corrupt.

OK, say that someone what a warrant to go in to my home and steal my personal stuff. Will I be informed so that I can present proof that they don't really need to do that?
I can't really see how that would work with a fair judicial system where everyone is allowed to defend themselves.
In that particular case I would not be given the opportunity to defend myself until after my entire world have been turned upside-down.

Re:The U.S. government is VERY corrupt. (1)

SuricouRaven (1897204) | more than 3 years ago | (#34599560)

Obviously you can't be informed, because then you might use the warning to relocate anything you don't want found. In princible, the ideal would be for you to recieve compensation afterwards of far more than the cost of repairing the house and any damaged posessions. In reality, you'd be more likely to get absolutly nothing except rumors from the neighbours over why the police broke your door down.

Re:The U.S. government is VERY corrupt. (1)

st0rmshad0w (412661) | more than 3 years ago | (#34599738)

Will I be charged with capital murder of a federal agent for shooting the armed burglar that I find in my house? Or will it be a perfectly legal response like it would be if the burglar was a regular citizen.

Re:The U.S. government is VERY corrupt. (5, Insightful)

Anonymous Coward | more than 3 years ago | (#34599926)

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.

Re:The U.S. government is VERY corrupt. (1)

Jawnn (445279) | more than 3 years ago | (#34599994)

That kind of behavior, burglarizing houses, committing a crime to stop other crimes, is destructive to the rest of the nation.

I don't find it such a bad thing, if they have a warrant from a non-corrupt judicial system.

You can hardly say fighting espionage is inherently corrupt.

True enough, but a government that increasingly finds it necessary to hide it's actions in that arena from even the tacit judicial oversight now in place deserves every bit of the suspicion it suffers, and then some. History has (or should have) taught us well that the excuse that "we're protecting you from " is almost always a sign of bad things to come.

Re:Obligatory xkcd (-1, Redundant)

TaoPhoenix (980487) | more than 3 years ago | (#34599018)

Re:Obligatory xkcd (2)

heptapod (243146) | more than 3 years ago | (#34599594)

xkcd is never obligatory. Form your own opinions and speak for yourself rather than simply agreeing with another individual.

Re:Obligatory xkcd (2)

cforciea (1926392) | more than 3 years ago | (#34599840)

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.

The FBI has vigilantes (3, Interesting)

elucido (870205) | more than 3 years ago | (#34599614)

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.

Re:The U.S. government is VERY corrupt. (0)

Anonymous Coward | more than 3 years ago | (#34599746)

You have to love how the US government is fine with committing crimes to prevent crimes and yet they condemn Wikileaks for exactly the same thing.

the word is burgle (1)

samjam (256347) | more than 3 years ago | (#34599980)

To burglarize a house is to turn the house into a burglar - I don't think that's what the FBI did, whatever they said they did.

I'm willing to believe the house was burgled - that seems more usual nefarious behaviour --- yes - a word with all the vowels in

Re:The U.S. government is VERY corrupt. (0, Offtopic)

Anonymous Coward | more than 3 years ago | (#34600064)

The worse thing is they invented a non-word 'burglarize' when 'burgle' was already in use by literate people.

I have better daydreams than this (1)

dragisha (788) | more than 3 years ago | (#34598966)

Let me submit one to Slashdot too.

Is "quantum computing" the next "cloud computing"? (3, Insightful)

Anonymous Coward | more than 3 years ago | (#34598970)

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.

Re:Is "quantum computing" the next "cloud computin (2)

Joce640k (829181) | more than 3 years ago | (#34599334)

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

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.

Quite right (5, Insightful)

AaxelB (1034884) | more than 3 years ago | (#34598974)

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

Re:Quite right (2)

Mr. Underbridge (666784) | more than 3 years ago | (#34599084)

but the fact that quantum computing breaks RSA is pretty standard knowledge (among people who have heard of quantum computing)

Yep - and given how well it's currently working, you're screwed if you're using 4-bit RSA (to steal a famous quote from Schneier).

We've been hearing this story for long enough that the 'quantum computing breaks crypto' crowd ought to stop broadcasting that claim until they can break keys of arbitrary length.

Re:Quite right (0)

Anonymous Coward | more than 3 years ago | (#34599210)

Exactly, I can factor a two bit number faster than they can click their quantum machine power-on button. So can any digital CPU.
It's not 128-RSA at risk, they aren't even at at a level where they could have been useful if they had appeared in the 1920s.
Can quantum computers scale at all? They apparently need insane amounts of grant money to work. Other than that they rely on quantum magic that hs been only "shown" to work in theory.
Some quantum properties might be usable, but quantum computing sounds like snake oil of the worst class.

Re:Quite right (1)

rmav (1149097) | more than 3 years ago | (#34600048)

Some quantum properties might be usable, but quantum computing sounds like snake oil of the worst class.

My personal opinion is that quantum computing is - currently - mainly a means to get fat grants.
Roberto

Re:Quite right (1)

spottedkangaroo (451692) | more than 3 years ago | (#34599120)

A minor nit: any "hard" problem that's harder one way than the other will ultimately be attackable via quantum methods. This is true for almost any public key system including ECC. There hasn't been as much work quantum vs ECC, but only because ECC is pretty cutting edge.

the source of all human knowledge [wikipedia.org] has a couple links to research on the topic.

It is certainly the case that you can overcome quantum attacks by using quantum crypto, but that's going to be a problem for people who have less money than banks.

One time pads are another option, but then we have to go back to the days of physically pre-sharing the keys. That's an interesting notion too ... In Fire Upon the Deep, there's much ado regarding missions to deliver one time use cipher entropy to other locations using space ships.

Re:Quite right (1)

AaxelB (1034884) | more than 3 years ago | (#34599564)

A minor nit: any "hard" problem that's harder one way than the other will ultimately be attackable via quantum methods.

Can you point me toward more information on this? I haven't heard anything like that before -- all arguments I've seen that say quantum computing breaks cryptographic schemes are just based on Shor's algorithm, which I didn't think had such broad implications. (I didn't know it breaks ECC, too.)

Re:Quite right (1)

Richard W.M. Jones (591125) | more than 3 years ago | (#34599208)

I knew it, yet I didn't know it.

Re:Quite right (1)

elashish14 (1302231) | more than 3 years ago | (#34599368)

Obviously you didn't RTFA, which states EC cryptography is just as easily breakable via quantum computation (moreso, in fact, than RSA). The upshot: use QKD to transmit the key, then rely on classical encryption schemes (e.g. AES) for the message (for which QKD is nearly useless). Actually, it sounds perfect since QKD is generally considered unbreakable. Then again, computing power increases so quickly that I doubt AES will be secure for long.

wow, I actually learned something FTFA.

Re:Quite right (1)

AaxelB (1034884) | more than 3 years ago | (#34599538)

Yeah, I didn't know about ECC also being vulnerable (I learned something, too!). The problem with using QKD is that it requires all involved parties to be on a network of quantum computers. The biggest danger I see is when a few people (like the NSA) have quantum computers, but no one else does. If there aren't classical public-key schemes that can stand up to quantum computing, then security as we know it is basically broken, and anyone who wants a real guarantee of privacy will have to resort to one-time pads.

Cost/benefit (1)

bill_mcgonigle (4333) | more than 3 years ago | (#34599420)

The title is misleading, but the fact that quantum computing breaks RSA is pretty standard knowledge

Yeah, but even if they knew it was RSA, breaking into a house is still easier [xkcd.com] than running a quantum computer. The FBI is pretty expert in this type of crime.

This operation was probably cheaper and took less time than getting access to the box at Fort Meade.

Re:Quite right (1)

steveb3210 (962811) | more than 3 years ago | (#34599816)

Yeah, that's true. 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.

Much like people work under the assumption that factoring is hard, you are working under the assumption that factoring is not NP-Complete. Nobody has proven this either...

Re:Quite right (1)

rmav (1149097) | more than 3 years ago | (#34600040)

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.

Actually, all discrete-logarithm based schemes can be broken in polynomial time by quantum computing, hence also elliptic curve cryptography.The details have to be re-worked out for each such scheme, but that's true also of any classical attack. See for instance http://www.mathcs.richmond.edu/~jad/summerwork/ellipticcurvequantum.pdf [richmond.edu]

Roberto

For all my encryption cracking needs... (4, Insightful)

lxs (131946) | more than 3 years ago | (#34598976)

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.

Re:For all my encryption cracking needs... (2)

Black Parrot (19622) | more than 3 years ago | (#34599048)

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.

And if you do get cracked, you just snort some of the dust and then you don't care anyway.

Re:For all my encryption cracking needs... (1)

elashish14 (1302231) | more than 3 years ago | (#34599528)

Right. And 640K should be enough for anyone too, right?

Qubits have already been demonstrated with great coherence times and we're now making great advances in fabrication so they can be scaled up to thousands of qubits and well beyond. There's no reason to believe that we won't have quantum machines with computational power meeting (if not exceeding, by a large margin) today's classical machines within a generation. Then again, if you refuse to seriously consider any technological innovation that takes more than a week to develop, maybe you don't believe in anything at all.

CWMike (5, Informative)

pjt33 (739471) | more than 3 years ago | (#34598984)

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 (5, Informative)

beakerMeep (716990) | more than 3 years ago | (#34599132)

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:CWMike (1)

heptapod (243146) | more than 3 years ago | (#34599604)

If only they followed Roland Piquepaille's lead... TO THE GRAVE!!!

Re:CWMike (1)

PhrostyMcByte (589271) | more than 3 years ago | (#34599158)

Who cares? If it's interesting, it's interesting. In this case it's not really very interesting, but I don't see a point in attaching a stigma because of the submitter. It's not like it's possible for the editors to pay any less attention to the submissions to let something slide!

Re:CWMike (1)

ScaryTom (1057310) | more than 3 years ago | (#34599934)

Anyone prepared to take a bet that the CW of CWMike stands for ComputerWorld

I'm guessing Michael R. Farnum -- http://blogs.computerworld.com/farnum [computerworld.com] -- is your man.

Useless article (1)

gozu (541069) | more than 3 years ago | (#34599004)

Basically, quantum computers could do magic on encryption, probably, in the future, possibly in 20 years?

Also possible: flying cars, cold fusion and immortality.

Cracking isn't the problem (2)

thogard (43403) | more than 3 years ago | (#34599008)

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.

Re:Cracking isn't the problem (0)

Anonymous Coward | more than 3 years ago | (#34599080)

In all the RSA competitions (such as the DES Challenges Deep Crack was involved in) the encrypted message was known to begin "The unknown message is: "

http://www.rsa.com/rsalabs/node.asp?id=2100

This makes identifying you have the correct key trivial.

Re:Cracking isn't the problem (0)

Anonymous Coward | more than 3 years ago | (#34599138)

If you're going to mangle your grammar and spelling, at least use some god damn punctuation.

Re:Cracking isn't the problem (5, Informative)

jimicus (737525) | more than 3 years ago | (#34599228)

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:Cracking isn't the problem (1)

SuricouRaven (1897204) | more than 3 years ago | (#34599586)

I wrote a proof-of-concept cracker for WEP that ran into a similar situation: It found a lot of keys that appeared to give valid, checksum-good packets. So I just modified it to require that every one in a series of packets all came out good, and that did it. Still too slow to be practical though... could break 40bit, eventually, if someone were to optimise it.

Obligatory... (-1)

Anonymous Coward | more than 3 years ago | (#34599028)

...XKCD Link: http://xkcd.com/538/ [xkcd.com]

Yawn (0)

Anonymous Coward | more than 3 years ago | (#34599052)

*Yawn*

Another crypto post about stuff we already have known about for a few years and won't affect us for a great many few years into the future.

In related news, seti@home scores are 10x faster (1)

fahlenkp (1939942) | more than 3 years ago | (#34599054)

Somehow they took my boring news of Moores's law - My seti@home and primegrid stats are moving 10x faster with my new laptop's gpu. They turned that into - IN THE FUTURE COMPUTERS MIGHT BE REALLY FAST AND MELT YOUR 1960s PASSWORD! It isn't exciting. Quantum computing will come with both encryption and decryption. Nobody cares what it does to your password from 15 years ago.

Oblig (0, Redundant)

mtinsley (1283400) | more than 3 years ago | (#34599056)

At that rate he thinks it is likely we will have a quantum computer within 20 years.

http://xkcd.com/678/ [xkcd.com]

So.. (0)

Anonymous Coward | more than 3 years ago | (#34599064)

The burglarizing led to the ability to progressize the investigation, resulting in the Russians being expellized?

What exactly is being broken by quantum computers? (4, Interesting)

vadim_t (324782) | more than 3 years ago | (#34599068)

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:

Integer factorization is believed to be computationally infeasible with an ordinary computer for large integers if they are the product of few prime numbers (e.g., products of two 300-digit primes).[5] By comparison, a quantum computer could efficiently solve this problem using Shor's algorithm to find its factors. This ability would allow a quantum computer to decrypt many of the cryptographic systems in use today, in the sense that there would be a polynomial time (in the number of digits of the integer) algorithm for solving the problem.

It has been proven that applying Grover's algorithm to break a symmetric (secret key) algorithm by brute force requires roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case,[10] meaning that symmetric key lengths are effectively halved: AES-256 would have the same security against an attack using Grover's algorithm that AES-128 has against classical brute-force search

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?

Not exactly (3, Interesting)

betterunixthanunix (980855) | more than 3 years ago | (#34599166)

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.

Re:Not exactly (1)

Nursie (632944) | more than 3 years ago | (#34599598)

"For one, AES is designed to have fixed key sizes, so "just switching to 512 bits" is not as trivial as you may think."

Err, no. AES was based on a simplification of Rijndael, which was designed for arbitrary key lengths. It should be fairly easy to adapt the AES algorithm to longer keys.

Maybe not trivial, but likely not that hard.

Re:Not exactly (1)

betterunixthanunix (980855) | more than 3 years ago | (#34599806)

That is true, but the point is that it is non-trivial. Already, AES256 (well, a reduced number of rounds) is known to be vulnerable to related key attacks that AES128 is not vulnerable to. It might not be terribly hard to get Rijndael to work for arbitrary key sizes, but there is no guarantee or reason to believe that a 512 bit Rijndael would actually be more secure than 256 bit Rijndael (or that it would not be less secure, though this is not likely). Rijndael is not a provably secure cipher, so claiming that just increasing the key size is a quick fix is not quite right.

Re:What exactly is being broken by quantum compute (2)

pwilli (1102893) | more than 3 years ago | (#34599184)

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

Re:What exactly is being broken by quantum compute (1)

TheTurtlesMoves (1442727) | more than 3 years ago | (#34599500)

The practice of quantum computing makes it quite doubtful that they will be any better than classical attacks for the foreseeable future. The problem is that quantum computers have exponential complexity in *construction*. A 2n qbit machine needs much more than just 2x the qbit, but also better decoherence times and much higher fidelity on the quantum to classical output channel (it gets harder to "read" the answer).

To make matters worse. A n bit quantum computer cannot simulate a (n+1) bit quantum computer like we can do with classical computers. So if you know that "they" have a 1024 bit quantum computer (many decades away, some say much longer), you just need a 1025 bit key to be secure from that machine.

There is at least one public key method (McEliece cryptosystem) that is not vulnerable to quantum computing attacks. It requires very big (1Mb or larger) keys which is less of a problem these days than 10 year ago.

The silver lining (3, Insightful)

petes_PoV (912422) | more than 3 years ago | (#34599072)

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

Cryptography, eh? (3, Insightful)

Jahava (946858) | more than 3 years ago | (#34599090)

Quantum computing could break known asymmetric cyphers, not symmetric. I'm not aware of any quantum solution to breaking any modern popular symmetric algorithms.

  1. If the 27-character password that they used protected an asymmetric key, then the FBI had to break into their house to recover more than the 216-bit password ... they had to recover the password and the encrypted key that it protected.
  2. If, on the other hand, the 27-character password generated a symmetric key, then the entire discussion of quantum computing is irrelevant.

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.

Entering one of the spies' homes (1)

AHuxley (892839) | more than 3 years ago | (#34599144)

Is really just part of the feds useful toolkit.
They can look for extra CC's, books, address books, rolodex, business card, photos get noted, hobbies, signs of other crimes..
When they walk out they may have a pw and a whole new area area of inquiries.
But think back to the foreseeable past, most of what was sold on the commercial/telco and NATO market has been weakened in someway. Tempest leaks or design flaws allowed dreamy Enigma like plaintext decrypting or plaintext entry to be collected.
http://cryptome.org/jya/nsa-sun.htm [cryptome.org] hints at the past where many codes would become trivial.
Clean home, clean laptop, clean networking in one life, get another life and be creative for the bursts of chatter back home.
Mix it up and the feds will find it :) The telco network is theirs, end to end, know anything to do with anonymity/codes is a honeypot, if your working with/around the US federal gov, they have the funding to watch.

The clock is not tickling me... (1)

Yvanhoe (564877) | more than 3 years ago | (#34599214)

First, there are such things as quantum-computer resistant encryption algorithms. They are not in current usage but it is possible to do.
Second, there are more and more people who suspect that quantum computers may be a pipe dream : http://arstechnica.com/science/news/2010/06/magic-quantum-wand-does-not-vanish-hard-maths.ars [arstechnica.com]
It has been a good way to make people invest in fundamental research though ;-)

It's a wetware issue (1)

Matey-O (518004) | more than 3 years ago | (#34599240)

It's not your complex 27 character password that's the problem, it's the 8 bit, John the Ripper-rapeable password of the person you email that's the problem.

Re:It's a wetware issue (1)

JamesP (688957) | more than 3 years ago | (#34599568)

No, the problem is

The 27 letter password should have been memorizable

If IT Morons insist in a too complex password that changes all the time
then noting it down is the only way to keep access to the system.

Remember that if the password changes FBI will just break in again and see the note

Relative complex passwords that are easly memorizable are better.

True, but there is always a countermeasure (0)

gatkinso (15975) | more than 3 years ago | (#34599354)

Right now the whole encryption field is basically security through obscurity.

The math exists as to how to crack most crypto, it is just above most peoples heads. Much research into new attacks and methods are supressed in one form or another.

The factoring algorithms are bordering on trival... they just take a very long time to run.

Re:True, but there is always a countermeasure (0)

Anonymous Coward | more than 3 years ago | (#34599524)

citation please?

Re:True, but there is always a countermeasure (1)

Anonymous Coward | more than 3 years ago | (#34599548)

A brute-force algorithm is trivial... it just takes a very long time to run.

*slaps head* (1)

windcask (1795642) | more than 3 years ago | (#34599400)

What in the HELL is the point of a 27-character password if you're going to write it down?

People can go so egregiously far off the deep end to protect their security and then make the most basic of mistakes. A password of half that length with a decent encryption process would be nearly inconceivable to break in any practical length of time.

Re:*slaps head* (1)

isorox (205688) | more than 3 years ago | (#34599552)

What in the HELL is the point of a 27-character password if you're going to write it down?

People that haven't been taught to remember a phrase rather than a password.

On complex password I have for example, is 30 characters long -- 3 orders of magnitude stronger than a 128bit phrase, even if you knew it was entirely lowercase.

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

Re:*slaps head* (1)

d6 (1944790) | more than 3 years ago | (#34599682)

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

One system I dealt with recently at a largish company (multi-billions revenue) introduced tougher new password guidelines:

The tough new standard? Must contain upper and lower case. Must contain at least one number. Must be EIGHT characters long.

gah...

Thank goodnes! (2)

PPH (736903) | more than 3 years ago | (#34599776)

Must contain upper and lower case. Must contain at least one number. Must be EIGHT characters long.

This means my 'Passw0rd' is OK.

Re:*slaps head* (1)

Clueless Moron (548336) | more than 3 years ago | (#34599810)

The tough new standard? Must contain upper and lower case. Must contain at least one number. Must be EIGHT characters long.

The next logical step would be to mandate that everybody's password must be "Gv7nLXyP".

Re:*slaps head* (3, Insightful)

Waffle Iron (339739) | more than 3 years ago | (#34599852)

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.

One more thing (1)

Javagator (679604) | more than 3 years ago | (#34599504)

Now they just need to recruit spies that can remember 27 character passwords without writing them down.

Only Option (0)

Anonymous Coward | more than 3 years ago | (#34599584)

I say we take off and use a one-time pad from orbit. It's the only way to be sure..

DONT PANIC! (Quantum computer size & crypto) (1)

SLOGEN (165834) | more than 3 years ago | (#34599678)

DONT PANIC!

Today, quantum computers are *very* limited in size. The number 15 has been succesfully factored into the primes 3 and 5.

There is no really promising ways to produce large amounts (~1000) qbits. I strongly suspect that the difficulty in generating qbits is (at least) exponential in the amount of qbits to produce.

qbits cannot be composed after they creation (at least with known physics), so I am definatly *not* holding my breath for quantum computers to break RSA-2048 or AES256.

When RSA is broken (when it takes less than a few hundred years on average to find a secret key), we already have multiple other crypto-systems ready. Elliptic versions of RSA are *already* part of standard-implementations in browsers and they shift the amount of qbits required with several orders of magnitude (with known math).

One-time pad encryption (1)

spaceyhackerlady (462530) | more than 3 years ago | (#34599720)

One-time pad encryption doesn't care how much compute power, quantum or otherwise, you throw at it. If you don't have the key, you don't have the message. Period.

I've sometimes thought it would be fun to hook something really random (like a geiger counter) up to my computer, generate a DVD full of really random encryption keys, send a copy to my Mom, and we could send email that even the NSA couldn't read.

...laura

Re:One-time pad encryption (1)

Clueless Moron (548336) | more than 3 years ago | (#34599834)

The other nice thing about OTP is that for a given encrypted message, you can create an OTP that produces any message you want.

So, for example, if the message gets intercepted and the NSA demands you produce the OTP key, you can provide one that decrypts the message into a recipe for cranberry muffins.

why encryption is truly useless (1)

Anonymous Coward | more than 3 years ago | (#34599768)

Obligatory XKCD http://xkcd.com/538/ with some notes:

The cyber-criminal drops a keyboard logger on your system.
The NSA would try to crack it.
The CIA would use the wrench.
The FBI gets a warrant and searches for it taped under your keyboard.
and your girlfriend gets you drunk and asks you for it.... wait a minute, there is no way you have a girlfirend that hot. omg, she's Mossad!

All Encryption Is Equally Easy to Break (1)

Greyfox (87712) | more than 3 years ago | (#34599944)

Given a pair of needle nosed pliers and some soft body parts.
Load More Comments
Slashdot Login

Need an Account?

Forgot your password?

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>