"I think that's the source as well - when the most recent of the TWINKLE and TWIRL papers came out, Lucky Green was talking about whether it was still safe to use 1024-bit keys, and $1B for 1 key/day is similar to Shamir & Tromer's estimate of ( http://www.wisdom.weizmann.ac.il/~tromer/papers/cbtwirl.pdf ) $20M upfront plus $10M for a 1 key/year capacity." My first question is, how easy is it for them to estimate the key size of an encrypted message? Can they do this without actually "chewing" on the message for a while? (ie, if it doesn't crack in x minutes then there's a 99% probability of the key being Y in length...) Second question: Is it possible to make a message appear to have been encrypted with a shorter key than was actually used? -TD

From: "Bill Stewart" <bill.stewart@pobox.com> To: <cypherpunks@lne.com> CC: <wk@gnupg.org> Subject: Re: Q: Has a change taken place in factoring RSA keys? Date: Wed, 29 Oct 2003 14:50:00 -0800 (PST)

...

...

In particular a claim was made that recent technology has come to light that allows factoring of 1024 bit RSA keys at $1B (US)/day. The basic gist was that

Adi Shamir's TWINKLE, I guess.

I think that's the source as well - when the most recent of the TWINKLE and TWIRL papers came out, Lucky Green was talking about whether it was still safe to use 1024-bit keys, and $1B for 1 key/day is similar to Shamir & Tromer's estimate of ( http://www.wisdom.weizmann.ac.il/~tromer/papers/cbtwirl.pdf ) $20M upfront plus $10M for a 1 key/year capacity. (The alternative is that it's people believing the usual FUD sources, whether they're the pro-government serious FUD sources or the fun-yanking-people's-chains clueless FUDsters.)

...

...

There was some discussion about hacking GPG to generate 8k keys.

But if 1024-bit keys are too weak, RSA is still near-exponential, and 2048-bit keys are roughly 2**100 times harder to crack than 1024-bit, vs. 4-8 times as slow to use. 4096 is a lot harder than that; even if you allow for Moore's law and medium mathematical breakthroughs, you're still not going to fit a 4096-bit cracker on the planet.

Basically, by the time you're interesting enough for them to spend $10M and a year to crack your machine, you'd better be using 2048-bit keys for tactical applications and maybe 4096-bit for long-term military secrets, and since they're targeting YOU, it's a lot cheaper for them to black-bag your PC or plant cameras in your ceiling or bribe your janitor.

...

That won't help unless you find a way to get random number as good as the keysize.

Large random numbers aren't that hard if you're using them for long-term signature keys, as opposed to DH or symmetric session keys; it just takes a bit longer to generate the bits. Also, once you're up above the 1024-bit range, incremental quality is less important, because attacks on the keyspace are hard to combine with factoring attacks on the keys, especially if you're whitening them.

But as you say, taking GPG from 4kbit to 8kbit keys doesn't matter, because it's no longer close to the weakest link by then.

_________________________________________________________________ Is your computer infected with a virus? Find out with a FREE computer virus scan from McAfee. Take the FreeScan now! http://clinic.mcafee.com/clinic/ibuy/campaign.asp?cid=3963