Forgot your password?
typodupeerror
Encryption

Math Advance Suggest RSA Encryption Could Fall Within 5 Years 282

Posted by Soulskill
from the which-will-be-about-the-time-encryption-becomes-useless-anyway dept.
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."
This discussion has been archived. No new comments can be posted.

Math Advance Suggest RSA Encryption Could Fall Within 5 Years

Comments Filter:
  • by BenSchuarmer (922752) on Tuesday August 06, 2013 @05:18PM (#44491131)
    otherwise hackers will use it to mess up the internets.
  • Elliptical Curve (Score:2, Informative)

    by Anonymous Coward

    http://en.wikipedia.org/wiki/Elliptic_curve_cryptography

  • by Anonymous Coward on Tuesday August 06, 2013 @05:23PM (#44491181)

    https://www.schneier.com/essay-198.html

    • by EvanED (569694) <evaned&gmail,com> on Tuesday August 06, 2013 @05:46PM (#44491423)

      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.)

    • by kasperd (592156)
      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
  • OpenSSL? (Score:5, Interesting)

    by pope1 (40057) on Tuesday August 06, 2013 @05:24PM (#44491203) Homepage

    OpenSSL [openssl.org] has had a good working implementation of ECDSA/ECDH for years: http://wiki.openssl.org/index.php/Elliptic_Curve_Cryptography [openssl.org]

    What exactly does BlackBerry have chained down that we don't have an open solution for?

    • Re: (Score:2, Informative)

      by Anonymous Coward

      They claim patents on various ECDSA/ECDH implementations. There really isn't more to say, we here at slashdot know how evil patents are. :)

      To avoid the patent issues its best to implement as specified in: http://tools.ietf.org/html/rfc6090

      Abstract

      This note describes the fundamental algorithms of Elliptic Curve
      Cryptography (ECC) as they were defined in some seminal references
      from 1994 and earlier. These descriptions may be useful for

      • I.E. If you implement these RFC 6090 "Pre-patent" methods, the first obvious thing you would think of to make it better is point compression. That is one of the obvious implementation things that were patented.

        • Re: (Score:2, Interesting)

          by Anonymous Coward

          Except thats not true. The patent often claimed to cover point compression specifies fields of characteristic 2 (not the large prime fields most implementations actually use; as the certicom patents cover a ton of characteristic 2 field stuff).

          It's also the case the point compression was described in publication at least as far back as 1986, making it too old to be patentable in general:

          Quoting DJB:

          Miller in 1986, in the paper that introduced elliptic-curve cryptography, suggested compressing a public key

    • 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...
      • by raymorris (2726007) on Tuesday August 06, 2013 @08:48PM (#44493007)
        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.
        • by gronofer (838299)
          So presumably they have a patent on ECC on some wacky new hardware device, and you are fine if you are just running it on a general purpose computer?
          • 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 i
  • by Anonymous Coward on Tuesday August 06, 2013 @05:25PM (#44491207)

    Hmm ... considering Blackberry/RIM's precarious hold on existence, I have a hunch those patents will be in other hands very soon.

  • by JoeyRox (2711699) on Tuesday August 06, 2013 @05:26PM (#44491225)
    Article is dated 8/2 (Friday), yesterday would be the first tradable day on the information.
  • 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.

  • You can't patent math.

  • by UnknowingFool (672806) on Tuesday August 06, 2013 @05:53PM (#44491505)
    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.
  • Patents have now become an issue of national security.

    • by amorsen (7485)

      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.

  • by Panaflex (13191) <convivialdingo&yahoo,com> on Tuesday August 06, 2013 @06:39PM (#44492005)

    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.

    • by Panaflex (13191)

      Okay, here's the slides from a talk:
      https://www.cryptolux.org/mediawiki-esc2013/images/c/cd/Joux-EM-multiuser-ESC2013.pdf [cryptolux.org]

      And a paper which is related:
      http://eprint.iacr.org/2013/095.pdf [iacr.org]

      Basically, from my first read, this is just a better sieve, a system which should find smooth numbers faster by choosing better starting points and using faster tests. I wouldn't call it a general break in RSA, and while it might certainly be a better sieve than GNFS, it's no silver bullet either. I can't imagine anyone bre

  • by mstefanro (1965558) on Tuesday August 06, 2013 @06:50PM (#44492149)

    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 [arxiv.org]) 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.

  • Please remember - when new tools give cryptographers the ability to exploit weaknesses in existing cryptosystems it also gives them the ability to device cryptosystems immune to those exploits.

    (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...

  • 1 + 1 = 3
    This is a correct answer. Do you know why?
  • by mendax (114116) on Tuesday August 06, 2013 @08:35PM (#44492935)

    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....

  • 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.

  • By its very nature, encryption is a never-ending arms race.

  • 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.

It is not for me to attempt to fathom the inscrutable workings of Providence. -- The Earl of Birkenhead

Working...