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."
Will quantum encryption be similarly trivial to crack?
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.
Let me submit one to Slashdot too.
http://opencm3.net, http://www.nongnu.org/gm2/
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.
Side effects include turning into a spambot touting the virtues of moldy tea.
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?
Rocks are indeed mysterious. However, you probably meant petabit encryption.
My first Journal Entry ever, in 8 years! http://slashdot.org/journal/365947/aphelion-scifi-fantasy-horror-poetry-webzine
Basically, quantum computers could do magic on encryption, probably, in the future, possibly in 20 years?
Also possible: flying cars, cold fusion and immortality.
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.
*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.
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.
http://xkcd.com/678/
The burglarizing led to the ability to progressize the investigation, resulting in the Russians being expellized?
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.
Is really just part of the feds useful toolkit. :) 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.
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 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
Domestic spying is now "Benign Information Gathering"
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
Apparently, from what I see, most of CWMike's submissions are Computer World articles.
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).
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
It has been a good way to make people invest in fundamental research though
The Wise adapts himself to the world. The Fool adapts the world to himself. Therefore, all progress depends on the Fool.
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.
"Draco dormiens nunquam titillandus."
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...
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.
I am very small, utmostly microscopic.
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.
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 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.
My God, it's Full of Source!
OUTSIDE_IP=$(dig +short my.ip @outsideip.net)
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 Grey Goo disaster happened 3 billion years ago. This rock is covered in self replicating machines!
Now they just need to recruit spies that can remember 27 character passwords without writing them down.
I say we take off and use a one-time pad from orbit. It's the only way to be sure..
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.
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).
SLOGEN [ http://ungdomshus.nu : Sebastian cover music]
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
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!
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.
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.
Given a pair of needle nosed pliers and some soft body parts.
I'm trying to teach myself to set people on fire with my mind... Is it hot in here?
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
blog.sam.liddicott.com
And loves to editorialize shit to try and spin things. Burglary is illegally entering someone's house for the purpose of theft. Now the important part there is "illegally" and also what the intent is. If I enter your house, because you gave me a key and want me to watch you cat, that is legal. Well guess what? It is also legal for the police to search your house, if they get a warrant which the FBI did. Further they can get warrants for surveillance of various types like tapping your phones or planting bugs in your house. In some cases, particularly in espionage or organized crime cases, there is a need to keep things secret. As such they can do that too. Details of an investigation, including that such an investigation is going on, are often kept secret while it is happening so it doesn't get compromised. There is nothing illegal in the slightest about this.
You'll notice that one of the links is to a big court document that catalogues what happened. Now that the case is over, things are made public.
So they didn't commit a crime. Sorry. They obeyed the law and kept perfectly withing the spirit of the Constitution. The Constitution just requires that the police act upon probable cause and obtain warrants. It doesn't require them to sit back and do nothing unless someone acts right in front of them.
If you want to see what kind of weapons a civilization has, study the amour. And vice versa. There is only a short time that one EVER outpaces the other, because they are one and the same. The thing is, when a mass level tech is made (one a person cannot reproduce by themselves) then the government and big corps holds the only keys... Nukes, Aircraft carriers, Quantum computers, these are all built within the collective and some never filter down. Now if they dis-allow all private (including corporate) quantum computers then our enemies may not; and then they would have an edge on us. So it's all based on how long you can keep the tech just for your government... think USA with the only nuke how long did that last?. If foreign labs build protein chain models with these things maybe they find a cure faster or more drugs. The point is the Q computers are vastly useful to our whole civilization so keeping this one 'under wraps' is impossible. So it's just a matter of time before we get our techy hands on one! It could be 20 years but it shall come! Then finally we can realtime raytrace everything, just for fun!
If large scale quantum computing comes on-line it solves one particular class of mathematical problems related to encryption: factoring of large numbers.
That makes a *subset* of modern crypto algorithms vulnerable to attack, specifically RSA and its (very common) derivatives.
Crypto as a whole those isn't in any danger of falling apart, it just means there will be a shift to other algorithms like AES.
Even if every synthetic algorithm were magically cracked tomorrow, there's always electronic one-time pads which are unbreakable, albeit difficult to distribute.
Probably could have thwarted the theft with a $200 home safe.
Or a $100 nanny cam to alert you to change the code.
Relatively low tech but multi pronged.
Get your most closely kept personal thought: .doc with a password lock. .rar with extraction precluded .rar because so far they ain’t impressed. .pgp and print the hex of it out,
put it in the Word
Stock it deep in the
by the ludicrous length and the strength of a reputedly
dictionary-attack-proof string of characters
(this, imperative to thwart all the disparagers
of privacy: the NSA and Homeland S).
You better PGP the
You better take the
scan that into a TIFF. Then, if you seek redoubt
for your data, scramble up the order of the pixels
with a one-time pad that describes the fun time had by the thick-soled-
boot-wearing stomper who danced to produce random
claptrap, all the intervals in between which, set in tandem
with the stomps themselves, begat a seed of math unguessable.
Ain’t no complaint about this cipher that’s redressable!
Best of all, your secret: nothing extant could extract it.
By 2025 a children’s Speak & Spell could crack it.
You can’t hide secrets from the future with math.
You can try, but I bet that in the future they laugh
at the half-assed schemes and algorithms amassed
to enforce cryptographs in the past.
GFA/M/S d-- s: a--- C++++ UBL++$ P+ L+++ !E- W++ N+ !o K- w--- !O !M !V PS++ PE Y+ PGP+ t+++ 5- X+ R tv@ b++ DI++++ D+ G
People forget that repeated tries to login with random passwords will raise a red flag. Stealing the password and using it to get in without failures can be done without being flagged.
...and even simpler still: anything you don't want someone else to see (ever) should not be left on a computer that is in any way accessible to someone you don't want it to. Encrypted or not, the fact that the data is there might be sufficient to do enough damage.
It's just a matter of being thorough. Just imagine you are guilty of some major crime - say murder, treason or whatever. (My academic background is in molecular forensics, so I might have more than usual interest in this.) You need to be damn thorough in covering your tracks, which means paying attention to detail. We will never know how many such crimes remain unsolved (or pinned on the wrong person), but it is (at least theoretically) possible to avoid being caught if you pay enough attention.
However, most of us can strike some sort of middle ground. The police can take a good look at my Visa card records (if they have nothing better to do) and find that I spend a bit more than I can really afford on CDs, but so be it. But that doesn't mean I'm about to paint my account number on a railway bridge for everybody to see.
xkcd is never obligatory.
Especially where it is redundant. The same link was posted earlier.
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
Oh but you forget about the new quantum encryption.You build one,I build the other.
I somehow get the sense that when quantum computing reaches that level, you'll be able to know either the precise encryption keys, or which computer they work with, but never both simultaneously. ;^P
--
Toro
So if you fear that someone might break into your house to get your passwords, make sure you've got some wrong passwords lying around.
The Tao of math: The numbers you can count are not the real numbers.
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.
Assuming you can make thousands of qubits act coherently. From what I understand you need about 4096 qubits to resolve a 2048 bit RSA key, while in practice we've factored 15 = 3*5 on a 7 qubit computer. Going from 7 to 4096 is like going from creating single anti-matter atoms to a working anti-matter drive that you can tank up at your local gas station. Seriously, even just to break RSA you have a long, long, loooooooooong way to go.
Live today, because you never know what tomorrow brings
torture someone immediately to save someone from something somewhere.
The truth about encryption keys
Slashdot's rate-of-post filter: Preventing you from posting too many great ideas at once.
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.
But within the foreseeable future, cracking those same codes could become trivial, thanks to quantum computing."
Awesome! I'm really curious what's in Julian Assange's insurance file!
Space game using normal deck of cards: http://BattleCards.org
I personally don't believe this will ever be possible.
There is no such thing as a free lunch. Somehow the universe will make you pay the true cost of your computation. I suspect this will be in the form of noise or diminishing returns on possible operations necessary to reinforce coherence amoung a significant number of entangled qbits.
Sure we'll have quantum computers in the future. They will be extremely useful in many areas. My guess they will be forced to stick with a more parallel scheme falling far short of the mythical 2^qbits (where qbits is a significantly large number) a real code breaking quantum computer would need.. It will be more like 2^qbits * n where qbits can never be astronomical...n no matter how large you make it is insignificant in the context of code breaking.
I think he might have meant petri dish encryption....
"City hall" in German is "Rathaus" Kinda explains a few things......
I'm in no means a security expert. Please correct me if I'm wrong but...
Why do they need to break into houses over encryption. I thought it was some government rule that any encryption products had to be registered or something with the government so they could easily decrypt messages? Like a government backdoor or something...
History knows bigger surprises than a possibility of someone already using efficient algorithms for cracking at least some curent "rock solid" cyphers. What would any reasonable Government do with such discovery? Publish of course, no?
Do not throw away your OTPs just yet.
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.
I don't believe such a method is known to exist (and it's not for lack of looking). Please correct me if I'm wrong!
when they have a really working quantum computer which really can decrypt DES. Right now we are at least decades away from such devices.
I believe Schneier once wrote that the strength must lie in the key, not the algorithm. Trouble is, when that's the case, quantum computers can decrypt you. A better position is to have a hefty key AND a secret algorithm. I think more-or-less anyone who can do some assembler bit-twiddling can devise an algorithm which will output something that looks indistinguishable from random numbers. A challenger can only decrypt your stuff if they have both the key AND the algorithm. Either on its own would be no use. If the challenger doesn't even know the length of the key, they are probably knackered even if they have a quantum computer.
The bloke who complained about YouCut on his blog states there that quantum computers won't solve NP-hard problems in polynomial time. And I've read elsewhere that some crypto-systems are resistant to quantum computer challenges.
Who should I believe?
Free Manning, jail Obama.
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.
Look a little closer and you always find a researcher greedy for funding or a company that want to sell you something.
There is no indication today that quantum computing can scale. There is no indication that it can perform complex computations at all. There are serious indications to the contrary. Crypto-security relies on physical limits. It is quite possible that building a quantum computer that can handle a 128 bit cipher is well beyond what can be done in this universe.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
Exactly right. A classical binary computer can be built from components, and hence making one of size n requires n^k effort with k>1, but relatively close to it and generally significantly smaller than 2. There are rather strong performance limits on what a single CPU can achive in maximum speeds, hence really large computations are always distributed or infeasible.
A quantum computer has to be built in one step, as the qbits need to be entangled. Thats each qbit has to be entangled with each other at the same time and during the whole computation. In a sense, a quantum computer is a single CPU. Moreover, you cannot really distribute search algorithms (and that is what we are talking about when breaking crypto) with quantum computers. The whole problem has to fit into that single CPU. With a classical computer you just divide the search space, which scales exceptionally well.
Generally, when this BS claim crops up, you find a researcher greedy for money or a company that wants to sell a product. Don't believe these morally corrupt sources of information.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
BS. You can build a PKK with polynomial times both ways. The difference just needs to be large enough and the smaller exponent small enough. n for encryption/decryption with key and n^3 for attackers is already enough. The "expinential one way, polynomial the other" mantra is just for convenience, but not needed.
Incidentally, you can spot those that have not understood asymmetrical encryption by their insistence that bringing down the attackers effort to polynomial breaks the system in a practical way.
Most ACs are not even worth the keystrokes to insult them. Be generically insulted by this and ignored otherwise.
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.
I'm no expert, but isn't the point about encryption-breaking-quantum-computing that the prime facorization is done in polynomial time rather then exponential so doubling the length of the key is not as effective as today? (it would only quadrouple the cracking-time)
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.
Agreed, the buzzword "cloud computing" might just be one marketing BS on top of the other, but the current state of public internet access is really what's being utilized and built around, and that is definetly not the same as in the 1970s.
If they don't encrypt/decrypt for the gov't, they don't do it for anyone else!
Actually code talkers used based on their native languages so other native speakers could conceivably understand them. For instance though many code talkers were from American Indian tribes, the US Marines used Basque code talkers during WWII in areas where there were no Basque or Euskara speakers.
Falcon
Should there be a Law?
It is difficult, if not impossible, to cover every possible clue, trace and or happenstance.
Not really. Do you have an idea of how many unsolved murders there are? How many ways are there to kill people? Want to shoot someone? Remove the slug from the bullet and use ice. With the cartridge below freezing gouge out a piece of ice from a block keeping it frozen until it's shot. Like the slug it replaced the ice can kill the person, but then it melts so the caliber of the shell may not be known. About all that is known, or can be tested for, is the power used in the round. However even the power can be made and doesn't need to be bought. The use of an air gun and even power traces don't exist.
Falcon
Should there be a Law?
the exponential problem is that increasing key size by a single bit doubles the time required to check the key space.
So yes, should quantum factorization actually work for real-world key sizes this would be a huge advantage for the attacker compared to the current situation but it's still less costly for the defender to double the key size in order to keep the "probably not decrypted while earth still exists" timeframe than for the attacker increase their cracking capability to match.
What's this notion that the "government", which consists of the same Joe's and Jane's as the normal populous, is somehow smarter and more resourceful, so much so that they can trivially crack our best crypto?
You are talking about one specific algorithm (Grover's) that reduces any search problem from n to sqrt(n). There are MANY other specific algorithms that solve other problems in faster and more useful ways. Shor's algorithm factors a number in O(log(n)^3) time, which is much faster than naive search. The real power in quantum computing lies in algorithms that would take exponential time on a traditional machine but can be done in polynomial time on a quantum one. Grover's algorithm does not do this because if a search space is O(n), for many cryptographic applications it is considered O(log(n)) input size, and a search on an input size of n would still be O(sqrt(2^n)) which is exponential.
If being a spy, assume that things will go wrong at some point, and do not leave accurate passwords lying around where any passing Tom, Dick, or J. Edgar can read them.