Subject: Re: Chosen-ciphertext attack on receiver anonymity

From: [email-masked] ("Hal Finney")
Date: Mon, 4 Jul 2005 16:59:00 -0700 (PDT)

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

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 05 Jul 2005 15:13:53 +1200

[email-masked] ("Hal Finney") writes:

>I'm not familiar with this term "throw-keyid". 

It's somewhat confusing GPG terminology.

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

It's not just misleading, it's an absolute bastard to support for
implementors.  So I think it should be deprecated not only because it serves
little useful purpose, but also because the large amount of complexity added
in supporting it isn't reflected by any matching payback in security.

Peter.

---

From: Brent Waters <[email-masked]>
Date: Mon, 4 Jul 2005 21:49:45 -0700 (PDT)

>   valid decrypted session key. This format helps reduce traffic
As Peter pointed out, I was using GNUPG command-line terminology. However, 
it seems we are talking about the same thing.

> does not provide strong anonymity and should not be relied upon for

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

---

From: Werner Koch <[email-masked]>
Date: Tue, 05 Jul 2005 09:36:36 +0200

> it until we are willing to do the work necessary to do the job right?

For one recipient it is actually a valuable feature.  MTAs using this
to hide BCC messages are of course not using it proper - they need to
send several messages.

> does not provide strong anonymity and should not be relied upon for

A word on that there are problems when used with more than one
recipient would be good.  However, the wild card keyID is an OpenPGP
feature and how it it used is more a matter of the actual
implemention.  I'll add a warning to gpg's man page.

Shalom-Salam,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Tue, 05 Jul 2005 09:31:15 +0200

> It's somewhat confusing GPG terminology.

I agree that --hidden-recipient is a better name; however 7 years ago
someone asked for an option of this name to be able to send anonymous
messages to public newsgroups without prior negotiation of a one time
key.

> implementors.  So I think it should be deprecated not only because it serves

Decryption are 38 lines including verbose error checking and status
reporting.

Salam-Shalom,

   Werner

---

From: Ian Grigg <[email-masked]>
Date: Tue, 5 Jul 2005 12:20:28 +0100

> in supporting it isn't reflected by any matching payback in security.

Right, that's what I feared.  Has anyone actually
implemented it *and* seen a benefit out in the field?

> some applications might rely on the feature whether it was intended to be 

Bummer.  Well, any views from Hushmail or from
whoever is encrypting to alt.anonymous?

Is there any reason why it has to be supported?
It's a MAY - just don't support it would be one
answer.  Hushmail supporting it in their 'closed'
system is fine, and as soon as they go out into
the broader world this is at their risk.

Maybe just mark the feature as only supported
within a given cooperating group of users - so
Hushmail can do it within their users, but it
won't be supported outside?

> the feature fully or remove it. Which one to do probably depends on what 

I don't recall that the goals of PGP in the wider sense
ever really considered anonymity or psuedonymity
except in the sense of avoiding mistakes surrounding
meatspace identity and ending up with engineering
psuedonymity.  PGP history quite clearly expresses
that you can call yourself Micky Mouse, but it doesn't
extend much if any guarantees about whether the software
protects you against any threats that might arise in that
cartoon.

Certainly *this RFC* is not the place to start on that.
It would seem that we need some project or team
to explore the possibilities, and create some demo
patches to gpg, and a paper or two.  Starting another
RFC might be possible but on our current record, I'd
not suggest that.

iang
-- 
Advances in Financial Cryptography, Issue 2:
   https://www.financialcryptography.com/mt/archives/000498.html
Mark Stiegler, An Introduction to Petname Systems
Nick Szabo, Scarce Objects
Ian Grigg, Triple Entry Accounting

---

From: [email-masked] (Peter Gutmann)
Date: Tue, 05 Jul 2005 20:13:06 +1200

>Decryption are 38 lines including verbose error checking and status

Well, in your implementation perhaps.  If you've got an interface that
supports a general-purpose key-fetch (fetch the key for this person or this
ID), not only is there no easy way to say "keep fetching whatever keys happen
to turn up until I tell you to stop" without maintaining state in the key-
source (making it non-multithreadable), but handling all of this stuff in an
implementation that's designed for "identify-key, fetch, decrypt" greatly
complicates the code.

Peter.

---

From: Ian Grigg <[email-masked]>
Date: Tue, 5 Jul 2005 11:35:49 +0100

>    valid decrypted session key. This format helps reduce traffic
...
> to consider.  However, strong anonymity is not something we have aimed

Yes.  This has never been a direction the project
that I've known, and has always been something
thrust up to the human layer as a "maybe".

> does not provide strong anonymity and should not be relied upon for

I think the paragraph covers all that adequately,
in that it is already a MAY, and the purpose says
that it "helps" to reduce TA.

We can't expect the RFC to teach basic crypto
or basic security.  This group and other resources
exist to fill in the gap.

OTOH, I must admit to being mildly conflicted about
the feature.  I think it was I who suggested it, and I
was somewhat surprised when it was accepted.  I
personally would have shot it down as an uneccessary
complication, myself ;-)  But it is only a MAY and I
can't quite put my finger on where it would cause a
problem to a developer.

iang

---

From: Jon Callas <[email-masked]>
Date: Wed, 6 Jul 2005 22:35:54 -0700

> implemented it *and* seen a benefit out in the field?

I think we should leave it the way it is.

Sorry. I want to put this RFC to bed, and that means we have to stop 
making tweaks.

	Jon

---

From: Ian Grigg <[email-masked]>
Date: Thu, 7 Jul 2005 14:06:59 +0100

> Sorry. I want to put this RFC to bed, and that means we have to stop 

I agree with anything that completes the RFC.  It's
been too long.

(In this case it is already a MAY so it's a teacup
looking for a storm.)

iang

---

From: Werner Koch <[email-masked]>
Date: Wed, 06 Jul 2005 12:09:58 +0200

> Well, in your implementation perhaps.  If you've got an interface that

It is an optional feature so I believe it is okay to just throw an
error if you can't find the key 0x0000000. 

> source (making it non-multithreadable), but handling all of this stuff in an

Agreed. I have another implementation where I can't enumerate the keys
and then it also won't work unless one implements an option to define
a list of keys to check on a wildcard keyid.

Shalom-Salam,

   Werner

---

From: Werner Koch <[email-masked]>
Date: Fri, 08 Jul 2005 09:05:16 +0200

> I think we should leave it the way it is.

Agreed.

> Sorry. I want to put this RFC to bed, and that means we have to stop

Yes please.

Shalom-Salam,

   Werner

---

From: Brent Waters <[email-masked]>
Date: Tue, 12 Jul 2005 16:18:20 -0700 (PDT)

It seems from everyone's comments that there is a desire/need to complete 
this particular RFC, which makes sense.

I do think, however, that it would also make sense to eventually define an 
encryption standard that has "Key-Privacy" built in. I think the norm 
should be for the ciphertext not to reveal the receiver's identity. If 
an application wishes to do so they can always tag the ciphertext with the 
identity and an application that does not wish to do so is not forced to.

Anyway, if anyone has interest furthering this idea on a different venue 
let me know.

-Brent

On Wed, 6 Jul 2005, Jon Callas wrote:

> Sorry. I want to put this RFC to bed, and that means we have to stop making 
> tweaks.
>
> 	Jon
>
>

---

From: Adam Back <[email-masked]>
Date: Wed, 20 Jul 2005 16:08:26 -0400

There was some work done on this as a filter to pgp (2.x) called
pgpstealth [1].

Basically it should be able to make a reversible transformation where
the output has unbiased rectangular distribution throughout (for both
key-transport, and remove any boilerplate).

openpgp has become a bit more complex since pgp2x but I think there
are potential customers for this -- as input to steganography
programs.

There was some discsussion a long time ago now in the context of the
feature under discussion here of whether pgpstealth-like functionality
could be added as a builtin feature of a pgp implementation.  

As an external filter I'm not sure the 0x000... or short keyid would
really help the transformation because the transformation has to
anyway be wrt a specific key.  ie so you're actually trying each key
with a trial transformation so it would actually hook either
externally where the empty keyid picks a key, does trial
transformation, tries to decrypt, fails, skips to the next keyid in
the keyring.

Of course there are also other potential uses for hiding the recipient
-- broadcast of a message (eg to alt.anonymous.messages), where the
recipient is by prior arrangement scanning for messages he can
decrypt.

Anyway pgp-stealth is at present a bit of an orphan project.  It might
be interesting / useful to update it as a standalone filter working
with openpgp or re-write it as a gnupg extension, or something like
that.

Adam

[1] http://www.cypherspace.org/openpgp/stealth/