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

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 …

[Tom Maddox]

Well, now

I await the many comments blaming "Micro$oft" for this shocking revelation.

[Nick Stallman]

Perspective

Dont you mean it is plenty secure for some things, but not others?

2 and a half years for nuclear launch codes? Thats horribly insecure.

2 and a half years to decrypt a router's firmware or someone's IM conversation? Very secure.

Morale of the story is you should use the right tool for the job, and computing power increases so keep that in mind.

[Gordon 10]

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.

[Anonymous Coward]

Re: Perspective

I somehow doubt the military keep the same nuclear launch codes for 2 years...

[Anonymous Coward]

Nicely written

It's good to see somebody wrote an article about this topic without getting all the details wrong. Well done.

[Quando]

So how long to factor it using a botnet?

If "Using a single-core 2.2GHz AMD Opteron with 2GB RAM, sieving would have taken about 1,500 years" then a 10,000 machine botnet takes 54 days or so. So a 70,000 machine network is a week, assuming they are all just single core and are running 24x7 [big assumption I know - I'd expect faster machines on average, but not running 24/7].

Alternatively how much would it cost to rent that much CPU time on Amazon's cloud?

[James O'Brien]

In the words of Eric Schmidt

'If your worried about privacy you are probably doing something illegal'

/Paraphrased yes but oh so worth it

[Anonymous Coward]

Re: in the words of...

To paraphrase the response "if you're not worried about privacy, why do you have curtains and an indoor toilet?"

Presumably the Schmidts of this world are fine with everyone watching them wiping their a%£e, having bath or making love, and don't mind their doctor discussing their STD in front of their granny and girlfriend....

Remember folks, everyone has a right to a private life.

[a walker]

interesting

While studying cryptographic algorithms in the late 1990's, one of the reference book I used indicated that at that time only 4096 bit public keys were deemed secure by the miltary. At the time DES was the common commerical algorithm along with supposed improved variants (which were later shown to be less secure). It is not unreasonable to assume that 4096bit key were required because 1024bit keys were crackable by those persons using 4096bit keys. If 768bit PKI keys are broken, why are secure wireless access point using 128 bit PKI keys, though anyone sensible would only be using already encrypted traffic before it is transmitted on the wireless connection.

[Anonymous Coward]

You did what?

For someone who was "studying cryptographic algorithms in the late 1990's" you've forgotten an awful lot in the meantime. Wireless access points don't use PKI, and the crypto employed doesn't use RSA. Various x509 certificates have been broken, due to for example md5 collision attacks (md5 produces 128 bit hashes, which are not keys), and DES uses 56 bit keys. Public Key (asymmetric) algorithms tend to use (much) bigger keys than private key (symmetric) algorithms; the successor to DES, AES, uses 128, 192, or 256 bits keys, and that is perfectly fine for contemporary use. Especially back then 4096 bit RSA will have been a right pain to use because of the computation needed to use it (nevermind crack it).

I don't know what reference book you're referencing, but I suspect lots of bitrot in transmission.

[Anonymous Coward]

About to be expected

Given how old RSA is and how much computing capacity has increased in the last few years, this is a good reminder that the state of the art does move on, but not much more than that. If you're still using <=1024 bits RSA keys it is definately time to move on to longer ones, but RSA itself is far from dead yet.

[John Smith 19]

smaller keys used by embedded devices

Like smart cards for digitial TV? Payment schemes?

A timely warning that this technology is clever and useful if used wisely and you have an upgrade scheme in place.

[lglethal]

So...

It took them 2 years to break the 768 bit key...

So there's no rush for me to go out and change just yet...

[AdelaideGrant]

now let me see.....

now lets see 1,2,3,4,5..........easy as that NOT! Make one wonder though with more powerful computers and the abilit to peer share resources,what length of cipher is truly secure in the future?

[Anonymous Coward]

Exaggerate much?

"768 bit RSA keys can no longer be counted on to encrypt or authenticate sensitive communications"

So basically, if you happen to have some information that someone else wants so badly that they'd commit to spending 1,500 cpu years to cracking its encryption, then you should be using a longer key. So probably not credit card data then. More like a "sensitive communication" containing nuclear missile launch codes. I don't think many of us have much to worry about if we're still using shorter keys for the foreseeable future.

All RSA keys are crackable given enough computer time. This just shows how much trouble it was to crack *one* 768 bit key; not all of them. If your secret data's shelf-life is less than a few years then it won't really matter uness the NSA really really wants it now. I bet it'd be cheaper and quicker to just bribe you to give it to them.

It's an interesting result. Spoilt somewhat by the hype.

[Pascal Monett]

ooh, disaster looms !

Really, I'm terrified. A bunch of scientists implemented the necessary infrastructure to harness the calculating power of hundreds of CPUs, probably via a readily-available communication medium, and tailored that effort to break the 768-bit level of RSA encryption.

As opposed to the russian mafia, who might have those scientists, and might even be able to implement the project, but who would probably be more likely to just send Ivan over to punch you into giving them the password. With a knife on the throat of your firstborn child if necessary.

And if its the NSA or some other spooky governmental agency, well if they're looking at you that intently they already have your password.

Are there really all that many industrial espionage cases based on cracking encryption ? What is encryption really for after all ? Maintaining an acceptable level of privacy. The basic thug cannot crack any RSA key. An international crime outfit doesn't care about personal emails unless you're already on their target list. And the government has hundreds of other ways to get that information if they really want it.

If it takes 1500 years for someone to be able to read the cookie recipie that I sent my brother-in-law last week, well I think that's good enough. Call me when it's down to six months.

[amanfromMars 1]

Free Information ..... on General Intelligence

"And if its the NSA or some other spooky governmental agency, well if they're looking at you that intently they already have your password." ..... Pascal Monett Posted Friday 8th January 2010 12:35 GMT

Pascall, As is admitted by POTUS of their Intelligence Services, having the information is one thing but understanding the meaning of what they may have and rearranging it into actionable intelligence is proving chaotic, if not impossible. And then there is always the added complication that any information they may have gleaned is already old and replaced by something else even before they have reacted to what they have discovered or been told.

The Secret of Great Uncrackable Security is to be Dynamically ProActive, then is Everything a Reaction to ITs Lead and the Worry, someone else's.

[bexley]

yawn

luckily the default bit length for RSA on ssh-keygen is 2048.

so, 3000 years on a modern pc ? i can live with that.

[Steen Hive]

The thing is that

RSA is so god-awfully slow that it's never used to encipher large amounts of data - it's usually just data of a few bytes - session keys, hash signatures & stuff. Anyone not using 2048-bit-plus RSA for that sortof thing nowadays should be sacked and/or given a whack of a cluebat. Nevermind that "makecert" will only output 1024-bit certificates to file.

[Paul_Murphy]

BOINC

Maybe they should produce a BOINC project for this - then see what the effect of millions of computers might be.

--------- info from http://boincstats.com/stats/project_graph.php?pr=sah -------

Last update 2010-01-07 16:45:30 GMT

Total Active

Users 1,052,256 183,028

Hosts 2,536,235 297,828

Teams 57,109 17,023

Countries 234 213

Average floating point operations per second 696,070.5 GigaFLOPS / 696.071 TeraFLOPS

-------------------------

might be good for a laugh

ttfn

[Peter Methven]

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!

[Anonymous Coward]

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.

[Graham Bartlett]

Read Cryptonomicon, folks

In particular: "I want them to remain secret for as long as men are capable of evil."

I don't much care if my mobile phone conversation can be decrypted with a week's worth of brute-force attacks. I might care if my wireless network can be cracked in a couple of weeks by my neighbour's PC. And I'd definitely care if the country's nuclear launch codes could be cracked in anything less than a decade. (Yeah I know, there's no such thing as nuclear launch codes that you can punch into any convenient internet-connected PC, contrary to what a zillion bad films say, but you get the idea.)

[Michael Nielsen]

it is as always a tradeoff.

If your information that you wish to protect is valuable enough, then some one is going to throw 1500 years of computer time into cracking it.

However, most personal information that we have, can be obtained in other easier ways, using trojans, and social engineering, so I would not bother.

Creditcard transactions may be valuable enough to bother cracking, but considering that it's 1500 years for one key, the few 1000 pounds you have on your bank account, likely isn't enough for it to be worth while.

However cracking Bill Gate's bank account, now that'd likely be worth while.

So take it easy, no one is going to throw 1500 years of computing time, into cracking your WLan, or some firmware upgrade.

However, as it isn't that expensive to move to 1024bit keys, or even 2048 bit keys, then if you're worried, or have something really valuable to hide, then by all means upgrade.

But remember, the basic security issue.

1. Is it worth while to break the key?

Therefore choose the key according to how sensitive, and important the data is.