Dear Bill, Sorry, but you may see this message twice. Bill Stewart wrote:
There are two countervailing arguments about very long keys; one is that if you understand cryptography well enough to evaluate the issue, you'll know you don't need to bother, but the other is that if you don't understand crypto very well, maybe you should be overly conservative. <<<<<
Well, personally, I guess by your def I'm in the second group, since I didn't know I don't need to bother.
Remember that factoring difficulty is roughly exponential; adding logn bits about doubles the cracking workload (depending on which factoring method is being used). Factoring a 1024-bit number is _much_ harder than factoring a 512-bit number, and factoring a 2048-bit number is well into age-of-the-universe difficulty level. The practical level of factoring right now is about 512 bits, for either a distributed internet effort or an NSA internal one; <<<<<
in the unlikely event that Moore's law lets us double processing power 100 times in the next 150 years,
I kind of knew this from a hypothesis, so PGP 5.x is being conservative, possibly overly so by your definition. I've seen a screen on a friend's computer and the default is something like 2048. By the way, we don't know about NSA. They may be able to factor any number, if they have an algorithm. that means a 1500-bit key could be crackable. So 2048 bits is certainly more than enough for _your_ lifetime. Increasing processing power 2**100 times is likely to be tough :-) After all, features in current microprocessors are on the order of 100 atoms wide. And by the time we've developed the level of nanotechnology needed to speed up processing that much, there'll be tiny audio bugs listening to you type your passphrase into your keyboard and reporting it back to the Central Intelligence Corporation, or picking up the electromagnetic fields from your direct neural interface, so the crypto strength won't matter much. <<<<< I believe in Moore's law, since in 1992-1993 I read an analysis that Moore's law was true for the last 100 years. I think its still true today. Your last set of thoughts is chilling, isn't it? But consider this. People 10, 20, 30 years ago like us are saying that the government can eavesdrop on their communication in the future, just as you are saying now. Look now. I am very proud that I am part of the e-crypto revolution (my coined word). I am helping to slow down NSA. I hope that, by the time the tech you hypothesize about is here, we again will have technology to slow down NSA.
But do you really _need_ to factor the prime number to crack PGP? No. Remember that PGP uses the RSA key to encrypt session keys for IDEA, or for signing MD5 hashes of documents, rather than using it directly. So you can decrypt the message by cracking IDEA, or forge a message by finding MD5 collisions. Cracking IDEA's 128-bit keys was estimated to be about as hard as factoring a 3100-bit number, though improvements to factoring technology may make a 4096-bit number as easy as IDEA. Also, PGP 2.x passphrases are encrypted with IDEA, so if they've got your secring.pgp and can crack 4096-bit keys, you're toast, <<<<<
even if your passphase isn't just your dog's name spelled backwards. Similarly, by the time processing power doubles 100 times making your 1500-bit key insecure, MD5 will be long toasted. Either way,
I know this. The point is that most if not all people know that RSA is the weak link, not IDEA. Would you rather start to work on a 1024-bit RSA key or IDEA passphrase of an enemy? Obviously the RSA key. Barring any mathematical weakness in IDEA, I am not worried about IDEA. By the way, my three-year-old info says that IDEA was being mathematicly attacked in many quarters, civilian and non-civilian alike. If they was anything, I would have heard by now, but I still want to ask. Has any significant cryptanalysis attack against IDEA been "successful"? there's no need to go beyond 4096-bit keys ever, with old-style PGP. Even if you're being overly conservative, that's more than enough. <<<<< You seem to be suggesting that MD5 will lead to the downfall of all of our keys. Let's think about your toasting of MD5. The worst thing that can happen to a one-way hash function is that it can go both ways. So its dead for signatures. So let's suppose now that I can take any document and produce another document with a higher or lower dollar figure in it and come up with the same hash. I can do this easily. But to somehow exploit MD5 to crack a passphrase it is impossible because you have nothing to start working with. You only have an encrypted key, encrypted with an 128-bit IDEA key. Look, for our lifetimes, I don't see much point in going beyond 4096 bits either, maybe even 3072.
Newer versions of PGP dump RSA and IDEA for patent reasons, but they also offer alternatives to IDEA and MD5 which may be stronger. (SHA-1 is stronger than MD5, triple-DES requires immense amounts of storage to reduce it to a strength similar to IDEA, and just being extensible means you can replace algorithms that are obsolete.) <<<<<
The other side of practical is how much work it takes to use long keys, and how many people who want to talk to you use them. The answer to the latter is "Not many" for RSA keys over 2048. The former is about N**2 for decryption and N**3 for key generation, and about linear for encryption with short exponents, so it'll take you 64 times as long (once) to generate the key, and 16 times as long to decrypt or sign anything, compared to
Triple-DES is not stronger than IDEA, although it is secure for the most part. According to Phil Zimmerman, its effective key length is 112 bits to 128 bits for IDEA. Its also 3 times slower than DES, which is comparably slow anyway. Also, to settle this issue once and for all in my mind, the Win95 version of PGP, what symetric algorithms do you have to choose from? Does anyone have any comments on the relative strength of Blowfish? What about the mathematics of Blowfish? Has anyone tried to cryptanalyze it yet? Also, I apologize for going on like this, I'll post a separate question on that. the far-more-than-strong-enough 2048-bit key, which is already 4 times as hard to use and 8 times as hard to generate as a 1024. <<<<< As I said, I have a 2048-bit key in hibernation. I haven't posted it to a key server, but a friend who recently got PGP decided to use my public key ring, and use my 2048-bit key. There are only two places in which this key of mine is accessible. Anyway, I don't see the 4 time slowdown for using my secret key. (I have a 133 MHz). However, the effect is probably true for slower processors. I agree that we shouldn't bother with keys above 4096 bits because its not necessary and it takes too long to communicate with people who have slower processors.
It's not worth the bother, unless you know have a really, really special application that needs to remain secret until long after you've overthrown the government. On the other hand, at least the RSA patent will have expired by then :-) <<<<<
I already addressed this point.
The Diffie-Hellman implementations in PGP 5.x will let you use key lengths up to 4096, but the speed behaviour is a bit different. In particular, key generation is much faster, so generating overkill-length keys isn't as boring. <<<<<
First of all, Win95 (not my computer) seems slow to me, even if that person's processor is faster than mine. And I hear so much disk reading or writing, no wonder its slow. Boring? Win95 cannot make you bored. Go do something else, or play a MIDI file. You can multi-task. --Alan