Possible chosen-ciphertext attack on receiver anonymity

[Werner Koch]

On Thu, 30 Jun 2005 10:16:01 -0700 (PDT), Brent Waters said:

> 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

That is correct.  The message or the session key K don't depend on the
public keys used.  It is trivial possible to add new E_{keyN}(K) to an
OpenPGP message.

A simple way for a client to avoid the attack is by keeeping a list of
seen session keys; they should be random and thus a duplicated one
will be suspicious.  It is not really practical to implement such a
feature.

In fact the --throw-keyid feature is not intended to hide the keys
between the set of recipients but to keep the recipients secret for
outsiders.  Its main use is with anonymous remailers:

   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.

I know that some folks are using the --hidden-encrypt-to feature (to
hide selected recipients) for their private archive copy of a mail.

For a future version of the OpenPGP message format it might make sense
to change the the format to something like E_{KeyN}(K|X) with X being
the total number of keys used to encrypt the session key or better a
hash of all the public keys used.

Do you want to raise this problem with the OpenPGP WG?


Salam-Shalom,

   Werner