From: Hal Finney <hal@rain.org>
Date: Mon, 14 Oct 1996 11:37:48 -0700 (PDT)
To: everheul@mail.rijnhaave.nl
Subject: RE: RE: Binding cryptography - a fraud-detectible alternative to
Message-ID: <199610141822.LAA06792@crypt>
MIME-Version: 1.0
Content-Type: text/plain


From: everheul@mail.rijnhaave.nl
> Hal Finney[SMTP:hal@rain.org] wrote:
> >Another flaw with schemes of this time (in terms of failing to meet
> >their goals) is that they cannot detect superencryption and other
> >forms of non-standard encryption of the message body proper.  All
> >they can really do is verify from the outside that the same session
> >key is encrypted for the two recipients (the intended recipient and
> >the Government Access to Keys Party - let's not abuse the term by
> >calling him a Trusted Third Party).  But they can't be sure that the
> >session key is sufficient information to decrypt the message.
> We offered a solution for the *first* task not for the *second*; the
> point is that criminals(!) do not gain any real advantage from using
> the system in that way as they - among other things - still face the
> key-management problem. The above dicussions are only relevant in
> countries where the use of crypto outside the structure would be
> prohibited. BTW, it is by such discussions that I believe such a ban
> is ineffective and in fact counterproductive.

I have not read your paper, but let me illustrate via what may be
a similar scheme how criminals can use the key management infrastructure,
create messages which look good from outside, yet which still cannot
be read by the GAK (government access to keys) people.

In ElGamal encryption we start with a message session key M which we
want to send across.  We have the public key y1 = g^x1 of the recipient
(^ is exponentiation).  We choose a random blinding factor xm, and
calculate ym = g^xm.  We send ym and M * (y1^xm).  y1^xm equals
g^(x1*xm), and the recipient can recover this by ym^x1.

Now with two recipients, if we choose the same blinding factor xm for
both, we send ym = g^xm, and both M * (y1^xm) and M * (y2^xm).  We use the
two different recipients' public keys y1 and y2.  I believe this can be
checked from outside by taking the ratios of these two factors (y1/y2)^xm
and using known methods to prove that this is of the proper form.

This can be circumvented though simply by replacing M, the true session
key, with M' = M*(y1^xm), where y1 is the intended recipient (and y2 is
the GAK party).  We send M'*(y1^xm) and M'*(y2^xm).  Outsiders still
verify that this is of the proper form.  And the intended recipient
can calculate the true M by dividing twice by y1^xm instead of once
(in effect M' is the El Gamal encryption of M for party 1).  But the GAK
party, who gets M'*(y2^xm) and recovers M', finds it useless in trying
to decrypt the message.

This shows how keys from a standard infrastructure can be used in a
slightly non-standard way to confound your scheme.  Granted, the parties
involved have to share knowledge about using the keys in this non-
standard way, but that is only one bit of information and not at all
hard to distribute.

Hal