USENIX Association
`
`Proceedings of the
`Summer 1994 USENIX Conference
`
`June 6 - 10, 1994
`Boston, Massachusetts, USA
`
`Petitioner Oracle-Apple - Exhibit 1014 - Page 1
`
`

`

`
`
`
`
`’
`
`For additional copies of these proceedings write:
`
`USENIX Association
`
`2560 Ninth Street, Suite 215
`
`Berkeley, CA 94710 USA
`
`The price is $25 for members and $33 for nonmembers.
`Outside the U.S.A. and Canada, please add
`$18 per copy for postage (via air printed matter).
`
`Past USENIX Technical Conferences
`
`1994 Winter San Francisco
`1993 Summer Cincinnati
`
`1993 Winter San Diego
`1992 Summer San Antonio
`1992 Winter San Francisco
`1991 Summer Nashville
`1991 Winter Dallas
`1990 Summer Anaheim
`
`1990 Winter Washington, DC
`1989 Summer Baltimore
`
`1989 Winter San Diego
`1988 Summer San Francisco
`
`1988 Winter Dallas
`1987 Summer Phoenix
`
`1987 Winter Washington, DC
`1986 Summer Atlanta
`1986 Winter Denver
`1985 Summer Portland
`1985 Winter Dallas
`
`1984 Summer Salt Lake City
`1984 Winter Washington, DC
`1983 Summer Toronto
`
`1983 Winter San Diego
`
`1994 © Copyright by The USENIX Association
`All Rights Reserved.
`
`ISBN 1-880446—62—6
`
`This volume is published as a collective work.
`Rights to individual papers remain with the author or the author’s employer.
`
`USENIX acknowledges all trademarks herein.
`
`Printed in the United States of America on 50% recycled paper, 10-15% post consumer waste. ®
`
`Petitioner Oracle-Apple - Exhibit 1014 - Page 2
`
`

`

`TABLE OF CONTENTS
`.
`USENIX Summer 1994 Technical Conference
`June 6 - 10, 1994
`Boston, Massachusetts, USA
`
`OFF THE BEATEN TRACK
`
`l {Q
`V
`» E
`
`F,“
`u 1,, ....a
`
`L) 8
`I C1‘ 9' <-ill.’
`Chair: Glen Dudek, VGI
`
`Wednesday 11:00 - 12:30
`
`A New Object-oriented Programming Language: sh ....................................................................................................... ..
`Jefirey S. Haemer, Canary Sofiware, Inc.
`
`1
`
`The Old Man and the C ................................................................................................................................................... .. 15
`
`Evan Adams, Sun Microsystems
`
`CLOSING THE SYSTEM
`
`Wednesday 2:00 - 3:30
`
`Chair: Greg Rose, RoseSecure
`
`Key Management in an Encrypting File System .......................................................................................................... .. 27
`Matt Blaze, AT&T Bell Laboratories
`
`A Toolkit and Methods for Internet Firewalls............................................................................................................... .. 37
`
`Marcus K. Ranum, Frederick M. Avolio, Trusted Information Systems, Inc.
`
`SNP: An Interface for Secure Network Programming .................................................................................................. .. 45
`Thomas Y.C. Woo, Raghuram Bindignavle, Shaowen Su, and Simon S. Lam, University of Texas, Austin
`
`UNDER THE COVERS
`
`Wednesday 4:00 - 5:30
`
`Chair: Adam Moskowitz, Menlo Consulting
`
`An Efficient Kemel-Based Implementation of POSIX Threads
`Robert A. Alfieri, Unix Kernel Development, Data General Corporation
`
`59
`
`Using OS Locking Services to Implement a DBMS: An Experience Report................................................................. 73
`Andrea H. Skarra, AT&TBell Laboratories
`
`The Slab Allocator‘. An Object-Caching Kernel Memory Allocator ..............................................................f. ........... .. 87
`Jefl’Bonwick, Sun Microsystems
`
`FILE SYSTEMS
`
`Thursday 9:00 - 10:30
`
`Chair: Kent Peacock
`
`A Better Update Policy ..........................................................................................................
`Jefirey C. Mogul, Digital Equipment Corporation, Western Research Laboratory
`
`..................................... .. 99
`
`The Desktop File System ......................................................................................... .3.................................................. .. 113
`Morgan Clark, Stephen Raga, Programmed Logic Corporation
`
`Sawmill: A High Bandwidth Logging File System ..................................................................................................... .. 125
`Ken Shirrijj‘; John Ousterhout, University of California, Berkeley
`
`Petitioner Oracle-Apple - Exhibit 1014 - Page 3
`
`

`

`Key Management in an Encrypting File System
`
`Matt Blaze
`AT&T Bell Laboratories
`
`Abstract
`
`As distributed computing systems grow in size,
`complexity and variety of application, the problem of
`protecting sensitive data from unauthorized disclo-
`sure and tampering becomes increasingly important.
`Cryptographic techniques can play an important role
`in protecting communication links and file data, since
`access to data can be litnited to those who hold the
`
`proper key. In the case of file data, however, the rou-
`tine use of encryption facilities often places the orga-
`nizational requirements of information security in
`opposition to those of information management.
`Since strong encryption implies that only the holders
`of the cryptographic key have access to the cleartext
`data, an organization may be denied the use of its
`own critical business records if the key used to
`encrypt
`these records becomes unavailable (e.g..
`through the accidental death of the key holder).
`
`This paper describes a system, based on cryp-
`tographic "smartcards," for the temporary "escrow"
`of file encryption keys for critical files in a crypto-
`graphic file system. Unlike conventional escrow
`schemes, this system is bilaterally auditable, in that
`the holder of an escrowed key can verify that, in fact,
`he or she holds the key to a particular directory and
`the owner of the key can verify, when the escrow
`period is ended,
`that
`the escrow agent has neither
`used the key not can use it in the future. We describe
`a new algorithm, based on the DES cipher, for the on-
`line encryption of file data in a secure and efficient
`manner that is suitable for use in a smartcard.
`
`1. Introduction
`
`Modern distributed computing systems, for all their
`virtues, make it difficult to limit reliably access to
`sensitive data. Networks often unselectively broad-
`cast data to far-reaching and unpredictable places,
`
`remote login facilities create new opportunities for
`trespassers and distributed file systems often assume
`that all machines to which they provide service are
`trustworthy and reliable. To reduce these risks, cryp-
`tographic techniques make it possible to limit data.
`access while still taking advantage of untrustworthy
`networks and services. Modern workstations can
`
`encrypt in software at close to network speeds [4] [5].
`Data encryption attempts to ensure that only those
`who possess the correct decryption key can obtain the
`cleartext data.
`
`Most commercial applications of encryption
`techniques protect communication links (and related
`services such as electronic mail). When communica-
`
`tion endpoints are under the cont:rol of a single entity,
`or trust a common authority,
`the management of
`cryptographic keys is a conceptually straightforward
`matter. Keys can be assigned and changed as often as
`desired, the main problem being to ensure that both
`sender and receiver agree as to the current keys and
`that keys are discarded when no longer in use.
`Should sender and receiver get "out of sync" with the
`keys,
`the problem becomes immediately apparent
`because communication fails. Ensuring access by
`third parties in the event that keys are lost or unavail-
`able is rarely an issue.* Public key techniques
`[3][10] make communication key management easier,
`allowing two parties to establish a secure channel
`without prior arrangement.
`
`“The law enforcement community argues that it may be an
`exception; widespread use of encryption techniques may impede
`police wiretap investigations [2]. The ethical,
`legal, social and
`technical implications of law enforcement access to cryptographic
`communication are presently the subjects of intense public debate
`in the United States and are (fortunately) outside the scope of this
`paper.
`\
`
`1994 Summer USENIX - June 6 - 10, 1994 - Boston, MA
`
`Petitioner Oracle-Apple - Exhibit 1014 -
`
`Page 4
`
`27
`
`

`

`Cryptography can also be used to protect file
`data, although there are relatively few tools for this
`purpose in widespread use. Most
`file encryption
`takes place at the application level, with tools such as
`the Unix crypt command or with special encrypting
`applications (e.g., "vi -x"). File encryption can also
`take place at a lower level, as a basic service of the
`file system [1][9][13].
`
`Regardless of where encryption takes place,
`key management for encrypted files is a fundamen-
`tally different problem from that
`in cryptographic
`communication.
`In a secure communication system,
`keys must be distributed and synchronized geograph-
`ically. Keys often serve the dual purpose of authenti-
`cating identity as well as protecting against eaves-
`droppers. The architecture for distributing communi-
`cation keys is closely tied to the trust relationships
`within the system, and practical key distribution pro-
`tocols (such as those employed by the Kerberos sys-
`tem[12]) must be carefiilly engineered to balance reli-
`ability, security and performance.
`
`In a file system, on the other hand, there is usu-
`ally little need to distribute keys geographically; most
`protected files are encrypted and decrypted at the
`same locations (and by the same users). Authentica-
`tion of identity is a less serious issue, with access
`implicitly controlled through knowledge of the key
`itself, although cryptographic techniques can also be
`used to detect unauthorized tampering with file data.
`File systems still present a significant, if differently
`formulated, key management problem, however,
`in
`that keys can be said to be distributed temporally.
`The corresponding keys must be available at both
`encryption and decryption time. File encryption keys
`have much longer lifetimes than their communication
`counterparts. If a key is lost or unavailable, the files
`encrypted with it are rendered useless. This condi-
`tion may not be detected until it is too late. The key
`distribution center and public key cryptographic pro-
`tocols developed for geographically distributed com-
`munication systems do not have direct analogues that
`can be readily applied to temporal file key manage-
`ment.
`
`Arguably, it is because of difficulties associated
`with key management that sensitive files are rarely
`encrypted in practice even when encryption tools are
`available. This is especially true in critical business
`environments where ensuring the availability of data
`to authorized users is at least as important as ensuring
`its unavailability to everyone else. Sometimes, files
`are protected with weak ciphers,
`such that
`the
`encrypted data can be recovered with the application
`of sufficient computing resources. A toolkit ("Crypt
`
`Breaker’s Workbench")
`
`is available in Internet
`
`archives for the purpose of decrypting files enci-
`phered with the Unix crypt program. Needless to
`say, since these tools are also available to the adver-
`sary, encryption with weak ciphers is of questionable
`value in the first place.
`
`information
`In the context of organizational
`systems, cryptographic file protection presents sev-
`eral problems not addressed by traditional (communi-
`cation-oriented) key management schemes. These
`problems are not only technical
`(e.g., providing
`mechanisms for ensuring that keys are available
`when and where authorized) but also managerial and
`social (balancing secrecy and privacy against emer-
`gency access requirements). Carefully controlled key
`management services with explicit, auditable trust
`relationships that are integrated into the underlying
`file system security architecture can help reconcile
`these often conflicting goals.
`
`2. Key Escrow
`
`Hence the problem: strong file encryption is often
`necessary
`to protect privacy while
`availability
`requirements sometimes dictate the need for a "back
`door" for emergency access. We use as our model
`the common problem of ensuring continued access to
`critical business files even after the only employees
`who know the keys to those files leave the organiza-
`tion. One approach adapts the procedures used for
`controlling physical locks and keys to file encryption
`keys and provides a central key distribution ("lock-
`smith") service. Any time a user requires an encryp-
`tion key, it is generated by a central service, which
`also keeps a copy for emergency access.
`
`locksmith
`the central
`In practice, however,
`model adapts poorly to large-scale file encryption key
`management. The central service must be uncondi-
`tionally trusted by all who obtain keys from it. No
`further controls preclude or audit access by those
`with access to the key database. (Note that this is not
`the case with locksmiths who manage physical keys
`— use of a key requires access to the lock, which
`may itself be controlled by independent security
`mechanisms and which can be changed if the lock-
`smith’s office is compromised.
`In the case of file
`keys, on the other hand, once a copy of the key
`database has leaked, all
`files with keys in the
`database must be considered compromised forever.)
`Furthermore, a central service can quickly become a
`service bottleneck or worse, a single point of failure
`or attack. The key service is an "online" part of the
`key creation process and users cannot create new
`
`28
`
`imsemanaaameneahlwl llfiicfl-'li°<)'§$l‘§‘i1,'~:’MA
`
`

`

`keys if the service is unavailable. Finally, the prob-
`lem of securing communication between the user and
`the key center introduces all the problems of commu-
`nication key management in addition to the existing
`problem of file key management.
`
`An alternative approach reverses the relation-
`ship and provides a controlled mechanism for users
`to deposit copies of their keys for emergency use as
`needed. The keys for crucial files could thereby be
`"escrowed" with a trusted caretaker who would
`
`reveal them only when certain conditions are met,
`such as when encrypted business data are required
`after the death of the legitimate key holder. Concep-
`tually, keys might be delivered within sealed
`"envelopes." When a set of files is no longer critical,
`the envelope containing its keys could be returned to
`its originator, who could verify the integrity of the
`seal and destroy the keys, preventing future access to
`outdated, but still private, data. The "escrow-deposit"
`approach has the benefit of allowing the key holder to
`generate keys in the usual manner, without direct
`"online" interaction with a third party. There is no
`central service bottleneck, since the escrow agent is
`not directly involved in the creation of new keys.
`Envelopes containing escrowed keys can be delivered
`to the escrow agent at any time and any inability to
`deliver the keys to the agent need not preclude their
`use by the key holder.
`
`Unfortunately, this is difficult to do in practice.
`The simplest procedure has the key holder write
`down the key, place it in a sealed envelope, and leave
`it with a trusted caretaker. This is vulnerable to mis-
`
`takes, however, since there is no inherent mechanism
`
`to ensure that the escrowed key is the same as the real
`one. The security of
`the scheme also depends
`entirely on the honesty of the caretaker and the
`tamper-resistance of the envelope. An electronic ana-
`logue to the sealed envelope can be implemented by
`encrypting the key with a "caretaker" key, perhaps
`using public key techniques. If this is done automati-
`cally as part of key generation, the problems associ-
`ated with transcription mistakes are avoided, but the
`scheme still depends entirely on the caretaker’s hon-
`esty (and even more so without the sealed envelope).
`If no single caretaker can be trusted, the key could be
`multiply encrypted with more than one caretaker’s
`key, split among several escrow agents (in the man-
`ner of the US Escrowed Encryption Standard) or
`encrypted using a group—oriented public key protocol.
`
`Both the manual and encrypted key escrow
`schemes suffer from a fundamental problem, how-
`ever. After an escrow agent “opens" the key and
`learns its value, no further controls on its use are
`
`possible. Anyone who learns the keys can use them
`at any time in the future without detection. Elec-
`Ironic escrow is particularly hard to revoke or audit,
`since it is difficult to ensure that all copies of the keys
`have been destroyed when the escrow period ends
`even if the keys have never actually been used (con-
`sider backups or illicit copies of the escrow data).
`
`Under these schemes, key escrow is an "all or
`nothing" proposition, with no mechanism to guaran-
`tee, in any formal sense, that the caretaker is doing
`his or her job honestly.
`It is not obvious how to
`implement key escrow schemes that offer stronger
`protection against abuse without relying on elaborate
`physical access controls or special purpose hardware.
`
`Cryptographic smartcards can be used to
`implement more carefully controlled and fully revo-
`cable file system key escrow. Smartcards have sev-
`eral properties that lend themselves to use as a con-
`trolled store for escrowed keys. These cards are
`designed to be sufficiently tamper-resistant to allow
`their use in financial applications, have a controlled-
`access non-volatile memory, can run general purpose
`software and include built-in cryptographic and ran-
`dom number generation capabilities.
`
`3. Smartcard-Based Key Escrow in a Crypto-
`graphic File System
`
`The shortcomings of entirely software-based key
`escrow schemes arise out of the inability to control
`the use of the key once it has been revealed to the
`escrow agent. Thus the problem is to guarantee the
`escrow agent use of the key without actually reveal-
`ing what it
`is. While this may appear to involve
`impossibly contradictory requirements, most com-
`mercial smartcards can be adapted to serve exactly
`this purpose.
`
`We propose a system in which an "escrow
`smartcard" can be created along with each file
`encryption key. This card is provided to a designated
`third party (the "escrow agent") who is authorized to
`use the key under some well-defined set of circum-
`stances. If emergency access is required the card can
`decrypt files without revealing what the key is, acting
`as a self-contained decryption engine for ciphertext
`sent to it by the escrow agent. Any time the card
`decrypts data it also records that fact" in its secure
`storage. Later, when the escrow period is terminated
`or when an audit is to be performed, the user can
`query the card to determine whether the escrow agent
`has used it. This section describes the design and
`implementation of a smartcard-based key escrow
`scheme for CFS, a file encryption system for Unix.
`
`
`
`1994 Summer USENIX - June 6 - 10, 1994 - Boston, MA
`
`29
`Petitioner Oracle-Apple - Exhibit 1014 - Page 6
`
`

`

`CFS is a cryptographic file system interface for
`Unix-like systems;
`it allows the user to associate
`cryptographic keys with directories.
`It runs entirely
`on the client workstation. No modification to the
`
`underlying file system (or file server) is required, and
`file contents as well as some meta-data (file names)
`are cryptographically protected. Backups and other
`such routine administrative services can take place in
`the normal manner and without the encryption keys.
`Details on CFS can be found in [1].
`
`Basically, CFS provides a mechanism to asso-
`ciate "real" directories (on other file systems) that
`contain encrypted data with temporary "virtual"
`names through which users can read and write cleart-
`ext. These virtual names appear in a separate names-
`pace under the CFS mount point, which is usually
`called /crypt. Users create encrypted directories
`on regular file systems (e.g., in their home directo-
`ries) using the cmkdir command, which creates the
`directory
`and
`assigns
`to
`it
`a
`cryptographic
`"passphrase" that will be used to encrypt its contents.
`To use an encrypted directory, it must be "attached"
`to CFS using the cattach command, which asks for
`the passphrase and installs an association between the
`"real" directory and a name under /crypt. Cleart—
`ext is read and written under the virtual directory in
`/crypt, but the files are stored in encrypted fonn
`(with encrypted names) in the real directory. When
`the directory is not in use, the association is removed
`with the cdetach command, which deletes the cleart-
`ext virtual directory under /crypt. When CFS is
`run on a client workstation, the cleartext data (and the
`cryptographic key passphrase) are never stored on a
`disk or sent over a network, even when the real direc-
`
`tory is located on a remote file server. The system is
`implemented as a user-level NFS[11] server. The
`basic flow of data in CFS is shown in Figure 1.
`
`Key escrow is implemented for CFS as an
`option to escrow the key when the encrypted direc-
`tory is created with cmkdir. When keys are initially
`assigned and whenever escrowed access is required,
`the machine running CFS must have a smartcard
`reader—writer attached.
`(In day—to—day user operation
`on encrypted files, no smartcard reader is required.)
`The smartcard has a small store of secure memory,
`the ability to run simple programs securely and a
`secret-key cryptographic engine compatible with that
`of the host file system. Ideally, the card could have a
`real-time calendar and the ability to schedule execu-
`tion at some future date, although the cards we use
`(the AT&T smartcard) do not have these capabilities.
`We call the user who created the files the "owner"
`
`and the caretakers of the escrowed keys the "escrow
`
`
`
`:
`; (local)
`L _________________ - _J
`
`File System Interface
`
`Encrypted
`
`(local or remote)
`I’ ‘ ’ ' ’ ' ‘ ' "' ‘ ' ' ' "
`
`" ‘ ‘ " " '1
`
`II I
`
`File
`I System
`: (local or remote)
`
`Figure 1 — Data Flow in Standard CFS System
`
` 1994 s‘illllilll?'
`
`£i!filS’:‘}BllJ:e6—'§’tl)‘Pll91:°.‘1§‘o‘sl%il9§4Zx
`
`F """"""""" ' '1
`: User-Level
`:
`I Application
`r
`I
`I
`I
`I
`l
`I
`L _ _ . _ _ _ _ _ _ _ _ _ _ _
`_ . _ _ .. .l
`
`System Calls
`r - - - - ~ - - - - - - - - -
`I
`I
`
`- - - ' ‘ 1
`I
`I
`
`: Unix
`I Kernel
`I
`
`:
`I
`I
`
`; (local)
`I
`L _ . _ . _ _ _ _ _ _ _ . _ _
`
`;
`I
`. _ _ _ _ _l
`
`File System Interface
`Cleartext
`. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`(internal - localhost)
`
`. . . . . . . . . . . . . . . . ..
`
`li
`IEIt
`IS
`
`CFS
`Daemon
`
`Encryptionl
`Decryption Engine
`; L _________________ _ _ J
`
`System Calls
`I‘ " ' ‘ ' ’ ' ‘ ' " ' ’ ' ‘ '
`I
`I
`, Unix
`i Kernel
`I
`
`' "" " ‘ 1
`I
`I
`,I
`n
`I
`
`Sys. Call Interface
`
`
`
`
`
`

`

`agents." The techniques described here could be
`applied to any file encryption system and are not lim-
`ited to CFS.
`
`At the time keys are assigned (e.g., with the
`CFS cmkdir command), the smartcard is initialized
`
`with three sets of cryptographic keys. The first key
`set, the "file system key," is used for actual file data
`encryption, and consists,
`in CFS, of two 56 bit
`DES[6] keys derived from a user-selected secret
`"passphrase." The file key is also used to hash a
`known plaintext string that is stored in the host file
`system in the "check file." The second key, the "audit
`key," is used to post-audit the card at escrow revoca-
`tion time and will be explained in more detail below.
`The audit key is also stored in a file on the host com-
`puter (encrypted under the file keys). The last key,
`the "escrow key," is used to encrypt the file system
`keys stored on the card.
`It must also be provided to
`the escrow agent (perhaps via public key techniques,
`and perhaps split among several agents, but this key
`is not essential to the security of the protocol). Ordi-
`narily,
`the escrow key is derived from a second
`passphrase entered by the owner. The encrypted file
`keys and audit key are maintained in secure storage
`on the card and cannot be easily "reverse engineered"
`from the card. All smartcard initialization takes place
`in CFS through a modified version of the cmkdir
`command.
`
`Once keys are assigned, the smartcard is turned
`over to an escrow agent for safekeeping and the
`escrow key passphrase revealed to the escrow agent.
`(The escrow agent who holds the card need not be the
`same agent who knows the escrow key). If the smart-
`card has a calendar and the ability to schedule future
`execution, the escrow data on the cards could be con-
`
`figured to automatically self-destruct after a set
`period. If needed, duplicate cards, with new escrow
`and audit keys, can be created by the owner (using
`the file passphrase) at any time.
`
`In normal CFS operation, the file system keys
`are derived from the user passphrase on the trusted
`host computer when the owner issues the "cattach"
`command for an encrypted directory; the smartcard is
`not involved. Regular user operation requires only
`the standard version of CFS (without any escrow
`software). The check file assures that the entered
`
`phrase is valid and that wildly incorrect decrypted file
`names and contents are not returned to the file sys-
`tem .
`
`The smartcard itself is used to perform three
`operations. The first operation, "pre-audit," simply
`verifies to the escrow agent that the keys on the card
`correspond to those used to encrypt the actual file
`
`In this mode of operation, the escrow agent
`system.
`sends the contents of the check file (in the escrowed
`file system) and the escrow key to the smartcard,
`which provides a "yes" or "no" answer based on the
`decrypted file keys.
`(The owner could "cheat" and
`provide a "dummy" check file; we discuss this
`below.) The escrowed keys do not leave the card.
`
`the smartcard
`In "escrow access" operation,
`decrypts files for the escrow agents. The agents sup-
`ply the escrow key; if it is supplied correctly, the card
`decrypts the file system keys and increments a
`counter in its secure store. Thereafter, for the remain-
`
`der of the session, the card will use the decrypted file
`keys to decrypt file data sent to it. If the card has a
`real
`time clock,
`it could also maintain two time
`stamps for the first and most recent times the escrow
`key was used. Again, the keys never leave the card;
`the card acts as a wholely self—contained decryption
`engine. Once the card is removed, its state is reset
`and the escrow key must be supplied again to enable‘
`further decryption. Escrow access in CFS takes place
`through a modified CFS file system daemon in which
`the crypto engine is replaced with calls to the smart-
`card interface. Additional support tools supply the
`escrow key to the smartcard. Note that the card inter-
`face is part of the data path for all decrypted data.
`The data flow is shown in Figure 2.
`
`The last mode of operation, "post-audit," is
`used when the escrow period is ended and the card is
`returned to the owner. The card reports the number
`of times the escrow keys were used. If the card has
`the capability to store this data it could also report the
`first and last access times and number of bytes
`decrypted under escrow (again, our cards do not). To
`help protect against card forgery and to safeguard
`against the return of a fake card by the escrow agent,
`the owner can challenge the card to perform encryp-
`tions under the audit key. The audit key is decrypted
`on the host computer with the owner passphrase; by
`comparing the results of a random challenge with the
`result of a decryption perfonned locally, the owner
`can verify that the card that was returned is the same
`one that was originally escrowed. Post audit is per-
`formed in CFS with an additional user tool.
`
`3.1. File Encryption Scheme
`
`One of the lessons learned from the design of CFS is
`that the problem of encrypting files on-line in a file
`system is somewhat different from other kinds of
`encryption problems. No single standard encryption
`mode[7] has all the properties required for file system
`use; further compounding the problem are concerns
`
`1994 Summer USENIX - June 6 - 10, 1994 - Boston, MA
`
`Petitioner Oracle-Apple - Exhibit 1014
`
`31
`- Page 8
`
`

`

`that the 56 bits of key used by the DES cipher are
`vulnerable to exhaustive search attack[14].
`
`CFS uses a combination of DES "codebook"
`
`to
`cipher modes
`"stream"
`and pre-computable
`approximate the strength of multiple iterations of
`DES with the runtime latency of only a single itera-
`tion of DES. This scheme has the resistance to struc-
`
`tural analysis of a chaining cipher but allows random
`read and write access in constant time.
`
`The encryption scheme relies on the ability to
`trade off space (in the precomputation of the streams)
`for time, To accommodate the key escrow system,
`we modified the CFS encryption scheme to allow
`"lazy evaluation" on the smartcard without the large
`memory requirements of the precomputed stream.
`We believe this scheme to be equivalent to 3-DES
`under currently known practical attacks. The new
`CFS cipher is as follows:
`
`Recall that keys in CFS consist of two DES
`keys, KI and K2, derived from the user passphrase.
`Conceptually, CFS file block encryption consists of
`encryption against a positionally defined stream
`cipher derived from K1, which is then encrypted with
`a codebook block cipher under K2, which is further
`encrypted with a second multi-use stream cipher
`derived from K,. Specifically,
`
`E, = DES'(K2, 1),, ea DES‘(K,, f(p mod m)) e i)
`
`<9 DES'(K,, g(p mod m))
`
`(1)
`
`The cipher is reversed in the obvious manner:
`
`DP = DES“(K2, 12,, e DES‘(K,, g(p mod m)))
`
`ea DES’(K,, f(p mod m)) ei
`
`(2)
`
`where:
`
`EP
`
`Dp
`
`65
`
`is the ciphertext block of a file at byte offset p.
`
`is the cleartext block of a file at byte offset p.
`
`is the bitwise exclusive-or operation.
`
`DES‘(k, b)
`is the Data Encryption Standard block encryp-
`tion function on cleartext b with key k.
`
`DES—](/C, b)
`is the Data Encryption Standard block decryp-
`tion function on ciphertext b with key k.
`
`i
`
`is a bit representation of a unique file identifier
`derived from the Unix inode number and cre-
`
`ation time of the encrypted file.
`
`I‘ ‘ ' ' ‘ ‘ ‘ " ’ ‘ ’ " ' ‘ ' ” ' “ ' ‘ ‘ ‘I
`I
`I
`
`I
`:
`I
`I
`_ _ _ .. _ J
`
`: User-Level
`I Application
`I
`L _ _ _ _ _ _ _ . _ _ _ _ _ _
`
`II
`
`System Calls
`I‘ ‘ ' ‘ ‘ ' ’ ‘ ‘ ‘ ‘ ‘ ' ‘ ‘
`I
`I
`
`' ' ‘ ’ ” "I
`I
`I
`
`: Unix
`I Kernel
`I
`
`:
`I
`I
`
`:
`: (local)
`L _________________ _ _J
`File System Interface
`Cleartext
`
`
`
`
`
`Escrow
`smartcard
`
`Decrypt
`Engine
`
`II Unix
`I Kernel
`I
`
`(internal - Iocalhost)
`- - - - - -I
`i I- - - - - - - -
`Daemonig
`pFS Escrow
`
`:
`NFS Svr. I erface
`
`
`
`|
`
`2
`
`Ig
`
`=2
`
`. . . .
`
`.
`
`. .
`
`.
`
`— — — — - J :
`
`
`
`
`
`' " ’ ' ‘ ‘I
`
`II
`
`I
`I
`I
`
`
`
`: (local)
`I
`L _ _ _ _ _ _ _ _ _ _ _ _ _ _
`
`:
`I
`_ _ _ _ _ _|
`
`File System Interface
`
`Encrypted
`
`(local or remote)
`I'' " ' ” ‘ ” ' ’ ' ‘ ' ” ‘ ' ‘
`I
`I
`
`‘ ‘ ' ' ‘ ‘I
`I
`I
`
`I
`1 File
`:
`: System
`:
`: (local or remote)
`I
`I
`I
`I
`L _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _. _I
`
`Figure 2 — Data Flow in CFS Escrow Agent System
`
`
`
`
`
` 199 § ‘IR?! §§I9§'—RP86—l‘ I '§ 9- 6I8l9,eNi’A
`
`

`

`f(rt), 30:)
`are publically known functions that map an
`integer representation n into unique bit strings
`of the DES codebook size (64 bits).
`
`m
`
`is the length of the precomputed stored stream
`(presently 256K bytes).
`
`the stream ciphers defined by
`Observe that
`DES‘(K1, f(p mod m)) and DES‘(K,, g(p mod m))
`can be precomputed for each K1 given 2m bytes of
`storage.
`The CFS daemon precomputes
`these
`streams when the cattach command is issued for a
`
`particular key. Vifith the streams precomputed, each
`block encryption requires only one online DES oper-
`ation (the codebook cipher based on K2).
`
`When decryption is performed on the card, the
`streams cannot be wholely precomputed in the card’s
`small
`local memory.
`Instead,
`the card calculates
`DES‘(K1, f(p mod m)) and DES1(K,,g(p mod m))
`for each cipherblock sent to it.
`(f(p mod m) and
`g( p mod m) are sent to the card from the host com-
`puter as parameters with the cipher block.) Although
`this is computationally slower than the precomputed
`cipher, requiring three DES encryptions per block
`instead of one, bandwidth to the card interface (a
`serial link) remains the primary limitation on encryp-
`tion speed.
`
`4. Practical Applications
`
`File system key escrow can support a variety of
`application domains. Ensuring organizational access
`to proprietary data was discussed and motivated
`above. Here, an employee has primary operational
`responsibility for data that belongs to an organization.
`Key escrow allows the organization to provide other
`individuals with emergency access capability in the
`primary employee’s
`absence. Access
`by these
`"backup"
`individuals can be granted, controlled,
`audited and revoked easily, without compromising
`the organization’s ability to maintain and control its
`own information.
`
`Smartcard-based escrow also facilitates other
`
`In the organizational
`backup access relationships.
`scenario above, the primary key holder is "subordi-
`nate" to the escrow holder. Alternatively, a manager
`may be the primary key holder for sensitive-but-
`critical business data for which the keys are escrowed
`with an employee. The escrow key holder may not
`be authorized for routine access, but in the manager’s
`absence may be required to perform "proxy" func-
`ti