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

[Adam Back <[e-mail]>]

On Wed, Apr 17, 2002 at 06:58:20PM -0700, Hal Finney wrote:
> 
> Adam Back writes:
> > 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
> 
> I haven't been able to get through to this site; I'll try again later.

(Seems to be reachable now.)  What we proposed is related.  Rather
than the normal encrypted signed message:

	Encrypt_Bob(K), Encrypt(K, Sign_Alice(Hash(msg)), msg)

we proposed:

	Encrypt_Bob(K), Encrypt(K, Sign_Alice(Hash(K||Bob_PK)), msg)

with the additional restriction that the encryption mode should be one
of the MDC modes (ie appended MAC with K outside encryption, or
appended hash of msg inside encryption).

To break that down: we hash Bob's public key so that Bob can't turn
around and forge an arbitrary an arbitrary message from Alice to
Charlie using signed K.  What Bob is left with is proof that Alice
sent him a message, but no evidence of what the message body was.

The approach generalises to multiple recipient's: either hash in all
of the recipient public keys, or include signatures for each recipient
-- the latter is probably preferable as then the recipient doesn't
need all the other recipient's public keys to verify.

> > 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).
> 
> Well, you can sign without encrypting the message by using the shared
> key to MAC the message rather than encrypt it, although you're right
> that there still has to be an element of encryption involved, and you
> do need to know who the recipient is.

Yes.  Needing to know who the recipient is was what made us feel a
natural place to put non-transferable sigantures was inside encryption
-- to avoid adding a confusing extra restriction and avoid causing
wide-ranging changes to the code, APIs and command line and GUI.

> My worry is more with the understanding on the part of the users as
> to what kinds of security guarantees they are getting.  Descriptions
> of digital signatures are widely available, and the motivated user
> has many sources he can go to in order to learn about how signatures
> work.
> 
> If we introduce these non-transferable signatures (good name btw) then
> there is more possibility for confusion.  

Indeed.  One aspect of our proposal which may be good is that
extracting a signature contained inside an encrypted message is
already not directly supported.  So nothing _new_ has been added from
the users perspective -- rather that feature has been
cryptographically assured rather than just being an unimplemented
implementation possibility.

You're right that it may confuse, but they won't be directly exposed
to it unless they dig under the hood.

Seems somewhat reasonable that people who are paranoid enough to not
want transferable signatures should also use encryption.  The kinds of
things they are worrying about -- eg off the record remark becoming on
the record and involved in a dispute -- are best also protected by
encryption as courts seem to view plaintext as evidence and
unauthenticated company and ISP mail logs things like that.

> Is there an extension of this to the multi-party case?  It doesn't
> work to use the simple idea of having Alice encrypt K to each recipient
> and sign those encryptions, then MAC (or encrypt) the message with K.
> The problem is that each recipient learns K, hence any of them might have
> created or altered the message body.  Each recipient is only convinced
> that the message came from Alice or someone on the recipient list.

Yes see above.

> Logically it seems to me that for this to work the message has to be one
> which was constructable either by the signer, or by the collective effort
> of all the recipients WORKING TOGETHER.  In this way, each recipient
> can know that, since he did not collude with the other recipients to
> make the message, it must have come from the claimed signer, making
> the signature convincing.  But outside parties cannot rule out the
> possibility that the recipients collectively "forged" the message,
> making the signature non-transferrable.
> 
> This concept can be applied pretty straightforwardly to the mathematical
> key-combining technique, I think (I figured out how to do it once) but
> I don't see how to use the simple hash/encrypt trick to accomplish this.

We also looked a bit at a group signature with a similar property to
the one you reference in Rivest et al's paper.  The reference I have
for it is:

Bernardo A. Huberman, Matt Franklin and Tad Hogg: Enhancing privacy
and trust inelectronic communities. ACM Conference on Electronic
Commerce, 1999, pp.78-86.

	http://citeseer.nj.nec.com/365811.html

however that paper also references some earlier work.

By combining the approach with these group signatures you reduce the
proof Bob ends up with.  Instead of a proof that Bob received a
message from Alice, but no proof of message content, Bob ends up with
a proof that either Alice sent him a message or he forged a message to
himself from Alice.

I agree with your collective effort argument for the generalized
version of this with multiple recipients.


It's all fairly related to forward secrecy also -- another form of
proof of authorship is for a court with a copy of a ciphertext to
demand appropriate private keys and verify for themselves.  This in
theory could have been forged, but they'll have mail headers and a
tendency to believe that Bob did not think ahead and forge a mail to
yourself pretending to be Alice.

Adam