Feeds

RSA crypto defiled again, with factoring of 768-bit keys

More where that came from

Website security in corporate America

Yet another domino in the RSA encryption scheme has fallen with the announcement Thursday that cryptographers have broken 768-bit keys using the widely used public-key algorithm.

An international team of mathematicians, computer scientists and cryptographers broke the key though NFS, or number field sieve, which allowed them to deduce two prime numbers that when multiplied together generated a number with 768 bits. The discovery, which took about two-and-a-half years and hundreds of general-purpose computers, means 768-bit RSA keys can no longer be counted on to encrypt or authenticate sensitive communications.

More importantly, it means it's only a matter of another decade or so - sooner assuming there's some sort of breakthrough in NFS or some other form of mathematical factoring - until the next largest RSA key size, at 1024 bits, is similarly cracked. The accomplishment was reached on December 12.

"It's an important milestone," said Benjamin Jun, vice president of technology at security consultancy Cryptography Research. "There's indisputable evidence here that 768-bit key are not enough. It's a pretty interesting way to close out a decade."

The team managed to factor the 232-digit number that RSA held out as a representative 768-bit modulus from a now-obsolete challenge. They spent half a year using 80 processors on polynomial selection. Sieving took almost two years and was done on "many hundreds of machines". Using a single-core 2.2GHz AMD Opteron with 2GB RAM, sieving would have taken about 1,500 years, they estimated.

Factoring the 768-bit key was "several thousand times harder" than factoring a 512-bit one, a feat that was first performed in 1999. By contrast, factoring a 1024-bit RSA modulus, will be about 1,000 times harder than this most recent milestone. That's more than five times easier than a 768-bit RSA modulus looked just a decade ago.

"If we are optimistic, it may be possible to factor a 1024-bit RSA modulus within the next decade by means of an academic effort on the same limited scale as the effort presented here," authors of the research wrote. "From a practical security point of view this is not a big deal, given that standards recommend phasing out such moduli by the end of the year 2010."

But Nate Lawson, a cryptographer who is principal of security consultancy Root Labs, said smaller keys continue to be used for a variety of purposes, often by smaller embedded devices that don't have the processing power to handle larger keys.

The research team includes Thorsten Kleinjung, Arjen K. Lenstra, Joppe W. Bos and Dag Arne Osvik of EPFL IC LACAL, in Lausanne, Switzerland; Kazumaro Aoki of NTT, in Tokyo; Jens Franke of the University of Bonn's Department of Mathematics; Emmanuel Thomé, Pierrick Gaudry, Alexander Kruppa and and Paul Zimmermann of France; and Peter L Montgomery, Herman te Riele and Andrey Timofeev of Microsoft. A copy of their paper is here (pdf). ®

Protecting users from Firesheep and other Sidejacking attacks with SSL

More from The Register

next story
'Kim Kardashian snaps naked selfies with a BLACKBERRY'. *Twitterati gasps*
More alleged private, nude celeb pics appear online
Hackers pop Brazil newspaper to root home routers
Step One: try default passwords. Step Two: Repeat Step One until success
UK.gov lobs another fistful of change at SME infosec nightmares
Senior Lib Dem in 'trying to be relevant' shocker. It's only taxpayers' money, after all
Spies would need SUPER POWERS to tap undersea cables
Why mess with armoured 10kV cables when land-based, and legal, snoop tools are easier?
TOR users become FBI's No.1 hacking target after legal power grab
Be afeared, me hearties, these scoundrels be spying our signals
Snowden, Dotcom, throw bombs into NZ election campaign
Claim of tapped undersea cable refuted by Kiwi PM as Kim claims extradition plot
Freenode IRC users told to change passwords after securo-breach
Miscreants probably got in, you guys know the drill by now
THREE QUARTERS of Android mobes open to web page spy bug
Metasploit module gobbles KitKat SOP slop
BitTorrent's peer-to-peer chat app Bleep goes live as public alpha
A good day for privacy as invisble.im also reveals its approach to untraceable chats
prev story

Whitepapers

Secure remote control for conventional and virtual desktops
Balancing user privacy and privileged access, in accordance with compliance frameworks and legislation. Evaluating any potential remote control choice.
WIN a very cool portable ZX Spectrum
Win a one-off portable Spectrum built by legendary hardware hacker Ben Heck
Storage capacity and performance optimization at Mizuno USA
Mizuno USA turn to Tegile storage technology to solve both their SAN and backup issues.
High Performance for All
While HPC is not new, it has traditionally been seen as a specialist area – is it now geared up to meet more mainstream requirements?
The next step in data security
With recent increased privacy concerns and computers becoming more powerful, the chance of hackers being able to crack smaller-sized RSA keys increases.