768-bit RSA, now officially not enough

http://eprint.iacr.org/2010/006

by fogus • 17 years ago

45 33 17 years ago

eprint.iacr.org

phantom784• 17 years ago

Every bit makes it exponentially harder to factor and 1024 bits is the standard, so I'm not worried.

jrockway4• 17 years ago

Not correct, see above.

The factoring algorithm is not "try every possible number". If it was, then your statement would be correct.

timf2• 17 years ago

Only 2000 compute years of a single AMD 2.2GHz were reported to be used. Using the rough estimate of 9GFlops for that chip, the current top supercomputer (that we know of) is very roughly 200,000 times as powerful.

The paper estimates 1024 would be "about a thousand times harder". 1000 times harder than 2000 compute years on that chip is roughly ten compute years on that supercomputer. Closing in...

1024 is widely not recommended anymore, though.

niyazpk• 17 years ago

I don't understand why 1024 bits is just a thousand times harder than 768 bits. Shouldn't it be like 2^256 times harder?

timf2• 17 years ago

As I am in severe 'back of the envelope' mode, I did not investigate that claim.

But I think they refer to footnote 21 for the estimate: http://people.csail.mit.edu/tromer/papers/factorest.pdf

ajross3• 17 years ago

I don't pretend to understand the deep details, but the core point is that the GNSF algorithm is exponential in the bit length of the number being factored, but the exponent turns out to be distressingly small.

Edit: http://en.wikipedia.org/wiki/General_number_field_sieve gives the complexity as O(constant ^ ((logN^1/3)*(log logN ^ 2/3)). Which grows really slowly.

bsaunder• 17 years ago

For me, posts (and the community comments) like this are a large part of the value of HN.

Read the title, scanned the linked page, read the insightful comments. Gained a bit of information on the current state of cryptography. On to the next item. The accumulation of all such tidbits that appear here that has been incredibly useful.

fogus: thanks for posting all: thanks for the perspectives.

Back to my irregularly scheduled program...

jonp• 17 years ago

The relevant numbers from the paper:

  1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
  =
  33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
  *
  36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

jrockway4• 17 years ago

Hey look, I can play my DVD in Linux now.

cperciva4• 17 years ago

It's always good to see confirmatory experiments like this, but I don't see anything surprising in these results. We've known for the past few years that RSA768 was within reach of anyone who could be bothered to coordinate it; and nobody serious trusts RSA1024 against sophisticated attackers.

angelbob• 17 years ago

And so time marches on...

It'd be neat to have a graph of when various algorithms and numbers of bits were cracked, and see what progress looks like, long-term and on average.

wingo• 17 years ago

http://valhenson.livejournal.com/3580.html

TimothyFitz• 17 years ago

This is a summary of cryptographic hashes being broken via cryptanalysis (breaking the algorithm), not RSA keys (big primes) being factored. I'd love to see the same chart but for prime factorization.

azakus• 17 years ago

Isn't the default for ssh-keygen RSA 2048? That should be safe for a little while longer.

BearOfNH• 17 years ago

As I understand it, PGP uses RSA just at the outset to generate a 128-bit (or 256-bit or whatever) key for the rest of the message. So the PGP key length is a one-time cost (per message).

Many years ago (early 1990s) I generated a 1024-bit public key which was the limit at the time. A lot of Moores have passed since then. Since key generation and usage is no more than O(bits^2), possibly only O(bits log bits), I don't see why people aren't creating >= 8192-bit keys these days.

Or maybe they are. The MIT keyserver is down at the moment, at least if I ask it for anything.

cperciva4• 17 years ago

Since key generation and usage is no more than O(bits^2), possibly only O(bits log bits)...

A private key operation with N-bit RSA takes O(N^3) time using classical arithmetic, while key generation takes O(N^4) time using classical arithmetic. Your numbers are correct for public key operations, though.

jcsalterego• 17 years ago

http://mathfail.com/2010/01/the-232-digit-number-rsa-768-has... has a good summary as well.

masomenos• 17 years ago

Yes. the 6 months of 10k computers churning required to factor is certainly instructive.

nathanb2• 17 years ago

Correct my ignorance, please, but people are talking like cryptosystems using 768-bit keys have been cracked.

These folks showed that you can factor a single 768-bit number in under four years, if you have the computing power of a moderate-size cluster at your disposal and approximately one terabyte of memory. Interesting, certainly, but this exposes no vulnerabilities we weren't already aware of.

Brute forcing a 768-bit key would require multiple, potentially billions, of such factorizations, correct? Proving that you can factor an n-bit number in time t simply demonstrates that the time required to crack a cryptosystem with an n-bit key on the same hardware is an integer multiple of t.

Am I misunderstanding this, or are the people claiming "768 bits are not enough" just the usual paranoid element?

tel• 17 years ago

I'm not a security person, but my understanding is that all security systems are known to fail and thus come with a lifetime. Real safes aren't uncrackable, but uncrackable under 15 minutes of duress.

Crypto seems a little different since exponential complexity pushes those lifetimes out to what people often assume is infnite. A demonstration of a 4 year lifetime of a 768-bit under moderately powerful attack makes it clear that it isn't different and that its lifetime is now scarily short.

It's a lot like what I assume the introduction of power tools might have done to safe cracking. What previously was a 30 minute safe becomes a 30 second safe once the people you want to keep out can drill.

Retric• 17 years ago

Factoring a single 768-bit key let's you read every message sent to a single person using 768-bit RSA. Of forge a message signed by someone using a related system to sign documents.

PS: Don't forget, a large bot net could use 1 million CPU cluster to crack the same number.

jrockway4• 17 years ago

Brute forcing a 768-bit key would require multiple, potentially billions, of such factorizations, correct?

No. There is only one possible factorization of an RSA public key. RSA public keys are, by definition, the product of exactly two primes.

Once you have factored the public key, it is trivial to derive the private key from the two factors.

RSA is only secure because it is hard to factor numbers. This work shows that it's just hard, not impossible.

nathanb2• 17 years ago

I see...thank you for correcting my false assumption.

teeja• 17 years ago

It must be really aggravating spending 100 days breaking a long key, only to find a short one-time-pad message dropped into the middle of a long string full of 'neenerneenerneener!'.

TallGuyShort• 17 years ago

The way I see it, is that if someone's willing to go to these measures to compromise your data and hurt you, you're pretty much screwed no matter what you do.

768-bit RSA, now officially not enough

Related Stories