Bernstein's NFS analyzed by Lenstra and Shamir

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

Comments

Whee! Slashdot FUD

[Jeremiah Blatz]

Also from the abstract:

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

And:

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 thi=us conclude that the practical security of RSA for commonly used modulus sizes is not significantly affected by [1].

If i recall correctly, the original device was impractical, as the speed increases gained by the parallelism were negated by the cost of collection/sifting through the results. Apparently, this weakness still holds.

Yes it does!

[John Harrison]

The first link doesn't even give you that information.

From the pdf:

Introduction

In [1], a new circuit-based approach is proposed for one of the steps of the number field sieve (NFS) integer factorization method, namely finding a linear relation in a large but sparse matrix.

This is on the first page of the linked pdf.

However, I agreed that it should have been spelled out in the post.

Re:Is factoring hard

[Jeremiah Blatz]

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.

Re:errrrr NFS?

[Enry]

Given that DJB already has implementations of DNS and SMTP around that are heavily focused on security, it wouldn't suprise me if he went into looking at securing NFS (the file system).

Re:Still behind the times

[wirelessbuzzers]

There are more efficient, deterministic ways of factorization than NFS.

True, but not by much, and if the jump was as big as claimed, not for long. But these guys revised it down considerably.

Additionally, in the not too distant future, off-the-shelf quantum computers will be able to make short work of 1024+.

Physicists aren't even sure if quantum computers are practical... sure Shor's algo made short work of factoring 15, but what if it turns out that engineering the rather arbitrary entanglements required for Shor's is NP-complete? Then what? That possibility hasn't been ruled out yet, and making those entanglements is already pretty hard...

Re:Is factoring hard

[Jeremiah Blatz]

Factoring, AFAIK, is not NP-Complete. Traveling salesman is. Here's a list of known NP-Complete problems, if you're interested.

Re:Cliff notes version

[btellier]

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

Re:The /. story quotes the wrong part of the paper

[Sircus]

So now that the matrix step has been made a whole 1.17 times faster (or even 3.01 times faster, if you want to believe Bernstein's numbers), you suddenly believe that factoring is within the reach of the common sysadmin?

The Slashdot quote also fails to mention that the device would cost $5000 only for "large quantities". The initial cost to get to the stage of being able to produce that circuit is over $1 million. Granted, they also say that the previous initial cost using off-the-shelf hardware was $62 million, but neither are exactly in your average sysadmin's price range. Bearing in mind that these prices *only* cover the matrix step, the authors are right to conclude that 1024-bit keys are just as safe as everyone thought they were.

If your enemies have a sufficiently large budget to build this kind of thing, they'd almost certainly find it easier just to bribe someone with access to the information to reveal it, to physically attack some unencrypted version of the information, or to retrieve the keys (by, for example, bugging your keyboard).

Re:Is factoring hard

[kma]

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.

We stand on even sketchier ground than this. Travelling Salesman, Knapsack, and the "etc." referred to above are "NP-complete" problems-- they are the hardest problems in NP, the class of problems whose solutions only expand their inputs polynomially. (For an example of a problem outside of NP: given a number in base 2, represent it in base 1 (e.g., in tick marks. The output of this problem is O(2^n) for input of length n.)

Factoring is in NP; however, we don't know whether it is NP-complete.

How "hard" are these NP-complete problems? Nobody knows. Most "serious" folks hypothesize that polynomial-time solutions to these problems aren't possible on conventional computers (essentially, because lots of smart people have worked on it and haven't found one). However, nobody has proven this yet; and because of the equivalency of NP-complete problems, a solution to one can be transformed mechanically into solutions for all NP-complete problems.

So, to summarize: we don't know how hard the NP-complete problems are; and factoring can only be as hard as the NP-complete problems (and just might be easier). Treating NP-complete problems as "hard" is a reasonable working assumption, but it is just that.

Still distant vaporware

[billstewart]

Quantum computers aren't deterministic - the techniques that have been discussed have non-trivial chances of getting incorrect answers. With problems like factorization, it's fast and trivial to determine whether an answer was correct or incorrect, but not obvious what to do about an incorrect one. There may be deterministic algorithms a bit faster than NFS (it's got lots of relatives), but they're mostly in the same general range.

The interesting thing about quantum computing is that it's the one technology that, if it's actually possible to develop usable machines with it, might offer the possibility of getting beyond the exponential-difficulty traps in factoring and other current techniques of public-key math. It's not clear that it will work, but it's the only thing so far that doesn't hit the "well, if you build a keycracking computer the size of the planet and run it for the remaining age of the solar system, I can add three more key bits and make you take over some more planets" wall.

They're not off the shelf, and won't be any time soon. The biggest quantum computer made so far was able to factor 15 into 5 x 3. The number of bits of answer you can get out of a quantum computer depends on the precision to which you can measure its output - does this hit Heisenberg limits? 10**47 is only ~140 bits. Or do you hit practical limits first? Or are there ways to break up the answer into many parts each of which gets you a few bits of precision? (The latter case is the only way to get it to work...)

What if quantum crypto does work? Maybe it'll crack conventional RSA and Diffie-Hellman, but that doesn't mean it transfers to Elliptic-Curve cracking, so we may luck out. Alternatively, it's back to conventional techniques like Kerberos and other symmetric-based Key Distribution Center systems.

But basically, you're trolling :-)