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.
...the NSA will have a backdoor into that epileptic curve whatnot too.
The RSA encryption has been depreciated for years now. Hell, back in 2000 we were saying that DES was insecure, and triple-DES was just a stop-gap. Everyone's been switching to AES for awhile now. This isn't news.
Every encryption scheme has to balance performance and security; And we balance it so that in the next 5, 10, 50, or however many years, advances in technology won't render the data vulnerable in the interim. It's basic engineering. It's like building a safe -- you can't stop it from being broken, but you can make it so that it takes time. Hopefully enough time to get additional resources to the site to stop the thieves. There is no such thing as an uncrackable safe... or an encryption scheme.
The goal is to make sure it takes long enough that by the time they get in, either the men with shotguns have arrived, or whatever it was protecting is now useless to them. If you don't understand this fundamental rule of security, then perhaps this article is newsworthy... but to anyone who works with information security... it's just confirmation of existing methodology.
#fuckbeta #iamslashdot #dicemustdie
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 */
I recently took a survey put out there by a researcher studying those working in the security community. One of the questions was about what threats really keep me up at night. My answer? That someone proves P = NP.
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.
And cue the conspiracy theories that will say the NSA can break elliptic curve cryptography, so they cause fear that the discrete logarithm problem will soon be solved to get people to migrate to that which they can break. Hell, in today's world it might even be true, though I would bet on it.
the NSA had already solved the discrete logarithm problem...
[...] elliptic curve cryptography, something the NSA has said is best practice for years.
...or cracked elliptic curve cryptography.
If Pandora's box is destined to be opened, *I* want to be the one to open it.
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.
Ed25519 by Dan Bernstein solves the patent issue and offers efficient and simple implementations.
Really, we want to take the NSA's advice on which crypto to use?
You can't patent math.
Schneier's essay refers to Dual_EC_DRBG, a pseudorandom number generator that is based (in part) on elliptic curve cryptography.
A broken or malicious pseudorandom number generator is bad news to be sure, but even if Dual_EC_DRBG is broken or malicious that doesn't mean that elliptic curve cryptography as a whole is broken or malicious.
In many countries encryption of past communications will be breakable before criminal statutes of limitations run out, and that's just for the crimes that aren't so serious that they have no time limit.
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.)
The old saw was that a solution to any NP complete problem is a solution to every NP complete problem. Therefore, if both discrete log & elliptic curve problems were NP complete, this research would break both of them. If, however, discrete log isn't NP complete, you can come up with a fast solution for that problem and still be OK using elliptic curves.
I don't see how moving to Elliptic Curve crypto helps, since it's also based on the discrete log problem. Search for the term here: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography
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
Maybe this will finally spur the abolishment of software patents.
Patents have now become an issue of national security.
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.
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 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...
Fuck patents on elliptical curve cryptography. Math should not be patented, period. Algorithms should not be patented.
I recently toured the University of Waterloo which is right beside RIM/BlackBerry. The co-founders of RIM have sponsored the creation of new buildings on campus, one of them being the Institute for Quantum Computing. Since RIM owns some patents on elliptic curve cryptography AND basically sponsors quantum computing research, they must have a hunch that soon Quantum computers will be able to crack RSA encryption which will create a demand for patent licensing.
1 + 1 = 3
This is a correct answer. Do you know why?
The mind conceives, the body achieves, the spirit manifests.
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!
wait, what?
CLI paste? paste.pr0.tips!
Algorithms for either can normally be converted to do the other. If either falls, the other is likely not far behind.
Ffunction ption, fine. For signatures and hashes, cascading WRAKENS 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)
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)
But Eliptic Curve crypto as published by NIST has a back door installed by the NSA. Isn't it interesting that just as people are looking at encryption to keep the eyes of government out of their data, someone provides a tentative reason not to use the best there is but to move to the compromised stuff? The fact that the back door exists suggests that getting EC right may be a hard problem. Now where is that article about the EC back door?
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.
Send Robert Redford and Sidney Poitier out to steal whatever device Joux is using to help solve these algorithms, before the mafia does.
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.
“Our conclusion is there is a small but definite chance that RSA and classic Diffie-Hellman will not be usable for encryption purposes in four to five years,” said Stamos
Laymen terms: There is a small, but non-zero probability that an asteroid will collide into the earth and destroy civilization in the next 4 or 5 years
My thought: There is a non-zero probability of INSERT_UNLIKELY_EVENT happening in the next 4 or 5 years. Should we panic? Nah. That is called life... There are no guarantees. If we worried about unlikely events happening...we'd be in a state of paranoia, fear, and constant worry of the next catastrophe. Oh wait....wrong thread.
That article gives no reason to be worried about elliptical curves. What it does give reason to be worried about is magical constants and the use of asymmetrical primitives for something that can be done with symmetrical primitives. The concern about the magical constants is why some algorithms use digits of e or pi for the constants. And since random number generators can be build using symmetrical primitives, it is suspicious when somebody choose to use asymmetrical primitives. That later decision need to be accompanied by a new formal security definition and a proof that such security definition cannot be achieved using symmetrical primities.
The combination of asymmetrical primitives where none are needed and magical constants of unknown origin is extremely suspicious. Even if you cannot prove it to be the case, it seems very likely that those magical constants are in fact a public key, and somebody knows the corresponding secret key.
Which asymmetrical primitive they chose for the construction is of no importance to the story though.
Do you care about the security of your wireless mouse?
I thought the bulk of encryption was usually done with some streaming cipher.
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.
I use Certicom's ECC Libraries everyday mostly for ECMQV (key agreement with user authentication) and also signatures. They charge nothing or almost nothing for the use of their patents in some industries. They do charge for their libraries and acting as a CA. For embedded devices with limited resources and bandwidth I can do things that are simply in-feasible with RSA. Certicom's math is beautiful. The curves that they chose and the neat properties they have make it possible to perform asymmetric encryption on devices with tiny amounts of RAM. I hate patents but I have no moral objection to paying Black Berry for what they provide.
> Unfortunately, key patents for implementing elliptic curve cryptography are controlled by BlackBerry.
"Who's gonna go broke now, bitches?!?!?"
(-1: Post disagrees with my already-settled worldview) is not a valid mod option.
By its very nature, encryption is a never-ending arms race.
I haven't read the patents, but not necessarily. I can't patent gears Just because a system is made up of gears, doesn't mean the system as a whole isn't patentable. Similarly, just because the software includes logic operations and equations doesn't mean the system isn't a new invention and patentable.
A new configuration of gears and levers, doing something new, is patentable.
A new configuration of logic operations, equations and and interfaces, doing something new, is patentable.
The question is "is it a new invention"? There's no distinction in law or in common sense between hardware and software. Either it's a new invention or not. Mathematical TRUTHS aren't new inventions just as facts about physics aren't new inventions. Someone might have DISCOVERED them, but they didn't invent them.
On the other hand, a device with 10,000 gears may well be a new invention. So too, a device made of 10,000 lines of code may be a new invention.
In fifteen years of programming, largely R&D, I've come up with one, maybe two completely new solutions to old problems which are significant. One replaces CAPTCHAS with something that testers have had no problem using from ten feet away. A legally blind customer uses it on his site. I believe the law is correct in considering this a new invention.
the development that will finally kill Windows XP
Very simple. Override the patent out of public interest by presidential decree. Much like Obama did on the Apple case recently, though that was out of American interest as opposed to world wide interest.
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
Bitcoin keys uses ECDSA. Is that also being claimed by RIM?
I think it was Phil Zimmerman, who built and published PGP , whom they wanted to rectal-analyze.
Regarding advances - it it actually not difficult to create a proper paper-based OTP and then use whatever pwned hardware/telecoms stuff you have to transmit.
Essentially, write the numbers 1 to 1000 on 1000 pieces of paper. Mix the pieces. Pull pieces out of pot and assign 1000/26 to the each letter from a to z (Of course you can have a non-uniform distribution as an optimization, so that e would have many more numbers assigned).
Also print out a second list from 1 to 1000. Note each numberletter assignment onto that list.
Now you have an OTP which can encode 1000 letters. Some guy Shannon proved you cannot break this, whatever math insights and/or alien/quantum computers you have.
Of course it is quite a bit of work, but you know what ? Only Slavery is "easy".
The New Zealanders used OTPs until they got TypeXs from their mother country.
Captcha: Absurd. Why ???
No, what it shows is that the NSA is sneaky. "I don't understand why the NSA was so insistent about including Dual_EC_DRBG in the standard." Because it's a distraction. It has a visible flaw and thus draws attention away from the other methods in the standard which presumably have other, more subtle flaws.
Altough the real lesson is to not use a weapon supplied by your enemy to fight him.
Forget magic. Any technology distinguishable from divine power is insufficiently advanced.
Trying to break RSA is basically trying to find integer x,y co-ordinates that lie on the y = n / x curve.
Breaking elliptic curve is nearly exactly the same problem, except instead of using y = n / x for the curve they used the equation of an ellipse.
I've always thought elliptic curve was developed as a tricky way to get around the RSA patent issue.
For keys that need to be 'safe up to 10 years away, recommend a minimum RSA key size of 16,384 bits.
I said from the beginning... the recent move of MS to require a minimum of 2048 bits is too little too late -- we need an order of magnitude increase in RSA key lengths to keep RSA as secure as it was 10 years ago.
Even an 'efficient' algorithm for attacking the problem is likely to have certain resource constraints.
It may not be written in stone, but the encrypted communications are stored for eternity.
This article and http://threatpost.com/crypto-gains-ramp-up-calls-to-get-ahead-of-inevitable-rsa-algorithm-downfall/101560 both imply that we need to jump to ECC and get off of RSA. Since there are direct quotes from Mr. Stamos in one of these articles, it sounds like he is the source of the confusion. Actually the recent advances weaken ECC more than RSA, and RSA is only weakened if the discrete log advances are followed by similar advances in factoring. There is no known theoretical reason for this to be guaranteed to happen, but folklore shows that it has indeed happened in the past: discrete log breakthroughs are intertwined with factoring breakthroughs, but there are only vague handwaving explanations about why this should be true.
So the problem is that RSA may well break soon, but ECC is already to some extent broken by Joux et al. Any advice to throw out RSA in favor of ECC seems wrong to me. What you really need is a totally new potentially hard problem to base new crypto algorithms on, and you maybe only have months to come up with the idea, and then only a few years to get the idea into practice, or else it's a return to snailmail if we haven't completely dismantled it before then.
See http://www.treefrogenterprises.com/research/funwithecc.html for more.
... is variable, as any child knows.
"Four and twenty blackbirds, baked in a pie"
Keeping information about cryptographic designs secret, when it should be public, is in no way unique to NSA. Secrecy does not prove malicious intent, it does not prove incompetence, it does not prove presence of backdoors or vulnerabilities. NSA contributed to DES. The reasoning behind this contribution was kept secret. It took many years before somebody else figured out which security bug in the original design was fixed by the contribution from NSA.
Do you care about the security of your wireless mouse?
China has probably already cracked it. They wouldn't tell you. That's why there are loads of 0-day exploits in the wild from them.
The whole thing is unsubstantiated FUD. I base my judgment on the slides at
https://media.blackhat.com/us-13/us-13-Stamos-The-Factoring-Dead.pdf
The whole argument boils down to:
a) there has recently been huge progress [*] in solving the Discrete Log Problem over fields of small characteristic;
b) progress in solving the DLP have historically implied progress in factorization, and vice versa;
c) factorization breaks RSA, and solving the DLP breaks DSA;
d) thus RSA and DSA are dead, move to ECDSA.
The fallacy of it is that in b) and c), the DLP is exclusively over fields of huge characteristics (thousands of bits), making the algorithms in a) powerless. The slides do not hint at the faintest research lead towards moving to huge characteristics. Best argument is that "renewed interest could result in further improvements".
One the positive side, the author is honest: "I’m not a mathematician, I just play one on stage".
François Grieu
[*] See e.g. this recent paper and its references
Razvan Barbulescu, Pierrick Gaudry, Antoine Joux, Emmanuel Thomé: A quasi-polynomial algorithm for discrete logarithm in finite fields of small characteristic
http://hal.inria.fr/docs/00/83/54/46/PDF/quasi.pdf
Many people in industry are thinking that we need to be very careful in the near-future when using public-key cryptography. A catastrophic event is a possibility. See the next month workshop about catastrophic events related to cryptography and their possible solutions: CATACRYPT ( http://catacrypt.org/ ) near London. You're welcome to participate. With a committee where a lot of very important contributors. This talk at Black Hat this summer is thus very interesting. It was anticipated by a talk at CCC in Berlin in December 2011, see 28th Chaos Communication Congress (28C3), Berlin, 29 December 2011: talk by Renaud Devalière and Jean-Jacques Quisquater, in cooperation with David Samyde, The future of cryptology: which 3 letters algorithm(s) could be our Titanic? RMS Olympic, RMS Titanic, HMHS Britannic vs Discrete Logarithm, Integer factorization, Conjectured hard problems: talk is at http://www.youtube.com/watch?v=t4n7yUBtTt0 There was also a high-level workshop this year in January in Menlo Park about the end of RSA. The slides are here: http://catacrypt.org/rsa-isat-brief%20-%20Public.pdf with permission.
...and allow us to acquire the solution in a dramatically more efficient manner!
Now, I should emphasize that such an approach is purely theoretical. So far, no one has been able to accomplish such constructions, yet..
You could probably adjust your definition of "function" and "algorithm" to claim they are the same thing. Neither of those is a term used in the relevant law, so it's beside the point.
...". One might very well use some math in a particular build of the invention. The invention, the new way of blocking spambots, isn't a mathematical law any more than a new design for a mouse trap is a law of physics.
The terms used in the law are "laws of nature" and "useful invention"
Suppose I develop something using the human ability to recognize music which works much better than CAPTCHA. That might well be a new invention, depending on the details. "music is better than captcha" is NOT a mathematical fact. The laws of math make no statements on the subject of "the best way to tell a human from a computer is
It's under $10 right now, could go over $100!
The only reason your music-CAPTCHA example can't be stated as math is the lack of a good model for the human part of the processing chain.
What I meant by describing the function of algorithmns and machines as 'mathematical truth' and 'physical fact' is, that the solution to a problem derives from the fundamental laws and I think it's wrong and development blocking to let someone possess it. Still the concrete implementations of such a solution will usually differ, so it's feasible to grant someone the copyright on their work.
In fifteen years of programming, largely R&D, I've come up with one, maybe two completely new solutions to old problems which are significant. One replaces CAPTCHAS with something that testers have had no problem using from ten feet away. A legally blind customer uses it on his site. I believe the law is correct in considering this a new invention.
Your thing might be a valid invention under USPO rules. It is an application of something, and quite likely not even directly tied to any encryption algorithm. Software patents are complete bullshit too, IMHO, since you aren't releasing source code in your patent application, and aren't really sharing you work with the world at large as intended. but that is neither here nor there since there is (quite strangely) no mention of software patents in anything laid down by the founding fathers.
I was speaking about elliptical curve encryption, and any sort of claim that blackberry could make about it. An encryption algorithm is math, pretty much as pure as it gets. That sort of thing should not ever be patentable. Not under software patents, not as bullshit 'business process' patents, not as anything.
HA! I just wasted some of your bandwidth with a frivolous sig!
And you never knew until MIT rediscovered it.
That depends. If you get an O(2^(n^(1/3))) attack, then 128-bit security would require a 2MB-sized key, Considering the GNFS already does factoring in time polynomial in that, we're really not that far away.
The original 4004 (Intel's first CPU) was little endian, so no, it wasn't for backwards compatibility with the 8088. According to here Intel got the idea from the Datapoint 2200, which needed it to do address calculations in its shift-register memory. (Line memory, ouch!)
Endianness matters for bit field address calculations. One operation for little endian, vs three for big endian. These operations are done a lot more than most people realize, since it is normally handled by the compiler and library routines, so the effect is often under-estimated.
Big endian has advantages for numerical string manipulation and real-time address mask calculations. The first is often over-estimated, since user interfaces have to handle it. The second only applies for address masking done in hardware and only if high order bits can be processed while low order bits are still on the wire. Software address calculations generally don't care about endianness, since they use whole word operations. There were also some advantages in the early days, when computers were designed entirely by hand, since big endian is easier for English speaking humans to parse.
It is in many ways like 'signed' integers on modern hardware are actually two's compliment. Actual sign+magnitude values are only found in IEEE compatible floating point units.