768-bit RSA, now officially not enough | Hacker News Reader

768-bit RSA, now officially not enough

eprint.iacr.org

45 pointsfogus33 comments

The relevant numbers from the paper:

  1230186684530117755130494958384962720772853569595334792197322452151726400507263657518745202199786469389956474942774063845925192557326303453731548268507917026122142913461670429214311602221240479274737794080665351419597459856902143413
  =
  33478071698956898786044169848212690817704794983713768568912431388982883793878002287614711652531743087737814467999489
  *
  36746043666799590428244633799627952632279158164343087642676032283815739666511279233373417143396810270092798736308917

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

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...

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.

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?

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

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.

the GNSF algorithm is exponential in the bit length of the number being factored

No. First, it's GNFS, not GNSF; and second, it's approximately exponential in the cube root of the bit length, not exponential in the bit length.

My profuse and abject apologies for transposing those glyphs. I can't imagine how that would have happened.

Maybe you could apply your expertise a little and give us a better explanation than mine instead of criticizing my spelling? I didn't claim to understand the deep details, but frankly your sniping is helping even less.

If you had left it at the apology I would have voted you up.

Isn't that the same thing?

(n^1/3)^c = n^(c/3)

Still an exponential relationship, just a smaller constant.

And that's why it's 1000, not 2^256.

Those are polynomial, not exponential.

Polynomial time: O(n^c)

GNFS time: O(c^(n^(1/3))

Exponential time: O(c^n)

I'm still not understanding where your criticism is directed. GNFS (see? no typo this time. Do I get a cookie?) is quite clearly outside of PTIME, though I'm not sure to which definitions of SUBEXP and EXPTIME it belongs. Thus RSA remains an algorithm which is infeasible for tractable key sizes, even if the early guesses of 512-1024 bits turned out to be wrong.

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.

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

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.

The Wikipedia page for the RSA Factoring Challenge has a nice chart that shows the dates RSA numbers have been broken: http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

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.

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?

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.

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.

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.

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

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

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

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!'.

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.

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

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

Not correct, see above.

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

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.

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.

Reply on news.ycombinator.com