Recipient-verifiable messages, was: forwarding an encrypted PGP message is useless

["Hal Finney" <[e-mail]>]

[Redirected to just OpenPGP list.  I guess this was a Mozilla bug
discussion that someone copied here?]

Sam Roberts <[e-mail]> writes:
> S/MIME only uses the signed and enveloped types from CMS, but RFC2630
> specifies authenticated as well. Its not well described there, but it is a
> way of "signing" something using a key agreement algorithm, such that the
> signature can ONLY be verified by using the sender or the receiver's
> private key.

I haven't read this RFC, but I had a long discussion with Wei Dai last
year about ways to do this within the OpenPGP framework.  We came up with
a couple of ideas.  These might be called "recipient-verifiable" signed
messages, to distinguish them from the regular PGP signed messages which
are "world-verifiable".  The general approach is to make the message such
that the recipient could "forge" fake messages from the sender that look
legitimate to third parties.  This prevents the real message from being
shown around in a convincing way.

Wei suggested that the recipient-verifiable message from Alice to Bob
could be as follows:

Sign_Alice( Encrypt_Bob( K ) ), MAC_K( Msg ), Msg.

The idea is that Alice chooses a MAC key K, encrypts it to Bob and then
signs the encrypted packet.  She sends this, along with the MAC'd message,
to Bob.  Bob can recover K from the encrypted packet, verifying the
signature by Alice on that packet, and then verify the MAC.

But if Bob shows this to someone else, although he may be able to convince
them that K was signed by Alice, he can't show that Msg is what she sent.
Given K, Bob could have MAC'd any message with that K and replaced Msg
with that.  So there is no evidence that Msg is what Alice actually
signed, hence she is not bound by it.

A subtlety is that if you did Encrypt_Bob( Sign_Alice( K ) ) instead,
this would let Bob remove his encryption envelope and then re-encrypt
for someone else, making them think that Alice had directed the message
to them and letting them verify the signature.  So the reverse ordering
is important.

I proposed a different method, which basic idea is expressed in a paper
by Rivest, Shamir and Tauman, "How to Leak a Secret", available from
http://theory.lcs.mit.edu:80/~rivest/publications.html.  This paper shows
how to produce a signature which can be verified to be from a specific
list of keys, but you can't tell which key on the list made the signature.
It is very simple and efficient for RSA keys.  I think extensions are
possible for discrete log keys, but the paper doesn't cover that.

For the recipient-verifiable signature, Alice would create one of these
multiple-signer signatures based on exactly two keys, Bob's and hers.
Anyone can verify that the resulting message has been signed by Alice or
Bob, but there is no way to tell which.  Alice then sends the message
to Bob.  He knows that he didn't sign it, so it must have been Alice.
But if he shows it to someone else, all they can see is that either
Bob or Alice signed it, so Bob could have created a signature like this
for any message he wanted.  Again there is no way for Bob to show the
message convincingly to a third party, and Alice is protected.

David Chaum has a patent on a variation on this idea, and he gave a talk
at PGP several years ago in which he advocated that recipient-verifiable
signatures are very useful, and in fact ought to be the default for
an email encryption system like PGP.  As others in this thread have
commented, often you don't want to sign something such that you can
be bound by it later, but you do want to assure the recipient that the
message is authentic.  Only rarely do you want to make a signature that
anyone can read.

Unfortunately I think that adding a new flavor of signature would tend
to create confusion among users who at best barely understand public
key cryptography.  The new kind of signature would have very different
security properties and usage scenarios, so it would add additional
complexity for people to deal with.

Hal