RSA crypto defiled again, with factoring of 768-bit keys
More where that came from
Agentless Backup is Not a Myth
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). ®
COMMENTS
That is also wrong
If you have read Schneider's book you would realise that eventually encryption becomes unbreakable with "enough CPU cycles". Let me give you 3 examples.
1) If I have a perfect symmetric key algorithm with a 256 bit key. This algorithm cannot be attacked by anything except brute force (hence it is perfect). The laws of physics give me a minimum quantum of energy required to do a state change in a state machine (like a computer for example). To simply count from 0 to 2^256 requires more energy than the Sun will produce for the remainder of it's life. That means if you make a perfectly efficient computer, build a Dyson sphere around the sun, and run the computer for the remainder of the sun's life powered by all the energy the sun produces, you will still fail to count through all the keys possible. That's without attempting any decryption.
2) A one time pad. So long as my one-time pad has been generated from truly random numbers (nuclear decay, or cosmic background radiation for example), then no computer in the world can crack it. Ever. Even if I could count through all the keys, the problem is that there is a key that will decrypt to my original message, but there is also a key that decrypts to every other possible message of the same length, and there is no way to know that you have the right message, or any of the other possible messages. You can find a key that will decrypt into Othello, or the 3rd episode of season 4 of South Park, or anything else.
3) Quantum Encryption. This basically uses quantum mechanics principles to generate a key for a one time pad.
Finally, I can guarantee that the techniques that the likes of GCHQ and NSA use are a lot more advanced. When 56 bit DES was still considered uncrackable by the general public, it was widely rumoured that NSA had a look-up attack machine. This basically consists of a big drive that has a bunch of common plaintexts (SMTP message headers, etc.) encrypted with every known key, and then indexed for fast lookup. If you have a big enough drive to store this, then you can crack the encryption in question in realtime. It just becomes a set of database lookups (one for each segment of the ciphertext) - albeit in a massive database. With hashing of the key, that lookup can be virtually instantaneous.
Before you think that this provides a route into (1) above, remember this. If you try this with a 256 bit key, firstly, you can't have enough compute power to generate the lookup database for the same reasons that you can't count to 2^256. Secondly, if you did generate this on a drive where 1Gb of data was stored on a media that weighed 1g, then your drive would be so heavy that it's own gravity would cause it to collapse into a black hole.
All encryption is breakable with enough CPU cycles...
All encryption is ultimately breakable with enough CPU cycles, that was the first thing I was taught in a University module on cryptography 8 years ago several times.
Anyone who honestly thinks any key will encrypt your data forever is fooling themselves and you have to ask yourself whether what you are encrypting is ever going to be the target of 150,000 years of cpu cycles and whether at that point it will have been worth the effort to break the encryption!
What Nick Said
Surely all this is a measure of the relative strength of the key. If you assume that this effort represents 1% of the NSA or GCHQ's ability to crack the same encryption you are still safe for 7 odd days before you need another key.
If you are a paranoid terrorist drop that to 0.1%.
Factor in Moores Law so half the safety window every 18 months,
As Nick says - right tool for right job.
IT infrastructure monitoring strategies
Requirements Checklist for Choosing a Cloud Backup and Recovery Service Provider
Data control in the cloud
Cloud based data management
Agentless Backup is Not a Myth
