Feeds

Crypto boffin: writing is on the wall for 1024-bit RSA

But nobody can read it yet

Seven Steps to Software Security

Crypto-busting boffins have broken a new record in their quest to find the prime factors in large numbers, and may soon threaten part of the encryption system used to secure retail websites.

Professor Arjen Lenstra of the Ecole Polytechnique Federale de Lausanne (EPFL) yesterday broke the news that computing clusters run by the EPFL, the University of Bonn, and NTT in Japan had managed to rip out the prime factors in a "whopping" 307-digit number.

On the face of it, this would seem to threaten the security of widely-used RSA 1024-bit encryption. The RSA algorithm uses two 150-odd digit primes to produce a 1024-bit code, similar in size to the one that Lenstra's computer clusters have factorised. The difficulty of extracting the prime factors involved in the creation of keys to the RSA code is what makes the algorithm secure.

Is the writing on the wall for 1024-bit RSA encryption?

"The answer to that question is an unqualified yes," says Lenstra.

However, the crypto prof then qualified his answer. The 307-digit monster his team has just broken wasn't a true RSA code but a so-called "special" number, describable in this case as 21039-1. RSA algorithms made up of two primes are harder to factorise. One might also note that even the special case 307-digit "behemoth" took 11 months and a century of computer time to crack.

The largest proper RSA number yet broken was a 200-digit "non-special" number whose two prime factors were identified in 2005 after 18 months of calculations that used over a half century of computer time. The 1024-bit numbers used in RSA encryption are around 100 orders of magnitude bigger than this. The writing may be on the wall for 1024-bit RSA: but as yet, um, nobody can read it.

However, Lenstra remains quietly confident.

"Last time, it took nine years for us to generalise from a special to a non-special hard to factor number," he said, referring to earlier efforts to break 155-digit numbers.

"I won't make predictions," he went on, "but let's just say it might be a good idea to stay tuned."

This would seem to indicate that Lenstra and his colleagues have even now moved on from 307-digit special numbers to similarly-sized non-special proper RSA numbers, and that he expects success within a few years. At that point, the writing would be on the 1024-bit RSA gravestone, not the wall. Crypto attackers would presumably need significant amounts of computer resources, but these aren't unobtainable. Large botnets, for instance, might conceivably be used in place of academic distributed projects or clusters.

Ari Juels, chief scientist at RSA Labs, told the Reg:

"Lenstra's result is consistent with the view of the scientific community that natural evolution in computing power will require the industry periodically to adopt longer key sizes. Indeed, Lenstra's result may confirm his prediction in 2001 that 1024-bit RSA keys will be within the reach of a concerted factoring effort by 2009...1024-bit RSA will reach the end of its effective lifetime around 2010...Our best estimate is that 2048-bit RSA keys will be suitably strong for use through 2030. Detailed scrutiny by the community of Lenstra's result may require some recalibration of key-lifetime recommendations."

Noted security brainbox Bruce Schneier commented more bluntly on the EPFL announcement in his blog, saying: "I hope RSA applications would have moved away from 1024-bit security years ago, but for those who haven't yet: wake up."

We're all RSA users on occasion: the padlock we see in our browser when logging onto a secure website such as a bank or web shopping checkout typically refers in part to an RSA handshaking process. We should probably all hope along with Bruce. ®

Mobile application security vulnerability report

More from The Register

next story
Yorkshire cops fail to grasp principle behind BT Fon Wi-Fi network
'Prevent people that are passing by to hook up to your network', pleads plod
HIDDEN packet sniffer spy tech in MILLIONS of iPhones, iPads – expert
Don't panic though – Apple's backdoor is not wide open to all, guru tells us
NEW, SINISTER web tracking tech fingerprints your computer by making it draw
Have you been on YouPorn lately, perhaps? White House website?
LibreSSL RNG bug fix: What's all the forking fuss about, ask devs
Blow to bit-spitter 'tis but a flesh wound, claim team
Attackers raid SWISS BANKS with DNS and malware bombs
'Retefe' trojan uses clever spin on old attacks to grant total control of bank accounts
Manic malware Mayhem spreads through Linux, FreeBSD web servers
And how Google could cripple infection rate in a second
Mozilla fixes CRITICAL security holes in Firefox, urges v31 upgrade
Misc memory hazards 'could be exploited' - and guess what, one's a Javascript vuln
Don't look, Snowden: Security biz chases Tails with zero-day flaws alert
Exodus vows not to sell secrets of whistleblower's favorite OS
prev story

Whitepapers

Designing a Defense for Mobile Applications
Learn about the various considerations for defending mobile applications - from the application architecture itself to the myriad testing technologies.
How modern custom applications can spur business growth
Learn how to create, deploy and manage custom applications without consuming or expanding the need for scarce, expensive IT resources.
Reducing security risks from open source software
Follow a few strategies and your organization can gain the full benefits of open source and the cloud without compromising the security of your applications.
Boost IT visibility and business value
How building a great service catalog relieves pressure points and demonstrates the value of IT service management.
Consolidation: the foundation for IT and business transformation
In this whitepaper learn how effective consolidation of IT and business resources can enable multiple, meaningful business benefits.