Possible chosen-ciphertext attack on receiver anonymity

Brent Waters bwaters at theory.Stanford.EDU
Thu Jun 30 21:35:12 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 problem.

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