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..."
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.
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.
There are more efficient, deterministic ways of factorization than NFS. Additionally, in the not too distant future, off-the-shelf quantum computers will be able to make short work of 1024+.
"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.
All the mathematical theorems used in public key cryptography have a fine print clause saying:
"Assuming factoring/[other oroblem] is hard"
this makes you think maybe it isn't
As of Postgres v6.2, time travel is no longer supported.
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)
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".
it's guys like these that drive the security bigwigs at Los Alamos and Sandia crazy. I guess it's keeps them employed though, because once they break it, they'll have to build a stonger algorithm and try to break that one.
:P.
Or they could just stop letting people work from home and stop letting their kids play MUDs on their secure terminal
Linux is dead.
LU
Well, I believe that mesh routing might just give us all the pluses without most or all of the minuses. First of all, it involves routing, which if you've paid attention to the formation of the Internet you'll quickly realize is a design that will lead to redundancy and reliability. More importantly, it is a mesh, which means that one end of the key is not necessarily tied to the other end. This should cut off many of the attacks that would have a chance of success on elliptic curves by way of its nature. Meshing also implies redundancy... there may be some size and speed tradeoffs here, but you can be certain you'll get your data back out of the cryptopot.
Bruce Schneier, a luminary in the field of cryptography and author of the book Applied Cryptography, has a web site here.
Try not. Do or do not, there is no try.
-- Dr. Spock, stardate 2822-3.
They clearly state in the paper that "1024-bit RSA keys are as secure as many believed them to be."
As they clearly state in the paper, "the security of RSA relies exclusively on the hardness of the relation collection step of the number field sieve." - The speedup that Bernstein proposed just makes the stuff surrounding that step a bit more efficient.
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.
So you only want to educate the people that are already educated?
Even if I had been aware of a Number Field Seive, I probably still would wonder, at first, about the file system.
Not to mention that there are obviously a lot of young, impressionable, children on this site that might like to learn something new, and skip right over an article about a stupid old file system.
No, you are the unreasonable one. The parent makes a good point.
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.
Lasers Controlled Games!
to total internet domination.
Umm, no. We're talking powers of two here. 1024 bits is a number 2 times bigger than 1023 bits. Not 512 bits.
Even if it is 3.01 times larger, that's still an effective strength of at least 1022 bits.
(For what it's worth, I've only read the abstract.)
Who the heck modded this up? "One end of the key is not necessarily tied to the other end?" Hilarious.
-- Brian
The most rabid believers in American Exceptionalism are the exact same people whose policies are destroying it.
PLUS ONE FUNNY!
Wow, what karma whore. You're making more shit up than a battalion of marines with dysentary.
You've obviously cracked the cover of Applied Cryptography, but did you get past the first chapter? :)
ROFL
Need For Speed !!
The GX specs specifically state that they support 4.2 GB per second. They also state that memory latency is about 40ns. I checked pricewatch and found at least 6ns for pretty cheap. There are to many areas where it says "at least", "probably" or "about" for calculations regarding how much time it takes. They might be right but their "proof" consists of restating mathmatics rules and estimations. They probably should have spent more time on actual calculations and proofs
"Freedom of speech has always been the abstract red-headed stepchild of the Constitution"
-Suck
Already taken into account -- it's 1.17 times (or 3.01 times) the LENGTH of the integer, not its value. If it had been 3.01, it would have been a big deal.
you know that is a typical reply to anyone accidentally mentioning "factoring primes" but seems now even that isn't required.
ie. more like +1 Limbo.
"...under an optimistic assumption about the matrix size, be completed within a day by a device that costs a few thousand dollars."
Wow, we can make The Matrix in under a day for a couple grand? Better start looking in the paper for real estate in Zion...
To make a pun demonstrates the highest understanding of a language
HA hah ahah hahaa
aaaaaaaaaa aaaaaaaaaaaaaaaab bo bo bo!
So, while for us an algorithm which takes 1024 steps when fed with the number 1024 and 4096 steps when fed with the number 4096 would probably be considered O(n), they would consider that algorithm O(2^n) because it takes 1024 steps when run with an input of bit-length 10 and 4096 steps when run on input of bit-length 12.
You can usually tell from context which definition of time and space someone is using, but sometimes it gets confusing.
Good to know - thanks...
:)
Though the statement, "You can usually tell from context which definition of time and space someone is using" just has to make me chuckle.
> but does it look pretty?
I'd say it does:
a color-coded simulation of the mesh routing algorithm (16MB)
And you're getting Karma for your one-line post being labelled +1 Funny. Who's the Karma Whore now, huh? :)
No... wait... That's Steve Jobs' favorite hacking movie... my bad.
/^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$/i
Hi, I'm Uncle Sam. Won't you be my neighbor?
/^[A-Z0-9._%+-]+@[A-Z0-9.-]+\.[A-Z]{2,4}$/i
I haven't been able to find anything anywhere.
I have some factorization ideas I'd like to test without reinventing the wheel.
The message on the other side of this sig is false.
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)
Not specifically about DJB, but since you refer NFS and security... I had to responsability in desigining a (small) Unix network, including authentification and shared filesystems. NFS main strenght is that it's bloody simple to use (in Solaris the 'share' command is all that it takes, and the other Unices have more or less similar mechanisms), but security-wise it's a no-no.
I then discovered AFS; it was exactly what I needed. Kerberos authentication builtin, support for every OS, very solid and comes with several interesting concepts of it's own. All in all AFS has proven to be a secure alternative to NFS (AFS can also scale incredibly well).
Just my 2 euro cents,
fsmunoz
Someone may prove the NP-complete problems are O(n^100), making them P, but not very easy.
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
Bill Stewart
New Fast-Compression-only CPR http://preview.tinyurl.com/dy575ks
the NSA is usually 5 ~ 8 years ahead in technology with regards to this stuff. Hmm...
Gnu MP for mult-precission numbers. They use the fastest known algorithms and hand-optimized asm on most platforms. I prefer to do crypto in Java and use the BigInteger class 'cause I'm lazy.
FYI, Sun's BigInteger.isProbablePrime(int) function is broken... don't use it. I was rather embarassed when a collegue and I emailed some people about a possible bug in the Secure Remote Password protocol, only to discover the problem was a known bug in the JVM... which Sun refuses to fix. I don't know why they won't fix it. My personal implementation of the Miller-Rabin primality test runs faster and correctly identifies the SRP modulus as probably prime. (Look in Applied Cryptography by Schneier for how to code it up.)
Copyright Violation:"theft, piracy"::Anti-Trust Violation:"thermonuclear price terrorism"<-Overly dramatic language.
However, it was certainly pretty damn fast, and I didn't come across any bugs.
Any sufficiently advanced technology is indistinguishable from a rigged demo
--Andy Finkel (J. Klass?)
Based on this, if I need 20 SSL certificates, would it be cheaper for me to register each of them with VeriSign for a year or to build a device to factor the VeriSign public key and sign them myself?
Hum.. isn't an Apple itself alien hardware ?
Another post replying to yours said "samba". I'm sure Tridge will forgive me for pointing out that Samba mimics Microsoft's unbelievably kludgy implementation of IBM's NetBIOS protocol - the kludges being there to compensate for the fact that IBM designed NetBIOS for networks of 25 machines or less. Samba is a wonderful way to interconnect VMS and *nix machines with Microsoft clients, but other than that it's an abortion. Do not use it if you don't have to!
Another poster pointed out the reason for the "Usually" in my description of "usually insecure". If all your *nix boxes run the same version of the same vendor's latest implementation of NFS, it can be secured. In a true heterogenous environment, though, I have never seen anything but pain and suffering result from trying to implement secure NFS. And incidentally, NFS is inherently subject to denial of service attacks (so is NIS/YP) so you certainly can't depend on it if there are any unsecured hosts elsewhere on the network.
Once you decide to sacrifice "nice" and go for "secure", or vice-versa, your options get broader. Look into Coda, Andrew, u9fs, or Styx, for example.