Slashdot Mirror
Math Advance Suggest RSA Encryption Could Fall Within 5 Years
holy_calamity writes "The two encryption systems used to secure the most important connections and digital files could become useless within years, reports MIT Technology Review, due to progress towards solving the discrete logarithm problem. Both RSA and Diffie-Hellman encryption rely on there being no efficient algorithm for that problem, but French math professor Antoine Joux has published two papers in the last six months that suggest one could soon be found. Security researchers that noticed Joux's work recommend companies large and small begin planning to move to elliptic curve cryptography, something the NSA has said is best practice for years. Unfortunately, key patents for implementing elliptic curve cryptography are controlled by BlackBerry."
otherwise hackers will use it to mess up the internets.
http://en.wikipedia.org/wiki/Elliptic_curve_cryptography
https://www.schneier.com/essay-198.html
OpenSSL has had a good working implementation of ECDSA/ECDH for years: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography
What exactly does BlackBerry have chained down that we don't have an open solution for?
/* * pope1 */
Hmm ... considering Blackberry/RIM's precarious hold on existence, I have a hunch those patents will be in other hands very soon.
Article is dated 8/2 (Friday), yesterday would be the first tradable day on the information.
Your first sentence sounds weird to me, and it isn't supported by your second. AES can't be a suitable replacement for RSA because AES is a secret-key system and RSA is a public-key one.
I'm not a crypto person, but RSA and elliptic-curve systems are the only two public-key systems I can think of. (There are others that allow secure exchange of a secret key, but that's different.)
Maybe it might be time for an algorithm challenge, similar to how AES got decided, and the lastest hash algorithm got chosen.
Of course, asymmetric algorithms are a lot harder to make that are secure than symmetric ones.
I wonder about, instead of naming one, naming three. That way, if in the future one gets compromised, the broken one would just not be used, or for very sensitive stuff, all three can be cascaded (not for bit length, but to keep things signed or encrypted in case one gets severely weakened.)
You need upvotes, but I'm out of modpoints.
You are very correct. Take for instance OpenVPN. It uses RSA to exchange an random AES session key. RSA and AES/DES/3DES have different uses, and replacing RSA with AES is simply not possible.
Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.
We used up all the good prime numbers during the Internet boom years under Clinton.
Based on my limited understanding, proving P = NP would not necessarily and automatically provide a manner of constructing reductions. It might. But there are proofs in computation theory that demonstrate limit complexities but do not provide the algorithms that might implement them, nor do they (currently, visibly) provide any indication of how that algorithm may be arrived at.
Besides, proving P = NP would have a vast number of consequences that would echo across mathematics and the more fundamental sciences. To harp upon the security implications is as short-sighted as fretting that all-out thermonuclear war would negatively affect the postal delivery service.
"Place me in the company of those who seek Truth, but deliver me from those who believe to have found it."
Yeah. They have taxes for that.
Without a statement as to whether the NSA has been involved in elliptic curve stuff (though I will point out that they have nearly as much motivation to make things hard for, say, the USSR/China [depending on era] to crack as they do to make things easy for them to crack), did you read your link? It isn't really talking about elliptic curve crypto at all.
It's describing a potential flaw in a random-number generator whose algorithm is based around elliptic curve crypto. Even if every worry presented by the article is true, that means absolutely nothing about whether elliptic curve is secure against the NSA.
(Actually it almost suggests that it is, because if EC was breakable then the NSA wouldn't have as much motivation to get a known key into the RNG standard.)
Wow, that is so wrong.
RSA is an asymmetric (aka publick key) cipher - because it requires two keys - one to encrypt, one to decrypt. AES, DES, 3DES are symmetric ciphers because you use the same key to encrypt and decrypt.
RSA and EC (elliptic curve) encryption is useful if you want to send data to someone without the hassles of secretly sharing the key ahead of time - e.g., I can encrypt a message using the public key and only the private key can decrypt it. Or I can use my private key to encrypt a message, and the public key can be used to decrypt it (the latter is often used to sign stuff, except the message is typically a hash instead of the original message).
The reason you use AES, DES, 3DES is because public key encryption is hideously slow. In the case of RSA, you're exponentiating one horrendously large number with other horrendously large numbers. (If your message is long, that horrendously large number Is big).
That's why what every public key encryption thing does is it encrypts the message with a fast symmetric cipher like AES, then encrypts the key (much shorter) with RSA or EC. If I want to send you a document, I encrypt it with AES, then use your public key to encrypt the AES key I used.
It's also why signing uses a hash - it's easier to encrypt the hash than the message. And verification just means recomputing the hash, and then decrypting the encrypted hash with the public key, producing the original hash to which can be compared to the just computed one.
The breakthrough in math would be a way to factor a large number quickly - which is what RSA relies on for security - it's easy to multiply two big numbers, but it's very time consuming to factor it.
They do. It is called taxes.
You pay to be spied on, good deal!
`echo $[0x853204FA81]|tr 0-9 ionbsdeaml`@gmail.com
There's a fundamental difference between breaking the algorithm mathematically and the key space being too small. People left DES and 3-DES because the key size was too small and a brute force became feasible. The same is becoming true for RSA, but this is completely different than solving the discrete logarithm problem that underpins RSA and Diffie-Hellman. Solving that would be an amazing feat of mathematics. So please stop trying to show off to /. how you're smarter than everyone else.
Actually in some ways it would be really really exciting and almost certainly a really good thing in the long run, because there are a lot of important, currently-intractable problems that become tractable if P=NP.
Proving that P=NP doesn't make anything tractable, unless you use the ridiculous definition where tractable is the same as polynomial time. What would have practical applications is if someone finds a very fast algorithm for solving all the NP problems. Whether P=NP is not really very much related to the question of whether such an algorithm exists. ML has exponential-time type checking, yet ML compiles don't take that long. Polynomial time is not the same as practical - it fails in both directions.
From what I remember some mathematician had figured out a shorter way to solve the discrete problem and built a black box to do it. The main characters then stole his machine.
Well, there's spam egg sausage and spam, that's not got much spam in it.
http://arxiv.org/abs/1306.4244
You can't patent math.
As TFS states, it's the implementation that is patented. Not sure which ones belong to blackberry, but google patents has a number of related patents based on a quick cursory search.
Adam Van Ymeren said it well. An algorithm's age doesn't necessarily speak to how secure it is. DES is considered insecure because it has a fixed key size that can be brute-forced, not because it is a fundamentally weak crypto system.
By contrast, the same objection does not apply to RSA, at least AFAIK: the key size can be scaled arbitrarily, so as computing resources grow so can the difficulty of the problem. I'm not familiar enough with the area to know how the discrete log helps RSA (integer factoring is the usual weakness I associate with that algorithm), but at least what the summary suggests is a fairly fundamental breaking of the algorithm. I didn't read TFA, but possibly key sizes would have to be scaled up prohibitively to remain secure.
DES vs AES is not the same situation at all as RSA vs EC.
Why elliptic curves when we can go back to good old fashioned original RSA that uses prime number factoring as the problem? No patent nonsense to worry about there.
Sometimes the past needs to remain in the past...
Although prime factoring is considered a hard problem, the sparse distribution of prime numbers (~x/ln(x)) makes RSA increasingly inefficient in that superlinearly large moduli (to match large primes) need to be used to increase security linearly.
Lest nostalgia continue to be your guide, the original RSA was also found to be broken and needed to be patched to avoid the insecurity
1. Messages corresponding to small input values could be simply inverted ignoring the modulus operation (just doing numerical root estimation to invert the exponentiation). The larger the modulus, the more "insecure" messages there are.
2. Encryption is deterministic so is subject to dictionary attacks.
When people say they are using RSA today, they are usually using RSA-OAEP (optimal asymmetric encryption padding) which patches these two specific vunerablities of RSA.
FYI, the original RSA was patented (although later RSA labs decided to not enforce the patent and let it expire). This patent nonsense around RSA was a big issue in its day...
What exactly, does proving P = NP have to do with the price of tea in China? We knew when RSA was created that advances in computation power would eventually make it feasible for us to decrypt its contents. We even know what that boundary is.. and we're coming up on it now.
No encryption algorithm is immune to the fact that the faster you can run an algorithm, the sooner you'll get a result. That's all encryption is. I don't need to be a math major to figure out that if I have a car that can go 200 MPH it'll get there twice as fast as a car that can only do 100 MPH.
#fuckbeta #iamslashdot #dicemustdie
Deprecated - I don't think that word means what you think it means. RSA can't be deprecated when there isn't a replacement. Elliptic curve cryptography has only really become a realistic replacement fairly recently, and nobody outside of government rushed to give Blackberry lots of money to use it because there wasn't a compelling reason to do so. Governments DID, which suggests to the conspiracy theorist that they might know of such a reason.
It's been long recommended you don't use short keys with RSA (which were used in the past for speed) but the algorithm itself is secure (as far as we know), no matter how much hardware you throw at it. This story is about the possibility of a mathematical advance (note, the possibility, it hasn't happened yet) that could make the RSA algorithm itself insecure, for any key length.
A breakthrough in solving the discrete logarithm problem would be a big deal. It could also very well lead to breakthroughs in integer factorisation.
You still can't replace an outdated public-key encryption key system with a symmetric system. Because, in real life, usage scenarios and key exchange systems actually matter - in fact, they are the most crucial aspect of the whole thing, otherwise we'd use true random one-time pads and be safe from any attack with any level of computing power forever.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
I didn't say that you said that AES could replace RSA: I said that your AES/DES analogy didn't support your statement that RSA is or should be deprecated. That may sound like I'm nitpicking here, but I'm really not: it's pretty fundamental to my point. And the reason is this:
This absolutely need not be true. RSA for instance is based in part around a hardness assumption: that given a very large number n which is the product of p and q, it is far harder to find p and q from n then it is to find n from p and q. Assume for the sake of argument that this is the only hardness assumption RSA depends on. (If the summary isn't misleading it apparently also depends on the hardness of discrete log, but I don't know how.)
If the hardness assumption holds, then RSA as such will never be insecure. Why? Suppose you say "here is a computer capable of factoring a number n with b bits." I'll say "OK, fine; I'll use 100*b bits (or something)"; because multiplying is so much easier than factoring, your computer will still be able to carry out that task but it won't be able to crack my key.
In other words, if the hardness assumption holds, RSA doesn't have a specific difficulty: it can scale with computational power. That's why you see people using 2048-bit keys now instead of 512-bit keys a couple of decades ago.
The only things that the age of the algorithm has to say about the security of it is (1) if the difficulty cannot scale with computational power (true of DES, not true of RSA) and (2) being out longer gives people more time to find flaws in its assumptions.
But here's the thing: #2 isn't necessarily bad or speak against the algorithm. It is conceivable that the assumptions just fundamentally hold. If they do, being out longer will not impact the security at all. If anything, being out longer with no one discovering anything should give a higher assurance that an algorithm is secure than a newer one would.
I don't think I've ever heard a blanket statement about RSA being insecure -- only things like certain key sizes or certain implementations or PRNGs being insecure. (Wikipedia also lists a couple of side-channel and plain-text attacks, but those are also arguably quality-of-implementation issues, and similar attacks exist for EC systems.) The intro to the Wikipedia article says nothing about RSA being insecure. "Deprecated" and "discouraged" both fail to appear on the page.
The strongest statement against RSA I've heard is just that EC is better.
Except that the DES vs AES case is not even close to being the same case, as Adam Van Ymeren said in response to you, and then I elaborated on elsewhere and above.
The reason it's not even close is that DES does not scale with computational power, because it has a fixed key size.
It's a great deal if you're an exhibitionist!
I'm surprised to see other people going in the direction I've been going for about 3 years now. Really. I thought I was quite alone in my path, LOL.
I need to read this paper still, but if it's taking the same path I did, then it's not a peachy as some think.
I'm only am amateur, so take this from the point of view as someone who kicks back with a beer and enjoys solving impossible computational problems.
I don't think it's that close to being broken... I think it'll take a huge computing effort (think multi-terabyte databases) to generate the tables across the PQ space required so that existing problems can be used to quickly find paths and intersections. At the beginning you're looking at only a VERY SMALL speedup from modern sieving, but once the tables get generated (years of effort) you'll eventually see faster and faster improvements. At least, that's with my algorithm, which I'm sure is far from perfect and only works on a certain set of primes right now. Which is about 20%. Which is far from optimal.
So yeah, progress. But I'm unconvinced that this will work for all primes.
I'm going to read the paper now... which I'm sure is far better than what I've been doing.
I said no... but I missed and it came out yes.
The story is talking about the possibility of a mathematical breakthrough that would make solving the discrete logarithm problem (and possibly the integer factorisation problem) much, much easier. RSA relies on it being much easier to raise something to an integer power than to find a discrete logarithm (inverse operations). If you figure out how to make the two operations of similar difficulty then any encryption scheme based on them is hopelessly broken for any key size.
We knew when RSA was created that advances in computation power would eventually make it feasible for us to decrypt its contents. We even know what that boundary is.. and we're coming up on it now.
No, we did not know any such thing. Advances in computation power can be defeated by increasing the key length of RSA, indefinitely. RSA cannot be made useless just by making regular computers run faster.
Finally! A year of moderation! Ready for 2019?
(One way this could fail is the following: factoring I think is in a no-mans land between P and NP, not known to be in P nor known to be NP-complete. If NP collapses into P then so must factoring, but it could be that factoring is some weird-ass O(n^23) algorithm or something while every NP-complete problem can't be done in less than, say, O(n^6000).)
Consider this: Performing 2^256 operations is physically impossible (based on the quantum mechanical minimum energy to do anything, and the total amount of energy in the universe). 100 digit numbers are about 330 bits in size. If factoring n bit numbers required n^30 operations, then factoring just one 330 bit number would be physically impossible.
There does not appear to exist any single piece of evidence that DLP (discrete logarithm problem)
will benefit from algorithms running in polynomial time. The recent work of Antoine Joux that they
are referring to (one of which I assume to be http://arxiv.org/pdf/1306.4244v1.pdf) provides
improvements of quasi-polynomial agorithms for breaking DLP. But there is no reason to believe
that these improvements can lead to a polynomial-time attack. And as long as this does not happen,
those attacks can still be defeated by increasing the key size.
If it's a question of key size, then why not use larger keys? The last time I checked, it is possible to increase the size of RSA keys quite a bit.
Because large RSA keys do unfortunate things to performance. You double the key length, and it takes 6-7 times longer to run the decryption.
upon the advice of my lawyer, i have no sig at this time
Patents have been an issue of national security for a while. Several countries, including the US, has secret patents. It takes someone wiser than me to explain how that promotes the progress of science and useful arts.
Finally! A year of moderation! Ready for 2019?
Based on my limited understanding, proving P = NP would not necessarily and automatically provide a manner of constructing reductions. It might. But there are proofs in computation theory that demonstrate limit complexities but do not provide the algorithms that might implement them, nor do they (currently, visibly) provide any indication of how that algorithm may be arrived at.
You are technically correct, but certainly the quickest and most direct proof is to show a general solution for an NP-complete problem that runs in P time. And while proving P=NP would not necessarily provide the manner of constructing reductions in the general case, solving any NP-complete problem in P time does absolutely provide automatic solutions for *all* NP-complete problems in P time since, by definition, all NP-complete problems are reducible to each other. And factoring is an NP-complete problem.
You misunderstand the difference between throwing hardware at a problem and coming up with a more efficient algorithm.
RSA doesn't specify a key length. I can use a key that's 64 bits long (used originally but insecure today) or 1 megabit long (secure against known classical algorithms for the age of the universe no matter how much hardware you throw at it). As hardware gets better I can encrypt things using longer keys, in the same amount of time. It takes you MUCH MORE time to decrypt that, even with the better hardware. So long as you keep increasing key length as hardware gets faster, the encryption actually gets BETTER with better hardware.
The article is talking about a breakthrough in mathematics that could make solving discrete algorithms much faster. If it made it anywhere near as fast as exponentiation then it wouldn't take me much longer to decrypt your message than it took you to encrypt it, regardless of key length.
DES is insecure because it uses fixed length keys, that became practical to brute force. RSA doesn't have that problem. The situations are entirely different, and the potential breaking of RSA is much more interesting, and much more of an accomplishment.
(if you can get a trusted version with no 'escrow' technology built in, that is)
As I recall, the guys who wrote PGP back in the day almost went to prison for publishing the source code - despite the fact that the RSA algorithm in use was already publicly documented (in Scientific American IIRC). "The Powers that Be" learned from that debacle and have far more reliable mechanisms for gaining access to everything you do in the clear if they want it (for example, the TCM in my new HP PC is turned on and enforcing - I can turn it off, but what other little goodies have manufacturers hidden in the firmware for me to discover?).
Moral of the story - IPv4 is exhausted, go to IPv6. BIND4 is obsolete, go to BIND8. NFS is dated and insecure, go to NFSv4. RSA is at risk of being compromised by advances in mathematics, go to [something better]. Really - is cryptography supposed to be carved in stone? I know that worked for the Egyptians, but anything related to the technology field...
I care more about Thieves gaining access to my bank account than Hackers or the NSA.
I don't care why you're posting AC
You don't know that for certain; it is conceivable (if seemingly unlikely) that the easiest proof and the first found could be non-constructive.
(Remember, to prove that a problem is in P you not only have to come up with a P algorithm for it but then you have to prove that the algorithm is actually in P. It could be that any algorithm for a (currently-considered) NP-complete problem is complex with a staggeringly complicated proof that it's in P at all.)
This is a bit of a nit, but factoring isn't known to be NP-complete; from what I can tell, it's actually widely believed to be in an intermediate class between P and NP. (No P algorithm is known, as you note, but there is a sub-exponential algorithm for it, which violates a widely-held belief that NP-complete problems are necessarily exponential.)
More to the point, how the FUCK does one weasel a patent on crypto (which is just math, and therefore, unpatentable) through the system? I would think the USPO would just round file anything coming in that has to do with crypto on general principle...
HA! I just wasted some of your bandwidth with a frivolous sig!
For encryption, that's fine. For signatures and hashes, cascading WEAKENS it. An attacker only has to crack ANY of the algorithms to crack the whole. To prove that to yourself, try it with one of the algorithms defined as:
function Weak(msg) {
return 1;
}
Compare these two:
Weak(MD5(msg))
MD5(msg)
Correct me if I'm wrong but you are not allowed to patent mathematical processes. "Elliptic curve cryptography" sure sounds like a "mathematical process" to me and a pack of especially smart and vicious patent lawyers should be able to blast RIM and Blackberry away in short order (by patent litigation standards which is aeons long). Sounds like a job for Amazon whose entire business model, the one they make money on anyway, depends upon the integrity of SSL which depends upon Diffie-Hellman and RSA for key exchange, if my flawed memory serves. Gotta blow the dust off my SSL book....
It's really quite a simple choice: Life, Death, or Los Angeles.
That's a common misconception. The actual law is:
You cannot patent the laws of nature, including the laws of physics and mathematics.
A car MAKES USE of the laws of physics, but it may be patentable if it's a new invention. You cannot patent X + 1 = X - (-1) because that's mathematical truth, it existed before you noticed it. Just as you can patent a new invention that USES the laws of physics, you can patent some system that uses math. In this case, a system for securely delivering secret messages across a public network. Of course it still has to be a new and useful invention in order to be patentable.
1 + 1 = 3
This is a correct answer. Do you know why?
It was calculated in Excel?
How is the Riemann zeta function like Trump rallies? Both have an endless number of trivial zeros.
Yes, we need to check everything. That being said, this feels like game theory. Don't you get the sense that the NSA wants us to doubt the technology. If cryptography was widely used most of what the NSA does would be made obsolete.
There is another promising public key encryption method known as NTRUEncrypt (http://en.wikipedia.org/wiki/NTRUEncrypt). It's lattice based, and apparently it will still be effective in a post quantum computing world where RSA/Elliptic curve methods will fail.
Not if you believe in "intellectual property" rather than "[...] To promote the Progress of Science and useful Arts, by securing for limited Times [...]"
This is why the "intellectual property" meme is so perniciously evil - it completely transforms the purpose and intent of copyrights and patents.
The RSA encryption is
c = m^e (mod n), where m is message, c is ciphertext, e is public exponent, and n is p*q
Decryption is
m = c^d (mod n) where d is the private exponent.
The process of computing d given m,n and c is exactly the discrete logarithm problem. Given n and e, which are public, you can pick an arbitrary m and generate a corresponding c.
I don't need to be a math major to figure out that if I have a car that can go 200 MPH it'll get there twice as fast as a car that can only do 100 MPH.
You would have been better as a math major. To understand the issue, realize that a car going 200MPH needs much more power than a car going 100MPH. A car going 400MPH will need even more power. Similarly, with some algorithms, the solution becomes harder and harder the larger the dataset grows; often exponentially (or even factorially).
"First they came for the slanderers and i said nothing."
I have been reading his papers for some time now, and the guy is definitely making progress. Recent work, however, in the field of multilinear maps seems to point into a new direction: multiparty Diffie-Hellman agreement. That would be a lot harder to break. Basically, in such a scheme, when wanting or needing to establish a classical Diffie-Hellman agreement, you'd invite a trusted third party in. Eventually, that scheme may get broken, too; yet, it may grant implementors and users another 10-to-20-year truce. As for TFA on technologyreview.com, it sounds a bit like fear-mongering, to my taste.
Religous speak to God. Insane are spoken to by God. When all shut up, one can finally hear Shostakovich in peace