Next: Avalanche and certificational
weaknesses Up: Mercy: a fast large
Previous: Mercy: a fast large
Disk sector encryption is an attractive approach to filesystem confidentiality. Filesystems access hard drive partitions at the granularity of the sector (or block) where a sector is typically 4096 bits: read and write requests are expressed in sector numbers, and data is read and modified a sector at at a time. Disk sector encryption systems present a ``virtual partition'' to the filesystem, mapping each sector of the virtual partition to the corresponding sector, through an encrypting transformation, on a physical disk partition with the same disk geometry. The performance is typically better than file-level encryption schemes, since every logical sector read or write results in exactly one physical sector read or write, and confidentiality is also better: not only are file contents obscured, but also filenames, file sizes, directory structure and modification dates. These schemes are also flexible since they make no special assumptions about the way the filesystem stores the file data; they work equally well with raw database partitions as with filesystems, and can be transparently layered underneath disk caching and disk compression schemes. Linux provides some support for such filesystems through the ``/dev/loop0'' filesystem device.
The stream cipher SEAL [17] is well suited to this need. SEAL provides a strong cryptographic PRNG (CPRNG) whose output is seekable. Thus the entire disk can be treated as a single contiguous array of bytes and XORred with the output from the CPRNG; when making reads or writes of specific sectors the appropriate portion of the output can be generated without the need to generate the preceding bytes. The same effect can be achieved, somewhat less efficiently, by keying a CPRNG such as ARCFOUR [10] with a (key, sector number) pair and generating 512 bytes with which to encrypt the sector. These schemes are highly efficient and provide good security against an attacker who seizes an encrypted hard drive and attempts to gain information about its contents.
However, this is not strong against attackers with other channels open to them. They may have user privileges on the system they're trying to attack, and be able to access the ciphertext stored on the hard drive at times when it's shut down. Or they may try to modify sectors with known contents while carrying a drive from place to place. They may even be able to place hardware probes on the drive chain while logged in as a normal user, and sniff or modify ciphertext. Against these attacks, SEAL and ARCFOUR (used as described) are ineffective. For example, an attacker can write a large file of all zeroes and thereby find the fixed encryption stream associated with many sectors; once the file is deleted, the sectors might be re-used by other users with secure data to write, and this data is easily decrypted by XORing with the known stream. Or, if attackers can make a guess of the plaintext in a given sector, they can modify this to another plaintext of their choosing while they have access to the drive by XORing the ciphertext with the XOR difference between the two plaintexts.
File-based encryption schemes defeat these attacks by using a new random IV for each new plaintext and authenticating with a MAC. However, applying these techniques directly to sector encryption would require that the ciphertext for each sector be larger than the plaintext, typically by at least 64 bytes. Thus either the plaintext sectors would need to be slightly smaller than the natural hardware sector size, harming performance when mapping files into memory (and necessitating a thorough re-engineering of the filesystem code) or auxiliary information would have to be stored in other sectors, potentially adding a seek to each read and write. In either case the size overhead will be about 1.5 - 3.1%. It's worth investigating what can be achieved without incurring these penalties.
SFS [9] uses a keyless mixing transformation on the plaintext before applying a block chaining stream cipher. This greatly reduces the practical usefulness of many such attacks, but it falls short of the highest security that pure disk sector encryption systems can aspire to: that the mapping between each virtual and physical disk sector appears to be an independent random permutation to an attacker who expends insufficient computation to exhaustively search the keyspace. In other words, the theoretical best solution under these constraints is a strong randomised large block cipher.
Several proposals exist for building large block ciphers from standard cryptographic components such as hash functions and stream ciphers [1,11,2]; however, these are not randomised ciphers, and as Section 2 shows, they have certificational weaknesses. More seriously, no proposal comes close to offering the performance needed: bit rates equal to or better than disk transfer rates. Since small improvements in disk access efficiency can mean big improvements to every part of the user experience, and since performance considerations are one of the main reasons why filesystem encryption is not more widely used, it seems worthwhile to develop a new cipher designed specifically to meet this need.
The rest of this paper is organised as follows. Section 2 describes a certificational weakness applicable to several existing classes of large block cipher, and proposes a quantitiative measure of avalanche based on the attack. Section 3 lays out the design goals for the solution here, a new block cipher Mercy with a native block size of 4096 bits, and Section 4 describes the cipher itself. Section 5 discusses the design of the cipher in detail with reference to the performance and security goals of Section 3. Finally Section 6 discusses some of the lessons learned in the design of Mercy.
Next: Avalanche and certificational
weaknesses Up: Mercy: a fast large
Previous: Mercy: a fast large