Slashdot Mirror
RSA Cracked - Not
fintler
was the first of many to tell us about the
ZDNetAsia
and
Philippine
newspaper
stories that proclaim that RSA encryption has been "cracked." This might make an entertaining
movie
plot but it isn't true. I bet cryptographers get hot tips like this
from well-meaning amateurs all the time, but most of them don't get this much press. Here's a
cleaned-up edit
of what's been bouncing around your inboxes all day (read parts [F] and [I]), and for a briefer commentary by the "R" in RSA, read on.
Hi Jamie --
Thanks for checking with me.
A fellow by the name of Leo de Velez from the Phillipines had thought he had broken RSA, and a reporter colleague wrote up this story and published it. This is probably what you have heard about.
Mr. Velez also wrote to me with his ideas. Unfortunately for him, his approach is actually much *slower* than the naive approach to factoring by trial division by 2, 3, 4, .... His approach doesn't improve on any known techniques, and doesn't constitute a "break" of RSA at all.
If you write to Mr. Velez (leo at teammail dot com) he will confirm...
Thanks again for checking...
Feel free to quote me...
Cheers,
Ron Rivest
RSA encryption will be one of the best types around, at least mathematically speaking.
This is incorrect. RSA is strictly worse than Diffie-Helman. To elaborate, there are four problems we need to distinguish:
To elaborate: a solution for the DHP would give a solution to the RSAP; thus RSA is on shakier ground than DH. Note that if cracking DH or RSA does not require solving DHP (resp. RSAP), then this is academic. We thus get the diagram:
that is, if you can solve DHP, you can solve all of these, but if you can solve RSAP, you only get RSA cracked. Thus the security of DH (resp. RSA) is based on two assumptions:
Unless you think there is something wrong with DH that allows cracking it without solving DHP, then DH is better than RSA. That said, the reason RSA is so prevalent is b/c it was patented after DH, and thus RSA inc. could make $$$ off it longer than if they used the technically superior DH; however, RSA has been ``good enough''; regardless of whether governments can crack it, $|<r1p+ <1dd1e$ sure can't. But that's all RSA is: good enough.
-- RTFM:Slackware::Beer:Saturday
rjh writes:
.
p /NP/ijcai91/paper/IJCAI91-paper.html.
I'm very hesitant to declare RSA to be "one of the best types around". RSA is built on several conjectures, none of which have been proven, namely:
1. The only way to make a general break of RSA is to factor large composite numbers
2. Factorization of large numbers is an NP-complete problem,
3. P != NP
#1 is incorrect, there are a few ways to break RSA, only one of which is to factor large composite numbers (another is this Leo person's method). Assuming effective key management, no method has been found which is significantly easier than the factorization problem (although some are no harder). For more detail, see http://www.rsasecurity.com/rsalabs/faq/3-1-3.html
#2 is also incorrect. Factorization is probably not NP-Complete, but RSA never depends on it being NP-Complete, merely on it being really hard to solve. Factorization is provably NP, but has not been shown to be NP-Complete. This is potentially a good thing, if #3 ever falls through for the NP-Complete set, the fact that it isn't NP-Complete means that Factorization will probably still be hard.
#3, of course, has not been proven. It also has not been disproven, despite hundreds of mathematicians trying for decades. A good analysis of the issue is at http://ic-www.arc.nasa.gov/ic/projects/bayes-grou
Just because #3 hasn't been proven doesn't mean it's not a useful assumption. People routinely bet their lives on much flimsier ones.
----
----
Open mind, insert foot.
Actually, factoring is a problem which is believed to be hard, but there is no proof that it is. There's no formal lower bound on the amount of computation required to break RSA. But it's a problem that many mathematicians have worked on without cracking it. That's the main reason for confidence in RSA. Nevertheless, the possibility of a new discovery cannot be excluded. (Nor can you exclude the possibility that it has been made already. You have to assume that the world's major cryptographic agencies have smart people working hard, but quietly, on the problem).
It's also worth remembering that there are lots of problems for which the worst case is exponentially hard, but the average case is far easier. Linear programming and the travelling salesman problem are examples. If you could break a high percentage of keys, that would be of practical use, even if some were harder than others. Note that there have been weak RSA implementations where the keys were ill-chosen from some subset of primes.
The first attempt at a public-key cryptosystem was based on the knapsack algorithm, a problem that hadn't received much attention. Once people starting looking hard at that problem, a way was found to solve it rapidly. Since then, cryptographers have been very cautious about new asymmetric-key algorithms.
I've cracked RSA. Unfortunately, the details of my algorithm are slightly too large to fit into this here Comment box.
-P. Fermat
I was reading "Crypto", and I remember them mentioning that an older version of PGP was using a pretty weak random number generator, making it easy to guess what the supposedly random keys were.
Maybe there'll be a shortcut somebody figures out for factoring large numbers quickly into their constituent primes.. -shrug-.. more likely, somebody will find some kind of buffer overflow or cruddy random number generator, or hashed passwords in one particular implemenation of RSA..
Disclaimer: I am not a mathematician! No need to mentally bully me if I screwed up a detail!
If it ain't broke, it doesn't have enough features yet.
Here you go.
cryptome.org/flannery-cp.htm
Shaun
Thanks to the War on Drugs, it's easier to buy meth than it is to buy cold medicine!
On average, its 10 years ahead of the curve on everything...
Where did that figure come from? Do you know of any concrete examples? (Not sarcasm, I'm really interested)
I know that when DES was being designed, in the early 70's, they were roughly 20 years ahead of the civilian mathematics field. The differential attacks that it had been designed to withstand weren't discovered until 1990.
Makes you wonder what they've been up to since then... :|
- cicadia
Living better through chemicals
By the way--how the hell do you define `really hard' without NP-completeness?
A slashdot staffer (actually) checked the story, and found it wasnt true.. Then posted the results! This has to be a first... doesnt it?
CK
---
Video meliora proboque deteriora sequor - Ovidius
Coming up with a quantum algorithm is a pretty weird process. The algorithm doesn't actually come up with a single solution, but a random one governed by a probability distribution. The clever thing is that different possible paths through the algorithm can interfere constructively and destructively with each other, so in effect the final probability distribution is a result of the combined effects of all possible computational paths. The tricky part is to come up with a system which takes advantage of this parallelism and interfere in order to make the correct outcome by far the most likely. This makes coming up with a successful quantum algorithm a completely different, and much harder, process than programming in, say, C.
The reason quantum computers are exciting is not that they do anything which classical ones can't or that they have a really high clock speed or something. It is that in certain cases, they can solve in polynomial time problems which classical machines take exponential time to complete. With classical computers, if someone came up with a machine which could factorise a 400 digit number in 1 hour, it would still take perhaps 2 hours to factorise a 401 digit number, 4 hourse to factorise a 402 digit numbers, 8 hours...etc. So if you used an 800 digit number it would still take a crazy amount of time to factorise it. With quantum computers (if you found a linear time algorithm) if a 400 digit number required 1 hour, an 800 digit number would require 2 hours, making any encryption based on factorising a large number crackable in minutes, hours or days rather than a billion billion billion years or something.
It is hoped that quantum computers will complement classical ones and be useful for specific problems, not that they will run word processors - classical computers do that well enough and are many orders of magnitude easier to program.
I achieved cold fusion in my bathtub this morning.
I will retract the following statement later today, after it has been forwarded to the scientific community ten times over
He who joyfully marches in rank and file has already earned my contempt. - "Big Al" Einstein
The TSP problem is "is there a path within this threshold?". it's in NP because there's an obvious poly-time algorithm for determining whether a particular path is no longer than the threshold.
For some reason optimisation problems are the most popular examples of NP-complete problems, but they're harder to think about than simple decision problems, because you have to look at them through this layer of abstraction. NP problems don't ask "what's the best you can do", they ask "can this be done?", so for an optimisation problem you have a family of questions "can this be done in 100 miles of travel?", "can this be done in 50 miles?" and so on.
--
Xenu loves you!
The moral of the story is to always obtain peer review (by qualified peers) before publishing your results!
I do not deploy Linux. Ever.
I've become wary of people who deliberately post misapprehensions because they think that helpfulness is laughable; I got a bit paranoid there. Glad to know I was wrong.
--
Xenu loves you!
I really needed something as funny as this to brighten my day.
Seriously, though, I don't recall all the specifics, but I do believe that, unless some brilliant advances in number theory or computational power happen soon, RSA encryption will be one of the best types around, at least mathematically speaking.
The thing we have to worry about most currently with RSA is whether or not we're all using the same keys over and over again. That's more of a threat than someone "breaking" RSA.
-Jellisky
But doing that naively is dangerous.
How can you prove that the product of the chain is not encoded with fewer bits than any of the steps? (Trivial example: double ROT-13)
I'm pretty impressed by how Ron handled this situation. I could understand someone in his position getting a little perturbed when a 'story' like this is leaked to the media. Instead, he put in the time and the effort to teach Leo the falicies of his algorithm. I got the feeling when reading the email conversations that Ron *truly* wants to challenge people to get out there and try to crack RSA...
"My mother never saw the irony in calling me a son-of-a-bitch." - Jack Nicholson
The whole basis of your argument is that if we use the algorythm too often, we're giving too much incentive to hackers to break it. That's stupid. If the algorythm is sufficiently breakable that we can realistically believe it may be broken anytime soon, we shouldn't use it at all because it's obviously not safe enough.
Also, by only encrypting "a small proportion of our data", you effectively take everything important and hang a neon sign on it saying "This is the valuable stuff that we are afraid you might want to steal!" It's a big pointer to potential hackers to tell them what to look for. Why else do you think sites using SecureID get so many hack attempts? Applying abnormally high security to something (such as encrypting it when nothing else is encrypted) makes it just scream that it's a target.
Given that, it seems a whole lot less "obvious" that it is not possible to find large prime factors in polynomial time--though based on the amount of research that has gone into it, I am inclined to believe it.
Likewise, Quantum Computing algorithms for factoring prime numbers are not perfect. Since QM is inherently statistical, it only has a statistical chance of getting the right answer -- of course, you can check it on a regular computer and try again if it doesn't work, but the point is, Quantum Computing algorithms may have very good runtime for various algorithms, but in general have completely unbounded worst case runtimes.
you assume tha RSA is breakable. It probably isnt unless quantum computers become a reality. Before you say something like "everything is breakable" learn some number theory. Understand what people mean when they say that a problem is hard. Given that most encryption schemes rely on factoring large numbers, for the most part, you break RSA, you pretty much have broken encryption. The only serious encryption that I know of that doesnt rely on factoring numbers being hard is a one time pad.
rjh asks:
By the way--how the hell do you define `really hard' without NP-completeness?
Personally, I define it as impossible to solve given current mathematical and computational technology in less than a year for less than a hundred thousand dollars. If I was in a field with stricter security requirements, I'd probably up the dollar figure. If I was in a less time-critical field I'd probably up the time. Factorization of a typical RSA key easily falls into my definition of "really hard".
Yes, people put a lot of faith in flimsier assumptions--but that doesn't mean we ought to put blind faith in an assumption.
The Brooklyn Bridge (finished 1883) was built with many assumptions, one of which was "Gravity acts in the way that Isaac Newton described". Not only had this assumption never been proven (just as current gravitational theory has never been proven), a few decades later that assumption was actually disproven. Does that make the bridge any less stable? No.
Most things in life are unprovable. If you only allow yourself provable things, you never leave abstract mathematics.
The heart of security is the management of risk; and without a fair and frank assessment of risk, there is no security.
Which is why RSA is so much more popular than elliptical cryptosystems. Because the risks involved in RSA are better understood, explored and documented. If you implement a security system that involves RSA, you have an easy-to-calculate risk involved in that link of the chain depending on key length. You can be confident that, absent an advance in technology, you fully understand the risks involved in your security system.
Note that "absent an advance in technology" phrase. That is not unique to RSA, but is true with any security system: be it cryptography, digital or even a physical security system. The risk of technological advances obsoleting your security system is always present. If you cannot stomach that, I'd suggest that you keep away from fields that require significant security.
----
----
Open mind, insert foot.
1. Yes, factorisation is the most effective attack on RSA known by far. Well, there's other stuff like low exponent attacks or chosen-ciphertext attacks which you can avoid with good practice, but factoring is the best approach given only the public key and one ciphertext.
2. I define "really hard" as "intractable": ie "yielding to no polynomial-time algorithm" or "outside P" in short. Assuming P != NP, I see no reason to believe that all problems in NP but outside P will be NP-complete.
3. We currently have no means to prove any cryptographic problem intractable. Thus the best we can do is base our cryptosystems on the best-tested assumptions. The RSA problem is certainly one of the best studied problems in cryptography.
--
Xenu loves you!
If the NP-complete problems are in P, all NP problems are in P, including factoring: that's what P=NP means.
--
Xenu loves you!
RSA is built on the assumption that the RSA problem is hard. This would imply point 3, and it would imply that factoring is hard, but RSA might still be strong even if both of your points 1 and 2 were false. In fact I don't think factoring is believed to be NP-complete, but it is believed to be outside P.
--
Xenu loves you!
This is just Not True. Though no encryption agorithm other than a one time pad has been proven unbreakable, the foundations of computer science are based on the ability to calculate (for some problems) with 100% certainty that "you have to do operation o at least f(n) times to solve a this problem", and that certain problems (ie, the halting problem) cannot be solved by computers. Even quantum computing doesn't get around this, it just allows many parallel computations to take place at once.
I don't think that any wide spread encryption algorithm falls into either the "unsolvable" or "known scale super-polynomically", and I don't expect to see any of the former (that would make it kind of hard to decrypt), but super-polynomic encryption algorithms are certainly possible. That kind of algorithm, while crackable, can be made arbitrairly hard to crack, at much lower cost to the encryptor (assuming the actual alg. runs as a polynomial of the key size).
Quantum Encryption (which really isn't an encryption algorithm, but a protocol for securely exchanging one time pads) looks like it is provably secure. It is based on the principle that it is impossible to duplicate a 2-state system exactly.
In 2 words, you're wrong.
This is an obvious troll, and repeats the tired old myth that only people with something to hide need to use encryption.
The security of the RSA algorithm is based around factoring of large prime numbers. Unless a faster method of factoring is developed (e.g. quantum computers) RSA (the algorithm) is safe.
The main vulnerabilities with RSA are implementation-specific: short passwords, keystroke recording, etc. That's why an open-source implementation is desirable. I'll give a meatspace analogy. Which would you choose - a lock that you have the blueprints for and hackers worldwide can't crack or a lock a martektroid assures you is secure.
Life is a psychology experiment gone awry.
If this is true, you can easily prove it.
Ron Rivest indicated he was happy to generate an RSA challenge for anyone who thought they had a break. Why don't you ask him for a challenge, break it, and then the world will believe you?
Alternatively, piss off and stop spreading FUD.
--
Xenu loves you!
As far as I can tell, 2 is inaccurate and 3 is not specific to RSA.
2) Factors doesn't have to be NP complete. If I have a P time way of solving Factors, that doesn't help me solve 3-SAT without a bidirectional reduction between them (from 3-SAT to Factors should be straight forward, the reverse is thought unlikely to exist). Factors only has not to be in P, which would require NP != P. which brings us to #3
3) ALL key-based encryption is based on the assumption that P!=NP, as ALL such schemes are in NP. Thus, if a solution demonstrating how to solve any one NP-complete problem (any one NP problem will not suffice) in P time is found, all key based encryption has been broken.
However, your first point is well taken.
Ok, now that I've nitpicked on your points, feel free to return the favor.
#146 bascially beat me to the punch, but I'd like to reiterate the fact that there is a whole slew of problems that are not in NP (and not in P) but are unlikely to be NP-complete.
Factors is one such problem, as are most other encryption schemes, including blowfish and rijndael (sp?).
For all these problems, if NP = P is proven, we're hosed. But it is fine if Factors is proven not to be NP-Complete.
However, Quantum Computing is a line of investigation these days that has the potential to break RSA. It's known that factoring can be performed in polynomial time on a quantum machine. Practical implementations are far away, but the problems inherent in this method of computation are being tackled bit by bit. It's conceivable that in a few decades a whole new class of computational devices may exist that make cracking RSA and many other problems trivial. You have been forewarned!
Are you making the distinction between deterministic and non-deterministic functions? Just asking.
As for quantum encryption, there are still problems. The MitM factor becomes very serious in quantum key exchange. But if you can get around that, it's possibly provable.
Returned Peace Corps IT Volunteer
the key to breaking RSA encryption, as most people know, is factoring large numbers quickly. according to the current state of mathimatics this is not possible except by trial and error, brute force. However if there was a way to factor numbers without the need for mathimatics, this method of encryption could be rendered useless. I have an idea for using physical means to break down large numbers into their prime number componants (factoring). If anybody is interesting in reading about my machine (which will never be build because i lack the skill, drive, and malice towards society) feel free to write me and i'll post it somewhere.
What you say is true, but it's mathematically much easier to explore the boundary between poly-time and super-poly-time than it is to work with the real-world constraints you describe. In practice, anything with a super-polynomial difficulty can be made too hard for your attacker with an appropriate keysize; people are less likely to be confident of that with poly-time problems.
Factorisation is super-polynomial but sub-exponential. I don't think Moore's Law will be threatening 4096-bit keys for some time to come...
--
Xenu loves you!
If someone were to crack RSA, that is, find a method to find one key from the other in less than exponential time, it would automatically follow that they had a method to factor numbers in polynomial time. It's not just that if you can factor numbers, you can solve RSA. If you have the public and the private key, you can recover the factors of N, which almost everyone thinks is hard.
Factoring is not believed to be NP-Complete, but it isn't thought to be in P either. It's in the "can't do it in P, but it's easier than other stuff you can't do in P". Breaking RSA isn't the same as breaking something like DES. DES is a strange bundle of a bunch of stuff with little theoretical backing (it just works). RSA is based on really simple number theory. Breaking it would probably be the biggest math story of the decade (this one, that is. last decade had a better one).
I take it that "subtle" and "innuendo" aren't in your dictionary?
Though seems unlikely that an unknown person might find the counterexample, it's a bad idea to dismiss it as "impossible" or "funny", because one day, in some mathematical field or another, it'll happen.
It has happened before, and could happen again. Higher mathematics is a fascinating field - every now and then you end up with interesting character. Erdos was a crazy vagabond but he is one the most prolific and insightful mathematicians of modern times. Ramajun (sp?) was an Indian college dropout who made made significant contributions in analysis with little formal training in math. He wasn't big on proof, and some of his 'thereoms' were just stated as truths, and not rigorously justified (or dejustified) until after his death.
RSA's biggest fear just might be some modern day Ramajun. The big 'R' should be understandably apprehensive whenever some guy off the street emails and says he's broken RSA - because it just could be true.
Check your sources people! Unless you can link to it on a reputable site or find it in a reputable (whatever), don't trust it. And for the reputable sites - CHECK IT FIRST!
Ok, end-of-rant. RSA is safe to use and since it is the simplest public-key algorithm I know of, I don't it believe it will be broken (simpler is easier in security). In fact, in order to break RSA, you'd have to find a way to discover prime numbers without having to check them individually - that'd be quite an achievement and a mathematical triumph.
The problem with capped Karma is it only goes down...
SIG: HUP
"Here's a cleaned-up edit of what's been bouncing around your inboxes all day..."
Turn off your javascript! I don't want you reading what's bouncing around MY inbox!
--
MailOne
Non-meta-modded "Overrated" mods are killing Slashdot
(Hey Ryan! Here's your proof!)
Right now, there are so many systems that are 100% reliant on encryption to provide their security. What's going to happen to our security infrastructure once someone *does* find a way to break these systems?
Don't we need some kind of "Plan B?" Whether it comes from a mathematical breakthrough on factoring, or quantum computing, these methods will eventually be broken. Nothing is unbreakable.
We're just lucky that this time someone was just a bit confused.
Ben Schumin :-)
A simple method of trisecting any angle has been developed by an amateur mathematician working in Los Angeles, following quickly on his patent for a perpetual motion machine.
Stories by credulous journalists everywhere.
Floating face-down in a river of regret...and thoughts of you...
I for one am very pleased to hear that the Republic of South Africa hasn't actually been cracked. They really have enough problems down there as it is.
I love going down to the elementary school, watching all the kids jump and shout, but they dont know I'm using blanks.
- The only way to make a general break of RSA is to factor large composite numbers,
- Factorization of large numbers is an NP-complete problem,
- P != NP
Remember: none of these have been proven. At all. There is absolutely no evidence of the correctness of any of the three conjectures, except that historically we haven't been able to do it--and that's exceptionally weak evidence.Compare this against something like elliptical-curve cryptography. ECC is also built on many conjectures, but one of them (the Taniyama-Shimura Conjecture) has recently been formally proven (by Wiles, et al). Mathematicians are still reviewing the multiple Taniyama-Shimura proofs to make sure that (a) they are correct singly, and (b) taken together they prove the entirety of Taniyama-Shimura--but last I heard, things were looking promising.
The thing we have to worry about most currently with RSA is whether or not we're all using the same keys over and over again.
Absolutely not. We've got some extremely good ways of generating large random primes. The odds of a collision in the keyspace is probably somewhere on the order of 10^(-150), a really really small chance.
If you want to see this principle in action, connect to a PGP keyserver and type in your key ID (a cryptographic hash of your key). If you get any other keys coming up with your same key ID, then I'll agree that we've got a problem. Otherwise, don't worry about it.
My understanding of "triple DES" is this: You encrypt a plaintext file with some key (say "A"), then you run the decrypt function with some other key (say "B") and then recrypt the results with the original key ("A") When you go to decrypt it, Do the opposite steps (Decrypt A -> encrypt B -> Decrypt A), and that gives you the strength of 112bit key (IIRC) Also, I think that encrypting DES with two different keys gives you the strength of a 57 bit key
Doh!
I would like to announce the solution to this difficult scientific problem as well as to establish prior art against any future patent holders. The following code is now in the public domain, feel free to add it to your security product.
Here is my algorithm for factoring prime numbers.
double FactorPrime(double PrimeNum)
{
cout << "The factors of prime number " << PrimeNum << " are 1 and << PrimeNum << ".";
return PrimeNum;
}
No, Thursday's out. How about never - is never good for you?
Leo: I cracked RSA!
Ron: How about some details.
Leo: Here are some. Blah, blah...
Ron: How about some details.
Leo: Here is an example. Blah, blah...
Ron: Silly rabbit, trix are for kids. You've proved to yourself that this is a "hard problem". Everyone else in this field already knows this. But good try and keep up the good work.
Leo: I think you are wrong and my method is faster.
Half of Slashdot Crowd: What an idiot!
Other Half of Slashdot Crowd: I think he's onto something!
Troll: Look at my goatse.cx link hidden as an informative link!
... is kind of interesting. If you look at very early versions of PGP, an algorithm of Phil Z's own design called Bass-o-Matic was used. Turns out that Bass-o-Matic wasn't a particularly good algo, but they learned from the mistake and from there on only used peer-reviewed algos.
Insofar as the likelihood of breaking RSA, history shows that you're exactly right. While RSA is built on a lot of conjecture, it's survived a lot of mathematical attack. Protocol attacks against RSA have historically been far more effective. Check out the Crypto-Gram of a couple of months back for a quick look at RSA protocol attacks over the years.
(I know Schneier covered at least one RSA protocol attack recently; I think he covered more than just the one. But my memory could be mistaken.)
I achieved cold fusion in my bathtub this morning.
You better double-check your results and to make sure that gas emission was indeed helium.
The ivory tower has never had to reach so h
Hasn't everyone cracked RSA? I did a long time ago. Read about it in my out-of-print book Undocumented Cryptographic Algorithm Cracks.
Pete Davis
Just asking. :)
"Dogs and cats, living together...it's mass hysteria!"