2.1 The basic capability scheme

Our protocol for using capabilities is similar to that of NASD [10,9] and SCARED [19], except that our capabilities describe access in terms of blocks rather than objects. Intuitively, a capability is a self-descriptive certificate that grants a specified type of access to parts of a disk (see Figure 1) when used with an associated secret. Our capabilities contain a group ID and a capability ID, which are used for revocations as explained in Section 2.2; a disk ID, which specifies the disk to which this capability applies; a list of extents, the ranges of physical blocks for which access is being granted; and an access mode (read, write, or both).

Figure 1: Contents of a capability. The group ID and capability ID are used in our new revocation scheme. The disk ID, extents, and mode describe the access granted by the capability.

The secret is used to prevent forgery of illegal capabilities or of illegal requests using legal capabilities, as we now explain. The secret is generated using a keyed-hash message authentication code, or MAC [1]. A MAC function $h({\text{\small\sffamily data}},{\text{\small\sffamily key}})$ returns a string ${\text{\small\sffamily mac}}$ of fixed length with the following unforgeability property: without knowing the value of ${\text{\small\sffamily key}}$, it is infeasible to find any new pairs of ${\text{\small\sffamily mac}}$ and ${\text{\small\sffamily data}}$ such that ${\text{\small\sffamily mac}}=h({\text{\small\sffamily data}},{\text{\small\sffamily key}})$. MAC functions can be computed quite efficiently in practice, unlike public-key signatures.

Every capability $c$ is associated with a secret $h(c, k)$, where $k$ is a secret key shared by the metadata server and the disk whose ID is specified in $c$. (There is a different key for each disk.) The use of this secret is best explained by an example. Figure 2 shows a client opening a file for the first time, and then reading or writing some data. To open the file, the client contacts the metadata server associated with the file. If the file's metadata is not cached at the server, the server must retrieve it from the relevant disk, shown by dashed lines in the figure (the metadata server accesses the disk in the same way that the client does, which we explain below).

The server checks if the client is permitted to access the file, and if so it gives the client the following: (1) the list of physical blocks comprising the file (its blockmap), (2) a capability $c$ for the file's blocks² with the requested access mode (read, write, or both), and (3) the secret $s=h(c,k)$ associated with $c$. The server's reply (in particular $s$) must be sent over a secure channel (shown by a darker line in the figure) to prevent eavesdroppers from learning the secret needed to use the capability. A secure channel can be obtained by encrypting under a block cipher using a session key established by an authentication protocol such as Kerberos.

Figure 2: Opening and accessing a file. When a client wishes to access a file, it talks to the metadata server to get a capability $c$ and its associated secret $s=h(c,k)$. The client can then access the file directly from disk. The disk verifies that the access is authentic by checking that the client has correctly computed the ``double MAC'' $m=h({\it op},s)=h({\it op},h(c,k))$.

Next, in order to read or write data from or to the file, the client issues block requests to the disk using the capability that it obtained. More precisely, the client sends to the disk an operation ${\it op}$ that consists of (1) the type of access (read or write); (2) the range of physical blocks to be accessed; and (3) in case of a write operation, the data to be written. Together with ${\it op}$, the client also sends the capability $c$ provided by the server and a MAC $m=h({\it op},s)$, where $s$ is the secret associated with $c$. Because $m=h({\it op},s)=h({\it op},h(c,k))$, we call this trick the ``double MAC''. (The double MAC is not new; the earliest references we know of are Gobioff et al. [10] and Mittra et al. [16].) The disk can verify that the MAC is correct since it receives both $c$ and ${\it op}$, and it has the secret key $k$. Note that the double MAC serves a double purpose: (1) it is a proof that the client knows $s$ and thus has been authorized to use the capability $c$ to issue the operation ${\it op}$, and (2) it prevents ${\it op}$ from being tampered with, because if an attacker changes ${\it op}$ it would not know how to compute the required new MAC.³

Once the disk has checked and executed the requested operation ${\it op}$, it sends back a response ${\it resp}$ together with $h({\it resp},s)$. Here ${\it resp}$ contains data (if the request was a read) or simply an acknowledgment (if the request was a write). The client verifies that $h({\it resp},s)$ was computed correctly, which prevents responses from being forged.

For simplicity, we presented this example without encryption for privacy. One simple way of adding encryption involves the server also giving the client a session key $e$ and a token, which is $e$ encrypted under $k$; the client and disk encrypt their messages using $e$, prepending the token in the clear so the disk can figure out which session key to use.