PEFS crypto primitives

This document was created from text written by Gleb Kurtsou at http://glebkurtsou.blogspot.com/2009/09/pefs-crypto-primitives.html .

Supported data encryption algorithms: AES and Camellia (with 128, 192 and 256 bits key sizes). Adding another block cipher with 128 block size should be trivial.

File names are always encrypted using AES-128 in CBC mode with zero IV. Encrypted file name consists of a unique per file tweak, checksum and the name itself:

XBase64(checksum || E(tweak || filename))

Checksum is VMAC of encrypted tweak and file name:

checksum = VMAC(E(tweak || filename))

Both the checksum and the tweak have 64 bit length. Stronger / larger lengths are not advisable because the filenames are limited by the file system name length limits (255 bytes); with multibyte encodings like UTF-8, the total available space might be very small (e.g. for non-ASCII European languages using 2 bytes per UTF-8 character, the process might leave only 80-90 characters for the actual user-specified filename).

Filenames are encrypted in AES-CBC mode with zero IV (and padded with zeros to cipher block boundary). First encryption block contains pseudo random tweak which makes all encrypted filenames unique due to CBC mode chaining.

Main reason for not providing alternatives to the name encryption algorithm is to keep the design simple. Data encryption differs from name encryption because the encrypted file data, unlike encrypted file name, is not parsed in any way by pefs and user expects to be able to use secure/fast/best-name cipher.

Encrypt-then-Authenticate construction is used. In addition to being most secure variant it allows checking if the name was encrypted by any given key without performing decryption. VMAC was chosen because of it performance characteristics and its ability to produce 64 bit MAC (without truncation of original result like in HMAC case). There is no real “authentication” performed; it's designed to be just a strong checksum. Breaking VMAC wouldn't result in breaking encrypted data. This checksum's main purpose is to be able to find a key the file is encrypted with.

Encrypted directory/socket/device names also contain tweak but it's used solely to randomize first CBC block and keep name structure uniform.

The idea behind using a tweak is to get unique per file ciphertext. Block ciphers (AES, Camellia) operate in XTS mode, in which a 64 bit tweak value concatenated with 64 bit file offset form the XTS tweak. All encryption operations are performed on 4096 bytes sectors (“data unit” in XTS notion). Incomplete sectors are also encrypted according to XTS standard, but encryption of sectors smaller then 128 bits is not defined for XTS. In this situation (e.g. the “remainder” of a file if the file size is not a multiple of 4 KiB when the remainder is also smaller than 16 bytes), CTR mode is used with tweak value generated as for XTS. If all 4096 bytes in a sector are zero before decryption it is not decrypted but treated as hole in a sparse file.

4 different keys are used with cryptographic primitives: one for name encryption, one for VMAC and two keys for data encryption as required by XTS. All these keys are derived from the 512 bit user supplied key using HKDF algorithm based on HMAC-SHA512 (IETF draft). The kernel part expects cryptographically strong key from userspace. This key is generated with PBKDF on using HMAC-SHA512 from passphrase.

Standard implementations of ciphers are used, but not opencrypto framework, so there is no hardware acceleration available. Opencrypto is not used mainly because it lacks full support for XTS mode (it is currently not able to encrypt incomplete / “short” sectors). It is also rather heavy weight (extra initialization and memory allocations) so using it may even hurt performance (hardware initialization costs for encrypting short chunks with different keys).

PEFS supports multiple keys, mixing files encrypted with different keys in single directory, transparent(unencrypted) mode, key chaining (adding a series of keys by entering just one of them) and more.