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

errrrr NFS?

[karrde]

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.

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

hackers...

[coronaride]

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

Quotes from the paper

[Beryllium Sphere(tm)]

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

Re:Quotes from the paper

[Telastyn]

Furthermore the paper goes on to say that the major improvements were done to the matrix half of the procedure rather than the collection side. "Half" probably isn't the most accurate term, as the collection side takes far longer (months) than the matrix side (days).

Even if you remove the matrix side, it takes a VERY long time to find all of the relations needed to make the matrix in order to solve it.

The /. story quotes the wrong part of the paper

[mridley]

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)

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

It's 1.17, not 3.01... your keys less compromised

[russotto]

The most important part of the abstract is the finding that "for a given cost, the new method can factor integers that are 1.17 times larger (rather than 3.01)." This means that even if the new factoring method scales to "small" numbers of bits like 1024, a 1024 bit key is only reduced to the security of an 875 bit key, not a 342 bit key. This is a big difference! It goes from "uh oh, better revoke all my keys right now" to "Hmm, might want to think about increasing them in the future".

Cliff notes version

[Ashurbanipal]

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.

Re:Cliff notes version

[MAXOMENOS]

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

This post should be modded +4 Understated.

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.

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:Off the shelf hardware??

[Eran Tromer]

I am a coauthor of the paper. Indeed, there are many rough estimates in the paper: the theoretical analysis (and indeed, the NFS method itself) relies on some unproven conjectures and asymptotical analysis. Also, the practical cost estimates rely on technological and ecnomical considerations which are rapidly changing. None the less, we believe the assumptions and their conclusions are quite sound when used as order-of-magnitude estimates.

As for the two technical points you mentioned:

> > The bandwidth of the fastest PC memory is 3.2GB/sec
> The GX specs specifically state that they support 4.2 GB per second.

Indeed, but both PC3200 (DDR400) and dual PC800 (RDRAM) have a bandwidth of 3.2GB/sec.

> I checked pricewatch and found at least 6ns for pretty cheap

These "6ns" parts do not have a 6ns random-access latency. For instance, check these figures.

Re:Off the shelf hardware??

[0x0d0a]

Oh, come on. This is crypto work. No one is going to care about being off by a factor of .3 when they're talking about factoring time. A factor of 10 probably wouldn't bother them that much.

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