Re: Chosen-ciphertext attack on receiver anonymity

[Brent Waters <[e-mail]>]

> 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