This tip is the complete response to an Ask the Expert question posed to expert Jon Callas. To read the original question, please click here.
A few years ago, I gave a talk called, "The seduction of the one-time pad." In it, I discuss how the pursuit of perfect security with one-time pads leads people to make suboptimal security decisions. People spend a lot of effort chasing the one-time pad, and then end up with security that is only good enough. Starting with security that is good enough and sticking to it is almost always the best thing to do.
I'm afraid you've succumbed to that seduction. Don't feel badly about it, most of us do at one time or another. But let me discuss what you did.
You are right that random data is not compressible. This is pretty much the definition of random data. Since compression algorithms like Zip work by finding repeats of data and then putting in shorthands they aren't going to find them in random data. Anything they do find should have just occurred randomly and is not going to offset the extra data that has to be put in for the compression structures. So compressed random data is most likely going to be larger than the base data itself.
Now then, let's look at how to transfer pads to your partners. Since the pads have perfect security, the true security of the system is actually the security of the courier. Let's imagine that you have an actual person delivering them. The security of the system is essentially the chance that the adversary can copy the pads without the courier noticing. That's the way to attack that system. (We'll ignore the storage security issues, as well as the issues of how well your random data was generated.)
If your courier is PGP, then the security of the transfer is the security of your PGP envelope. If that has a 512-bit RSA key, and underneath that a 128-bit cipher, then the weak point of the system is the 512-bit RSA key, which has about the same strength as a 56-bit symmetric key. So, when you encrypt that pad, you have lowered its security to that of a 56-bit key. It would be simpler and just as secure to just use a 56-bit key.
Had you used a 4K-bit public key, then the weakest link in the courier subsystem would be the 128-bit symmetric key. The U.S. NIST estimates that a 3K-bit public key is equivalent in strength to a 128-bit symmetric key, and a 7.5K-bit public key equivalent to a 192-bit symmetric key.
Do you see what I mean by seduction? Chasing the perfection of the one-time pad led you astray and you used a small public key. If I may hypothesize about your motivations, I'll bet you did this because you worried about the size of the key when you were looking at the size of the final compressed pad. The difference in size between a 512 key and a 4000-bit key is insignificant to the size of the data. My guess is that you had your eye on the perfection of the one time pad, not on the rest of the system.
So let's look a little more at the rest of the system. How good would the cryptanalysis of PGP with a 4096-bit public key and 128-bit symmetric key be? As I said, in this case, the public key is stronger than the symmetric key, so let's look at that first.
I first heard this explanation from Burt Kaliski of RSA. Imagine that you have a computer the size of a grain of sandand it can test one symmetric key in the time it takes light to cross it. It is unlikely that it could be faster than that, assuming that general relativity is correct. Now then, let's take a sphere the size of the Earth and cover it with these computers to the height of one meter. This distributed system will crack a single 128-bit symmetric key on average in 1,000 years.
It literally takes a spare planet full of computers to break a 128-bit key. I don't believe that any of the major governments have that at their disposal. I don't believe that all of them together do. Now, the real fear should be if the algorithm has a flaw in it that they know about and the rest of us don't. This gets into true speculation. If any of us civilian cryptographers thought there was a real flaw in any of the widely-used ciphers, you'd hear about it. Such things are widely discussed, and the international community of serious cryptographers has a couple thousand smart minds in it. For example, there are continued doubts about RC4, and a new paper out of this year's FSE (Fast Software Encryption) conference. I haven't had time to read it yet, but I would respond to these doubts by not using RC4 in any new systems. This may be slightly negligent of me, but I haven't heard any cries of "Oh my! Stop using RC4 now." What I hear is, "Interesting paper, you should read it."
If you're still worried about 128-bit keys, then you should use 256-bit keys. The U.S. government recently approved 256-bit AES for use with top-secret classified data. If you're worried about AES, then pick either Twofish or Serpent. They were finalists for the AES, and there is nothing wrong with either of them and are at least as strong as the AES. Twofish is slightly slower than the AES, and Serpent about half the speed of the AES. They're all three faster than single-DES.
So let's look at public key algorithms. Adi Shamir and his team at Technion in Israel estimate that you could make a machine that can break a 1024-bit in one year for about U.S.$10 million. This is still under debate, but let's take them at their word and extrapolate a bit.
This means that if a major government has a spare U.S.$1 billion, they can break 100 keys that are 1024-bits long in a year. If you're not one of the top 100 people they want to hit this year, you're safe, even with a 1024-bit key. If you want to just stop the threat, you can stop it by making a new key that is 1025-bits long. This is because the machinery needed to factor has a hard maximum size. Unlike with symmetric keys, where you can re-target an N bit cracker to an N+1 bit cracker that just takes twice as long, you need a completely new machine to do a 1025-bit factor machine. Also, another consideration is that the memory required to run a sieve increases with the square of the size of the key -- but let's ignore that.
NIST estimates that 1024-bit public key is as strong as an 80-bit symmetric key, and a 3072-bit public key as strong as a 128-bit key. That's 48 bits more. So with a lot of extrapolation, a machine to break a 3072-bit key should cost 2^48 as much.
Tying all this together -- I don't know about you, but it seems simpler and good enough to me to just use PGP with a 128-bit symmetric key and a 3K public key than to worry about the hassles of one time pads. If you're still not impressed, there's still that 256-bit key stuff around.
Have you ever seen one of those movies where the hero chases after a beautiful, unattainable woman and ignores the solid, pretty girl who lives next door? One of the current movies in the U.S. is that theme, except it's a woman who has to choose between a movie star and the guy next door. We all know how it ends and why.
That's what the seduction of the one-time pad is. It's chasing something perfect and unattainable, when there's something under your nose that is better than you ever need. The combination of the perfection of what you can't have, and the all-too-human tendency to think poorly of what is at hand leads to bad decisions.