headers
Brent Waters | 5 Jul 2005 01:03
Picon

Chosen-ciphertext attack on receiver anonymity


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

I have been discussing this type of a problem in the context of BCC 
privacy for email programs with Adam Barth and Dan Boneh. However, there 
could be wider implications as PGP is used in other contextes.
Anyway, I would be interested to hear comments.

Regards,
(Continue reading)

Permalink | Reply | 0 comments |
headers
Hal Finney | 5 Jul 2005 01:59

Re: Chosen-ciphertext attack on receiver anonymity


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
(Continue reading)

Permalink | Reply | 502 comments |
headers
Peter Gutmann | 5 Jul 2005 05:13
Picon
Picon
Picon
Favicon

Re: Chosen-ciphertext attack on receiver anonymity


hal <at> finney.org ("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.
Permalink | Reply | 504 comments |
headers
Brent Waters | 5 Jul 2005 06:49
Picon

Re: Chosen-ciphertext attack on receiver anonymity


> 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.
As Peter pointed out, I was using GNUPG command-line terminology. However, 
it seems we are talking about the same thing.

> 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.
(Continue reading)

Permalink | Reply | 0 comments |
headers
Werner Koch | 5 Jul 2005 09:31
Picon
Favicon

Re: Chosen-ciphertext attack on receiver anonymity


On Tue, 05 Jul 2005 15:13:53 +1200, Peter Gutmann said:

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

> 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

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

Salam-Shalom,

   Werner
Permalink | Reply | 2 comments |
headers
Werner Koch | 5 Jul 2005 09:36
Picon
Favicon

Re: Chosen-ciphertext attack on receiver anonymity


On Mon,  4 Jul 2005 16:59:00 -0700 (PDT), "Hal Finney" said:

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

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.

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

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
Permalink | Reply | 0 comments |
headers
Peter Gutmann | 5 Jul 2005 10:13
Picon
Picon
Picon
Favicon

Re: Chosen-ciphertext attack on receiver anonymity


Werner Koch <wk <at> gnupg.org> writes:
>On Tue, 05 Jul 2005 15:13:53 +1200, Peter Gutmann said:
>> 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
>
>Decryption are 38 lines including verbose error checking and status
>reporting.

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.
Permalink | Reply | 1 comment |
headers
Ian Grigg | 5 Jul 2005 12:35

Re: Chosen-ciphertext attack on receiver anonymity


On Tuesday 05 July 2005 00:59, Hal Finney wrote:
> 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.
...
> 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.

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

> 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?
(Continue reading)

Permalink | Reply | 0 comments |
headers
Ian Grigg | 5 Jul 2005 13:20

Re: Chosen-ciphertext attack on receiver anonymity


On Tuesday 05 July 2005 04:13, Peter Gutmann wrote:

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

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

To which Brent answered:
> 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.

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
(Continue reading)

Permalink | Reply | 5 comments |
headers
Derek Atkins | 5 Jul 2005 21:16
Favicon

Meet in Paris?


Hi,

Do the members of this working group feel we need a meeting
in Paris?  I think we might want to meet in order to consider
work beyond 2440bis (e.g. PFS, Mail-Headers, or other work
that's been proposed).

If you feel strongly that we either should or should not meet
in Paris, please let me know.

If you have a non-2440bis work item that you'd like (Ben: This is
a hint to you) please let me know how much time you'd like on
the agenda to discuss your new work items.

Thanks,

-derek, your friendly neighborhood chair
--

-- 
       Derek Atkins                 617-623-3745
       derek <at> ihtfp.com             www.ihtfp.com
       Computer and Internet Security Consultant
Permalink | Reply | 8 comments |

Gmane