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

From: "Hal Finney" <[email-masked]>
Date: Thu, 11 Apr 2002 08:45:39 -0700

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

Sam Roberts <[email-masked]> 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

---

From: "vedaal" <[email-masked]>
Date: Thu, 11 Apr 2002 16:43:56 -0400

----- Original Message -----
From: "Hal Finney" <[email-masked]>
To: <[email-masked]>
Sent: Thursday, April 11, 2002 11:45 AM
Subject: Recipient-verifiable messages, was: forwarding an encrypted PGP
message is useless
...

> message convincingly to a third party, and Alice is protected.
...
> complexity for people to deal with.
...

no new signature type is needed.
this can be done now with a split key setup, for either an RSA or DH key:

Alice or Bob produces a new key  'Alice&Bob'

the share is set for 1, and the 'Alice&Bob' key is split with a share to
Alice's key, and a share to Bob's key,

either Alice or Bob can now sign with the 'Alice&Bob' key, without anyone
being able to detect whether it was Alice or Bob,
and  it will verify as a good signature from the 'Alice&Bob' key.

the 'Alice&Bob' split key can be imported into gnupg and the signatures
verified,
but gnupg cannot (yet) rejoin, sign or decrypt with a split shared system

if this is worthwhile/necessary, perhaps it could be considered for addition
to the gnupg system.

hth,
vedaal

---

From: Jon Callas <[email-masked]>
Date: Thu, 11 Apr 2002 15:42:02 -0700

>complexity for people to deal with.

Could we do something both simple and useful, however?

For example, if I send a message to Alice, the signature could be made
safely as a combo of my key and Alice's key. It would not be a
misrepresentation in Alice's MUA for it to assume I signed it. You'd have
to be careful in the UI, but I think it could be done. It might be able to
be extended to multiple recipients, but with two it might be an easy
hand-wave.

	Jon

---

From: "David P. Kemp" <[email-masked]>
Date: Thu, 11 Apr 2002 20:06:33 -0400

> be extended to multiple recipients, but with two it might be an easy

What is the difference between a "recipient-verifiable signature" and
a MAC?

One of the properties of a digital signature mechanism is that it
is computationally infeasible for any entity other than the signer
to find, for any message, a signature value that is valid for that
message.  [HAC, p.23]

Thus it would seem that a "signature" that can't be bound later
to the signer is an oxymoron.  Why not just call it an authentication
code, where it is accepted that anyone who can verify a MAC has
the information necessary to create it.

---

From: Jon Callas <[email-masked]>
Date: Thu, 11 Apr 2002 17:29:42 -0700

>the information necessary to create it.

The obvious difference is this:

If the shared secret (shared by, say, Alice and Bob) used to generate a MAC
is leaked -- suppose Charlie learns it -- then anyone, Alice, Bob, or
Charlie can rewrite the MAC undetectably.

On the other hand if Alice generates one of these signatures and sends it
to Bob, a third party, Teresa can verify the signature but:

 * not be able to create one of her own and
 * cannot tell from the signature itself whether Alice or Bob made it.

I'm not sure how useful it is in the real world, but it's a fascinating thing.

I could sign a message to this list combining a dozen keys and thus create
a presumption that I made it without explicit demonstration of it.

	Jon

---

From: "David P. Kemp" <[email-masked]>
Date: Fri, 12 Apr 2002 18:44:58 -0400

> a presumption that I made it without explicit demonstration of it.

Thanks, Jon.  I'm still missing something though.

If the algorithm requires 1 private key and n-1 public keys to verify
(so that only the recipients can verify it), then Teresa, not being a
recipient of the original encrypted message but having a forwarded copy
of the decrypt, would not be able to verify it.

Thus by elimination you are talking about an algorithm that requires n
public keys to verify, and anyone can verify that one of n people
generated it without being able to tell which one. 
"Recipient-verifiable" seems like a misnomer for something that
recipients and not-recipients alike can verify.

Now assume that Alice gives something to Charlie, or a bug in her
software allows him to steal it.  Your job is to figure out whether
Charlie got hold of Alice's private key or the shared secret that Alice
derived from her private key and Bob's public key.

There are two possible algorithms: a
"signature-algorithm-that-is-not-a-MAC" that Teresa can verify, and a
MAC function whose key input is derived from Alice's private key and n-1
public keys.  What is the difference between those two algorithms with
respect to what they tell you about what Charlie got from Alice?  (Or
what they tell you about any other question you care to ask?)

In other words, the algorithm is a black box.  You can't see it, you can
only see the g'zoutas and you can do whatever you want with the
g'zintas.  Does the algorithm use a MAC or not?

If it walks like a MAC and it quacks like a MAC, then ...

---

From: Adam Back <[email-masked]>
Date: Thu, 18 Apr 2002 02:27:56 +0100

Only just saw this thread due to mailer config issue and Ian Brown
pointed it out to me.

The approach of signing encrypted key and using the key to MAC the
data is interesting.  It's very similar to what Ian and I proposed in:

Non-Transferable Signatures using PGP, Usenix Annual Technical
Conference, 98, Ian Brown and Adam Back

There's a short summary here:

	http://www.cs.ucl.ac.uk/staff/I.Brown/nts.htm

> complexity for people to deal with.

I don't think that so bad.  I think a reasonable approach for example
would be to by default non-transferably sign when messages are
encrypted and transferably sign when they are not (which makes sense
as it's probably what you want anyway as you described in a later
message, and with this particular scheme you can't sign without
encrypting).

btw We originally were going to put the non-transferable signature
stuff in the Forward Secrecy Extensions for PGP ID, but opted instead
to separate concerns and keep the ID simple.

	http://www.cypherspace.org/openpgp/pfs/openpgp-pfs.txt

Adam