Slashdot Mirror
RSA-640 Factored
gslin writes to tell us MathWorld News is reporting that RSA-640 has been factored. F. Bahr, M. Boehm, J. Franke, and T. Kleinjung, memebers of the German Federal Agency for Information Technology Security (BSI) announced they had cracked the 193-digit number last Friday using the General Number Field Sieve. The team purportedly used 80 opteron CPUs and 5 months to achieve victory.
640=2*2*2*2*2*2*2*5.
What do I win?
I wish had nothing better to do for five moths than factor numbers...geez...who needs the Internet when there are numbers to factor. :)
I hardly know 'er...
Seriously, this is interesting stuff. Of course, everytime we come up with a new security mechanism, computing power will overcome it. Fortunately, not everyone can do this sort of thing, and it takes time. But, as a mathematician, it is interesting to see both the methods used to crack this sort of thing, and, at least to me, more interestingly, the methods that are used to come up with new encryption systems. I cannot wait to see what will occur in several years, and even bigger prime numbers are known and usable...
The answer was 42!
Now what was the question
The German Federal Government is short on cash, I know, but resorting to funding the "Agency for Information Technology Security" by winning RSA contests? Besides, if they're so up on IT security, why didn't they just cheat by logging onto RSA's computers?
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
I think that's really cool and would wish them the best of luck, but I would like to know how many processor hours that took them to crack it? Also, with that chunky $30,000 reward, did they turn any profit (after taxes, fees, and such). Second one's a joke, calm down. But it'd be cool to know the processor time it took.
I like suggestions, but I don't like contributing towards them.
My TI-82 was just about to solve that one!
Well, he certainly failed miserably at using less than 640k.
I knew that one of the factors ended in a 1 and the other ended in a 9 or that they both ended in 3. Am I eligible to split the prize?
However what if that team had decrypted a banks RSA key. Sure it may have taken 5 months and the bank may well have changed keys since. But what if they captured all the packets sent/recieved using the cracked key. I guarentee there would be a bit of useful information in them. I know I don't change account numbers / credit card numbers every 5 months.
From a security point of view, "less than five seconds on modern hardware" is absolutely unnecessary. After a transmission has been intercepted, and we work under the assumption that essentially all of them are these days, that transmission has to remain secure potentially for a very, very long time (sure, an encrypted radio communication might have no operational significance in two hours -- an encrypted dossier of a field agent had better stay secure until he's dead, and an encrypted report on security breaches in US nuclear command&control protocols better stay unbroken for the better part of the next century). And what takes a beowulf cluster of supercomputers 5 months to do today will be possible to crack on a botneck in less than a week by 2010, I guarantee you (I write distributed applications for a living and worked with a three-letter agency which was rather miffed that a competing TLA had the existence of their own internal distributed cracker leaked to the press back in 2002 or so). A couple years after that it will be a few minutes on dedicated hardware and a few years after that a desktop machine will smash it as a matter of course. Events like this are warning flares to people with serious security needs that you need to start transitioning to harder codes or longer key lengths.
Help poke pirates in the eyepatch, arr.
should be enough for anyone."
And will not be, unless P=NP, or we use some form of new computers.
Factoring is almost certainly not NP-hard. It could very well be that P != NP, and yet factoring is easy.
Oh wait. No, that wouldn't have worked. Nevermind.
I wonder how long it would have taken 1.5 million zombie PCs.
To a politician, one email equals one voter.
I won't be interested until they do RSA-2048. Then we could factor the Xbox private key and do whatever we want.
Melissa
"Screw Sun, cross-platform will never work. Let's move on and steal the Java language." - Visual J++ Product Manager
Actually, the next one has only 212 digits...
Telltale Games: Bone, Sam and Max
Why don't we just start using 1.44mb encryption keys. We'd finally have a use for all of these floppies.
I think he was joking.. I hope he was joking
The Wikipedia article on RSA-640 has more info. Check this for easy money ;)
And in only 5 months... how P Q ular.
...now if he could just find his keys.
Stop invalid scientific research. Ask your local scientists to feed their lab rats with a phytoestrogen-free chow.
...many are asking. It's hard to find introductory materials on the NFS, because the number of people who actually understand the algorithm is probably in the hundreds, if not less, and most are worried about research not teaching. For those interested in a high-level view, plus some low-level details, of the (special and general) NFS, you can have a look at the slides for a talk that I gave on exactly this topic at a crypto workshop a couple of months ago. I won't even try to summarize the NFS here, because anything other than a very high level, handwaving, bird's eye view of NFS would take the better part of a page to explain. However, in this thread I can answer specific questions that anyone might have about the talk above.
Now for those with the mathematical maturity to delve into the algorithm, I suggest the book Prime Numbers: A Computational Perspective by R. Crandall and C. Pomerance (link to Amazon.com lifted from Google, no referrals), which is certainly one of the best introductions to the algorithm that I have read.
By the way, if anyone wants to help perform huge factorizations in a distributed computing network, check out the NFSNET, although they mostly apply SNFS on values from the Cunningham tables, no cryptographic targets.
Join the NFSNET. Our prime goal is making little numbers out of big ones. http://www.nfsnet.org/
factor:2 72754572016194882320644051808150455634682967172328 67824379162728380334154710731085019195485290073377 24822783525742386454014691736602477652346609' is too large
`310741824049004372135075003588856793003734602284
isomerica.net | Foonetic IRC
What did I write that is inconsistent with the wikipedia entry?
"Integer factorization is widely suspected to be outside both of those classes [NP-complete and co-NP-complete]."
Just because a problem is outside P, doesn't mean it's NP-hard. Which is exactly what I said to start with.
The 212 digit one (RSA-704) won't be cracked for a long, long time yet using current algorithms like the ones the RSA-640 winners did. 640->704 doesn't sound like much, but it is monumental. I did some back-of-the-envelope math. I'm naively assuming that with a 64-bit gain in key size, the problem complexity is 2^32 harder (since one factor is always under the square root). I'm sure that seive algorithm they're using manages to cut that 2^32 down some, but it's not going to make a practical difference I don't think. If you happen to have ~8000 Opteron cpus at your disposal instead of their 80, and you have the same code they cracked RSA-640 in 5 months with, and it scales up to 8000 cpus just fine, it would take somewhere in the neighborhood of hundreds of millions of years to break RSA-704.
11*43+456^2
I don't know who this general Steve is, but he must be one heck of a math whiz!
from http://www.rsasecurity.com/rsalabs/node.asp?id=208 8
;)
To put this in perspective, it would require about 1.4 billion 500 MHz machines, each with about 170 Gbytes of memory to do the sieving for a 1024-bit number in the same time as RSA-512. While a hacker might try to steal cycles on the Internet by creating a ?Number Field Sieve Worm? it is hard to see how such an attack could find enough machines with enough memory to make such an attack feasible. Further, such an attack would be detected and shut down rather quickly as with the Robert Morris worm. Of course increasing speed will reduce the required number accordingly. It would take a single Cray with 6 Terabytes of memory approximately 70 million days (192,000 years) to solve the matrix. One could reduce this to a mere 19 years with 10000 Crays each with only 600 Mbytes of memory running perfectly in parallel. It is likely that within 10 years common desktop machines will be as fast or faster than a Cray C90 is now. However, it is unlikely in the extreme that 10000 machines running in parallel will be anywhere close to 10000 times as fast as one machine. It would require 10 million such machines running perfectly in parallel to solve the matrix in about the same time as that for RSA-512.
So basically, according to the article from RSA it's not feasable... but still an interesting IDEA. Maybe a worm that installs something like folding@home that would have immediate benefits.
So, an opteron has roughly <8.8 peak GFlops:http://www.amd.com/us-en/Processors/Product Information/0,,30_118_8796_8800~96867,00.html> [amd.com] 60 of them would give around 528 GFlops (theoretical max). Given the fastest super computer in the world, the Blue Gene/L has roughly <183500 GFlops:http://www.top500.org/lists/plists.php?Y=20 05&M=06> [top500.org]. That means the Blue Gene/L can factor it roughly 350 times faster (assuming the algorithm scales linearly) or in roughly 9 hours 45 mins. Scary
Here is a very useful site, listing estimates of how long various algorithms will be secure, and at what key sizes. It covers public- and secret-key algorithms, as well as hashes.
http://www.keylength.com/
Signature.
celeron's
(Score:1, Funny)
by rufuseddy (781982) on Tuesday November 08, @11:35PM (#13985872)
(http://www.oceighty.net/)
blah, if they would of used 80 celeron's they would have cracked it twice as fast.......
Dude, what's wrong with you? You wrote "would of"[sic] and "would have" in the same sentence! To make matters worse, you didn't capitalize a proper noun ("Celeron"), you used an apostrophe before an "s" in a plural twice, you didn't capitalize the first word of a sentence, and you ended your "sentence" with seven periods. Go back to the fifth grade. Do not pass go. Do not collect 200 dollars.
You are completely off track here and made 2 huge mistakes in your comparison:
1) The number RSA-640 has 193 *decimal* digits, but 640 bits (as the number in RSA-640 indicates).
2) You are comparing symetric key suzes (RC5-64 = 64 bit) with assymetric key sizes (RSA-640 640 bit). You can't compare these key sizes directly. Assymetric key sizes are much bigger than symetric key sizes for the same level of security. So you are trying to compare numebrs that simply cannot be compared.
Marcel
For any base b, the sum of the digits (in base b) of a multiple of (b-1) add to a multiple of (b-1). The proof is fairly simple: http://www.pseudorandom.co.uk/2002/maths/divby9/.
For instance, in base 16, 3 * F (45 dec) is 2D, and 2+D=F.
This leads to a (slow) algorithm for primality check. For a given number r, simply (hah!) check all the bases up to about log_b(r) to see if all your base r belong to us.
Raise your children as if you were teaching them to raise your grandchildren, because you are.
I have an even better one. If you convert the number to binary, you'll observe it ends in 1. The only way to get that from two numbers is if they both end in 1. So here's your first digit with 100% certainty!
Please correct me if I got my facts wrong.
A nice result! Interestingly, the same team factored RSA-200 last May, which is 663 bits long (confusingly, there's two series of RSA challenge numbers with different naming conventions) but for which no prize was given for its solution. RSA-640 is shorter, at 640 bits, but carries a US$20,000 prize. It's not entirely clear why the team went for the larger, prizeless number first.
Maybe there's other factors at work here besides prize money? (ROFL etc).
RSA cost study says "It makes no sense for an adversary to spend (say) $10 million breaking a key if recovering the key will only net (say) $10 thousand." Third party payer negates this asumption. Exceptions to the rule are seen in the everyday spending of U.S. taxpayer's millions by low level government employees and politicians alike for their personal gain or amusement, no matter how minor.
Remember that those calculations assume a specific algorithm.
It could always happen that some bright guy finds a more efficient (or more easily distributed) way to attack the problem. This is always a risk with encryption that relies on "computationally hard" problems.
Has anyone publish (theoretical) costs of system capable to break given RSA lenght in one day based on the known systems?
Although it's identical to the issue that the UK police claim they currently have. Which is why they want 90 days to lock citizens up without charge while they 'factor' their hard-drives.
No.
About 1200 years.
Progress in computation of the solution is linear. Moore's law is exponential. By year 3200 the computers will be strong enough to crack it in 6 months.
Anagram("United States of America") == "Dine out, taste a Mac, fries"
So you are trying to compare numebrs that simply cannot be compared.
Well, you can compare them, but you have to factor in the relationship between the complexity of the attack and the keysize in each case. In the case of RC5, brute force search of the keyspace is O(2^n) where n is the size of the key in bits. As a previous post mentions, the GNFS algorithm's complexity is O(e^(1.9229+O(1))*ln(n)^(1/3)*ln(ln(n))^(2/3)), where n is the number to be factored.
So to compare the complexity of these two attacks you just need to see if 2^64 is larger or smaller than e^(1.9229*ln(2^640)^(1/3)*ln(ln(2^640))^(2/3)).
Unless I made a mistake, the complexity of RSA-640 is about 5.5e13, whereas RC5-64 is about 1.8e19, so RC5-64 is approximately 300,000 times harder than RSA-640. I'm not sure that GNFS is as easy to massively parellelize as RC5 searching, though, so in practice RSA-640 may be harder than RC5-64, even though it has lower complexity. Also, big-O complexity ignores constant multipliers, so if each step in the GNFS algorithm is, say, a million times more complex than each RC5 trial encryption, than RSA-640 may actually be three times as hard as RC5.
Okay, so maybe you can't compare them :-)
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
It's like figuring out how many times you'd need to toss a coin before you'd be likely to get 7 heads in a row... and after figuring this out, actually tossing the coin until you get 7 heads. Anybody who actually did that would a moron. It would show nothing... much like these "factor this" challenges.
However, this is not the point. The point is to prove ANYONE (not only cryptanalyst) that it CAN be broken, though it takes some processing, and there is no alternative for doing.