[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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


By Lewis Page
22nd May 2007

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.

Attend Black Hat USA, July 28-August 2 in Las Vegas, 
the world's premier technical event for ICT security 
experts. Featuring 30 hands-on training courses and 
90 Briefings presentations with lots of new content 
and new tools. Network with 4,000 delegates from 
70 nations.   Visit product displays by 30 top
sponsors in a relaxed setting. Rates increase on 
June 1 so register today. http://www.blackhat.com