Slashdot Mirror
The End of Encryption?
An anonymous reader writes "The encryption algorithms that make virtually all electronic commerce possible work only because certain mathematical problems are very, very hard to solve. But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems--known in the math biz as P and NP. In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum."
No no no no no. How many more times? Cryptography has absolutely nothing to do with the question of P?=NP.
P?=NP refers to the asymptotic complexity as the problem. i.e. as the input size goes to infinity. It quite possible to have a problem whos complexity is approximately linear at the 100-1000-bit range and still NP-Complete. Conversely, it's possible to have a p-time algorithm for solving a problem that has a O(n^100) so it's still difficult to solve. While resolving P?=NP might bring new tricks to the table it's difficult to legislate for these tricks. There might not even be any we don't already know.
Another point, p?=np has no bearing on the security proof of the one-time pad or quantum mechanical key exchange. The latter will become practical over large distances to enable the former long before p?np is resolved. Cryptography will die when the last human draws its breath.
Simon.
Guvf jbexf whfg svar sbe zr!
Right is wrong when left is right.
... write 'Bridge over encrypted waters ~(__8-(0) Doh!'?
This is really quite simple - the type of machine that can render Prime-based and Discrete Log-based encryption "useless" has not been invented yet. Furthermore, as the article points out, most (including Adelman) belive it'll be a long time before one is.
The problem (P vs. NP) is still just as difficult, and we aren't really much closer to solving it than 10 or 20 years ago.
dmiessler.com -- grep understanding knowledge
Which is not exactly true. It could be true but not provable. It could be false but not provable. It could be provably true, or provably false. Or, it could be neither true nor false.
In other words, cryptography is dust in the air?
OTP will always remain a viable means of private key cryptography. When you interleave signal with noise, the result will always have the properties of noise.
For 90% of the public, ALL math problems more complex than 2+2 are hard!
Learning HOW to think is more important than learning WHAT to think.
It can well be argued that absolutely nothing is in fact random. From coin flips to roulette anything can eventually be learned and predicted on some level. The only point where I might even question this is with quantam states, and even there we really know precious little. It is simply too early to say one way or another on quantam.
In an article on TechnologyReview.com, Simson Garfinkel spells out the real-world consequences of this mathematical conundrum.
Who else read that as Simon Garfunkle? Come on... I couldn't be the only person here, could I?
And besides... if you want real security, just do double encryption. use two common, off-the-shelf encryption methods, one encrypting the other's data and your data is now as safe as it can get. further encryptions in encryptions will only add to bloat and time to decrypt.
So far as we know, P != NP.
And that's it. And I haven't seen a shred of evidence to the contrary.
Yes, the article is somewhat truthful, in that if P == NP, the world will have been turned on its head, but the same thing is true about thousands of scientific and/or mathematical assertions, each of which is more likely to be overturned than P != NP.
As one would say to Mycroft in The Moon is a Harsh Mistress, that's a "funny only once" joke...and the "once" was probably decades ago.
When will people learn that as long as people have secrets to keep they'll find ways of keeping them? There may be advances in technology which will render certain methods of keeping the secret obsolete, but this search for a magic algorithm is silly.
I imagine one day there may be an advance that will mean a total security overhaul will be required though, and that could provide a window of chaos in the most extreme circumstances. However every advance in decryption tends to quickly lead to an advance in encryption that can beat it. At least historically that's been the way it is.
Until they can literally read the contents of my brain, I'm not too worried.
These posts express my own personal views, not those of my employer
Ignoring the fact that the answer to P?=NP has little to do with breaking encryption for a moment, even if an NP computer is conceived and developed, it'll just lay down a *huge* plethora of computing possibilities at our disposal, including new encryption techniques.
Encryption cannot die, algorithms can.
An Indian-American Hindu committed to non-violent thought/speech/action alarmed by the global explosion of radical Islam
I saw a movie about this exact same thing. Luckliy Robert Redford and his team won and the world was made safe from Ben Kingsley, but it was touch and go there for a little bit.
I was worried.
The one way to tell for sure if the good guys win, is if the Republican National Committee goes bankrupt and GreenPeace gets a sizable donation. Also, you might see Sydney Poitier in Tahiti and Dan Akroyd in a brand spanking new RV.
--
Pain?
Try Prison.
> Or a quantum computer is made that can break all these passwords.
No. To put in plain language: there are forms of encryption more advanced than those that employ difficult math problems. Quantum computing does not pose a threat to a OTP system that employs quantum key exchange. Sorry.
You are thinking of One time pads
The only encryption theoretically unbreakable.
Free XBox, PS2
I have discovered a truly remarkable proof which this post is too small to contain.
LongTail SSH Brute Force analysis tool is here!
Ask Slashdot dealt with this issue three years ago! When it comes to uninformed, idle speculation, this site is way ahead of MIT!
What I'm listening to now on Pandora...
Cryptography will die when the last human draws its breath. Er.... shouldn't that be third-to-last human?
Sometimes seventeen/Syllables aren't enough to/Express a complete
But if a quantum computer can be made to do this, then most likely a quantum computer can be created to securly transmit one time pads to the other end. A one time pad is unbreakable because the key length is the same as the message length. (boy I hope I got that right :)
Quantum computing does not pose a threat to a OTP system that employs quantum key exchange.
In practice it may never pose a threat to symmetric ciphers, like AES, either. Those don't rely on hard math problems as much as on non-linearity and complexity. Quantum computers may someday be good at solving simple but hard problems, but it's likely they'll never be able to attack complex problems, easy or hard.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
The whole thing is a bunch of alarmist speculation.
"The market alone cannot provide sufficient constraints on corporation's penchant to cause harm." -- Joel Bakan
But some mathematicians are trying to prove that there's really no difference between 'hard' and 'not hard' problems
Well, it's always better to have the hard problem. You may have to seek medical attention, but at least your pride remains intact.
"In short, his method would allow really [really-really] fast code breaking using quantum 'computers'."
AFAIR the best known quantum algorithm for breaking conventional crypto merely reduces search time to about its square root. So increase your key length from 128 to 256 bits, and it will take about as long to crack a key as a current computer would for a 128-bit key.
This is one reason why most new crypto algorithms have 256-bit keys rather than 128-bit.
Bruce
Bruce Perens.
Bell-bottom pants aren't cool anymore? Man... what a bummer. I got to quit bogarting those roaches.
If you post it, they will read.
The ability to feed the correct message back from that universe to the rest of us may be a bit tricky, but could perhaps be done by having the individual in the lucky universe set all quanta to 0xFF in a bank of LEDs in a pattern representing the plaintext.
"50 Ways to Break Encryption"...
just calculate the key, Lee
hack the algorithm, Jim
reverse-engineer, Samir
sleep, what's that?
I'm surprised that Simson made this elementary mistake.
Factoring has *not* been proved to belong to either P or NP. It's an "open problem".
DNA is a Turing machine. You, however, being dynamic and emergent, are not.
You don't want the aliens decoding your pr0n collection.
I have a proof that proving P = NP is an NP-complete problem. Unfortunately this posting is too small to hold the proof.
Adding 2 numbers and 25 billion numbers is really not that dissimilar in ways of difficulty, however it still takes a lot longer to do one than the other. The strength of cryptography doesn't come from how hard something is so much as how long it takes to do all that simple math.
Digital Fortress was a complete piece of shit. Please don't base anything off that rag. It was written with the express purpose of capitalizing off of Dan Brown's momentum being made into a movie. The "visuals" described fit Hollywood nicely -- meaning they have no basis in reality.
It is easy for a person to come up with an algorithm that THEY can't crack. Most are painfully obvious to outsiders with any experience.
Other than proper implementation of a one-time pad, you'll probably find any encryption will eventually fall.
Learning HOW to think is more important than learning WHAT to think.
Well, since he's a graduate student at MIT, I'll wager he has.
"Garfinkel holds three degrees from the Massachusetts Institute of Technology and a masters of science degree from Columbia University. He is a member of the Association for Computing Machinery (ACM), Computer Professionals for Social Responsibility (CPSR), and has a certification in computer security (CISSP) from International Information Systems Security Certifications Consortium."
Ironically, the word ironically is often used incorrectly.
If they succeed, won't it be humiliating for those mathematicians that have spent decades studying this problem to find it isn't harder than solving 2 + 2.
Actually, the article's not all that bad.
Two problems: in his explanation of "P", the author says that P-time algorithms consume an amount of time proportional to the input size. That's way incomplete. P-time problems consume time proportional to some polynomial function of the input size, such as O(n^2), O(n^3), O(n^100), in addition to just plain O(n).
The second problem is where the author states that fast solutions to NP-complete problems would open up vulnerabilities to "hackers and viruses". Well, I'm not up on the latest virus developments, but AFAIK most viruses exploit known vulnerabilities rather than trying to crack algorithmically hard problems. Maybe there's some subtle way a virus could use a powerful P-time factorizer, but I think the author really just stated "hackers and viruses" because it sounded nice.
The article's also incomplete, as other posters have pointed out, because plenty of P-time algorithms are useless for real attacks. If your algorithm takes (1000 years) * (n^1000), where "n" is the key length, that is polynomial time, but it's still too damn long.
I've seen much worse in the trade press.
P=NP
P/P=NP/P
1=N
Therefore, P=NP for all problems where N=1.
See, that clearly wasn't a NP problem!
There's no mathematical proof, but consider this: a lot of problems have been shown to be NP complete. That is, if they can be solved quickly (in polynomial time), every NP problem can also be solved quickly (in polynomial time).
Some of these problems would make you a very, very rich person if you came up with a way to solve them quickly.
Nobody has.
That's enough evidence for every-day use, IMO.
Digital Fortress was a total piece of crap. While A moderatly interesting book, the crypto is totally wrong. The ONLY perfect encryption is a one-time-pad. If there is a key it can be broken. The whole "make it impossible to figure out it its really cleartext" is just a not-so-clever plot device.
Think about it this way, when you use PGP/GPG to encrypt something, it compresses the file first. The argument Dan Brown used was that when you try a key on this "unbreakable" crypto that you get garbage out and can't use the typical language statistics to figure out if the result is valid or not. If this was true, then any form of binary data would be impossible to decrypt.
A more mathish approach. The idea was to take a cleartext, M, run it through a "magic function" Z then encrypt that, or Encrypt(Z(M)). Well, a little digging will find that chained encryption doesn't buy much. Thats why AES is around, rather than using 3DES or 5DES. or nDES. All his digital fortress was doing was using two encryption methods. But, this just doesn't work.
Dan Brown doesn't think or do any research whatsoever before he writes a book. Virtually ALL of the crypto related information was WRONG. Skipjack was a problem, not because of any backdoor, but because it was only availible as a tamper-proof hardware chip, noone got to look at it. The Caesar cipher was an alphabetic rotation, not a geometric cipher. Hell, there simply isn't enough energy given out by a star in a year to power a machine capable of brute-forcing 256-bit encryption, schieder wrote an essay on it.
Under current theory, the ONLY perfect encryption scheme is a OTP.
Yeah and 640KB should be enough for anybody.
Well, "enough CPU cycles" is usually so high a number that it isn't possible to compute before the end of the universe.
by having a plaintext and cyphertext, a quantum computer can make it very trivial to find the key using certain iterative attacks on the algorithm. I mean, isn't the quantum computer "instantly" backtracking up until the substitution step of each round, as the operations would be reversible up until that point? I would think the complexity to crack is only dependant on the number of rounds.
There is no possibility to use a quantum computer to make simultaneous dictionary attack (guessing the key by trying all possible keys at the same time), because, contrary to what most people think, you can do only one usable computation at the same time on a quantum computer. The difference between classical and quantum computer is that you can 'tune' the quantum computer into doing this one computation which is important -- like the one needed to break the key. If you can do that, you've cracked the cipher. But it requires an algorithm specific to the cipher in question. A good defense before such attack would be to change the cipher in such a way as to make the corresponding quantum algorithm useless, and make attacker think really hard before coming up with another one. A bit more challenging than just increasing the key length.
IANAQCE (I Am Not A Quantum Computing Expert), but that's what I gathered from listening to seminars delivered by people from the field.
"Long run is a misleading guide to current affairs. In the long run we are all dead." (John Maynard Keynes)
that P=NP. Of course some of them are. But almost every other mathematician with at least three brain cells is reasonably convinced of the opposite. The article covers the "consequences" of P=NP that anyone who's read an introductory text already understands, but fails to mention that a single NP-complete problem inside P is about as likely as finding a number without Goldbach property. It's just silly sensationalism for the sake of ... um, something about uninformed people that starts with 's'.
Thank you for making my point. Quantitative changes occur incrementally over time, like memory requirements. Qualitative changes, however, like the fundamental difference between quantum computers and Von Neumann computers, and the algorithms that can be executed on each, don't.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
True randomness does exist, it's all around us.
You are probably thinking "If we just knew everything about the starting conditions, we could predict the outcome."
In this universe, however, you CANNOT know the starting conditions to an infinite degree of accuracy. I don't mean "it's difficult" or "we can't do it with today's technology" but that it's fundamentally not possible. No state exists whereby you can know waht you would need to know. Such predictions are not possible.
You can say we don't know enough about quantum mechanics yet or whatever.. but look at something as simple as the Heisenberg uncertainty principle: you cannot know the speed and location of a particle at the same time. The more accurately you know one, the less you know of the other. This coupled with chaos theory means things really are random.
You are correct in that some things can be predicted.. we COULD measure enough about a roulette wheel to predict with a high degree of accuracy what is going on.. same with a coin toss. But look at something like nuclear decay, for instance... and we will NEVER be able to predict when a given atom is going to decay... it's buried in the quantum noise and in the uncertainty principle.
I thought that all the public key (etc) systems relied on a "hard math problem" to produce the public-key secret-key pair.
Sort of. Actually, they rely on the hard math problem to make it so someone who knows the secret key can do something that someone who knows the public key cannot, and, potentially, vice versa. Generation of keys is simpler.
When I generate my DES and AES keys I go through that "mostly prime" exercise.
Umm, no. DES and AES don't care about primes, or factoring, etc., at all. The DES and AES keyspaces are (nearly) flat. To pick a DES/AES key, you just choose a random 56-bit/128-bit number. (I said nearly because DES does have some weak keys, so some people choose to avoid those).
So quantum computing should be able to do the "large nubmer factoring" exercise necessary to crack the key...
For public-key algorithsm like RSA, DSA, Diffie-Hellman, ECC (well, you don't use factoring to attack ECC, but same notion), etc., yes. For secret-key algorithms like DES, AES, IDEA, RC-4, Twofish, etc., no, there is no number factoring exercise or similar that will help. So probably not, which was my point.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
P=NP
P/P=NP/P
1=N
Your proof fails when P=0, in which case any value of N will work.
-Tom Duff
"In practical terms, that would spell the end of encryption as we know it. The Internet would be vulnerable to hackers and computer viruses." Made me laugh :p~~~
Poor man was only two letters away from being a music sensation...
I'm sure he's never heard that before in his life.
As many of his other repliers already pointed out, parent mixed up the NP and NPC (NP-complete) classes. Factoring is in NP. On the other hand, it is very-very unlikely that it is NP-complete (more precisely NP-hard), because this would imply that NP=co-NP.
What does NP=co-NP mean, you ask? You can consult http://en.wikipedia.org/wiki/Co-NP for the details. But the important point is that it is just as unlikely as P=NP.
The consequences are that I won't be able to safely browse Slashdot from work over an ssh tunnel without getting in trouble, anymore.
I've had secure, non-snoopable access to the Internet for my entire professional life. If I actually have to start working I don't think I'll be able to handle it.
(1) The terminology is misleading. The author speaks of "NP problems" without further qualification, and calls these problems "hard problems". NP problems, in the sense of problems belonging to the complexity class NP, however, are not "hard" in general, because all problems in P belong to NP (this is a trivial theorem). And no problem has been shown to be in NP but outside P. He might be referring to the so-called NP-hard problems, which formally are the problems at least as hard as the hardest problems in NP. But this wouldn't make much sense, since he doesn't bring up the NP-complete problems (the only NP-hard problems we know of inside the class NP) until the end of the article.
(2) Suppose P=NP. I, for one, would see this to be a good thing. The gain in the field of e.g. combinatorial planning and scheduling would be enormous, far outweighing any loss in the field of cryptography.
Disclaimer: I don't know a bra from a ket, but...
If you had a quantum computer, could you break any public-key cryptosystem by doing:
(Or is the above stupid and wrong, and I'd need an actual course in quantum physics to even understand why?)
>;k
Primality testing is in NP. Every problem in P is in NP. What you meant was primality testing is not NP-hard.
Researchers have shown that simply throwing a thick blanket over a subject can result in a Denial of Light attack. Pundits have suggested that with this knowledge, there is no longer any point in using light any more, when it can be denied so simply. Experts are working overtime to come up with a solution.
Few people know that Ashcroft was once a crusader for personal freedom and privacy and took a stance against the Clipper Chip. Oh course, NOW he is a total fucktard who wipes various parts of his body with the bill of rights, I guess prolonged exposure to government does that to people.
Incidently most of the geeks I know (myself included) who voted for Bush did so because at the time he appeared to be the lesser of two evils. Al "Mr Clipper Chip" Gore certainly was no friend of the technology industry or anyone interested in privacy while he was VP.
Of course now we know that there are no lesser of two evils. Kerry and Bush will both screw over the country hard. Let's face it, nobody likes either of these two failures. They just hate the other guy enough to pretend to like one of them. It is a sad say in the US when these two are the best options we have.
Finkployd
What's the difference?
That's a tough one to answer concisely. The best way to see the difference is probably to look at the algorithms.
Symmetric ciphers work by doing a whole bunch of different operations, mixing and munging the data in complex ways, and doing it over and over again. In the case of DES, for example, there are 16 rounds. AES-128 uses 10 rounds. Each of the individual mathemetical operations are simple, easily reversible and weak, from a security standpoint. The strength is achieved by repeating them many times in particular ways to create an overall structure that is hard to break.
In contrast, public key ciphers, like RSA, consist of only a single mathematical operation, one that has useful properties. An RSA encryption operation just requires calculating m^n mod p. The operation is very simple and straightforward, but there's no known way to reverse it efficently without the private key.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
One important class of problems which should be included in this discussion is the class of P Complete problems.
These are problems for which there exists a polynomial time reduction to the P Problem, which is the ability to optimally distribute P straight pegs in U linearly arranged slots (where P less than or equal to U), so as to maximize the distance between pegs.
For example, for (P=2, U=5), the optimal solution is a peg at the first and last slots. For (P=3, U=5), optimal is U0, U2, U4, etc.
It can be shown that any problem which can be reduced in polynomial time to straight men at a row of urinals is P Complete.
"I thought they were the dominant species..."
It is by having a satelite system, like the GPS system, constantly broadcast synchronized truly random data. That way, any two recipients can communicate as much data as they want by simply synchronizing their communication to a certain time, and using the one time pad that's being broadcast by the satelites at that point in time.
Now, this turns the one time pad bandwidth issue into a secret key (the timestamp) issue. How do you communicate the timestamp between the two sources?
There's another benefit though, and that's that the sheer amount of data being generated by these satelites will make it prohibitive to analyze a transmission after the fact... only live interceptions could be used.
If there is only one correct key, you can use the Grover algorithm to reduce the complexity to O(sqrt(N)). It first make a superposition of all possible N=2^n keys, then for each iteration the encryption algorithm is applied on it (simulataneously to all keys), yielding a "it is the right key or not" answer for each key, still superposed. Then a conditional 180deg-phase-shift operator and a "diffuse" operator is applied on the resulting superposed state, the result being that the eigenstate containing the correct key now has a larger weight than others in the superposed state, so that it has a higher probability to be observed when measured. By repeating the encryption-conditionPhaseShift-diffuse process O(sqrt(N)) times, the eigenstate containing the correct key will have a sufficiently large weight in the superposed state, and we can measure it and get the correct key with a high probability. So you see the encryption operation is always done simultaneously to every key, but you need to repeat the operation O(sqrt(N)) times to make the desired result strong enough to be measured.
Of course, the Grover algorithm is O(sqrt(N)), as opposed to O(N) of a purely brute-force attack, so just double the key length and you will be safe.
For references, google for "quprog.pdf".
Because factoring is not known to be NP-complete, there might turn out to be a polynomial-time algorithm for factoring, but no polynomial-time algorithm for NP-complete problems. If this were true, RSA might be broken, but other public-key algorithms might still be strong enough.
I think my parents had some of their albums...
Today we use the same approach:
No. It's not the same. Holes in DES or AES arise only because of human error in creating the cipher. (And if you wanted better security, you'd be using Diffie-Hellman anyhow). They are not expected, anticipated, or unavoidable.
But in a hypothetical future with quantum computing, breaking the encryption doesn't rely on discovering a flaw, just going through the work. Fundamentally so much easier.
A "P" problem is a decision problem (a yes/no question essentially) that can be solved in polynomial time: Worst case for searching for a book in a finite collection is a multiple of the worst case time it takes to search one book in the house and the number of books - a straight linear search of all books in the house.
An "NP" problem is a decision problem where a solution can be verified in polynomial time. If P=NP then any problem where a solution can be verified in polynomial time can also be solved in polynomial time. Solving the problem here refers to finding the answer (is the book I seek in the house?) while verifying the solution refers to controlling that the answer is correct.
An P problem is also an NP problem - if you can solve a problem in polynomial time you can by definition also verify an answer in polynomial time: solve the problem, and compare the result with the proposed answer.
However the problem is that while it is thought that not all NP problems are also in P, it is not proven, and may be unprovable. But we don't know which, and don't have a simple way of verifying whether an NP problem is in P or not.
This is what sucks for encryption. Encryption currently rely on it being hard to solve a specific problem but easy to verify the solution (the key) by trying to decrypt an encrypted message, and if it fails (or presents us with gibberish) we know the key presented to us was not the right solution. This can be done in polynomial time
However, it only protects us because nobody (at least as far as we know) can solve the problems posed by the encryption methods in less than exponential time. Exponential time to solve the problem means that the effort could for instance (but not necessarily) double for each extra bit added to the key. The general rule is that the effort is 2^p(n) where p() is a polynomial function of n, and n is the size of the information space of the problem. The problem asked by encryption is essentially "will this key slotted into this encryption function give the original message?"
Let's go back to the book search, and twist it so that it fits the situation with encryption now. In the book search, the question is "does the book I seek exist in the house?". In a normal world, this problems worst case solution increases in effort by a constant factor for each extra book added, but to make it comparable to encryption we need to complicate the problem.
Imagine a crazy world where the best way we have to look for a solution to the book problem is to compare all the books with eachother and a paper strip with the title of the book we want, and only when we happen to compare the paper slip with the right book have we found the solution. In that case, each time we add a book, the problem increases (the number of direct relationships between n entities n(n-1), where n in this case would include the paper strip with the solution) but where we can still verify the final solution by comparing the book we finally found with the paper strip.
The kind of twisted scenario above is what most encryption algorithms are today: A problem that gives protection only because we don't know how to quickly solve it, but where there could be a simple way of solving them right around the corner. If P=NP all encryption algorithms that depend on this relationship can be broken in polynomial time.
However even proving that P and NP are not equal only means that "safe" encryption using this relationship is possible, not that current algorithms are safe - to prove that an algorithm is safe you'd need to separately prove that the problem can only be solved in exponential time. But a proof that P!=NP would give us an indication that it might at least be possible for such a proof to exist, as proving that the problem posed by an encryption algorithm can only be solved in exponential time would at the same time prove that P!=NP.
A proof of P=NP could merely show there must exist a P algorithm for every NP problem. It doesn't necessarily have to give such an algorithm, only show its theoretical existence. While such a proof would prove P=NP, it would still be of little practicle use.
Only once such a conversion algorithm is found then, yes, every NP problem can be actually solved in polynomial time.