Possible chosen-ciphertext attack on receiver anonymity

Brent Waters bwaters at theory.Stanford.EDU
Thu Jun 30 19:16:01 CEST 2005


I thought that there might be a chosen-ciphertext attack on receiver 
anonymity for a message to multiple recipients. I wanted to check my 
understanding of how GPG handles a certain case to see if this is a 

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. 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 

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:
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.

Anyway, I wanted to see if my understanding of how this was implemented 
was correct. Can anyone comment on this?


More information about the Gnupg-devel mailing list