Hacker News Reader

Comment by arange | Hacker News Reader

For us that don't understand, what does this mean? Is RSA less secure now?

It's as secure as it ever was, it just shows how advancing technology means that you can brute force a larger number. RSA is dependent on math problems that take a fairly long time to solve unless you know one of the base factors. What this is saying is that on a ~$5000 computer, it will take a bit over a couple days to factor a 697 bit RSA number. This is more a demonstration as to why you need to continually increase RSA keysizes -- at this point, a 1024 bit number is probably within range of something a three letter agency could factor within reason.

The implication of the parent is that with a ~ $10000 computer you can take a couple of days to factor a 698 bit RSA number. Or $20,000 can factor 699 in a couple of days - $40,000 gets you 700, $80K for 701, $160K 702, $320K 703, $640K 704, $1.28M 705, $2.56M 706, call it $5M 707, $10M 708, $20M 709, $40M 710, $80M 711, $160M 712, $320M 713, $640M 714, call it $1.2B 715, $2.4B 716, $4.8B 717, $9.6B 718, $19.2B 719, $38.4B 720, $76.8B 721, $153.6B 722, call it $300B for 723. We'll stop here because long before reaching this amount you would have realized massive economies of scale such as running entire plants making custom chips. Then again, we're talking about what can be done in a "couple days".

If we extrapolate couple of days, to 4 days we can add +1 bit, 8 days, +2 bits, 16 days +3, 32 +4, 64 +5, 128 +6, 256 +7, 512 (1.4 years) +8, 2.8 yrs +9, 5.6 yrs +10.

By that time again whatever is sitting there is obsolete.

Still, we're up to 733 bits. If we assume some massive growth and large economies of scale it is quite conceivable that $300B gets you a 10,000,000x increase on the bang per buck based on economies of scale alone (23 bits) working with today's technology; or that by waiting, within 5 years breakthrough technology would cause another 1,000,000 fold increase (call it another 20 bits). We are now up to 776 bits. That is just 248 bits away from 1024 bits:

If we make ALL of the above assumptions, and you throw $300B at the problem for 5 years and get to experience 1 million fold better technology and also a ten million fold better price than the commodity demonstration, you can brute force

1 / 452312848583266388373324160190187140051835877600158453279131187530910662656th of the keyspace.

Thus I would say that the demonstration is NO threat of "advancing technology", on the basis provided.

RSA doesn't scale the same way as a symmetric encryption algorithm, though. It took a rather heavy duty cluster for its day months to crack RSA-512 ( http://web.archive.org/web/20070621021111/http://rsa.com/rsa... ). NIST itself states that RSA-1024 should no longer be considered secure ( https://blogs.rsa.com/rsa-768-factored/ press release regarding RSA-768 being factored, because NIST's pages are part of the shutdown ). While your numbers are true for a traditional crypto algorithm, factorial based problems don't scale the same way.

Some time ago Eran Tromer gave an estimate of single-digit millions of dollars for a device that could factor a 1024 bit key in a year. I can't quite tell what you're suggesting about the useful lifespan of a 1024 bit key, but I feel like Tromer's opinion represents a growing consensus.

You might also think in terms of the security level that a 1024, 2048, 4096 &c key gets you. It isn't 1024 bits for a 1024 bit RSA key!

I stand corrected by the two replies!

According to this article: http://en.wikipedia.org/wiki/Key_size

"For example, the security available with a 1024-bit key using asymmetric RSA is considered approximately equal in security to an 80-bit key in a symmetric algorithm (Source: RSA Security)."

"As of 2003 RSA Security claims that 1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys and 3072-bit RSA keys to 128-bit symmetric keys. RSA claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030. An RSA key length of 3072 bits should be used if security is required beyond 2030. NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys."

As such my post contains very grave misinformation and should be disregarded!

The analysis in it applies to symmetric cipher key size.

See above. Another commenter pointed out that the 52 hours figure was only the last step in the factorization process, and that the complete process likely took months. That adds an order of magnitude to all the figures in the reply to your comment, as well.

No, it's the solution to one of the problems in the RSA Factoring Challenge [1].

[1] http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

It just means that lower bit keys are less secure as was known. Folks have been trying to get people to switch to higher bit keys as a result. RSA-210 is just the name of the challenge: https://en.wikipedia.org/wiki/RSA_numbers#RSA-210

There's still 1024bits, which is still in common use and more people are switching to 2048. You're still fine.

Reply on news.ycombinator.com