Article 7242 of sci.crypt
Path: msuinfo!caen!sdd.hp.com!cs.utexas.edu!qt.cs.utexas.edu!yale.edu!jvnc.net!darwin.sura.net!gatech!udel!rochester!cantaloupe.srv.cs.cmu.edu!crabapple.srv.cs.cmu.edu!PLAY.TRUST.CS.CMU.EDU!bsy
From: bsy+@CS.CMU.EDU (Bennet Yee)
Newsgroups: sci.crypt
Subject: Re: Reply to respondents re pd encryption software
Message-ID: <1992Feb05.024511.294141@cs.cmu.edu>
Date: 5 Feb 92 02:45:11 GMT
References: <3281@wet.UUCP> <PMETZGER.92Feb3185120@snark.shearson.com>
Reply-To: bsy+@cs.cmu.edu
Distribution: usa
Organization: Cranberry Melon, School of Cucumber Science
Lines: 137
Nntp-Posting-Host: play.trust.cs.cmu.edu

In article <PMETZGER.92Feb3185120@snark.shearson.com>, pmetzger@snark.shearson.com (Perry E. Metzger) writes:
>
> from naga@wet.UUCP (Peter Davidson)
> ...
> Did I say that the record should include the keys? This is another example
> of (conveniently) seeing idiocy where it does not exist. (Phil is not
> alone in this.) The record should include only such information as dates,
> names and file sizes - helpful in a situation where a large amount of data
> encryption and decryption is being performed.
>
>You mean, like
>
>typescript
> ...
>I can't believe that ANYONE would be stupid enough to pay money for
>such a thing, but obviously you take us for fools.
>
> His remark is clearly meant sarcastically but is actually true of
> cryptosystems that are to be used a corporate environment:
>
> "What happens if an employee is sick or is killed or is fired and
> refuses to restore the encrypted files? With many packages it is
> impossible to recover the files. This interrupts work flow and is
> costly, especially if the files cannot be restored from other data.
>
> "On the other hand, there are some packages that provide for an
> 'emergency' key usable only by the security administrator. He or she,
> using a special recovery program, is able to decipher any file without
> knowing the original password. This, we believe, is one essential
> element that must be included in any package selected."
>
> - H. J. Highland, FICS, "How to Evaluate Microcomputer
> Encryption Software and Hardware", Computers & Security,
> Vol. 6, No. 3, June 1987, pp.229-244.
>
>
>All you have proven, sir, is that H. J. Highland of FICS is suffering
>from the same disease you are, to whit, severe lack of understanding
>of the requirements of cryptosystems. I don't care if the man has a
>PhD in mathematics; he is obviously untrustworthy from the start.
>
>NO ENCRYPTION SYSTEM THAT HAS A TRAPDOOR CAN BE TRUSTED. PERIOD.
>THE WHOLE POINT OF ENCRYPTION IS TO MAKE FILES UNRECOVERABLE.

Please, can we stop this thread? Besides the excessive flamage,
technically it is not quite correct to say that making files
recoverable would necessarily compromise security.

While it seems unlikely that Peter Davidson's software uses secret
sharing techniques, secret sharing, coupled with public key
cryptography, *can* be used to securely log the (private) encryption
key used in such a way that at least m of n ``corporate security
officers'' _must_ get together to extract it.

This is not so different than the idea of doubly keyed locks, which is
a real world analog.

Here's a synopsis of how Shamir's secret sharing scheme works:

Suppose I encrypt a file using a key K. Encode it as an element k of
Z_p, p a prime (i.e., with k a 56-bit DES key, p would be a >56 bit
prime, or we iterate 7 times and use a 9 bit prime). All calculations
will be computed modulo p. Construct the polynomial
p(x)=\sum_{i=0}^{m-1} a_i x^i, where a_0=k, the other coefficients
random (except that a_{m-1}<>0 is required). Compute s_i=p(i),
i=1,...,n. These secret pieces will be ``distributed'' among n
people, any m of which can together reconstruct k. To ``distribute''
the s_i's, public key encrypt them with the public keys of the n
people, i.e., save E_{e_i}(s_i) to disk. Note there's no need to
actually send these encrypted secret pieces. The private keys d_i are
accessible only to each of the people, respectively, and the
assumption is that they are trusted security officers of the firm,
perhaps encrypted under their own private keys which are ``backed up''
in a similar manner.

Suppose that person who knew the key K is disabled or is fired, and
the company needs to recover the files. At least m of these people
decrypt their copy of s_i. Here's why they can recover the key k:

What we have is simply the usual matrix equation

A x = b

where A is an n by m matrix have row vectors (n>m)

{ r^{m-1} r^{m-2} ... r^2 r 1}

where r is the row number ranging from 1 to n. The b column vector
are the s_i's. Clearly from the construction, A is invertible, and
only m of the rows are required to invert it. Hence, having m of the
s_i's is sufficient to recover the a_i's, which are the entries of the
x vector. Also, it should be clear that with m-1 or fewer entries of
b, none of the values of x can be recovered.

For more details on secret sharing schemes and their applications,
below are three articles from my bib file. Rabin's secret sharing
scheme keeps the size of the secret pieces smaller and is appropriate
for larger pieces of data, but a little information is leaked, and so
it _may_ be possible (with very low probability) that fewer than m
pieces can be used to reconstruct the original secret -- however,
since we're going to encrypt the pieces with the public keys of the
security officers anyway, very little is lost.

-bsy

@Article(ShamirSS,
Key="Shamir",
Author="A. Shamir",
Title="How to Share a Secret",
Journal="Communications of the ACM",
Volume="22",
Number="11",
Pages="612--614",
Month="November",
Year="1979")

@TechReport(RabinSS,
Key="Rabin",
Author="Michael O. Rabin",
Title="Efficient Dispersal of Information for Security and Fault Tolerance",
Institution="Aiken Laboratory, Harvard Univerisity",
Number="TR-02-87",
Month="April",
Year=1987)

@inproceedings(HerlihyTygar,
Key="Herlihy and Tygar",
Author="Maurice P. Herlihy and J. D. Tygar",
Title="How to Make Replicated Data Secure",
BookTitle="Advances in Cryptology, CRYPTO-87",
Month="August", Year=1987,
Publisher="Springer-Verlag",
Note="To appear in {\it Journal of Cryptology}")

--
Bennet S. Yee Phone: +1 412 268-7571 Email: bsy+@cs.cmu.edu
School of Computer Science, Carnegie Mellon, Pittsburgh, PA 15213-3890