United States Patent
`
`5,931,947
`[19]
`(11)
`[45]
`Aug.3, 1999
`Date of Patent:
`Burnset al.
`
`Patent Number:
`
`US005931947A
`
`SECURE ARRAY OF REMOTELY
`ENCRYPTED STORAGE DEVICES
`
`OTHER PUBLICATIONS
`
`Inventors: Randal Chilton Burns; Edward
`Gustav Chron, both of Sunnyvale;
`Darrell Long, Soquel; Benjamin Clay
`Reed, SanJose, all of Calif.
`
`[73]
`
`Assignee:
`
`International Business Machines
`Corporation, Armonk, N.Y.
`
`NoBe
`
`boi)
`
`soooweUtNeSecS|4
`
`YIwe
`
`Appl. No.: 08/927,775
`
`Filed:
`
`Sep. 11, 1997
`
`Tint. CIS eecccccccceccsseecssseees GO6F 12/14; GO6F 13/00
`US. C1 occ ececcesssesesessneseesesnsueseeesereeseeneeneanenss 713/201
`Field of Search 0.0.0.0 707/9, 10, 103;
`713/201
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`5,175,852 12/1992 Johnson et al. ol ee eeeee 395/600
`5,349,643
`9/1994 Coxet al.uecccesscsusesssneesesees 380/25
`
`5,475,819
`12/1995 Miller et al.
`..
`395/200.03
`5,495,533
`2/1996 Linehanetal. ...
`.. 380/21
`3/1996 Hartman, Jr ore 380/25
`5,500,897
`
`.
`395/200.06
`5,550,976
`8/1996 Henderson et al.
`
`.........
`5,617,568
`4/1997 Aulletal.
`395/612
`6/1997 Nguyen ...ccceccreeseecereeeenecsseeees 380/29
`5,638,448
`5,781,725
`7/1998 Saito wicecscceeseneeteeececteeeees 713/201
`5,809,145
`9/1998 Slik et alo oe 713/201 &
`FOREIGN PATENT DOCUMENTS
`
`08297638
`
`11/1996
`
`Japan ...srecscceeeereereereee GO6F 001/00
`
`G. Gibson et al., “File Server Scaling with Network—At-
`tached Secure Disks”, Proceedings of the ACM International
`Conference on Measurement and Modeling of Computer
`Systems (Sigmetrics °97), Seattle, Washington, Jun. 15-18,
`1997.
`
`“Network—Attached Secure Disks (NASD)Y’, Computer Sci-
`ence Department, Carnegie Mellon University, Web page,
`http://www.cs.cmu.edu/Groups/NASD/.
`
`H. Krawezykct al., “HMAC: Kcycd—Hashing for Message
`Authentication”, Network Working Group, RFC 2104,
`HMAC,Informational, Feb. 1997.
`
`Primary Examiner—Thomas M. Heckler
`Attorney, Agent, or Firm—Khanh Q. Tran
`
`[57]
`
`ABSTRACT
`
`A network storage device is disclosed for use in a secure
`array of such devices to support a distributed file system.
`Each device is an independent repository of remotely
`encrypted data objects to be accessed by authorized network
`clients. All encryption is done bythe clients, rather than by
`the devices. In order for the system to revoke access to an
`object on the device, the object must be re-encrypted. Each
`storage device has a device ownerfor controlling access to
`the device’s data. All data requests from the clients and
`responses to them are authenticated using keys derived trom
`the owner key and hashed message authentication codes.
`
`1 Claim, 5 Drawing Sheets
`
`
`
`STORAGE DEVICE
`
`FIRMWARE:
`
`
`
`
`NONCEHISTORY
`
`
`
`1il
`
`
`OBJECT REPOSITORY
`
`REQUEST PROCESSOR
`
`NETWORK
`
`Google Exhibit 1092
`Google v. VirtaMove
`
`DEVICE OWNER KEY|-3
`
`
`STORAGE MEDIA:
`10
`SUBSCRIBER LIST
`
`
`NONCE
`
`
`
`
`L-4
`
`
`
`Google Exhibit 1092
`Google v. VirtaMove
`
`

`

`U.S. Patent
`
`Aug.3, 1999
`
`Sheet 1 of 5
`
`5,931,947
`
`RAM:
`
`5
`
`NONCEHISTORY
`
`STORAGE MEDIA:
`
`19
`
`SUBSCRIBER LIST
`
`OBJECT REPOSITORY
`
`1]
`
`STORAGE DEVICE
`
`FIRMWARE:
`
`DEVICE OWNER KEY
`
`NONCE
`
`REQUEST PROCESSOR
`
`NETWORK
`
`FIG, 1
`
`

`

`U.S. Patent
`
`Aug.3, 1999
`
`Sheet 2 of 5
`
`5,931,947
`
`
`
`AULNAGAldAYON]
`
`NOINWWYOINI
`
`éOld
`
`ANOLOWIA SAINAMOLOANGJOAVA|‘OANI
`
`DVIdMAOO]|OVLAUWNA|SSIDOV|NOIVOIGOW|NOVO
`1OardOViVdFd dWVISINIL
`1O3rgO 1OdPdOVIVO
`dINVISSIWILLdINVISAWILUWSdi
`
`
`ANOLOIVI|YAdVIH
`
`
`SSIDOV|NOUVDIIGOWNOLW3dOYIgIOSENns
`
`
`dWVISIWILdWNVISAWILdWIVISSAIL
`
`
`VIVdFdGAldAYONSUOVv3HLosrgO
`
`
`
`YdQVSHLOArdO
`
`AJOLOING
`
`AMINA
`
`
`

`

`U.S. Patent
`
`Aug.3, 1999
`
`Sheet 3 of 5
`
`5,931,947
`
`OWNER KEY
`
`SUBSCRIBER KEY
`
`BACKUP KEY
`
`OBJECT ADMIN
`KEY
`
`EXTEND|}CHANGE}}DELETE READ
`
`KEY
`KEY
`KEY
`KEY
`
`FIG, 3
`
`

`

`U.S. Patent
`
`Aug.3, 1999
`
`Sheet 4 of 5
`
`5,931,947
`
`RECEIVE REQUEST
`FROM NETWORK
`
`REJECT REQUEST
`
`\ 4
`
`3
`
`
` YES
`
`DEVICE
`
`NONCE
`REQUEST
`
`NO
`42
`GENERATE AUTH KEY
`YES
`
`4
`
`4
`
`45
`
`AUTHORIZED?
`
`NO
`
`YES
`
`PERFORM REQUEST
`
`AUTHENTICATE
`
`SEND RESPONSE
`
`FIG, 4
`
`Ab
`
`47
`
`48
`
`

`

`U.S. Patent
`
`Aug.3, 1999
`
`Sheet 5 of 5
`
`5,931,947
`
`GET CURRENT
`DEVICE NONCE
`
`REQUEST NONCE
`EVICE
`
`5]
`
`YES
`
`54
`
`ANSWER NOT FRESH
`
`YES
`
`
`
`N
`
`
` HAS REQUEST
`HMAC ALREADY
`
`
`BEEN USED WITH
`
`THIS NONCE?
`
`
`
`ADD REQUEST NONCE
`AND HMACTO HISTORY
`
`
`
`
`ANSWER FRESH
`
`FIG. 5
`
`

`

`5,931,947
`
`1
`SECURE ARRAY OF REMOTELY
`ENCRYPTED STORAGE DEVICES
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application contains materials related to an applica-
`tion for “A Decentralized Remotely Encrypted File System,”
`by R. Burnset al., Ser. No. 08/927,772,filed concurrently
`with this application, commonly assigned, and incorporated
`by reference herein.
`
`10
`
`FIELD OF THE INVENTION
`
`BACKGROUND OF THE INVENTION
`
`20
`
`2
`across the network, an eavesdropper could view andalter the
`contents of the packets. Authentication was later added to
`version 3 of the NFS protocol.
`Another file system,
`the Andrew File System (AFS,
`reference 2), and its follow-on Decorum File System (DFS,
`reference 3) are other network file systems that allow uscrs
`accessto the file systems as if they were local file systems.
`AFSrelies on the authorization service Kerberos (reference
`4) to authenticate exchanges between the network client and
`the file system. AFS does not encrypt the file system data.
`So, an eavesdropper can view the data that is requested or
`sent to an AFS server. Version 1.2 of DFS added the option
`of encryption and integrity guarantees (reference 5).
`‘lhe present invention relates generally to distributed data
`Cryptographic File System (CFS, reference 6) isafile
`15
`processing. More particularly,
`the invention relates to a
`system that acts as a local file system and uses another
`system of remotely encrypted data storage devices for
`shadowfile system as a repository of data. Each directory of
`providing secure data sharing among networked clients in a
`the file system has an encryption key associated that is used
`distributed file system.
`to encrypt
`important meta-data (such as filenames and
`symbolic links) and file data. CFS uses a modified Data
`Encryption Standard (reference 7) to perform the encryp-
`tion. Data is encrypted and then stored in the shadow file
`system. Each file in CFS has a corresponding file in the
`shadow file system. Using NFS as the shadow file system
`allows CFSto act as a networkfile system. Since the shadow
`file system is the repository of data, it must provide authen-
`tication for changesto the files. If NFS is used as the shadow
`file system, for example, CI'S can be subjectto replays(i.e.,
`a copy of the data is presented to pretend that it is coming
`from the originator).
`In general, the above-described distributed file systems
`Distributed file systems have manysecurity problems that
`run on general purpose hardware and general purpose oper-
`local file systems do not have. The networkitself is suscep-
`ating systems. There has been workdoneto design hardware
`tible to security risks such as snooping (unauthorized break-
`and operating systems specifically for file serving. An
`ins), spoofing (impersonation), and packet eavesdropping
`example of this is the “file server appliance” described in
`(unauthorized receipt of data being transmitted over the
`reference 8. Special purpose file servers are able to outper-
`network). The identity of a network client can be spoofed
`form file servers running on general purpose platforms
`such as where a user id can be forged in requeststoafile
`because they can be optimized for file serving. However,
`server. In addition, the distributed file systems still have the
`these file servers are still left with the security problems
`vulnerabilities of the local file systems. The disk containing
`file data can be stolen and mounted on another machine,
`inherent in the distributed file systems they are supporting.
`bypassing the protection afforded by the operating system.
`Other storage device configurations are defined in the
`The distributed file server can be broken into, giving the
`Serial Storage Architecture (SSA, reference 9) and Fibre
`attacker root access to the disk. Backup tapes are not
`Channel Arbitrated Loop (FCAL,reference 10) to allow a
`generally encrypted, and data is easily accessed if they are
`network of the devices and host computers to share
`stolen.
`resources. These types of storage networks are inherently
`private. Thus, many of the above security problems can be
`ignored (and not adequately addressed) where the hosts and
`devices attached to the storage network are trusted.
`Architectural convergence of LAN and I/O devices is
`occurring because one interconnect can often satisfy both
`environments. The network is emerging as the future “back-
`plane” of high-performance systems. Studies have shown
`that attaching storage devices to an area network can reduce
`the load onfile servers, resulting in improved performance
`of the distributed file system (reference 11). Traditionally,
`storage networks such as SSA and FCAL are isolated
`networks. Isolated networks limit access to only the hosts
`and devices directly connected to the network. In general,
`local area networks are interconnected to other networks.
`The interconnection of networks make it more difficult to
`
`Distributed file systems allow networked computers
`(referredto as clients) to access remote storage devices asif
`the devices were on a local file system. These file systems
`allow for sharing of data among networked clients.
`Additionally, a user can access the networked data from
`other networked computers in the same way she accessesit
`from her own computer. This type of network file sharing is
`becoming increasingly prevalent as the computing industry
`becomes more network centric.
`
`There are three security areas that existing distributed file
`systems either fail
`to address, or address inadequately:
`confidentiality, integrity and authentication. Confidentiality
`refers to the requirement that the file system data can only
`be read by the parties that are intended to have access to the
`data.
`Integrity means that
`it
`is possible for the parties
`accessing the data to verify that the data read wasnotaltered.
`Authentication requires that the exchanges between the data
`repositories and the file system clients are done such that
`both parties of the exchangesare able to verify the messages
`involved came from the other.
`
`Network File System (NFS) was an early network file
`system that has gained wide spread adoption. (See, for
`example, reference 1). When NFSwasintroduced,it relied
`on the operating system to enforce confidentiality, integrity,
`and authentication. It allowed uscrs to access the network
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`file system. Network
`file system as if it were a local
`communications were unencrypted and unauthenticated.
`The administrators of the local machine could become any
`user on the machine and gain accessto the users files. Other
`machines on the network could disguise as another machine
`and fool the NFS server. Since packets were not encrypted
`
`65
`
`limit access to hosts and devices. In particular, TCP/IP is
`vulnerable to a variety of security attacks. Often, proposals
`to LAN-attached storage devices ignore the security impli-
`cations of controlling device access in this more vulnerable
`environment. In reference 11, Gibson et al. propose using
`time-limited capabilities and secure coprocessors to estab-
`lish a secure communication channel to the storage devicc,
`
`

`

`5,931,947
`
`3
`in which the security of the data on the device rests with the
`security of the coprocessor.
`Accordingly, there is still a need for a secure network of
`storage devices that can support a distributed networkfile
`system in which data can be moved,archived, and backed up
`in asecure manner,files can be securely copied directly from
`one device to another, and all data encryption is handled by
`the clients rather
`the devices to overcome the above-
`described security problems.
`REFERENCES
`
`1. Sandberg,R., et al., “Design and Implementation of the
`Sun Network Filesystem,” USENIX Conference
`Proceedings, USENIX Association, Berkeley, Calif., Sum-
`mer 1985.
`
`2. Howard, J. H. et al., “Scale and Performance in a
`Distributed File System, ACM Transactions on Computer
`Systems”, Vol. 6, No. 1, February 1988.
`3. Kazer, M., et al., “DEcorum File System Architectural
`Overview”, USENIX Summer Conference, June 1990.
`4. Steiner, J. G., “Kerberos: An Authentication Service
`For Open Network Systems,” Winter USEIX, 1988, Dallas,
`Tex.
`
`5. Everhart, C., “Security Enhancements for DCE DFS”,
`OSF RFC 90.0, February 1996.
`6. Blaze, M., “A Cryptographic File System for Unix”,
`First ACM Conference on Communications and Computing
`Security, November 1993.
`7. Data Encryption Standard, National Bureau of
`Standards, Federal Information Processing Standards Pub-
`lication Number 46, National Technical
`Information
`Service, Springfield, Va., Jan. 15, 1977.
`8. Ilitz, D., et al., “I'ile System Design for an NI’S Tile
`Server Appliance”, 1994 Winter USENIX, January 1994.
`9. ANSI X3.294-1996, “Information Technology - Serial
`Storage Architecture SCSI-2 Protocol”.
`10. ANSI X3.272-1996, “Information Technology - Fibre
`Channel - Arbitrated Loop (FC-AL)”.
`11. Gibson, G. A., et al., “File Server Scaling with
`Network-Attached Secure Disks”, Proceedings of the ACM
`International Conference on Measurement and Modeling of
`Computer Systems (Sigmetrics °97), June 1997.
`SUMMARY OF THE INVENTION
`
`The present invention relates to a secure array of network
`storage devices and method for storing, accessing, and
`updating data stored on those devices in secure manner. The
`devices and methods facilitate the implementation of dis-
`tributed file systems. Data is made accessible only to autho-
`rized network clients. The network client performs all
`encryption and decryption of data and metadata. The storage
`devices themselves do not have encryption, but serve as an
`authenticated repository of data. Backup, migration or rep-
`lication of data is performed by copying the contents of a
`storage device, a file systemora file. Data and/or metadata
`always remains secured while in transit.
`The advantages offered by this approach include:
`Secure movement of data and metadata between the
`
`network client and the network storage device.
`Possession of either a network storage device or a backup
`of a storage device, file system or file does not permit
`access to data or metadata.
`
`The arrayof network storage devices can be comprised of
`existing direct-access disk drives, optical drives, tape
`devices, or a combination of such devices.
`
`4
`Files can be copied directly from one storage device to
`another storage device in a secure manner. The network
`clients only involvement would beto initiate the action.
`Also, since data transferis directly device to device the
`overhead to the network client is minimal.
`
`Backup, archive and migration of data and metadata is
`secure.
`
`The present invention achieves the foregoing and other
`objects by providing an array of network storage devices
`that serve as repositories of remotely encrypted data, where
`each network storage device is an independent entity. All
`encryption is done by the networkclients rather than by the
`devices.
`Each network storage device in the array has a device
`ownerfor managing access to the device’s data. It also sets
`up subscribers who can create objects on the device. The
`ownertypically includes an owner key, a device nonce, and
`a noncehistory. The owner keyis used for deriving authen-
`tication keys. The device nonce is used for guaranteeing
`freshness of the requests of the clients, and is changed after
`each request. ‘he nonce history contains a list of recent
`nonces and the hashed message authentication codes used
`with them. The owner key and the device nonceare typically
`implemented in the firmwarearea of the storage device, and
`are usually shipped with the device to a user. The device also
`includes a storage media and a request processor. The
`storage media contains a list of subscribers that are able to
`create objects on the device, and a repository of network
`objects. Each object has a unique id.
`The request processor receives requests from the network,
`services them, and returns responses to the clients. Each
`request specifies an object id and a byte range, whichis into
`sectors on the device. To read or write directory entries onto
`a device, a request includes an object id, an entry tag, and a
`lookupkey.In the case of read, the request specifies a range
`of directory entries.
`Network objects are used to store data on the storage
`devices. There are two types of network objects: directory
`data objects and file data objects. File data objects containall
`orpartof the file data of a file. Directory data objects contain
`all or part of the directory entries of a directory. Each
`network object on a device is identified by a unique object
`id.
`
`Requests to a network storage device need to be authen-
`ticated and guaranteed for freshness. A request that will
`change the state of the storage will be authenticated by the
`device, rather than the client. The results of a request needs
`to be authenticated by the network client to prevent spoofing
`problems. The authentication of the results and access rights
`is done using hashed message authentication codes
`(HMACs), such as those described in “HMAC: Keyed-
`Hashing Jor Message Authentication,” Request for Com-
`ments No. 2104, by Krawczyk et al., Network Working
`Group, Feb., 1997 (hereinafter, Krawczyk et al.).
`Additional objects and advantages of the present inven-
`tion will be set forth in the description which follows, and
`in part will be obvious from the description and with the
`accompanying drawing, or maybe learned from the practice
`of this invention.
`
`BRILI DESCRIPTION OF TITE DRAWINGS
`
`FIG. 1 is a simplified block diagram of a network storage
`device in accordance with the invention.
`
`FIG. 2 shows the structure of the network objects in
`accordance with the invention.
`
`FIG. 3 showsthe relationships among the authentication
`keys used by the device and data access methods of the
`invention.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`

`

`5,931,947
`
`5
`FIG. 4 is a flowchart representing showing an operational
`sequence of a preferred embodimentfor the request proces-
`sor in FIG. 1, for processing requests from the network
`clients.
`
`FIG. 5 is a flowchart representing an operational sequence
`of a preferred embodiment of step 43 in FIG. 4, for deter-
`mining the freshness of a client request.
`DESCRIPTION OF THE PREFERRED
`EMBODIMENTS
`
`10
`
`The invention will be described in terms of a remotcly
`encrypted device for use in an array of like devices to
`support a secure distributed file system, and methods for
`storing, sharing, updating, and accessing file data stored in
`such a system. However, persons skilled in the art will
`recognize that a processor, a process controller, or a distrib-
`uted computing system, which includes data storage and
`suitable programming means for operating in accordance
`with the devices and methods to be disclosed, also falls
`within the spirit and scope of the invention. In addition, the
`invention may also be embodied in a computer program
`product,
`i.e., a computer-readable medium such as a dis-
`kette. Such a product may be intended, manufactured, or
`sold for use with a suitable data processing system. Pro-
`gramming means for directing the data processing system,
`with which the productis to be used, to execute the steps of
`the methods of the invention, is written on the recording
`medium in a form read by the data processing system.
`The network storage devices of the present invention
`address the security issues associated with a distributedfile
`system, in which the devices are attached to a local area
`network (LAN) as well as other network types. These
`devices include direct-access disk drives (DASDs), optical
`storage disks,
`tape drives, computers or instruments that
`include means for storing data, or a combination of them.
`The devices form a secure computer system to allow secure
`movement of data and metadata between a network client
`
`and a network storage device such as in data backup, archive
`and migration operations. Possession of either a network
`storage device or a backup of a storage device, file system
`or file does not permit access to data or metadata. Data files
`can be copied directly from one storage device to another
`device in a secure manner. ‘he network client’s only
`involvement would be to initiate the copying action. Also,
`sinee data is transferred directly between the devices, the
`overhead to the network client is minimal.
`
`To achieve the above goals, the network storage devices
`of the invention are used as repositories of remotely
`encrypted data, where each network storage device is an
`independent entity. All encryption is done by the network
`clicnts (thc components of the network that request data
`from the devices), so that data that travels over the network
`is stored encrypted. The advantage of this approachis that
`data is encrypted or decrypted by the clients as opposed to
`having the encryption being done at both the devices and the
`clients. In order for the system to revoke access to an object
`(file or directory) on the device,
`the object must be
`re-encrypted.
`FIG. 1 is a block diagram of a network storage device 1,
`which is part of the sccure array of enerypted devices,
`according to the invention. The device 1 is one of many
`similar devices attached to a network 2, along with the
`network clicnts (not shown). Each storage device 1 has a
`device ownerfor controlling access to the device’s data. The
`device owner sets up subscribers who are authorized to
`ercate objects on the device and typically includes an owner
`
`weOo
`
`40
`
`50
`
`55
`
`60
`
`6
`key 3, a device nonce 4, and a nonce history 5. The owner
`key 3 is used for deriving authentication keys, as described
`below andillustrated in PIG. 3. The device nonce 4 is used
`
`for guaranteeing freshness of the requests ofthe clients, and
`is changed after each request. The nonce history 5 contains
`a list of recent nonces and hashed message authentication
`codes (HMACs) that were used with them. HMACsare
`described, for example, by Krawczyk et al. The determina-
`tion of freshness of the requests and the updating of the
`nonce history 5 are described below in reference to FIG. 4.
`The owner key 3 and the device nonce 4 are typically
`implemented in the firmware area 6 of the storage device 1,
`and are usually shipped together with the device 1 to its user.
`The nonce history 5 preferably resides in the random-access-
`memory (RAM)area 7 of the device 1.
`
`The device 1 also includes a storage media 8 and a request
`processor 9. The storage media 8 contains a subscriber list
`10 and an object repository 11. The subscriber list 10
`includes the subscriber ids of the clients that are able to
`
`create objects on the device, while the object repository 11
`houses the network objects. Each object will have a unique
`id that will never be used again on this device even if the
`object is deleted. Details on the layout of the network objects
`are described below in reference to in FIG. 2. The request
`processor 9 receives requests from the network, services
`them, and returns responses as provided in the flowchart of
`FIG. 4. Arcquest is a command scnt by a clicnt to a nctwork
`storage device to access data stored on it. The request
`specifies an object id and a byte range. The networkstorage
`device 1 is responsible for mapping the byte range in the
`request to sectors on the device(i.e., corresponding units of
`data stored on the storage media 8). To read or write
`directory entries, a request is also sent to a network storage
`device. Such a request specifies an object id, an entry lag,
`and a lookup key. In the case of read, the request specifies
`a range of directory cntrics. Again,
`the nctwork storage
`device is responsible for mapping the directory entries in the
`request to sectors on the device.
`NETWORK OBJECTS
`
`Network objects arc used to store data on the storage
`devices. There are two types of network objects: directory
`data objects and file data objects. File data objects containall
`orpartofthe file data of a file. Directory data objects contain
`all or part of the directory entries of a directory. Each
`network object on a device is identified by a unique object
`id. Note that an object id is not reused even if the corre-
`sponding object is deleted. Each object has an object admin-
`istrator key, which is used to create the lookup,read, extend,
`delete, and update keys for the object. The backup key is
`derived from the owner key 3 and is used to enumerate the
`objects on the storage device 1 and read those objects. This
`granularity of access allows a subscriber to create an object
`and delegate write authority to another user without having
`to also give the user the ability to grow the object. Table 1
`below lists the access rights for the various components in
`the device 1.
`
`FIG. 2 showsthe preferred formats for thefile data objects
`and directory data objects in the repositories, according to
`the invention. Both types of network
`
`

`

`5,931,947
`
`7
`
`TABLE 1
`
`The accesses rights and corresponding capabilities for the storage device.
`ACCESS RIGHT
`CAPABILITIES
`
`Owner
`Subscriber
`Object Administrator
`
`Extend
`Read
`Entry Change
`Update
`Delete
`Backup
`
`Create/Delete subscribers
`Create objects on the device
`Create extend, read, write, delete keys
`for a given object
`Increase or truncate the size of the object
`Read from the object
`Change or delete a directory entry
`Change the object
`Delete the object
`Enumerate the objects on the device
`Read objects from the device
`
`objects use a common object header. The format of the
`common header for both file and directory data objects is
`shown in FIG. 2. The first header ficld is a subscriber id,
`which represents the identification of the subscriber that
`created the object (i.e., its owner). This field is set by the
`storage device on object. The secondfield is a salt (a random
`data item) that is used to affect the generation of an object
`administrator key. To generate a new object administrator
`key, only the salt has to be changed. The third field is a
`timestamp which specifies the time of creation of the object
`on the storage device. The creation timestamp is set by the
`storage device. The fourth field is a modification timestamp
`thal is updated by the storage device 1 wheneverthe object
`is changed. The fifth headerfield is the access timestampthat
`is updated by the storage device whenever a read is per-
`formed on the object.
`Eachfile data object, also shown in FIG. 2, preferably
`includes the common network object header followed by
`encrypted file data. The network client is responsible for
`performing encryption and decryption of file data.
`Encrypted file data is seen simplyas a randomstring of bytes
`by the network storage device.
`A directory data object, also shown in FIG. 2, preferably
`includes of a common network object header followed by an
`encrypted directory information block and anarray of direc-
`tory entries. The network client is responsible for perform-
`ing encryption and decryption of the directory information
`block. FIG. 2 also showsa preferred structure of a directory
`entry. Each directory entry has a creation time stamp,
`modification time stamp and access time stamp that
`is
`maintained by the storage device on entry creation, update,
`and read. The access time stamp is followed by an cntry tag.
`The entry tag is set by the storage device on object creation.
`The tag is unique in the directory data object and is not
`reused bythe directorydata object. The entry tag is followed
`by the lookup tag of the directory entry. The lookup tag can
`be changed by the network client, but must be unique in the
`directory data object. The lookup tag is followed bythe entry
`data which is opaque to the device
`FRESHNESS AND AUTHENTICATION
`
`Requests to a network storage device need to be authen-
`ticated and guaranteed for freshness. The storage device also
`enforces access rights listed in Table 1 above. A request that
`will change the state of the storage will be authenticated by
`the device, rather than the clicnt. The results of a request
`needs to be authenticated by the network client to prevent
`spoofing problems. Furthermore, all requests and responses
`must also be guarantecd fresh to prevent replays (i.c.,
`presenting of copies of requests and responses by some other
`entities in the system to impersonate the true requester or
`recipient). The authentication of the results and accessrights
`
`10
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`8
`is done using Hashed message authentication codes
`(HMACs), such as those described in Krawczyk et al., for
`improved performance. Freshness is guaranteed using non-
`ces in the HMAC. Since the network storage device does not
`have any encryption capability, HMAC keys can’t be
`exchanged via the network. ‘l'ypically, the network storage
`device is shipped with a device owner key in firmware and
`the owner is given the key with the device upon purchase.
`All keys pertaining to access to the device are derived from
`the owner key.
`KEY DERIVATION
`FIG. 3 showsthe relationship of the HMACkeys to each
`other. The derivation of access keys from the owner keyis
`done using published formulas and involve shared secrets so
`that key exchange over the network doesn’t have to take
`place. Table 2 shows howthe keysto the accessrights (from
`Table 1) are derived. The basis of the derivation is the
`one-way-ness and randomness of the hash function (HQ),
`wheresid is the subscriber id, oid is the object id, and uid is
`the user id used by the network client. The hash function is
`expressed as having variable number of arguments. To use
`standard hash fuoctions, the arguments are concatenated and
`then hashed. Examples of standard hash functions are
`described in “The MD5 Message Digest Algorithm’, by
`Rivest, R. L., Request For Comments 1321, April 1992, and
`“Security Enhancements for DCE DFS”, by Everhart, C.,
`OSF RFC 90.0, February 1996.
`
`TABLE 2
`
`ACCESS KEY
`
`Derivations of device keys
`DERIVATION
`
`Owner (Ko)
`Subscriber (Ks[sid])
`Object Administrator (Ka[oid])
`Extend (Kx[oid])
`Read (Ki[oid,uid])
`Lookup (Kl[oid,uid])
`Update (Ku[oid])
`Delete (Kd[oid])
`Backup (Kb)
`
`Shipped with device
`H(Ko,sid)
`H(Ks[sidoid)
`H(Ka[oid],‘x’)
`II(Ka[oid],uid,‘r’)
`H(Ka[oid],uid,‘1’)
`H(Kafoid],‘u’)
`H(Kafoid],‘d’)
`H(Ko,‘b’)
`
`NONCES
`
`Both the network clients and storage devices need to
`guarantee the freshness of the requests and responses to
`avoid replay attacks. Network clients guarantee freshness of
`the responses by generating a nonce. Nonces are numbers
`that are generated at random and used only once. They are
`included in the requests. The freshness of a response is
`validated by verifying that the nonce was used in the HMAC
`of the response. Storage devices guarantee freshness of a
`request byvalidating that its own nonce is included in each
`request’s HMAC.
`The device 1 changes its nonce after each request. A
`network client can request the device’s nonce at any time.
`This request is an exception to the rule that the device nonce
`is included in all requests. To allow concurrent use of a
`device nonce, the storage device will keep a short history of
`recent nonces and the HMACsused with them. A requestis
`considered a replay under one of two circumstances: a
`request arrives with a device nonce that is not current and
`notin the history, or the request has a nonce and HMACwith
`is already in the history. Otherwise, the request is accepted
`and added to the nonce history.
`FIG. 4 is a flowchart showing an opcrational sequence of
`a request processor 9 for processing requests from the
`network clients. Starting with step 40, a request from the
`network is reccived at the storage device 1. If the requestis
`
`

`

`5,931,947
`
`10
`to the key used it the request. K is the key that was used in
`the request. Note, if the request failed due to an invalid key
`used in the request, keydata and K are not used.
`Subscriber requests
`Subscribers are clients who can insert objects onto the
`device. Each subscriber has an id (sid). Table 2 showsthat
`the subscriber key is derived from the subscriber id. Sub-
`scribers can onlybe created and deleted by the device owner.
`Anyone can enumerate the subscribers of a device. Only
`subscribers can authenticate the enumeration response. The
`disk maintains a list of subscribers on the storage media.
`Creating subscriber keys
`An ownerusesthe following protocol to create subscriber
`keys:
`C—=>D:
`
`AddSubscriber,sid, I, 1,, H(AddSubscriber, sid, I, K,)
`The owner sends the AddSubscriber request with the
`subscriberid (sid) and the current device nonce. The request
`is hashed with the owner key to authenticate that the request
`was made by the owner and the device nonceis included in
`the request to guarantee freshness. If successful the device
`responds with:
`D—>C:
`SubscriberAdded, sid, Ij, I., H(SubscriberAdd, sid, Iz, K,)
`The device doesn’t need t