Researchers crack 768-bit RSA
A team of researchers has cracked their way into the RSA algorithm, albeit with a limited 768-bit keyspace.
As reported over on eWeekEurope.co.uk, the team - which includes individuals from NTT in Japan, the University of Bonn in Germany, and Microsoft in the US - used a novel algorithm along with a cluster of souped-up PCs to break the RSA algorithm with a 768-bit keyspace, which was previously thought to need around 1,500 years to complete on an average PC.
Indeed, the problem was solved so quickly by the cluster that the team describes "the overall effort [as] sufficiently low that even for short-term protection of data of little value, 768-bit RSA moduli can no longer be recommended."
The news that RSA can now be brute-forced in this manner raises concerns for the safety of the RSA-based Secure Sockets Layer, used to protect sensitive data - including logins and credit card details - during transit on the Web. Thankfully, the team believes that 1024-bit RSA - which uses a significantly larger keyspace, and is the most commonly used version on the Web today - should remain secure against such attacks.
However, the team advises corporations and governments to make plans for its replacement now - stating that 1024-bit RSA should be phased out "within the next three to four years." While the obvious patch is to replace it with a still-larger keyspace - 2048-bit RSA is not uncommon - Origin Storage's Andy Cordial believes that the future lies in two-factor authentication.
In a statement regarding the research, Cordial opined that although biometrics - such as fingerprint or iris recognition systems - are the obvious choice for data security, their currently high cost is prohibitive. Instead, he recommends the use of a smartcard or other physical token - allowing "the CEO or chairman to put his/her hand on heart and say the company's data is secure whilst in transit from one place to another," a promise that cannot be made "any more with single factor encryption."
For those interested in the technical details of the research, a white paper is available as a PDF file.
Are you concerned to see the previously unassailable RSA being broken in this way, or is 768 bits too small a keyspace to draw any conclusions about the security of the algorithm in the wild? Share your thoughts over in the forums.
Previous Article
31 Comments
Discuss in the forums ReplyWHAT 9000 ?!?!?!
LOL!
Compared to the recently discovered exploitable flaw in SSL, this isn't actually the biggest threat to SSL security. A hacker is rarely going to brute force an attack if there is an easier alternative.
http://wiki.twit.tv/wiki/Security_Now_223#The_Latest_SSL_Exploit
Given time and loads of computational power.
This is true but your statement is misleading. If it takes 1000 years to brute force a code then it's a little unfeasible for a hacker to want to do so, wouldn't you say? :P
Interesting article though... however I wonder if it's more a case of holes and exploits in software that are more likely to be the threat nowadays as mentioned by a poster above. Whats the point in breaking down the front door when the window is unlocked.
Dirty maths: 1000 x 365 x 24 = 8.76 million = the number of 'average computers' required to crack a "1000-year" encryption in an hour - not out of the realm of feasibility I would posit.
EDIT: Someone correct me if I'm over-simplifying please.
that's pretty cool research =] guys are all into it..
Tens, hundreds or thousands?
Especially now when you have machines like the FASTRA. Get a few of those and you can do a lot of kinky things with pi. Just not while you are playing crysis......
This is a non sequitur. Public key algorithms are valuable because they allow you to verify the security of a communication without exchanging keys in advance. This is important because transmitting keys over an insecure medium (such as the net, phone system, postal service or any situation where you cannot guarantee privacy) is dangerous and because maintaining separate keys for every party you wish to communicate is impractical.
Two factor authentication simply means replacing a password with, for example, a password and a iris scan. "Something you have, something you know". The main point of this is to make it harder for idiots to compromise their own authentication credentials (by writing them down) or to prevent people from intentionally sharing their credentials.
This bears no relevance to the security of RSA because the attack does not rely on the user giving an attacker access to their key but rather allows the key to be factored from the encrypted data.
This also has nothing to do with the security of RSA and is a pretty dubious claim anyway.
Andy Cordial is either being misquoted in the original article or is completely clueless about cryptography. Origin Storage sell the sort of pin-protected hard drives he is recommending, so take what you will from that.
In regards to the actual news story, while academically interesting it isn't a big deal from a security standpoint. 1024 bits was a short key in 1995. Anyone actually using a 768 bit key doesn't care about security.
Note, however, that RSA is NP-complete: there is (so far) no silver bullet to make cracking it any faster than the brute-force approach. Double your key size, you'll be fine for the next several years. When they get close to cracking that, double it again, and you'll be fine again.
Tl;dr: Meh. RSA is still good, just increase your key length.
while it is pretty amazing that they found a fast way to factor RSA i agree with both flax and techno-dan. 2 factor authentication has nothing to do with data encryption, and when your RSA key gets too short just make it longer.
I am so disturbed :D
Whoa, now that is big news! +1 rep
I was thinking along the same lines. ] wonder what they mean by "average" computers these days and how they would compare to the Bt folding rig, for example.
+1 to SSL having bigger problems than 768 bit encryption.
So in 2030 SSL should be at what 16000-bit?
meh, 365,000 computers and day > 8.76 million computers and an hour
The RSA key length that is brute forceable has so far doubled roughly every 10 years (512 bit was broken in 1999 iirc). If that keeps up a 4096 bit key might be looking a bit dodgy by 2030, but a 8192 bit will probably still be strong.
their running it against the data. capture a few encrypted packets and crack the key with those, now you have that persons key.
at least that is the way i understand it, i could be wrong, admittedly i only skimmed the paper.
It will be very tough. Especially on anybody trying to use SSL on their EEE . It will probably take the poor thing the rest of its life to handle a single request.
OMG The shock of it!!!
It is assuming that the most basic forms of brute force algorithms would be used.
Just like in this new method, even though it required a component of brute force to obtain the solution, the main work effort was in the initial maths / technical research.
Therefore, even when the researchers here state that 1024-bit is currently safe, that is only in the case of using THEIR procedure. It does not mean that another research team couldn't develop a more efficient algorithm in the near future that could be a threat to 1024 or even 2048-bit encryption.
I think the main item of information to take away from the article is that brute force isn't just one method. If this team has created a 'more efficient' brute force procedure, it indicates that the basis of this whole type of encryption could be at risk.
SouperAndy