When evaluating Cryptfs, we compared it to CFS (also using Blowfish) on all three systems and TCFS on Linux ones.3 The purpose of our work was primarily to create a practical and portable stackable file system. Performance and portability were more important to us than security because the design was such that stronger or weaker security measures could be put in place with relative ease.
We used two sets of performance tests. The first set measured specific common operations such as reading and writing files of various sizes. The second set used a more realistic test of building a large package inside the file system.
For most of our tests, we included figures for a native disk-based file system because disk hardware performance can be a significant factor. This number should be considered the base to which other file systems compare to. Since Cryptfs is a stackable file system, we also included figures for Wrapfs (our full-fledged stackable file system) and for lofs (the low-overhead simpler one), to be used as a base for evaluating the cost of stacking. When using lofs, Wrapfs, or Cryptfs, we mounted them over a local disk based file system. CFS and TCFS are based on NFS, so we included the performance of native NFS. All NFS mounts used the local host as both server and client (i.e. mounting localhost:/path on /mnt,) and used protocol version 2 over a UDP transport.
CFS is implemented as a user-level NFS file server. TCFS is a kernel module, but it accesses two user-level servers: nfsd and xattrd. Furthermore, the NFS server in Linux 2.0 is implemented completely in user level, further slowing down performance. As such, we expected that both CFS and TCFS would run slower due to the number of additional context switches that must take place when a user-level file server is called by the kernel to satisfy a user process request, and due to NFS V.2 protocol overheads such as synchronous writing. Lastly, TCFS does not support the Blowfish algorithm so we had to use DES instead; DES consumes more CPU resources than Blowfish.
For the first set of tests, we concentrated on the x86 platform since it was common to all ports. We ran tests that represent common operations in file systems: opening files for reading or writing. In the first test we wrote 1024 different new files of 8KB size each. The second test wrote 8 new files of 1MB size each. Then we read one 8KB file 1024 times, and one 1MB file 8 times. The intent of these tests was that the total amount of data read and written would be the same. Finally we included measurements for reading a directory with 1024 entries repeatedly for 100 times; while that is a less popular operation, cryptographic file systems encrypt file names and thus can significantly affect the performance of reading a directory. All times reported are elapsed, in seconds, and measured on an otherwise quiet system.
Since Linux is the only platform on which TCFS runs, we tested all file systems on it, as reported in Table 1. For Solaris and FreeBSD, we only included figures for the file systems relevant to comparing Cryptfs to CFS; these are reported in Tables 2 and 3, respectively.
Concentrating on Linux (Table 1) first, we see that lofs adds a small overhead over the native disk-based file system, and wrapfs adds another overhead due to stacking on all vnodes and due to performing data copies. The difference between Cryptfs and Wrapfs is that of encryption only. Writing files is 6-12 times faster in Cryptfs than in CFS/TCFS. The main reasons for this are the additional context switches that must take place in user-level file servers, and that NFS V.2 writes are synchronous. When reading files, caching and memory sizes come into play more than the file system in question. That is why the difference in file reading performance for all file systems is not as significant as when writing files. The reason lofs is slower than wrapfs is that the original lofs we used on Linux does not cache data, while Wrapfs and Cryptfs do. Reading a directory with 1024 files one hundred times is 10-37 times faster in Cryptfs than in TCFS or CFS, mostly due to context switches. When Cryptfs is mounted on top of ext2fs, it slows performance of these measured operations 2-3 times. But since these are fast to begin with, users hardly notice the difference; in practice overall slowness is smaller, as reported in Table 4.
Native file systems in Linux perform their operations asynchronously, while Solaris and FreeBSD do so synchronously. That is why the performance improvement of Cryptfs over CFS/TCFS for Solaris and FreeBSD is smaller; when writing vnode operations are passed from Cryptfs to the lower level file system, they must be completed before returning to the caller. For the operations measured, Cryptfs improves performance by anywhere from 50% to 2 times, with the exception of writing large files on Solaris, where performance is improved by more than an order of magnitude.
For the next set of tests, we decided to use as our performance measure a full build of Am-utils, a new version of the Berkeley Amd automounter. The test auto-configures the package and then builds it. The configuration runs several hundred (600-700) small tests, many of which are small compilations and executions. The build phase compiles about 50,000 lines of C code spread among several dozen files and links about a dozen binaries. The whole procedure contains a fair mix of CPU and I/O bound operations as well as file system operations: many writes, binaries executed, small files created and unlinked, a fair number of reads and lookups, and a few directory and symbolic link creations. We felt that is a more realistic measure of the overall file system performance, and would give users a better feel for the expected impact Cryptfs might have on their workstation. For each file system measured, we ran 10 successive builds on a quiet system, measured the elapsed times of each run, and averaged them. The results are summarized in Table 4. Results of TCFS are available on the only platform it runs, Linux. Also, there is no native lofs for FreeBSD (and the nullfs available is not fully functional.)
First we need to evaluate the performance impact of stacking a file system. Lofs is only 0.7-1.2% slower than the native disk based file system. Wrapfs adds an overhead of 4.7-6.8% for Solaris and Linux systems, but that is comparable to the 3-10% degradation previously reported.[5,19] On FreeBSD, however, Wrapfs adds an overhead of 21.1% compared to UFS; that is because of limitations of nullfs, we were forced to use synchronous writes exclusively. Wrapfs is more costly than lofs because it stacks over every vnode and keeps its own copies of data, while lofs stacks only on directory vnodes, and passes all other vnode operations to the lower level verbatim.
Wrapfs is used as the baseline for evaluating the performance impact of the encryption algorithm. The only difference between Wrapfs and Cryptfs is that the latter encrypts and decrypts data and file names. Cryptfs adds an overhead of 9.2-22.7% over Wrapfs. That is a significant overhead but is unavoidable. It is the cost of the Blowfish encryption code, which while designed as a fast software cipher, is still CPU intensive.
Next we measure the overhead of CFS and TCFS and compare them to Cryptfs. When compared to NFS, TCFS is 45.3-69.3% slower on Linux, and CFS is 3.2-45.5% slower. Cryptfs is 40-52% faster than TCFS on Linux. Since TCFS uses DES and Cryptfs uses Blowfish, however, it would be fairer to compare Cryptfs to CFS. Cryptfs is 12-30% faster than CFS. In order to improve performance, CFS precomputes large stream ciphers for the attached directories. Cryptfs, on the other hand, has not been tuned or optimized yet.
A complete and detailed comparison of various operating systems and the performance of their native file system is beyond the scope of this paper. Nevertheless, several interesting observations became apparent from Table 4. It was surprising to find that SPARC Linux surpassed the performance of every Solaris file system on the same SPARC architecture by 3.5-45.9%. Even the performance of the native disk-based performance was 13.2% faster on Linux, and NFS was 12.7% faster.
When we compare x86 based operating systems, Linux and FreeBSD appear comparable. NFS and CFS are 1.4-10.7% slower on Linux 2.0 because the NFS server is in user-level. On the other hand, all other file systems are 5.2-19.3% faster on Linux because of their asynchronous nature.
Solaris x86 is 78-132% slower that Linux. The asynchronous nature of Linux cannot explain why Solaris x86 is 71-136% slower than FreeBSD on identical hardware, since FreeBSD is also synchronous. To find the reason for this, we traced the system calls executing during several compilations of single C source file from the building of Am-utils. These are reported in Table 5. We found out that more than 95% of the time spent by the kernel on behalf of the compiler was spread among three system calls: open, unlink, and brk (to allocate more memory to a running process.) The most frequently called system call, brk, was called almost 900 times -- more than 4 times the frequency of all other calls. We have found that the cost of a single call to brk on Solaris x86 is 813 microseconds; that is 5.6 times slower than FreeBSD, and almost 10 times slower than on Linux x86. Given the frequency of this call, and how slow it is on Solaris x86, it is not surprising that our compilations reported in Table 4 took twice as long on that platform. Luckily, memory allocation speed is not directly impacted by the file system in use.
To be certain, we turned off the default synchronous behavior of Solaris x86, and reran some tests. As expected, the speeds of read and unlink improved manyfold, and were brought more in line with their speeds on Linux and FreeBSD. Since brk is a more dominant call during compilation, and is unaffected by the asynchronous vs. synchronous nature of file systems, we did not expect turning off synchronous operations on Solaris x86 to result in significantly improved speeds. Indeed, when we ran a full build of Am-utils with Solaris x86 using asynchronous operations, the performance as reported in Table 4 improved by less than 6%.
We used the Blowfish encryption algorithm with the default 128 bit key length. 56 bit encryption had already been broken and efforts are underway to break 64 bit encryption. We felt that 128 bit keys were large enough to be secure for years to come, and at the same time they were not too large to require excessive CPU power. (Increasing the key size would be a simple matter of recompilation.) Blowfish is a newer cipher than DES, and as such has not survived the test of time that DES had, but Blowfish is believed to be very secure. At this time, Cryptfs can only use Blowfish. CFS offers the widest choice of ciphers, including DES.
Cryptfs requires a session ID to use keys after they were supplied, to ensure that only processes in that session group get access to the key and thus to the unencrypted data. Requiring a session ID to use an encryption key prevents attackers from easily decrypting the data belonging to a valid user, even if the user's account was compromised on the same machine Cryptfs was mounted. All an attacker could do, even with root privileges, is read the ciphertext, but could not modify or remove files, since we overlay the mount point (see Section 2.4.) In comparison, CFS and TCFS are more vulnerable to the compromising of the users' accounts on the same host because they associate a key with a UID alone, not with a session ID.
Changing keys in Cryptfs is more cumbersome, since only one active key can be associated with a given session. Users have to use a special program we provide that sets a re-encryption key, reads files using old keys, and writes them back using the new key. CFS offers a more flexible solution that allows the user to change the passphrase without re-creating or copying the secure directory.
Cryptfs uses one Initialization Vector (IV) per mount, used to ``jump start'' a sequence of encryption. If not specified, a predefined IV is used. The superuser mounting Cryptfs can choose a different one, but that will make all previously encrypted files undecipherable with the new IV. Files that use the same IV and key produce identical ciphertext blocks that are subject to analysis of identical blocks. CFS' default mode uses no IVs, and we also felt that using a fixed one produces sufficiently strong security.
Both CFS and TCFS use auxiliary files to store encryption related information such as encrypted keys, types of encryption used, IVs4, and more. CFS is the only file system that can store all of these on a more secure ``smart card.'' TCFS uses login passwords as default keys and those are generally considered insecure and easily guessable. Cryptfs does not store any auxiliary information on disk, because we believe doing so could potentially create security vulnerabilities; it only has a modified instance of the key in use in kernel memory, for the duration of the session, or until the user chooses to remove it.
Since CFS and TCFS use NFS V.2, they are vulnerable to known (or yet undiscovered) attacks on NFS and related servers such as port mappers or mount protocol daemons. Cryptfs does not suffer from these problems.
All three cryptographic file systems suffer from a few similar yet unavoidable problems. At given times, cleartext keys and file data exist in the memory of user processes and in kernel memory and are thus vulnerable to an attack with root privileges through /dev/kmem; a sophisticated attacker aided by source access could read kernel memory to follow data structures representing processes, users, file systems, and vnodes -- until he reaches plaintext keys and data. Also, if the system pages to an insecure device, there is a chance that parts of active processes containing cleartext will page to an insecure system, but that is not a Cryptfs problem per se.
We conducted a series of tests with a set of users such as letting them store mail and other important files under directories encrypted using Cryptfs. Over a period of one month, these users reported that they found Cryptfs to have a useful balancing of security and convenience. They liked Cryptfs' transparency; once the key was provided, they were able to perform normal file operations without noticing any difference or impact on their workstations.
Cryptfs encrypts all file and directory data, names, and symbolic link values. In comparison, CFS does not support special files or named pipes. Sparse files' holes get filled in by Cryptfs and encrypted because it was a necessary part of the implementation; however, it also has the benefit of reducing the chance that an attacker could guess the type of file by noticing that it is sparse.
By encrypting and encoding file names into a reduced character set, cryptographic file systems lengthen file names on disk; this reduces the maximum allowed path name and component name lengths at the cryptographic file systems' level. On average, TCFS and CFS halve the lengths of component names and maximum path names. Cryptfs reduces the length only by 25%. In practice, component names are 255 bytes long, and maximum path names are 1024 or more bytes long, so even a reduction of 50% in their lengths is not likely to seriously affect any users.
Solaris and FreeBSD have similar vnode interfaces, but both differ from Linux. Most of the Cryptfs code could not be directly shared between them. 20% of the code we wrote (about 4000 lines for Solaris) were general subroutines shared among all ports. The other 80% of the code was not all a ``loss'' when it came to other ports. Most of the vnode functions are very similar in behavior: find the interposed vnode V' from the current one V and apply the same vnode operation on V' in some order. The code looks different and the symbol names are not the same, but at its core the same stackable vnode operations occur in all three ports.
It took us almost a year to fully develop Wrapfs and Cryptfs together for Solaris, during which time we had to overcome our lack of experience with Solaris kernel internals and principles of stackable file systems. In comparison, we were able to complete the Linux port in under 3 weeks, and took one week to port to FreeBSD.