Home

WhisperSystems edited this page Apr 3, 2011 · 2 revisions
Clone this wiki locally

Introduction

WhisperYAFFS is an experimental set of changes that bring encrypted filesystem support to YAFFS. These changes are designed to allow for FDE support on Android devices that store user data on unmanaged flash.

Flash Background

Modern NAND flash is broken up into 128kb eraseblocks that are composed of 2k pages. After a page is written to once, it can only be written to again if the entire eraseblock it resides within is erased. Additionally, each page is associated with a 64byte out of band (OOB) data area, which stores ECC information (which is necessary) along with arbitrary page metadata. The same write-once rules apply to the OOB section.

An eraseblock will eventually wear out, and can only be erased so many times before it dies.

YAFFS Methodology

YAFFS attempts to provide an efficient FS implementation that also does effective wear-leveling to extend the life of an eraseblock. YAFFS achieves this primarily through a log-structured format. The log starts at the first free eraseblock, and the writes progress through each page to the next eraseblock. When all eraseblocks have been written to, YAFFS starts over at the beginning by flashing any eraseblocks that are now composed of completely stale pages. Additionally, YAFFS continually does garbage collection, copying isolated in-use pages from a mostly-stale eraseblock forward to an eraseblock that is mostly active.

YAFFS uses the OOB area to do ECC, mark the number of bytes which actually reside in a page, mark which object a page corresponds to (if applicable), and mark what position a page corresponds to within an object. Additionally, every page gets a sequence number, which is incremented every time the log advances to a new eraseblock. The purpose of the latter is to determine the relevant priority of data when the log is being recovered at mount time.

WhisperYAFFS Methodology

WhisperYAFFS aims to encrypt all FS data and metadata. Our approach is fairly straightforward.

  1. Each page is encrypted before being written to NAND and decrypted after being read from NAND.
  2. The ECC in the OOB is left unencrypted, but it is computed on the ciphertext, and so should not leak any information.
  3. The rest of the OOB is encrypted, with the exception of the sequence number, which has to be left unencrypted in order to determine whether a block is flashed or not.

All page and OOB encryption is done using AES-128 in XTS mode. The XTS tweak for a page is its position within the NAND device * 2. This is ((eraseBlockIndex * pagesPerBlock) + pageInEraseBlock) * 2. The XTS tweak for an OOB region is the position of the OOB region's corresponding page within a NAND device * 2 + 1. This is ((eraseBlockIndex * pagesPerBlock) + oobPageInEraseblock) * 2 + 1.

Performing the AES-XTS operations on a page is straightforward, given that it is a multiple of the cipher's block size. Performing the same AES-XTS operations on the OOB region is only non-trivial in that the OOB data to encrypt is 12 bytes, which is less than the cipher's block size.

WhisperYAFFS handles this by doing ciphertext stealing from the OOB region's page ciphertext. The missing 4 bytes are taken from the last 4 bytes of the page's ciphertext, the resulting 16-byte block is AES-XTS encrypted, and then the first 4 bytes of that ciphertext output are overwritten to the last 4 bytes of the page's ciphertext. The remaining 12 ciphertext bytes are stored in the OOB region. The inverse of this operation is performed on a decrypt, meaning that the OOB region needs to be decrypted first in order to properly construct the page's ciphertext for decryption.

Keying Methodology

Keys are stored in the first good eraseblock, and are encrypted using PBKDF2. A user's passphrase is run through PBKDF2 in order to compute a 128bit AES key and a 160bit HmacSHA1 key. This AES key is used in CBC$ mode to encrypt randomly generated AES-XTS keys. The HmacSHA1 key is used to MAC the entire KeyDescriptor data structure.

The on-disk format is as follows:

typedef struct {
  __u32 versionNumber;  /* The version of this key block record. */
  __u32 iterationCount; /* The number of PBKDF2 iterations to perform. */
  
  __u8 keySalt[16];     /* The PBKDF2 salt used for computing the keyblock AES key. */
  __u8 macSalt[16];     /* The PBKDF2 salt used for computing the keyblock MAC key. */
  
  __u8 iv[AES_BLOCK_SIZE]; /* The IV used to encrypt the AES-XTS keys in CBC mode. */
  __u8 keys[XTS_KEY_SIZE]; /* The encrypted AES-XTS keys. */

  __u8 mac[SHA1_DIGEST_SIZE]; /* The HmacSHA1 of everything preceeding it. */
} yaffs_KeyDescriptorBlock;

The NAND disk geometry is then adjusted such that this first eraseblock is not visible to normal YAFFS operations.

WhisperYAFFS Analysis

While filesystem-level encryption can occasionally be problematic due to information leakage from the structure of data on disk, we believe that the YAFFS filesystem is well suited for encryption at the filesystem level. Due to its log structure and garbage collection, we believe that the on-flash format provides very little information leakage for analysis. By encrypting all pages and the bulk of the metadata, an attacker should not be capable of determining the content of an individual file on flash, the size of an individual file on flash, or the total number of files stored in the filesystem.

In some situations an attacker might, however, be able to determine the approximate total amount of information stored within the entire filesystem.

While we believe the above statements to be true, WhisperYAFFS is still experimental, and should not be used in situations where the security or reliability of data are critical.