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

From: "Hal Finney" <[email-masked]>
Date: Wed, 17 Apr 2002 18:58:20 -0700

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.

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

My main concern is not so much with the operational complexity; as you
say, the software could automatically create the right kind of signature
in most cases.  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.  It's completely different from
a regular signature; for one thing, Alice doesn't even have to type her
passphrase, because her signature key is not used when she creates this
kind of "signature"!  Imagine the paranoia that would trigger on the PGP
user lists.  In general it's going to increase the explanatory burden
for people who want to understand what the software is doing.

I am also concerned about the security of this specific construction,
Sign_Alice(Encrypt_Bob(K)), MAC(K,Msg), Msg.  (Also applies to
Sign_Alice(Encrypt_Bob(K)), Encrypt(K, Msg).)  One attack I noticed is
that if Bob accidentally reveals K to an eavesdropper Eve, Eve can replay
the Sign_Alice(Encrypt_Bob(K)) block and replace the Msg with her own.
To defend against this either Bob could keep a list of recently used
K values (and perhaps include timestamps in the signed block).  Or of
course he could just be careful about leaking K, but it is an important
consideration for the designer.  It would be nice to see some security
proofs for this construction.

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.

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.

BTW please do not forward this message elsewhere; by our company policy we
are supposed to restrict technical discussion of cryptography to research
oriented forums, and this list counts for that, but not most others.

Hal

---

From: Adam Back <[email-masked]>
Date: Thu, 18 Apr 2002 14:44:54 +0100

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

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

> that the message came from Alice or someone on the recipient list.

Yes see above.

> 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

---

From: Adam Back <[email-masked]>
Date: Fri, 19 Apr 2002 03:19:45 +0100

Hal Finney wrote:
> I don't think that works for multiple recipients, because any recipient
> can recover K, alter the msg, and re-create an apparently valid message
> that would be accepted by other recipients.  Alice's signature is only
> on K and public keys so that part doesn't change when the msg does.

You're right.  That doesn't work.  See below...

On Wed, Apr 17, 2002 at 06:58:20PM -0700, Hal Finney wrote:
> [...]

On the simple hash/encrypt approach, I think this should work:

Alice sending non-transferably signed message to Bob and Charlie:

Encrypt_Bob(K_B), Encrypt( K_B, Sign_Alice(K_B||Bob), H(msg) ), 
  Encrypt_Charlie(K_C), Encrypt( K_C, Sign_Alice(K_C||Charlie), H(msg) ), 
  msg

the message could optionally be encrypted using standard multiple
recipient technique (just include common key K):

Encrypt_Bob(K_B,K), Encrypt( K_B, Sign_Alice(K_B||Bob), H(msg) ), 
  Encrypt_Charlie(K_C,K), Encrypt( K_C, Sign_Alice(K_C||Charlie), H(msg) ), 
  Encrypt( K, msg )

The Encrypt() function should include MDC in both uses.

Bob can't transfer signatures as all he has is a signature that he
received a message from Alice and a random key.  He could forge any
message to himself with that information.

Similarly Bob and Charlie collaborating also can not transfer
signatures from Alice as they can collaboratively forge any message to
themselves.

As long as K_B is kept secret Bob is sure Alice sent him the message,
but can't convince anyone else of this fact.

Bob can't forge a message from Alice to Charlie with the information
he sees as he doesn't see Sign_Alice(K_C||Charlie), and can't
transform Sign_Alice(K_B||Bob) into that, and he doesn't know KC so he
can't decrypt to find out, nor can he modify the encryption because of
the MDC also keyed via K_C.

Adam
--
http://www.cypherspace.org/adam/