Zero-interaction authentication.
Laptops are vulnerable to theft, greatly increasing the likelihood of exposing sensitive files. Unfortunately, storing data in a cryptographic file system does not fully address this problem. Such systems ask the user to imbue them with long-term authority for decryption, but that authority can be used by anyone who physically possesses the machine. Forcing the user to frequently reestablish his identity is intrusive, encouraging him to disable encryption.Our solution to this problem is Zero-Interaction Authentication, or ZIA. In ZIA, a user wears a small authentication token that communicates with a laptop over a short-range, wireless link. Whenever the laptop needs decryption authority, it acquires it from the token; authority is retained only as long as necessary. With careful key management, ZIA imposes an overhead of only 9.3% for representative workloads. The largest file cache on our hardware can be re-encrypted within five seconds of the user's departure, and restored in just over six seconds after detecting the user's return. This secures the machine before an attacker can gain physical access, but recovers full performance before a returning user resumes work.
Figure

1: Decrypting File Encrypting Keys
not impose undue usability burdens or noticeably reduce
le system performance.
The main contribution of this paper is not the construction
of a cryptographic le system. Blaze's CFS [1], Zadok's
Cryptfs [32], and Microsoft's EFS [19] all address the archi-
tecture, administration, and cryptographic methods for a
le system. However, none of these combine user authentication
and encryption properly. Some systems, such as EFS,
require the user to reauthenticate after certain events, such
as suspension, hibernation, or long idle periods, in an attempt
to bound the window of vulnerability. The user must
explicitly produce a password when any of these events oc-
cur. This burden, though small, will encourage some users
to disable or work around the mechanism.
2. DESIGN
ZIA's goal is to provide eective le encryption without
reducing performance or usability. All on-disk les are encrypted
for safety, but all cached les are decrypted for per-
formance. With its limited hardware and networking per-
formance, the token is not able to encrypt and decrypt le
data without a signicant performance penalty. Instead,
le keys are stored on the laptop's disk, encrypted by a key-encrypting
key. Only an authorized token holds the key-encrypting
key, thus the token is required to read les. This
process is illustrated in Figure 1.
There are two requirements for system security. First, a
user's token cannot provide key decryption services to other
users' laptops. Second, the token cannot send decrypted
le keys over the wireless link in cleartext form. Therefore,
the token and laptop use an authenticated, encrypted link.
Before the rst use of a token, the user must unlock it using
a PIN. Then he must bind the token and laptop, ensuring
that his token only answers key requests from his laptop.
Next, ZIA mutually authenticates the identity of the token
and laptop over the wireless link and exchanges a session
encryption key. After authentication, polling ensures that
the token, and thus the user, is still present. When the token
is out of range, ZIA encrypts cached objects for safety. The
cache retains these encrypted pages to minimize recovery
time when the user returns, preserving usability. The overall
process is illustrated in Figure 2. The remainder of this
section presents the detailed design of ZIA, starting with
the trust and threat model.
Use PIN
Bind to Token
Authentication/
Session Keys
Poll Token
Secure Laptop
Token Returns
This gure shows the process for authenticating and interacting
with the token. Once an unlocked token is bound
to a laptop, ZIA negotiates session keys and can detect the
departure of the token.

Figure

2: Token Authentication System
2.1 Trust and Threat Model
Our focus is to defend against attacks involving physical
possession of a laptop or proximity to it. Possession enables
a wide range of exploits. If the user leaves his login session
open, attacks are not even necessary; the attacker has all
of the legitimate user's rights. Even without a current login
session, console access admits a variety of well-known
attacks, some resulting in root access. An attacker can also
bypass the operating system entirely. For example, one can
remove and inspect the disk using another machine. A determined
attacker might even probe the physical memory of
a running machine.
ZIA must also defend against exploitation of the wireless
link between the laptop and token: observation, modica-
tion, or insertion of messages. Simple attacks include eavesdropping
in the hopes of obtaining decrypted le keys. A
more sophisticated attacker might record a session between
the token and laptop, and later steal the laptop in the hopes
of decrypting prior trac. ZIA defeats these attacks through
the use of well-known, secure mechanisms.
We assume that some collection of users and laptops belong
to a single administrative domain, within which data
can be shared. The domain includes at least one trusted authority
to simplify key management and rights revocation.
However, the system must be usable even when the laptop
is disconnected from the rest of the network. The token
and the laptop operating system form the trusted computing
base.
ZIA does not defend against a trusted but malicious user,
who can easily leak sensitive data and potentially extract key
material. ZIA does not provide protection for remote users;
they must be physically present. Attackers that jam the
spectrum used by the laptop-token channel will eectively
deny users access to their les. Our work is orthogonal to the
prevention of network-based exploits such as buer overow
attacks.
ZIA's security depends on the limited range of the radio
link between the token and the laptop. Repeaters could
be used to extend this range, though time-based techniques
to defeat such wormhole attacks exist [4, 13]. Similarly,
an attacker with an arbitrarily powerful and sensitive radio
could extend the range, though such attacks are dicult
given the attenuation of high frequency radios.
2.2 Key-Encrypting Keys
In ZIA, each on-disk object is encrypted by some symmetric
Ke. The link connecting the laptop and token is
slow, and the token is much less powerful than the laptop.
Consequently, le decryption must take place on the laptop,
not the token. The le system stores each Ke, encrypted
by some key-encrypting key, Kk; we write this as Kk(Ke).
Only tokens know key-encrypting keys; they are never di-
vulged. A token with the appropriate Kk can decrypt Ke,
and hence enable reading any le encrypted by Ke.
In our model, the local administrative authority is responsible
for assigning key-encrypting keys. For reliability in the
face of lost or destroyed tokens, the administrative authority
must also hold these keys in escrow. Otherwise, losing a
token is the equivalent of losing all of one's les. Escrowed
keys need not be highly available, eliminating the need for
oblivious escrow [3] or similar approaches.
Laptops are typically \owned" by a particular user; in
many settings, one could provide only a single, unique Kk
to each user. However, ZIA must support shared access
as well, because most installations within a single administrative
domain share notions of identity and privilege. For
example, two colleagues in a department may borrow each
others' machines, and ZIA cannot preclude such uses. To
support sharing, each le key, Ke, can be encrypted by both
a user key, Ku, and some number of group keys, Kg.
The specic semantics of group access and authorization
are left to the le system. For example, one can assign key-encrypting
keys to approximate standard UNIX le protec-
tions. Access to a le in the UNIX model is determined by
dividing the universe of users into three disjoint sets: the
le's owner, members of the le's group, and anyone else
empowered to log in to that machine. We refer to this last
set as the world. Each user has a particular identity, and is
a member of one or more groups. One could assign a user
key, Ku, to each user; a group key, Kg, to each group; and
a world key, Kw, to each machine. A user's token holds her
specic Ku, each applicable Kg, and one Kw per machine on
which she has an account. Each le's encryption key, Ke, is
stored on disk, sealed with its owner's key, Ku. If a le was
readable, writable, or executable by members of its owning
group, Kg(Ke) would also be stored. Finally, Kw(Ke)
would be stored for les that are world-accessible. Note that
the latter is not equivalent to leaving world-accessible les
unencrypted; only those with login authority on a machine
would hold the appropriate Kw.
Group keys have important implications for sharing and
revocation in ZIA. Members of a group have the implicit
ability to share les belonging to that group, since each
member has the corresponding Kg. However, if a user leaves
a group, that group's Kg must be changed to a new Kg0 . Fur-
thermore, the departing user|who is no longer authorized
to view these les|may have access to previously-unsealed
le keys. As a result, re-keying a group requires that the
contents of each le accessible to that group be re-encrypted
with a new Ke0 , and that new key be re-sealed with the appropriate
key-encrypting keys.
Re-keying can be done incrementally. To distribute a new
group key, the administrative authority must supply a certied
Kg0 to the token of each still-authorized user. This
must be done in a secure environment to prevent exposure
of Kg0 . Thereafter, a token encountering a laptop with \old"
can continue to use it until it is re-keyed. However,
this policy must be pursued judiciously, since it increases
the amount of data potentially visible to an ejected group
member.
2.3 Token Vulnerabilities
Tokens provide higher physical security than laptops, since
they are worn rather than carried. Unfortunately, it is still
possible for a user to lose a token. Token loss is a very serious
threat since tokens hold key-encrypting keys. How can
we limit the damage of such an occurrence?
The most serious vulnerability surrounding token loss is
the extraction of key-encrypting keys. PIN-protected, tamper-resistant
hardware [31] makes this more dicult, as does
storing all Kk encrypted with some password. In either
case, the PIN/password must be known only to the token's
rightful owner. At rst glance, this seems to merely shift
the problem of authentication from the laptop to the token.
However, since the token is worn, it is more physically secure
than a laptop|it is reasonable to allow long-lived authentication
between the token and the user, perhaps on the order
of once a day.
Bounding the authentication session between the user and
token also prevents an attacker from protably stealing a
token, and then later a laptop. After the authentication
period expires, the token will no longer be able to supply
any requested Ke. Such schemes can be further improved
through the use of server-assisted protocols to prevent oine
dictionary attacks [17], with the laptop playing the role of
the server to the token's device.
Even tokens that have not been stolen can act as liabili-
ties. Supposed an attacker has a stolen laptop but no token,
and is sitting near a legitimate user from the same domain.
This tailgating attacker can force the stolen laptop to generate
decryption requests that could use one of the legitimate
user's key-encrypting keys. If the legitimate token
were to respond, the system would be compromised.
To prevent this, we provide a mechanism that establishes
bindings between tokens and laptops. Before a token will
respond to a particular laptop's request, the user must acknowledge
that he intends to use this token with that laptop.
There are several ways one can accomplish this. For exam-
ple, a token with a rudimentary user interface would alert
the user when some new laptop rst asks it to decrypt a le
key. The user then chooses to allow or deny that laptop's
current and future requests. As with token authentication,
bindings have relatively long but bounded duration; after
a binding expires, the token/laptop pair must be rebound.
Since a user can use more than one machine, a token may
be bound to more than one laptop. Likewise, a laptop may
have more than one token bound to it.
User-token authentication and token-laptop binding are
necessarily visible to the user, and thus add to the burden
of using the system. However, since they are both long-
lived, they require infrequent user action. In practice, they
are no more intrusive than having to unlock your oce door
once daily, without the accompanying threat of forgetting
to re-lock it. The right balance between usability and security
depends on the physical nature of the token, its user
interface capabilities, and the user population.
2.4 Token-Laptop Interaction
The binding process must accomplish two things: mutual
authentication and session key establishment. Mutual
authentication can be provided with public-key cryptography
[22]. In public-key systems, each principal has a pair
of keys, one public and one secret. To be secure, each prin-
cipal's public key must be certied, so that it is known to
belong to that principal. Because laptops and tokens fall
under the same administrative domain, that domain is also
responsible for certifying public keys.
ZIA uses the Station-to-Station protocol [9], which combines
public-key authentication and Die-Hellman key ex-
change. Die-Hellman key exchange provides perfect forward
session keys cannot be reconstructed, even if
the private keys of both endpoints are known. Once a session
key is established, it is used to encrypt all messages between
the laptop and token. Each message includes a nonce,
a number that uniquely identies a packet within each session
to prevent replay attacks [5]. In addition, the session
key is used to compute a message authentication code, verifying
that a received packet was neither sent nor modied
by some malicious third party [21].
2.5 Assigning File Keys
What is the right granularity at which to assign le encryption
small grain size reduces the data exposed
if a le key is revealed, but a larger grain size provides more
opportunity for key caching and re-use.
ZIA hides the latency of key acquisition by overlapping it
with physical disk I/O. Further, it must amortize acquisition
costs by re-using keys when locality suggests that doing so
is benecial. In light of this, we have chosen to assign le
keys on a per-directory basis.
People tend to put related les together, so les in the
same directory tend to be used at the same time. Therefore,
many le systems place all les in a directory in the same
cylinder group to reduce seek time between them [18]. This
makes it dicult to hide key acquisition costs for per-le
keys. Instead, since each le in a directory shares the same
le key, key acquisition costs are amortized across intra-
directory accesses. Alternatively, one could imagine keeping
per-le keys in one le, and reading them in bulk; however,
maintaining this structure requires an extra seek on each le
creation or deletion.
In our prototype, we store the le key for a directory in
a keyle within that directory. The keyle contains two encrypted
copies of the le key; Ku(Ke) and Kg(Ke), where
Ku and Kg correspond to the directory's owner and group.
We have chosen not to implement world keys, but adding
them is straightforward. This borrows from the UNIX protection
model, though it does not replicate it exactly. AFS,
the Andrew File System, makes a similar tradeo in managing
access control lists on a per-directory basis rather than a
per-le one [28]. However, AFS is motivated by conceptual
simplicity and storage overhead, not eciency in retrieving
access control list entries.
2.6 Handling Keys Efficiently
Key acquisition time can be a signicant expense, so we
overlap key acquisition with disk operations whenever possi-
ble. Since disk layout policies and other optimizations often
reduce the opportunity to hide latency, we cache decrypted
keys obtained from the token.
Disk reads provide opportunities for overlap. When a read
requiring an uncached key commences, ZIA asks the token
to decrypt the key in parallel. Unfortunately, writes do not
oer the same opportunity; the key must be in hand to
encrypt the data before the write commences. However, it
is likely that the decryption key is already in the key cache
for writes. To write a le, one must rst open it. This open
requires a lookup in the enclosing directory. If this lookup
is cached, the le key is also likely to be cached. If not,
then key acquisition can be overlapped with any disk I/O
required for lookup.
Neither overlapping nor caching applies to directory cre-
ation, which requires a fresh key. Since this directory is new,
it cannot have a cached key already in place. Since this is
a write, the key must be acquired before the disk operation
initiates. However, ZIA does not need a particular key to associate
with this directory; any key will do. Therefore, ZIA
can prefetch keys from the authentication token, encrypted
with the current user's Ku and Kg, to be used for directories
created later. The initial set of fresh keys is prefetched
when the user binds a token to a laptop. Thereafter, if the
number of fresh keys drops below a threshold, a background
daemon obtains more.
Key caching and prefetching greatly reduce the need for
laptop/token interactions. However, frequent assurance that
the token is present is our only defense against intruders. To
provide this assurance, we add a periodic challenge/response
between the laptop and the token. The period must be short
enough that the time to discover an absence plus the time to
secure the machine is less than that required for a physical
attack. It also must be long enough to impose only a light
load on the system. We currently set the interval to be
one second; this is long enough to produce no measurable
load, but shorter than the time to protect the laptop in the
worst case. Thus, it does not contribute substantially to the
window in which an attacker can work.
2.7 Departure and Return
When the token does not respond to key requests or chal-
lenges, the user is declared absent. All le system state must
be protected and all cached le keys ushed. When the user
returns, ZIA must re-fetch le keys and restore the le cache
to its pre-departure state. This process should be transparent
to the user: it should complete before he resumes work.
There are two reasons why a laptop might not receive a
response from the token. The user could truly be away, or
the link may have dropped a packet. ZIA must recover from
the latter to avoid imposing a performance penalty on a still-
present user. To accomplish this, we use the expected round
time between the laptop and the token. Because this
is a single, uncongested network hop, this time is relatively
stable. ZIA retries key requests if responses are not received
within twice the expected round trip time, with a total of
three attempts. Retries do not employ exponential backo,
since we expect losses to be due to link noise, not congestion;
congestion from nearby users is unlikely because of the short
range.
If there is still no response, the user is declared absent and
the le system must be secured. ZIA rst removes all name
mappings from the name cache, forcing any new operations
to block during lookup. ZIA then walks the list of its cached
pages, removing the clear text versions of the pages. There
are two ways to accomplish this: writing dirty pages to disk
and zeroing the cache, or encrypting all cached pages in
place.
Zeroing the cache has the attractive property that little
work is required to secure the machine. Most pages will be
clean, and do not need to be written to disk. However, when
the user returns, ZIA must recover and decrypt pages that
were in the cache. They are likely to be scattered across the
disk, so this will be expensive.
Instead, ZIA encrypts all of the cached pages in place.
Each page belongs to a le on disk, with a matching le
key. The page descriptor holds a reference to the cached,
decrypted key. Referenced keys may not be evicted|they
are wired in the cache. Without a corresponding key, there
would be no way to encrypt a cached page, and such keys
cannot be obtained from the now-departed token.
The expense of encryption is tolerable given our goal of
foiling a physical attack. For example, the largest le cache
we can observe on our hardware can be encrypted within ve
seconds. To be successful, an attacker would have to gain
possession of the machine and extract information within
that time|an unlikely occurance.
While the user is absent, most disk operations block until
the token is once again within range; ZIA then resumes
pending operations. This means that background processes
cannot continue while the user is away. In a physically secure
location, such as an oce building, xed beacons can
provide authentication in lieu of the user. Unfortunately,
such beacons would not prevent intra-oce theft and must
be used judiciously. At insecure locations, such as an air-
port, the user must not leave unencrypted data exposed and
background computation should not be enabled. This would
defeat the purpose of the system.
2.8 Laptop Vulnerabilities
What happens when a laptop is stolen or lost? Since ZIA
automatically secures the le system, no data can be extracted
from the disk. Likewise, all le keys and session
have been zeroed in memory. However, the laptop's
private key, sd, must remain on the laptop to allow transparent
re-authentication. If the attacker recovers sd, he can
impersonate a valid laptop. To defend against this, the user
must remove the binding between the token and the stolen
device. This capability can be provided through a simple
interface on the token. Use of tamper-resistant hardware in
the laptop would make extracting sd more dicult.
Instead of oine inspection, suppose an attacker modies
the device and returns it to a user. Now the system may
contain trojans, nullifying all protections aorded by ZIA.
Any device that is stolen, and later recovered, should be
regarded as suspect and not used. Secure booting [6, 14]
can be used to guard against this attack.
VFS
Keyiod
Authentication
Page Cache Client
Keyd
Authentication
Server
Token
ZIA Key Cache
Underlying
FS Kernel Module
This gure shows ZIA's design. The kernel module handles
cryptographic le I/O. The authentication client and server
manage key decryption and detect token proximity. A key
cache is included to improve performance.

Figure

3: An overall view of ZIA
3. IMPLEMENTATION
Our implementation of ZIA consists of two parts: an in-kernel
encryption module and a user-level authentication
system. The kernel portion provides cryptographic I/O,
manages le keys, and polls for the token's presence. The
authentication system consists of a client on the user's lap-top
and a server on the token, communicating via a secured
channel.

Figure

3 is a block diagram of the ZIA prototype. The
kernel module handles all operations intended for our le
system and forwards key requests to the authentication sys-
tem. We used FiST [33], a tool for constructing stackable
le systems [11, 27], to build our kernel-resident code. This
code is integrated with the Linux 2.4.10 kernel.
The authentication system consists of two components.
The client, keyiod, runs on the laptop, and the server, keyd,
runs on the token; both are written in C. The client handles
session establishment and request retransmission. The
server must respond to key decryption and polling requests.
The processing requirements of keyd are small enough that
it can be implemented in a simple, low-power device.
3.1 Kernel Module
In Linux, all le system calls pass through the Virtual File
System (VFS) layer [15]. VFS provides an abstract view of
the le systems supported by the OS. A stackable le system
inserts services between the concrete implementations of an
upper and lower le system. FiST implements a general
mechanism for manipulating page data and le names; this
makes it ideal for constructing cryptographic le services.
The FiST distribution also includes a proof-of-concept cryptographic
le system, Cryptfs.
3.1.1 File and Name Encryption
The kernel module encrypts both le pages and le names
with the Rijndael cipher [8]. We selected Rijndael for two
reasons. First, it has been chosen as NIST's Advanced Encryption
Standard, AES. Second, it has excellent perfor-
mance, particularly for key setup|a serious concern in the
face of per-directory keys.
ZIA preserves le sizes under encryption. File pages are
encrypted in cipher block chaining (CBC) mode with a
byte block. We use the inode and page osets to compute
a dierent initialization vector for each page of a le. Tail
portions that are not an even 16 bytes are encrypted in
cipher feedback mode (CFB). We chose CFB rather than ciphertext
stealing [7], since we are concerned with preventing
exposure, not providing integrity.
ZIA does not preserve the size of le names under encryp-
tion; they are further encoded in Base-64, ensuring that encrypted
lenames use only printable characters. Otherwise,
the underlying le system might reject encrypted le names
as invalid. In exchange, limits on le and path name sizes
are reduced by 25%. Cryptfs made the same decision for the
same reasons [32].
The kernel module performs two additional tasks. First,
the module prefetches fresh le keys to be used during directory
creation. Second, the module manages the storage of
encrypted keys. The underlying le system stores keys in a
but keyles are not visible within ZIA. This is done
for transparency, not security; on-disk le keys are always
encrypted.
3.1.2 Polling, Disconnection, and Reconnection
ZIA periodically polls the token to ensure that the user
is still present. The polling period must be longer than a
small multiple of network round-trip time, but shorter than
the time required for an adversary to obtain and inspect the
laptop. This window is between hundreds of milliseconds
and tens of seconds. We chose a period of one second; this
generates unnoticeable trac, but provides tight control.
Demonstrated knowledge of the session key is sucient to
prove the token's presence. Therefore, a poll message need
only be an exchange of nonces [5]: the device sends a num-
ber, n, encrypted with the key and the token returns n
encrypted by the same key. The kernel is responsible for
polling; it cannot depend on a user-level process to declare
the token absent, since it must be fail-stop. Similarly, if
the user suspends the laptop, or it suspends itself due to
inactivity, the kernel treats this as equivalent to loss of communication

If the kernel declares the user absent, it secures the le
system. Cached data is encrypted, decrypted le keys are
ushed, and both are marked invalid. We added a ag to
the page structure to distinguish encrypted pages from those
that were invalidated through other means. Most I/O in ZIA
blocks during the user's absence; non-blocking operations
return the appropriate error code.
When keyiod reestablishes a secure connection with the
token, two things happen. First, decrypted le keys are re-fetched
from the token. Second, le pages are decrypted
and made valid. As pages are made valid, any operations
blocked on them resume. We considered overlapping key
validation with page decryption to improve restore latency.
However, the simpler scheme is suciently fast.
3.2 Authentication System
The authentication system is implemented in user space
for convenience. All laptop-token communication is encrypted
and authenticated by session keys plus nonces. Communication
between the laptop and the token uses UDP rather
than TCP, so that we can provide our own retransmission
mechanism. This enables a more aggressive schedule, since
congestion is not a concern. We declare the user absent after
three dropped messages; this parameter is tunable. The to-
ken, in the form of keyd, holds all of a user's key-encrypting
keys. Since session establishment is the most taxing operation
required of keyd, and it is infrequent, keyd is easily
implemented on low-power hardware.
4. EVALUATION
In evaluating ZIA, we set out to answer the following questions

What is the cost of key acquisition?
What overhead does ZIA impose? What contributes
to this overhead?
Can ZIA secure the machine quickly enough to prevent
attacks when the user departs?
Can ZIA recover system state before a returning user
resumes work?
To answer these questions, we subjected our prototype to
a variety of benchmarks. For these experiments, the client
machine was an IBM ThinkPad 570, with 128 MB of physical
memory, a 366 MHz Pentium II CPU, and a 6.4 GB
IDE disk drive with a 13 ms average seek time. The token
was a Compaq iPAQ 3650 with 32MB of RAM. They were
connected by an 802.11 wireless network running in ad hoc
mode at 1 Mb/s. All keys were 128 bits long. The token
is somewhat more powerful than current wearable devices.
However, the rapid advancements in embedded, low-power
devices makes this a realistic token in the near future.
4.1 Key Acquisition
Our rst task is to compare the cost of key acquisition
with typical le access times. To do so, we measured the
elapsed time between the kernel's request for key decryption
and the delivery of the key to the kernel. The average
acquisition cost is 13.9 milliseconds, with a standard deviation
of 0.0015. This is similar to the average seek time of
the disk in our laptops, though layout policy and other disk
optimizations will tend to reduce seek costs in the common
case.
4.2 ZIA Overhead
Our second goal is to understand the overhead imposed by
ZIA on typical system operation. Our benchmark is similar
to the Andrew Benchmark [12] in structure. The Andrew
Benchmark consists of copying a source tree, traversing the
tree and its contents, and compiling it. We use the Apache
source tree. It is 7.4 MB in size; when compiled, the
total tree occupies 9.7 MB. We pre-congure the source tree
for each trial of the benchmark, since the conguration step
does not involve appreciable I/O in the test le system.
While the Andrew Benchmark is well known, it does have
several shortcomings; the primary one is a marked dependence
on compiler performance. In light of this, we also
subject ZIA to three I/O-intensive workloads: directory cre-
ation, directory traversal, and tree copying. The rst two
highlight the cost of key creation and acquisition. The third
measures the cost of data encryption and decryption.
File System Time, sec Over Ext2fs
Ext2fs 52.63 (0.30) -
Base+ 52.76 (0.22) 0.24%
Cryptfs 57.52 (0.18) 9.28%
ZIA 57.54 (0.20) 9.32%
This shows the performance of Ext2fs against ve stacked
le systems using a Modied Andrew Benchmark. Standard
deviations are shown in parentheses. ZIA has an overhead
of less than 10% in comparison to an Ext2fs system
and performs similarly to a simple single key encryption
system, Cryptfs.

Figure

4: Modied Andrew Benchmark
4.2.1 Modified Andrew Benchmark
We compare the performance of Linux's ext2fs against
four stacking le systems: Base+, Cryptfs, ZIA, and ZIA-
NPC. Base+ is a null stacked le system. It transfers le
pages but provides no name translation. Cryptfs adds le
and name encryption; it uses a single, static key for the
le system. Both Base+ and Cryptfs are samples from
the FiST distribution [33]. To provide a fair comparison, we
replaced Blowsh [29] with Rijndael in Cryptfs, improving
its performance. ZIA is as described in this paper. ZIA-
NPC obtains a key on every disk access; it provides neither
caching nor prefetching of keys.
Each experiment consists of 20 runs. Before each set,
we compile the same source in a separate location. This
ensures that the test does not include the eects of loading
the compiler and linker from a separate le system. Each
run uses separate source and destination directories to avoid
caching les and name translations. The results are shown
in

Figure

standard deviations are shown in parenthesis.
The results for ext2fs give baseline performance. The result
for Base+ quanties the penalty for using a stacking
le system. Cryptfs adds overhead for encrypting and decrypting
le pages and names. ZIA encompasses both of
these penalties, plus any costs due to key retrieval, token
communication and key storage.
For this benchmark, ZIA imposes less than a 10% penalty
over ext2fs. Its performance is statistically indistinguishable
from that of Cryptfs, which uses a single key for all
cryptographic operations. Key caching is critical; without
it, ZIA-NPC is more than four times slower than the base
le system.
To examine the root causes of ZIA's overhead, we instrumented
the 28 major le and inode operations in both ZIA
and Base+. The dierence between the two, normalized by
the number of operations, gives the average time ZIA adds
to each. Most operations incur little or no penalty, but ve
operations incur measurable overhead. The result is shown
in

Figure

5.
Overhead in each operation stems from ZIA's encryption
and key management functions. In Base+, the readpage
and writepage functions merely transfer pages between the
upper and lower le system. Since writepage is asynchro-
nous, this operation is relatively inexpensive. In ZIA we
must encrypt the page synchronously before writing to the
lower le system. During readpage, we must decrypt the
pages synchronously; this leads to the overheads shown.
ZIA's mkdir must write the keyle to the disk. This adds
an extra le creation to every mkdir. Finally, filldir and20001000
Time (us) / Operation0
Filldir Mkdir Readpage Writepage Lookup
Operation Type
This shows the per-operation overhead for ZIA compared
to the Base+ le system. Writing and reading directory
keys from disk is an expensive operation, as is encrypting
and decrypting le pages.

Figure

5: Per-Operation Overhead
File System Time, sec Over Ext2fs
Ext2fs 9.67 (0.23) -
Base+ 9.66 (0.13) -0.15%
Cryptfs 9.88 (0.14) 2.17%
ZIA 10.25 (0.09) 5.9%
This table shows the performance for the creation of 1000
directories, each containing one zero-length le. Standard
deviations are shown in parentheses. Although ZIA has
a cache of fresh keys for directory creation, it must write
those keyles to disk.

Figure

Creating Directories
lookup must encrypt and decrypt le names, and must sometimes
acquire a decrypted le key.
4.2.2 I/O Intensive Benchmarks
Although the Modied Andrew Benchmark shows only
a small overhead, I/O intensive workloads will incur larger
penalties. We conducted three benchmarks to quantify them.
The rst two stress directory operations, and the third measures
the cost of copying data in bulk.
The rst experiment measures the time to create 1000
directories, each containing a zero length le. The results
are shown in Figure 6. Each new directory requires ZIA to
write a new keyle to the disk, adding an extra disk write to
each operation; the write-behind policy of ext2fs keeps these
overheads manageable. In addition, the lenames must be
encrypted, accounting for the rest of the overhead.
The next benchmark examines ZIA's overhead for reading
1000 directories and a zero length le in each directory. This
stresses keyle reads and key acquisition. Note that without
the empty le ZIA does not need the decrypted key and the
token would never be used. We ran a find across the 1000
directories and les created during the previous experiment.
We rebooted the machine between the previous test and
this one to make sure the name cache was not a factor. The
results are shown in Figure 7.
The results show a large overhead for ZIA. This is not
surprising since we have created a le layout with the smallest
degree of directory locality possible. ZIA is forced to
fetch 1000 keys, one for each directory; there is no locality
File System Time, sec Over Ext2fs
Base+ 15.72 (1.16) 1.04%
Cryptfs 15.41 (1.07) -0.94%
ZIA 29.76 (3.33) 91.24%
This table shows the performance for reading 1000 direc-
tories, each containing one zero-length le. Standard deviations
are shown in parentheses. In this case, ZIA must
synchronously acquire each le key.

Figure

7: Scanning Directories
File System Time, sec Over Ext2fs
Ext2fs 19.68 (0.28) -
Base+ 31.05 (0.68) 57.78%
Cryptfs 42.81 (1.34) 117.57%
ZIA 43.56 (1.13) 121.38%
This table shows the performance for copying a 40MB
source tree from one directory in the le system to an-
other. Standard deviations are shown in parentheses. Synchronously
decrypting and encrypting each le page adds
overhead to each page copy. This is true for ZIA as well as
Cryptfs.

Figure

8: Copying Within the File System
for key caching to exploit. This inserts a network round
into reading the contents of each directory, accounting
for an extra 14 milliseconds per directory read. Note that
the dierences between Base+, Cryptfs and Ext2fs are not
statistically signicant.
Each directory read in ZIA requires a keyle read and a
acquisition in addition to the work done by the underlying
ext2fs. Interestingly, the amount of unmasked acquisition
time plus the time to read the keyle was similar to
the measured acquisition costs. To better understand this
phenomenon, we instrumented the internals of the directory
operations. Surprisingly, the directory read completed
in a few tens of microseconds, while the keyle read was a
typical disk access. We believe that this is because, in our
benchmark, keyles and directory pages are always placed
on the same disk track. In this situation, the track buer
will contain the directory page before it is requested.
It is likely that an aged le system would not show such
consistent behavior [30]. Nevertheless, we are considering
moving keyles out of directories and into a separate location
in the lower le system. Since keys are small, one
could read them in batches, in the hopes of prefetching useful
encrypted le keys. When encrypted keys are already in
hand, the directory read would no longer be found in the
track buer, and would have to go to disk. However, this
time would be overlapped with key acquisition, reducing total
overheads.
The nal I/O intensive experiment is to copy the Pine 4.21
source tree from one part of the le system to another. The
initial les are copied in and then the machine is rebooted to
avoid hitting the page cache. This measures data intensive
operations. The Pine source is 40.4 MB spread across 47
directories. The results are shown in Figure 8. In light of
the previous experiments, it is clear why Crypt and ZIA are
slow in comparison to Base+ and Ext2fs. Each le page is
synchronously decrypted after a read and encrypted before
a
Time (s)20
Reconnection
Disconnection
Page Cache Size (MB)
This plot shows the disconnection encryption time and re-connection
decryption time. The line shows the time required
to encrypt all the le pages when the token moves
out of range. The blocks show the time required to refetch
all the cached keys and decrypt the cached le pages.

Figure

9: Disconnection and Reconnection
4.3 Departure and Return
In addition to good performance, ZIA must have two additional
properties. For security, all le page data must be encrypted
soon after a user departs. To be usable, ZIA should
restore the machine to the pre-departure state before the
user resumes work. Recall that when the user leaves, the
system encrypts the le pages in place. When the user re-
turns, ZIA requests decryption of all keys in the key cache
and then decrypts the data in the page cache. To measure
both disconnection and reconnection time, we copied several
source directories of various sizes into ZIA, removed the
token, and then brought it back into range. Figure 9 shows
these results. The line shows the time required to secure
the le system and the points represent the time required
to restore it. The right-most points on the graph represent
the largest le cache we could produce in our test system.
The encryption time depends solely on the amount of data
in the page cache. Unsurprisingly, encryption time is linear
with page cache size. Decryption is also linear, though
fetching requires a variable amount of time due to the
unknown number of keys in the cache. We believe that a
window of ve seconds is too short for a thief to obtain the
laptop and examine the contents of the page cache. Further-
more, the user should come back to a system with a warm
cache. Once the user is within radio range, he must walk to
the laptop, sit down, and resume work; this is likely to be
more than six seconds.
5. RELATED WORK
To the best of our knowledge, ZIA is the rst system to
provide encrypted ling services that defend against physical
attack while imposing negligible usability and performance
burdens on a trusted user. ZIA accomplishes this by separating
the long-term authority to act on the user's behalf
from the entity performing the actions. The actor holds
this authority only over the short term, and refreshes it as
necessary.
There are a number of le systems that provide transparent
encryption; the best known is CFS [1]. CFS is built
as an indirection layer between applications and an arbitrary
underlying le system. This layer is implemented as
a \thin" NFS server that composes encryption atop some
other, locally-available le system. Keys are assigned on a
directory tree basis. These trees are exposed to the user; the
secure le system consists of a set of one or more top-level
subtrees, each protected by a single key.
When mounting a secure directory tree in CFS, the user
must supply the decryption keys via a pass-phrase. These
remain in force until the user consciously revokes them.
This is an explicit design decision, intended to reduce the
burden on users of the system. In exchange, the security of
the system is weakened by vesting long-term authority with
the laptop. CFS also provides for the use of smart cards
to provide keys [2], but they too are fetched at mount time
rather than periodically. Even if fetched periodically, a user
would be tempted to leave the smart card in the machine
most of the time.
CFS' overhead can be substantial. One way to implement
a cryptographic le system more eciently is to place
it in the kernel, avoiding cross-domain copies. This task is
simplied by a stackable le system infrastructure [11, 27].
Stackable le systems provide the ability to interpose layers
below, within, or above existing le systems, enabling
incremental construction of services.
FiST [33] is a language and associated compiler for constructing
portable, stackable le system layers. We use FiST
in our own implementation of ZIA, though our use of the virtual
memory and buer cache mechanisms native to Linux
would require eort to port to other operating systems. We
have found FiST to be a very useful tool in constructing le
system services.
Cryptfs is the most complete prior example of a stacking
implementation of encryption. It was rst implemented as
a custom-built, stacked layer [32], and later built as an example
use of FiST. Cryptfs|in both forms|shares many
of the goals and shortcomings of CFS. A user supplies his
only once; thereafter, the le system is empowered to
decrypt les on the user's behalf. Cryptfs signicantly out-performs
CFS, and our benchmarks show Cryptfs in an even
better light. This is primarily due to the replacement of
Blowsh [29] with Rijndael [8].
Microsoft Windows 2000 provides the Encrypting File System
(EFS) [19]. While EFS solves many administrative is-
sues, it is essentially no dierent from CFS or Cryptfs. A
single password serves as the key-encrypting key for on-disk,
per-le keys. EFS still depends on screen saver or suspension
locks to revoke this key-encrypting key, rather than
departure of the authorized user. The user may disable the
screen saver or suspension locks after nding them intru-
sive. Anecdotally, we have found that many Windows 2000
laptop users have done exactly that.
In addition to le system state, applications often hold
sensitive data in their address spaces. If any of this state is
paged out to disk, it will be available to an attacker much as
an unencrypted le system would be. Provos provides a system
for protecting paging space using per-page encryption
with short lifetimes [26]. ZIA is complimentary to this
system; ZIA protects le system state, while Provos' system
protects persistent copies of application address spaces.
Several eorts have used proximity-based hardware tokens
to detect the presence of an authorized user. Landwehr [16]
proposes disabling hardware access to the keyboard and
mouse when the trusted user is away. This system does not
fully defend against physical possession attacks, since the
contents of disk and possibly memory may be inspected at
the attackers leisure. Similar systems have reached the commercial
world. For example, the XyLoc system [10] could
serve as the hardware platform for ZIA's authentication token

Rather than use passwords or hardware tokens, one could
instead use biometrics. Biometric authentication schemes
intrude on users in two ways. The rst is the false-negative
rate: the chance of rejecting of a valid user [25]. For face
recognition, this ranges between 10% and 40%, depending
on the amount of time between training and using the recognition
system. For ngerprints, the false-negative rate can
be as high as 44%, depending on the subject. The second intrusion
stems from physical constraints. For example, a user
must touch a special reader to validate his ngerprint. Such
burdens encourage users to disable or work around biometric
protection. A notable exception is iris recognition. It can
have a low false-negative rate, and can be performed unobtrusively
[23]. However, doing so requires three cameras|an
expensive and bulky proposition for a laptop.
6. CONCLUSION
Because laptops are vulnerable to theft, they require additional
protection against physical attacks. Without such
protection, anyone in possession of a laptop is also in possession
of all of its data. Current cryptographic le systems
do not oer this protection, because the user grants
the le system long-term authority to decrypt on his be-
half. Closing this vulnerability with available mechanisms|
passwords, secure hardware, or biometrics|would place unpleasant
burdens on the user, encouraging him to forfeit security
entirely.
This paper presents our solution to this problem: Zero-
Interaction Authentication, or ZIA. In ZIA, a user wears an
authentication token that retains the long-term authority to
act on his behalf. The laptop, connected to the token by a
short-range wireless link, obtains this authority only when it
is needed. Despite the additional communication required,
this scheme imposes an overhead of only 9.3% above the
local le system for representative workloads; this is indistinguishable
from the costs of simple encryption.
If the user leaves, the laptop encrypts any cached le system
data. For the largest buer cache on our hardware, this
process takes less than ve seconds|less time than would be
required for a nearby thief to examine data. Once the user
is back in range, the le system is restored to pre-departure
state within six seconds. The user never notices a performance
loss on return. ZIA thus prevents physical possession
attacks without imposing any performance or usability burden

We are currently extending ZIA's model to system services
and applications [24]. By protecting application state
and access to sensitive services, ZIA can protect the entire
machine|not just the le system|from attack.

Acknowledgements

The authors wish to thank Peter Chen, who suggested the
recovery time metric, and Peter Honeyman, for many valuable
conversations about this work. Mary Baker, Landon
Cox, Jason Flinn, Minkyong Kim, Sam King, and James
Mickens provided helpful feedback on earlier drafts.
This work is supported in part by the Intel Corporation; [15]
Novell, Inc.; the National Science Foundation under grant
CCR-0208740; and the Defense Advanced Projects Agency
(DARPA) and Air Force Materiel Command, USAF, under
agreement number F30602-00-2-0508. The U.S. Government [16]
is authorized to reproduce and distribute reprints for Governmental
purposes notwithstanding any copyright annotation
thereon. The views and conclusions contained herein
are those of the authors and should not be interpreted as [17]
necessarily representing the ocial policies or endorsements,
either expressed or implied, of the Intel Corporation; Nov-
ell, Inc.; the National Science Foundation; the Defense Advanced
Research Projects Agency (DARPA); the Air Force
[18]
Research Laboratory; or the U.S. Government.
7.


--R




Scale and performance in a distributed le
Wormhole detection in wireless ad hoc networks.
Personal secure booting.

An architecture for multiple
le system types in Sun UNIX.
Association Summer Conference

Protecting unattended computers

Computer Security Applications Conference


cryptographic devices resilient to capture.




http://www.
howitworks/security/encrypt.

design for a smart watch with a high resolution

Symposium on Wearable Computers
National Institute of Standards and Technology.
Computer data authentication.

encryption for authentication in large networks of




system for public and personal use.
The case for transient



An introduction to evaluating biometric

Encrypting virtual memory.
of the Ninth USENIX Security Symposium

Evolving the vnode interface.
USENIX Association Conference
Integrating security in a large
distributed system.

Description of a new variable-length key


File system


Measurement and Modeling of Computer Systems
pages 203-13
Secure coprocessors in
A stackable vnode level encryption le system.
--TR
A fast file system for UNIX
Scale and performance in a distributed file system
Integrating security in a large distributed system
A logic of authentication
A cryptographic file system for UNIX
File-system development with stackable layers
Distance-bounding protocols
BITS: a smartcard protected operating system
File system agingMYAMPERSANDmdash;increasing the relevance of file system benchmarks
Using encryption for authentication in large networks of computers
An Introduction to Evaluating Biometric Systems
An Iris Biometric System for Public and Personal Use
Personal Secure Booting
Oblevious Key Escrow
Description of a New Variable-Length Key, 64-bit Block Cipher (Blowfish)
Application Design for a Smart Watch with a High Resolution Display
Protecting unattended computers without software
Networked Cryptographic Devices Resilient to Capture

--CTR
Shwetak N. Patel , Jeffrey S. Pierce , Gregory D. Abowd, A gesture-based authentication scheme for untrusted public terminals, Proceedings of the 17th annual ACM symposium on User interface software and technology, October 24-27, 2004, Santa Fe, NM, USA
Brian D. Noble , Mark D. Corner, The case for transient authentication, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France
Kenta Matsumiya , Soko Aoki , Masana Murase , Hideyuki Tokuda, A zero-stop authentication system for sensor-based embedded real-time applications, Journal of Embedded Computing, v.1 n.1, p.119-132, January 2005
Andrew D. Wilson , Raman Sarin, BlueTable: connecting wireless mobile devices on interactive surfaces using vision-based handshaking, Proceedings of Graphics Interface 2007, May 28-30, 2007, Montreal, Canada
Naveen Sastry , Umesh Shankar , David Wagner, Secure verification of location claims, Proceedings of the ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA
Shelley Zhuang , Kevin Lai , Ion Stoica , Randy Katz , Scott Shenker, Host mobility using an internet indirection infrastructure, Wireless Networks, v.11 n.6, p.741-756, November 2005
Mark D. Corner , Brian D. Noble, Protecting applications with transient authentication, Proceedings of the 1st international conference on Mobile systems, applications and services, p.57-70, May 05-08, 2003, San Francisco, California
Yih-Chun Hu , Adrian Perrig, A Survey of Secure Wireless Ad Hoc Routing, IEEE Security and Privacy, v.2 n.3, p.28-39, May 2004
Srdjan Capkun , Jean-Pierre Hubaux, BISS: building secure routing out of an incomplete set of security associations, Proceedings of the ACM workshop on Wireless security, September 19-19, 2003, San Diego, CA, USA
Levente Buttyn , Jean-Pierre Hubaux, Report on a working session on security in wireless ad hoc networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.1, January
Erez Zadok , Rakesh Iyer , Nikolai Joukov , Gopalan Sivathanu , Charles P. Wright, On incremental file system development, ACM Transactions on Storage (TOS), v.2 n.2, p.161-196, May 2006
Julie Thorpe , P. C. van Oorschot , Anil Somayaji, Pass-thoughts: authenticating with our minds, Proceedings of the 2005 workshop on New security paradigms, September 20-23, 2005, Lake Arrowhead, California
Shelley Zhuang , Kevin Lai , Ion Stoica , Randy Katz , Scott Shenker, Host Mobility Using an Internet Indirection Infrastructure, Proceedings of the 1st international conference on Mobile systems, applications and services, p.129-144, May 05-08, 2003, San Francisco, California
mobile computing;stackable file systems;transient authentication;cryptographic file systems