Binding cryptography - a fraud-detectible alternative to key-esc

In this message, we introduce binding cryptography, a new proposal for
establishing an information security infrastructure that does not
hamper law enforcement. We present an alternative that can give
law-enforcement agencies access to session keys, without users having
to deposit private keys. Unilateral fraud in this scheme is easily
detectible. We outline the proposal below, and announce two articles
which will describe the proposal in more detail and which will provide
the legal and the technical context.

The text is also available at
http://cwis.kub.nl/~frw/people/koops/binding.htm.

9 October 1996
Eric Verheul, everheul@ngi.nl
Bert-Jaap Koops, koops@kub.nl
Henk van Tilborg, henkvt@win.tue.nl

-------------------------------------------

(c) 1996 Eric Verheul, Bert-Jaap Koops, Henk van Tilborg
This message may only be redistributed in its entirety and with
inclusion of the copyright notice. Credit if quoting.

_Binding Cryptography, a fraud-detectible alternative to key-escrow
proposals_

_1. Introduction_
Information security, and so cryptography, is essential in today's
information society. A robust (information) security infrastructure
must be set up, including a Key Management Infrastructure. However,
the unconditional use of encryption by criminals poses a threat to law
enforcement, a problem that is hard to solve. Consequently,
governments have two tasks. The first is stimulating the establishment
of a security structure that protects their citizens, but which does
not aid criminals. The second task is coping with the use of
encryption by criminals outside of this framework. We think that
encryption outside of the framework (e.g., PGP) should not be outlawed
- but it need not be mainstream either. It is crucial that any such
established security structure is widely accepted and trusted, as this
will lower the demand for encryption outside of this framework, and so
will make the second goal easier to achieve (or, at least, not more
difficult). The establishment of such a widely accepted and trusted
security structure is now the challenge that (US) IT businesses face
if they want to participate in the recent CLIPPER IV initiative.

_2. Binding cryptography_
In a series of two articles, we address the establishment of an
information security infrastructure. Several proposals have been made
by governments and others to establish such an infrastructure, but a
satisfactory overall solution remains yet to be found. In the
non-technical article [VKT], we review several technical proposals and
a few government initiatives, focusing on key-escrow proposals. We
present a series of criteria that acceptable solutions should meet,
and note that all proposals so far fail to meet many of these
criteria. We argued that the establishment of a worldwide security
infrastructure can not be achieved without strong cooperation of
governments. In fact, governments themselves should take up the
challenge of establishing a security infrastructure, based on
public-key encryption, which does not hamper law enforcement. We offer
a new solution to achieve this: "binding data", which also improves
upon current proposals. It has the advantage that it helps the
establishment of a strong security infrastructure which discourages
abuse for criminal or subversive purposes by making unilateral abuse
easily detectible. It allows a straightforward monitoring of
compliance with law-enforcement regulations, without users having to
deposit ("escrow") keys beforehand. Thus, an information security
infrastructure can be established, which does not worsen the crypto
problem for law enforcement.

Metaphorically speaking, our solution consists of equipping public-key
encryption systems used for confidentiality with a (car) governor (a
speed-limiting device). The specifications of this governor are rather
general, and so many systems can probably be equipped with them. It is
inspired by the proposal of Bellare and Rivest [BR], in which users'
encrypted messages consist of three components:
1. the (actual) message encrypted with any symmetric system, using a random session
key; 
2. the session key encrypted with the public key(s) of the addressee(s);
3. the session key encrypted with the public key of a Trusted Retrieval Party (TRP).

In effect, the TRP is treated as a virtual addressee, although the
message is not sent to it. When a law-enforcement agency is conducting
a lawful intercept and strikes upon an enciphered message, they take
the third information component to the TRP. If shown an appropriate
warrant, the TRP decrypts the information component and hands over the
session key, so that the law-enforcement agency has access to the
message. Observe that users are not obliged to escrow their (master)
keys, they only give access to the (temporary) session keys used in
the communication. The concept of "virtual escrow" has been the base
of several escrow products (AT&T Crypto, RSA Secure, TIS Commercial
Key Escrow).

The main drawback of this concept is that it offers no possibility, at
least for others than the TRP, to check whether the third component
actually contains the (right) session key; moreover, the TRP will only
discover fraud after a lawful wiretap. This renders the solution
almost entirely unenforceable.

Therefore, we propose a binding alternative, which adds a fourth
component to the encrypted message: 
4. binding data.

The idea is that any third party, e.g., a network or service provider,
who has access to components 2, 3 and 4 (but not to any additional
secret information) can: 
a. check whether the session keys in components 2 and 3 coincide; 
b. not determine any information on the actual session key.

In this way, fraud is easily detectible: a sender that attempts to
virtually address a session key to the TRP (component 3) that is
different from the real one he uses on the message (or just nonsense)
will be discovered by anyone checking the binding data. If such
checking happens regularly, fraud can be properly discouraged and
punished. The binding concept supports the virtual addressing of
session keys to several TRPs (or none for that matter), for instance,
one to a TRP in the country of the sender and one in the country of
the addressee. The solution therefore offers the same advantage for
worldwide usability as the Royal Holloway [Holl] concept. We also
remark that the concept supports the use of controllable key splitting
in the sense of Micali [Mica] as well: a sender can split the session
key and virtually address all the shares separately to the addressee
and various TRPs using the binding concept. Moreover, the number of
shares and the TRPs can - in principle - be chosen freely by each
user. Finally we remark that the time-boundedness conditon (the
enforceability of the timelimits of a warrant) can be fulfilled by
additionally demanding that encrypted information (or all components)
be timestamped and signed by the sender; a condition that can be
publicly verified by any third party (e.g., monitor) as well.

A PKI that incorporates binding data hence has the following four
players: 
- Users, i.e., governments, businesses, and citizens, 
- TTPs offering trusted services (e.g., time-stamping and certification of
public keys), 
- TRPs aiding law-enforcement agencies with decrypting legally intercepted messages, 
- Monitors, monitoring communications encrypted via the PKI on compliance with 
binding regulations. For instance, these could be network operators or (Internet) service
providers.

In [VKT], we explain how we envision the framework in which the
binding concept could present a security tool in the information
society. We think the concept is flexible enough (e.g., in the choice
of TRPs) to be incorporated into almost any national crypto policy, on
both the domestic and foreign use of cryptography.

In a mathematical paper [VT], Verheul and Van Tilborg propose a
technical construction for binding data for an important public-key
encryption system: ElGamal. This construction is compatible with
Desmedt's [DESM] traceable variant of ElGamal. The construction is
based on the techniques used in zero knowledge proofs. We expect that
these constructions can be improved and that various other public-key
encryption systems can be equipped with binding data. We present this
as a challenge to the cryptographic research community.

An outline of the mathematical construction of binding ElGamal can be
found at http://cwis.kub.nl/~frw/people/koops/bindtech.htm.


_3. References_

[BR]	
M. Bellare, R.L. Rivest, "Translucent Cryptography. An Alternative to
Key Escrow, and its Implementation via Fractional Oblivious Transfer",
see http://theory.lcs.mit.edu/~rivest

[Desm]	
Y. Desmedt, "Securing Traceability of Ciphertexts - Towards a Secure
Key Escrow System", Advances in Cryptology - EUROCRYPT'95 Proceedings,
Springer-Verlag, 1995, pp.147-157.

[Holl]
N. Jefferies, C. Mitchell, M. Walker, "A Proposed Architecture for
Trusted Third Party Services", Royal Holloway, University of London,
see http://platon.cs.rhbnc.ac.uk

[Mica]
S. Micali, "Fair Public-key Cryptosystems'", Advances in Cryptology -
CRYPTO '92 Proceedings, Springer-Verlag, 1993, pp. 113-138.

[VKT]
E. Verheul, B.J. Koops, H.C.A. van Tilborg, "Binding Cryptography. A
fraud-detectible alternative to key-escrow solutions", Computer Law
and Security Report, January-February 1997, to appear. [*]

[VT]
E. Verheul, H.C.A. van Tilborg, "Binding ElGamal. A fraud-detectible
alternative to key-escrow solutions", will be submitted to
Eurocrypt97.

[*] For the Computer Law and Security Report, send subscription
enquiries, orders and payments to:

Pam Purvey
The Oxford Fulfilment Centre
PO Box 800, Kidlington
Oxford 0X5 1DX  UK
Tel: +44 1865 843373
Fax: +44 1865 843940

For the United States:
Elsevier Advanced Technology
Fulfilment (enquiries)
660 White Plains Road, Tarrytown
New York, NY 10591-5153
USA 
Tel: 914 333 2458

---------------------------------------------------------------------
Bert-Jaap Koops                         tel     +31 13 466 8101
Center for Law, Administration and      facs    +31 13 466 8149
Informatization, Tilburg University     e-mail  E.J.Koops@kub.nl
                  --------------------------------------------------
Postbus 90153    |  This world's just mad enough to have been made  |
5000 LE Tilburg  |    by the Being his beings into being prayed.    |
The Netherlands  |                (Howard Nemerov)                  |
---------------------------------------------------------------------
         http://cwis.kub.nl/~frw/people/koops/bertjaap.htm
---------------------------------------------------------------------

Hey Bert-Jaap, I had you down as one of the good guys, what caused you
to fold :-)

Bert-Jaap Koops <E.J.Koops@kub.nl> writes on cpunks:
> We present an alternative that can give law-enforcement agencies
> access to session keys, without users having to deposit private
> keys.  Unilateral fraud in this scheme is easily detectible.

OK, so I can see how the `binding data' technique acheives a more
robust form of keys escrow of session keys, without handing over
private keys.  (Your wording also implied to me that the problem would
not exist if private keys were handed over, but I think this is not
the case, if a warrant is required to get the private keys, the stated
presumtion is that no speculative decryptions will be tried).  Also
the proposal (and other proposals which escrow session keys) doesn't
really provide any guarantees of protection from LE abuse, as such,
because they can decrypt all of the escrowed session keys with their
own private key.  But then the original clipper proposal had similar
supposed safeguards, they claimed to have the decryption keys split
across two databases, and they claimed that they would place the key
in a tamper resistant device so that it could only be used for the
duration of the court approved wiretap.

`binding data' combats the problem of people sabotaging key escrow by
using garbage for the escrowed session key.  Matt Blaze was able to
produce compliant capstone/tessera messages which would be accepted by
the recipient, and yet would reveal nothing to the LE agent.  Your
binding data technique would allow a software only implementation of
the non-interoperability requirements of clipper III, and combat
attacks such as Matt's.

However, simpler approaches I think fulfill the requirements given the
(stated) voluntary nature of GAK.

For instance, if you are using a hybrid RSA/symmetric key system with
the session key encrypted with RSA, you can encrypt the session key to
a second recipient also (PGP allows this much, Carl Ellison suggested
this for PGP, Bill Stewart recently also suggested the same).  If the
recipient wishes to check that the sender is really escrowing the same
session key, this can be acheived by revealing to the primary
recipient the random padding of the second recipient's RSA encrypted
copy of the session key.  The primary recipient can then repeat the
encryption, and check.  (I proposed this on sci.crypt last year some
time, with an anti-GAK caveat :-).

As GAK is (stated to be) voluntary, surely the only person who has any
business knowing whether the message is honestly GAKked is the
recipient.  After all you can double encrypt or not use GAK at your
option, so this seems to lose nothing for the GAKkers.

The description of the paper also says nothing about trust worthiness
of the TTPs, from the public's perspective.  It would be nice to see a
proposal which also resulted in the cryptographic revealing of number
of wire taps, as an unavoidable result of the protocol.  (Not that I,
or anyone else would want to use GAK still, but it would be a gesture
of good will on the part of the GAKkers, and would show intentions not
to misuse the system.  I suggest that they would never agree to such a
system because their stated aims are untrue: they *do* want to outlaw
non-escrowed encryption for domestic US traffic, and they *do* want to
decrypt without warrants, and without public audit.  Export control
and temporarily `voluntary' GAK is a means, not an end.)

Adam
--
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)