Brent Waters writes:
I wanted to bring up an issue that had to do with chosen-ciphertext
attacks on receiver anonymity.
The specific case I am worried about is when the "throw-keyid" option is
used to encrypt a message to multiple recipients. My understanding is that
the throw-keyid option should hide the identity of the a receiver of the
message (by throwing away the key-id) even from other receivers of a
message.
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.
Suppose I made such an encryption of M to Alice and Bob, then the
hybrid encryption (at a high level) would look something like this:
1)Choose random symmetric key key K
2)Ciphertext: (C1,C2,C')=E_{KeyAlice}(K)E_{KeyBob}(K),E_K(Message)
where C1,C2 are asymmetric encryption and C' is a symmetric key
encryption.
At this point Alice and Bob can both decrypt the message, but neither can
tell if the other was the other receiver. Suppose Bob suspects Alice was
the other receiver. Then he can create a ciphertext:
(C1,C'')=E_{KeyAlice}(K)E_K(NewMessage)
and send this to Alice, if Alice responds to this in a meaningful way she
was the other receiver. NewMessage could be something simple like "Do you
want to go to lunch?" which would likely elicit a response. Note, this can
be a problem even if the ciphers are CCA-secure.
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.
Hal Finney