crypto flaw in secure mail standards

[dmolnar]

On 22 Jun 2001, Derek Atkins wrote:

> the set {Alice,Bob,Charlie,Daniel,Eve,Fred,Greg}, there is no way to
> know which of them sent it.  All members of the set must be mutually
> trusted, which means there is no way to sign a document that a set of
> people can verify comes EXACTLY from you.

Good point. There's always the approach of Alice sending each of
Bob,Charlie,Daniel,Eve,Fred,Greg a separate individual DVP, but this
incurs undesirable overhead. Plus Alice could send them all slightly
different messages and they'd be unable to prove to each other that she
was trying to trick them.

The original Impagliazzo, Jakobsson, Sako paper partially adresses this.
Their method of implementing designated verifier proofs is to perform
proofs of the form

	"Either A is true OR I know secret key K."

In the peer-to-peer case, A is "document signed by Alice" and K is Bob's
private key. So Bob knows the document is real (assuming he hasn't lost
K), but no one else can be sure that he has not faked the proof/forged a
signature.

Their suggestion for multiple recipients is to have all the recipients
share a key K. Following your example, Bob,Charlie,Daniel,Eve,Fred, and
Greg generate a secret key using some distributed algorithm such that they
each have a share of the key and all shares are required to reconstruct.

Now when Alice sends the document to them, each one knows, given that
their share is safe, that the document really did come from Alice. An
outside observer, on the other hand, has to consider the possibility that
the group got together to forge a signature with their knowledge of K.
(This forgery can also be done in a distributed manner, so faking one
signature doesn't reveal the full key K to anyone).

There are at least two flaws with this approach. The first is that it
seems to require a new key K for each group of receipients. This may be
adressable through the use of group signatures. I haven't thought about it
much. I suspect this flaw is closest to the objection you raised.

The second flaw is tangential, but I think worth noting. The flaw is that
the members of the group must collaborate in order to forge a signature.
Whether or not the designation "works" depends on whether or not it is
plausible that the group members would collaborate.

For instance, suppose that a message is designated to Bob and Carol, who
are the heads of state of two warring countries? (The scene from "13 Days"
with its "these assurances can never be made public" comes to mind, but
isn't quite right).

It is not plausible that Bob and Carol would create a shared key K in the
first place, never mind collaborate to forge a signature. If the message
leaks and is published, Alice cannot convincingly argue that Bob and
Carol signed the message instead of her. This might be bad. So the issue
becomes not so much one of efficiency, but repudiation.

So how do you do designated verifier proofs with multiple
non-collaborating verifiers?

I think this may be partially adressed as follows:
Suppose Alice wants to designate a message to Bob and Carol. Alice sends
to Bob
	M, X_B := E_C( DVS(M,Carol)) , DVS("X_B := E_C(DVS(M,Carol))", Bob)

and to Carol sends
	M, X_C := E_B(DVS(M,Bob)), DVS( "X_C := E_B(DVS(M, Bob))", Carol)

Here M is the message, and by "X :=" I am giving a definition of X.
DVS(E,F) stands for "A non-interactive designated verifier proof of E
which is designated to F." E_B and E_C are public-key encryption using Bob
and Carol's public keys respectively. The notation is slightly
inconsistent as written, because by "DVS(M, Carol)" I really mean a
signature of M designated to Carol, while by "DVS( "X := E_C(DVS(M,
Carol))", Bob) I mean a proof that X is a valid encryption of a designated
verifier signature.

I claim that this gives us a signature in which

	1) Carol can determine that M is signed by Alice
	2) Carol can determine that M will be verified by Bob as
	being signed by Alice if she presents X to Bob and he decrypts
	it to find M
	3) Carol cannot prove 1) or 2) to anyone else.

Proof:
	1) The DVS("X_C := DVS(M,Bob)", Carol) proves that Alice
	knows a signature from Alice designated to Bob on M. If Carol is
	willing to assume Alice does not know Bob's private key,
	this is enough. Otherwise she can require a separate
	DVS(M, Carol).

	2) The DVS(X_C := E_B(DVS(M,Bob)), Carol) convinces Carol that
	Bob can decrypt X_C to obtain a valid designated verifier
  	signature of M. This is required to prevent Alice from sending
	different messages to Bob and Carol; while it won't catch
	Alice immediately, it will allow Bob and Carol to determine
	that such cheating has occured (they exchange their X values and
	find that they are different messages).

	3) All these signatures are designated verifier for Carol.

and the above is similar for Bob.

For three designees, Bob, Carol, and David, Alice prepares

Bob
	M, X_B1 := E_C(DVS(M, Carol)), DVS (X_B1 := E_C(DVS(M,Carol)),Bob)
	M, X_B2 := E_D(DVS(M, David)), DVS (X_B1 := E_C(DVS(M,David)),Bob)


Carol
	M, X_C1 := E_B(DVS(M, Bob)), DVS(X_C1 := E_C(DVS(M,Bob)),Carol)

	M, X_C2 := E_D(DVS(M, David)), DVS(X_C2 := E_C(DVS(M,David)),Carol)


David
	M, X_D1 := E_B(DVS(M, Bob)), DVS(X_D1 := E_B(DVS(M,Bob)),David)
	M, X_D2 := E_C(DVS(M, Carol)), DVS(X_D2 := E_C(DVS(M,Carol)),David)

For four or more the construction is similar.

Note that the length of the signature grows linearly in the number of
designees. So if there are n designees, Alice has the pleasurable job of
computing n^2 messages, none of which are nice by themselves. My guess is
that there's some cute combinatorial result I don't know which will make
this easier or show it optimal.

The issue now is proving that a string X is a valid encryption of a
designated verifier signature. Note that this is a statement with a
succinct polynomial time certificate, namely the transcript of the program
used to create these messages. So by the generic GMW theorem that all NP
statements have ZKPs, plus random oracles to make them noninteractive, we
know this can be done. by foolhardy masochists, anyway.

A better solution seems to be to note that the IJS paper implements
designated verifier signatures as ordinary signature schemes + a chameleon
commitment function. I will consider chameleon hash functions (introduced
by Rabin and Krawczyk) instead. A chameleon hash function is a public hash
function with a secret key; knowing the key allows you to produce
arbitrary hash collisions easily, while finding collisions remains
intractable without the key.

Chameleon hash functions are randomized, so they take the form
CHAM-HASH(Key,M,r), where "Key" is the public description of a particular
entity's hash. For example, CHAM-HASH(Alice,M,r1) means "the string
resulting from a hash of M with Alice's chameleon hash and random value
r1". Alice would be able to find a collision for this value, but no one
else. A designated verifier signature from Bob to Alice then consists of
SIG(CHAM-HASH(Alice,M,r1)), where SIG() is any ordinary signature scheme.
Because Alice can create arbitrary collisions in CHAM-HASH, Alice cannot
credibly claim that this signature refers to a particular M.
(it occurs to me that this still shows that Bob sent Alice *a* message).

The idea is that we can leverage this to use existing protocols for
verifiable encryption of signatures. Alice tells Carol how to obtain the
same hash string S for M as the one Alice used for her DVS for Bob. Then
Alice just needs to show that a string X is a proper encryption of an
*ordinary* signature.

More formally, if Alice wishes to construct
X_C := E_B(DVS(M,Bob)), DVS(X_C := E_B(DVS(M,Bob)),Carol)

then she does the following

	1) Computes S := CHAM-HASH(Bob,M,r1)
	2) Computes SIG(S)
	3) Computes X_C := E_B(SIG(S)). Sends X_C to Carol.
	4) Sends r1 to Carol. Carol computes S := CHAM-HASH(Bob,M,r1)
	5) Alice proves that X_C := E_B(SIG(S)) to Carol

Note that under the assumption that Alice does not know Bob's private key,
she must send Carol the correct r1 for M in step 4. Otherwise Alice could
compute a collision on S.

Now for step 5, we need a protocol for verifiable encryption of
signatures, i.e. a way to show X_C := E_B(SIG(S)) without needing D_B().
Reuben Sumner pointed out Asokan, Shoup, and Waidner made use of these
protocols in their fair exchange protocol. Giuseppe Atienese has a few of
them as well.

I think that may do it. Now the members of the group can all verify that
they received the same message M from Alice by exchanging their X values,
yet none of them can claim to outside parties that Alice signed M. I'm
sure there's a better way; this feels a little bit inelegant/obvious...

-David





---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com