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.

Comments

Factor?

[brilinux]

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

Re:Factor?

[jgc7]

Inerestingly enough, there is no proof that encryption is even possible. Presently we do not know of any methods to factor a number in polynomial time while we can create primes in polynomial time, but an algorithm may exist that can factor primes in polynomial time. If one is discovered, encryption as we know it today will be impossible... even with your quantum computer. In fact, a solution to the P NP problem comes with a $1,000,000 prize.

Processor time?

[panth0r]

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.

Re:Processor time?

[Thundersnatch]

Assuming 50W per Opteron and 5 months continuous operation, I calculate they spent at least US$1400 on electricity alone (based on Chicago electric prices, I'm not sure if it's more orless over there).

And that figure ignores the electriciy used by the other components in the computers (be they servers, workstations, or whatever).

Still, the $30K in prize money goes a long way toward paying the electric bill.

Re:Processor time?

[Anonymous Coward]

>Aren't some subsets of SAT (like 2-SAT) in P?
2-SAT is in P (and apparently NL which I have not studied), but 3-SAT is NP complete.

>How small of a subset is factorization of SAT?
You can easily construct a multiplcation circuit and then ask whether the given "inputs" multiply out to a predefined value, except you have to include overflow restrictions to prevent aliasing so you don't get the wrong result like: 5 * 9 = 13 (mod 16 or 32). Anyway, this method allows you to transform any factorization problem into a SAT problem; so factorization is a subset of SAT. How small? Well that's a bit harder to quantify.

Remember that simply going from 2-SAT to 3-SAT crosses the line from P (a small subset) to NP complete (the identity subset). I consider it a small subset because it's a well-defined transformation that's at worst N^2 in the size of the input, which is sqrt in the size of the target value. That makes it a linear transformation in the size of the target, but there's a lot information "lost" in the reduction so I believe it to be irreversible and therefore a small subset. Technically you could prove me wrong by showing a transformation from some NP complete problem onto factorization, which would mean factorization is NP complete. However, for all we know, there may be some way to prove that factorization is in P (this would be a natural consequence if someone proved P = NP).

For another example of a subset of SAT that's solvable in P, replace the multiplier above with an adder or remove the overflow/aliasing restriction on the multiplier. In the case of addition, the resulting problem is related to the subset-sum problem, which is NP complete; however, it differs from subset-sum in that it only considers one addition instead of the additions of an exponential number of subsets.

>If RSA-1024 is only 8000x as complex as RSA-640...
I incorrectly corrected myself in a followup post before I noticed your reply, so I'll correct it here. GNFS grows from 2^73 to 2^90 to 2^120 as it goes from 640 to 1024 to 2048 bits. That's a growth of 128k followed by a growth of 1 billion (2^90/2^73 = 2^17, and 2^120/2^90 = 2^30). I stand by my belief in a lower bound for GI that predicts minimum growths of 2^13 and 2^21 for those same numbers.

--- Switching gears ---

>computer power has historically grown exponentially
Transistor density has doubled approximately every 18 months. As the die sizes have fallen, clock rates have gone up; however, we've reached a plateu as I'm sure you've noticed. Clock speeds have not increased much in the past few years, but we have seen a rise in hyperthreading/multi cores. I personally do not expect to see more than a couple of doublings over the next decade, but I'll assume that we will see doublings every 18 months for the remaining calculations.

To achieve an increase of 2^33, we would need to see 33 doublings, or 50 years worth of steady performance growth. (* As a bonus exercise, go check my fact that we only need about 10 doublings = 15 years to get from current supercomputers to the ability to simulate a human nervous system.)

Using GNFS, that would require at least 47 doublings; 47 * 1.5 = 70 years before we would have the technology to break RSA-2048 as quickly as they broke RSA-640. And that's just one key, and that's assuming everything goes right.

But wait... I'm just getting started. Let's talk memory requirements. I don't know about the GNFS memory requirements, but I believe that my theoretical performance lower bound for GI is also the lower bound for memory usage. If that's true, then assuming you could get away with storing only one bit per atom, the largest power-of-2 RSA factoring problem we could solve with all the resources of the planet would be RSA-4096. (RSA-8192 would require several times the 2^163 atoms in the planet, and RSA-65536 would a good chunk of the 2^264 atoms in the known universe.) As for "likely," I'd estimate a top end just past RSA-1024 but well shy of RSA-2048, which would literally require megatons of RAM if my calculations are correct.

Again, I've presented a lot of IFs and speculation from an AC, but that's the best I've got.

Re:Hmmm.

[LnxAddct]

While I think your remark was a joke about them breaking into RSA's computers, this is still worth mentioning. Noone in the entire world knows or has ever known the factors of the remaining numbers. Read this for more info.
Regards,
Steve

Re:Hmmm.

[panth0r]

Let's seriously think about this, the Germans, if anything, lost money on this excursion, they upped an bought 80 opteron processors with the hardware required to run them and the RAM needed, they pumped electricity into the building where this heavy processing was taking place, and they paid the people running the computers... all for $30,000 - fees, customs, taxes and such... if anything, they probably lost a substantial sum.

I'll wait for RSA-2048

[Myria]

I won't be interested until they do RSA-2048. Then we could factor the Xbox private key and do whatever we want.

Melissa

Re:Irrelevant

[cpeikert]

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.

Re:Factored... Big Deal

[photon317]

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.

Re:Factored... Big Deal

[photon317]

Scratch that, I read some more about the GNFS they're using, and while I don't claim to understand completely, I don't think it would take them 2^32 longer to reach RSA-704 - it may well be in reach in the relatively near future.

Recommended key sizes

[atomm1024]

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/

Re:Dual Cores

[et764]

Reminds me of this paper where they argued that large computations can actually be completed faster by slacking off for a few months and then buying a faster computer.

Not the largest RSA number factored to date

[clap_hands]

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

Spending tax dollars vs common sense

[appro]

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.

Cost of "one day breaker" system

[anfi]

Has anyone publish (theoretical) costs of system capable to break given RSA lenght in one day based on the known systems?

Re:Cost of "one day breaker" system

[MooseTick]

Here you go. 80 PCs at $1000/PC churning for 5 months to crack a 640 bit #.

Assuming it was truly distributive, then 12000 PCs could crack it in a day. Assume each use 500Watts, then each has a power cost of about $.25/day if 1kW/h is a dime. That totals to $12 million for the PCs and another $3000 for power. The power cost is negligable but the infrastructure to distribute that power likely wouldn't be. We'll pretend that we already have a nice building with a 13000 socket power strip for our PCs. Let's say it cost $1 million to be easy.

That would total $13 million to crack a 640 bit number in a day. Since each added bit doubles the complexity, then to solve for numbers with bits > 640 we could say N= # of bits - 640. From there the cost to crack a number would be $13M * 2^N.

If you think about it, this is well within the reach of most corporations and could likely be achieved by someone using a virus to steal computing power. The virus could break up the problem and whenever someone hit on the answer it could phone home with it and they could collect the $20k!

Re:what about the xbox rsa-2048

[Vo0k]

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.

Re:How does this compare to RC5-64?

[swillden]

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

Sorry, but isn't this just a waste of electricity?

[Dr. Spork]

I want it to be clear that I support science and the use of brute computation in science, but this is not anything of the sort. After this five-month exercise which cost thousands of dollars of wasted electricity (all those processors could have been idling instead) and the associated increase in global polution, what have we learned? Absolutely nothing. We already knew roughly how long it would take to factor this, it's a quick calculation. But then going through the motions of actually factoring the number is absolutely pointless, and I'd even say irresponsible.

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.

not the point

[elgatozorbas]

This is completely correct. Any cryptologist could have predicted this give or take a certain margin. Even more: if I were them, I would not have started without an initial estimate.

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.