Tim May writes:
Speculatively, knowing the passphrase-encrypted secret key may make it easier to crack RSA; this is just a speculation. It is not yet even been proven that RSA is a strong as factoring. i.e., we don't know for sure that the RSA information provided as part of the protocol doesn't in some way make the problem simpler than straight factoring of the modulus.
Here is a little-known fact. In fact, I had forgotten it myself until what Tim said reminded me. Your PGP secret key file is partially encrypted using IDEA keyed with the hash of your pass phrase. But some fields are left in the clear. In particular, the number of bits in p and q is left exposed, as is the number of bits in d, the decryption exponent. Now, this is not really a big deal. Usually with a 1024-bit key p and q will both be 512 bits long, so knowing this for sure doesn't add that much information. And I don't think that knowing the exact number of bits in the factors will help with the factoring when the two factors are about the same size. Nevertheless it does represent an information leak that many people may not be aware exists. One way an attacker might exploit this is as follows. Suppose he wants to do an exhaustive search of pass phrases. As Tim said, a lot of people may have ones which are easy to guess. How does he know when he's guessed correctly? The secret key has a checksum (in the clear). After decrypting all of d, p, q, and u, PGP accumulates a checksum as it does this and com- pares it with the checksum stored in the secret key. If they match, PGP (or the cracker) knows that he has used the right pass phrase. This requires decrypting all four of these numbers, a total of about 320 bytes. But he can do a provisional check much faster by using the in-the-clear lengths. Just decrypting the first byte of each MP number allows you to see immediately what the bit length of the resulting MP value will be since they are stored in MSB form. For the most extreme case, suppose the length of p were one more than a multiple of 8, say 505 bits. Now we decrypt the first part of p and see if the first byte of the decryption is exactly 1. If not, we can know immediately that we have the wrong pass phrase and move on without doing any more IDEA op- erations. This will immediately reject 255 out of 256 wrong pass phrases. I don't know how much of a speedup you would actually see from this; IDEA has a setup phase and you still have to run MD5 on each pass phrase. But possibly it could be significant. Hal Finney hfinney@shell.portal.com