Slashdot Mirror

← Back to Stories (view on slashdot.org)

Bernstein's NFS analyzed by Lenstra and Shamir

Posted by CmdrTaco on from the my-c0de-is-s3kr37 dept.

kousik writes "The analysis of Bernstein's NFS by Arjen Lenstra, Adi Shamir, Jim Tomlinson, Eran Tromer has been put up on cryptosavvy. Seems interesting it comes from Lenstra and Shamir. Lenstra lead the 1994 factorisation of RSA 129. From the abstract: ... We also propose an improved circuit design based on a new mesh routing algorithm, and show that for factorization of 1024-bit integers the matrix step can, under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars..."

8 of 168 comments (clear)

  1. errrrr NFS? by karrde · · Score: 5, Informative

    Let's just ignore the fact that we're all a bunch of geeks, and the acronymn NFS usually equal 'Network File System'. Not 'Number Field Sieve' as it does in this case. Would it have been so dificult to say that in the post?? The first link doesn't even give you that information.

  2. hackers... by coronaride · · Score: 5, Funny

    still waiting for that level of encryption shown in everyones favorite hacking movie that displays the giant skull and crossbones in a cheezy GUI to let you know that you don't have access..

    --
    Those who can, do. Those who can't, go into business for themselves.
  3. Quotes from the paper by Beryllium+Sphere(tm) · · Score: 5, Interesting

    "In particular, we show that 1024-bit RSA keys are as secure as many
    believed them to be."

    "We thus
    conclude that the practical security of RSA for commonly used modulus
    sizes is not significantly affected"

    Sounds like it only speeds up one step of the factoring process, which is important to keep an eye on but not grounds for alarm.

  4. The /. story quotes the wrong part of the paper by mridley · · Score: 5, Interesting

    Well the /. story exerpt is kind of alarmist but I think the more relevant quote from the paper is "However, the theoretical analysis shows that the cost of the relation collection step cannot be significantly reduced, regardless of the cost of the matrix step. We thus conclude that the practical security of RSA for commonly used modulus sizes is not significantly affected..." (typos probably mine)

  5. Cliff notes version by Ashurbanipal · · Score: 5, Interesting

    Basically, Dan Bernstein (who has written useable but controversial alternatives to BIND and SENDMAIL) figured out a new method for breaking RSA encryption based on custom hardware. The fellows mentioned in the headline, who are also legit crypto guys, have analysed Dr. Bernstein's work and make the following observations:

    1) it's not quite as fast as Bernstein estimated (about half as fast for cliff notes purposes)
    2) the hardware could be affordable (others have claimed costs that are only feasible for governments)
    3) you don't have to revoke all your RSA keys because there are steps that precede the application of the Berstein method that still take absurd amounts of time and horsepower.

    Oh, yeah, and it has nothing to do with Sun's NFS (Network File System, a lame and usually insecure way to share files).

    Bernstein will no doubt reply. He isn't a shy guy from my experience.

    1. Re:Cliff notes version by MAXOMENOS · · Score: 5, Funny
      Bernstein will no doubt reply. He isn't a shy guy from my experience.

      This post should be modded +4 Understated.

      --
      Finding God in a Dog
    2. Re:Cliff notes version by btellier · · Score: 5, Insightful

      >is qmail controversial ?

      Well I can only speak from a security standpoint, not for functionality, though I've heard that it has nearly all the same features as sendmail and is faster. However, I did a free-time security audit of Qmail to get an idea of how secure DJB's work was. I can say that, bar none, this guy is the best secure coder I've seen to date. Probably the best way to see this is in the fact that he uses all of his own routines to do memory management. In these routines his bounds checking is complete and he is extremely careful about signed/unsigned conversion bugs. Quite impressive.

      Granted the guy is known for being a prick when people question his work (this is known as De Raadt Syndrome), such as this response to someone who supposedly found a hole in his mailing list software:

      ----
      Here we go again: This advisory is fraudulent. My ezmlm 0.53 package
      does not include anything called ezmlm-cgi.

      Perhaps someone else's ezmlm-cgi program has a problem. But ezmlm-cgi
      isn't part of ezmlm. I didn't write it. I haven't reviewed it. I don't
      distribute it. I don't use it. I am not responsible for its bugs.

      vort-fu was aware of these facts before he sent his advisory to bugtraq.
      Why did he continue? Can this be adequately explained by stupidity?
      ---

      The problem is that while he may be abrasive, he's always right. Bottom line: if you want secure software, stick with DJB.

  6. Re:Is factoring hard by Jeremiah+Blatz · · Score: 5, Insightful
    I don't know. If somebody knows it isn't, they aren't saying.

    The problem is this, there are certain mathematical problems that are known to be Hard. Traveling Salesman, Knapsack, etc. There are no shortcuts to solving these problems. Many mathematical problems can be proven to be in this class of problems. Nobody has, to date, publicly, shown that factoring numbers is Hard, and nobody has shown that it isn't.

    Of course, nobody has proven the security any of the symmetric cryptosystems (with the exception of one-time pads), so any practical system is already victim to this uncertainty.