I'm not familiar with this term "throw-keyid". We don't use it in
RFC2440-bis as far as I know. I think however that you are referring
to this feature discussed in section 5.1:
An implementation MAY accept or use a Key ID of zero as a "wild
card" or "speculative" Key ID. In this case, the receiving
implementation would try all available private keys, checking for a
valid decrypted session key. This format helps reduce traffic
analysis of messages.
As Peter pointed out, I was using GNUPG command-line terminology. However,
it seems we are talking about the same thing.
That does seem to be a valid attack against the anonymity. However
you should be aware that OpenPGP is not trying to provide very strong
anonymity here. No effort is made to obfuscate the key size, for example,
so unusually sized keys tend to reveal themselves. All the RFC phrasing
suggests or claims is that it can "help reduce" traffic analysis.
If we really wanted to guarantee strong anonymity I think we would have
to do quite a bit more work here. Your attack is definitely something
to consider. However, strong anonymity is not something we have aimed
to provide.
Given the weak level of anonymity it affords, perhaps the zero keyid
feature is misleading to users? If so, should we consider deprecating
it until we are willing to do the work necessary to do the job right?
Or we could at least put a note in the RFC emphasizing that this feature
does not provide strong anonymity and should not be relied upon for
that purpose.
Yes, there are certainly other issues in anonymity. Even if two keys are
the same number of bits there could be attacks. E.g. If 110000001 and
100000001 were both primes used for different ElGamal keys and adversary
would still have a significant advantage in distinguishing the receiver.
Having common ElGamal NIST primes would take care of this and have the
small benefit of faster key generation. This is discussed in a Bellare
paper: http://www-cse.ucsd.edu/users/mihir/papers/anonenc.html .
The thing unique about the attack I described is that no one has
considered a definition "Key-Privacy" in the multiple recipient
case. However, I believe a solution from "commodity parts" can be made.
As far as whether it is a problem, I believe that Hushmail uses such
feature to implement BCC functionality. Also, I PGP is used in some other
contexts such as newsgroups like alt.anonymous. In short it seems that
some applications might rely on the feature whether it was intended to be
strong or not.
In the short term it might help to serve notice in some way.
Perhaps a note of the RFC would be good. While there does seems to be a
bit of work to do, it seems feasible to implement the feature properly.
My opinion is that eventually it would probably be best to either provide
the feature fully or remove it. Which one to do probably depends on what
goals of PGP are.
-Brent