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