English

Chinese (Simplified)

UBIFS Authentication Support¶

Introduction¶

UBIFS utilizes the fscrypt framework to provide confidentiality for filecontents and file names. This prevents attacks where an attacker is able toread contents of the filesystem on a single point in time. A classic exampleis a lost smartphone where the attacker is unable to read personal data storedon the device without the filesystem decryption key.

At the current state, UBIFS encryption however does not prevent attacks wherethe attacker is able to modify the filesystem contents and the user uses thedevice afterwards. In such a scenario an attacker can modify filesystemcontents arbitrarily without the user noticing. One example is to modify abinary to perform a malicious action when executed [DMC-CBC-ATTACK]. Sincemost of the filesystem metadata of UBIFS is stored in plain, this makes itfairly easy to swap files and replace their contents.

Other full disk encryption systems like dm-crypt cover all filesystem metadata,which makes such kinds of attacks more complicated, but not impossible.Especially, if the attacker is given access to the device multiple points intime. For dm-crypt and other filesystems that build upon the Linux block IOlayer, the dm-integrity or dm-verity subsystems [DM-INTEGRITY, DM-VERITY]can be used to get full data authentication at the block layer.These can also be combined with dm-crypt [CRYPTSETUP2].

This document describes an approach to get file contents _and_ full metadataauthentication for UBIFS. Since UBIFS uses fscrypt for file contents and filename encryption, the authentication system could be tied into fscrypt such thatexisting features like key derivation can be utilized. It should however alsobe possible to use UBIFS authentication without using encryption.

MTD, UBI & UBIFS¶

On Linux, the MTD (Memory Technology Devices) subsystem provides a uniforminterface to access raw flash devices. One of the more prominent subsystems thatwork on top of MTD is UBI (Unsorted Block Images). It provides volume managementfor flash devices and is thus somewhat similar to LVM for block devices. Inaddition, it deals with flash-specific wear-leveling and transparent I/O errorhandling. UBI offers logical erase blocks (LEBs) to the layers on top of itand maps them transparently to physical erase blocks (PEBs) on the flash.

UBIFS is a filesystem for raw flash which operates on top of UBI. Thus, wearleveling and some flash specifics are left to UBI, while UBIFS focuses onscalability, performance and recoverability.

+------------+ +*******+ +-----------+ +-----+|            | * UBIFS * | UBI-BLOCK | | ... || JFFS/JFFS2 | +*******+ +-----------+ +-----+|            | +-----------------------------+ +-----------+ +-----+|            | |              UBI            | | MTD-BLOCK | | ... |+------------+ +-----------------------------+ +-----------+ +-----++------------------------------------------------------------------+|                  MEMORY TECHNOLOGY DEVICES (MTD)                 |+------------------------------------------------------------------++-----------------------------+ +--------------------------+ +-----+|         NAND DRIVERS        | |        NOR DRIVERS       | | ... |+-----------------------------+ +--------------------------+ +-----+    Figure 1: Linux kernel subsystems for dealing with raw flash

Internally, UBIFS maintains multiple data structures which are persisted onthe flash:

Index: an on-flash B+ tree where the leaf nodes contain filesystem data
Journal: an additional data structure to collect FS changes before updatingthe on-flash index and reduce flash wear.
Tree Node Cache (TNC): an in-memory B+ tree that reflects the current FSstate to avoid frequent flash reads. It is basically the in-memoryrepresentation of the index, but contains additional attributes.
LEB property tree (LPT): an on-flash B+ tree for free space accounting perUBI LEB.

In the remainder of this section we will cover the on-flash UBIFS datastructures in more detail. The TNC is of less importance here since it is neverpersisted onto the flash directly. More details on UBIFS can also be found in[UBIFS-WP].

UBIFS Index & Tree Node Cache¶

Basic on-flash UBIFS entities are callednodes. UBIFS knows different typesof nodes. Eg. data nodes (structubifs_data_node) which store chunks of filecontents or inode nodes (structubifs_ino_node) which represent VFS inodes.Almost all types of nodes share a common header (ubifs_ch) containing basicinformation like node type, node length, a sequence number, etc. (seefs/ubifs/ubifs-media.h in kernel source). Exceptions are entries of the LPTand some less important node types like padding nodes which are used to padunusable content at the end of LEBs.

To avoid re-writing the whole B+ tree on every single change, it is implementedaswandering tree, where only the changed nodes are re-written and previousversions of them are obsoleted without erasing them right away. As a result,the index is not stored in a single place on the flash, butwanders aroundand there are obsolete parts on the flash as long as the LEB containing them isnot reused by UBIFS. To find the most recent version of the index, UBIFS storesa special node calledmaster node into UBI LEB 1 which always points to themost recent root node of the UBIFS index. For recoverability, the master nodeis additionally duplicated to LEB 2. Mounting UBIFS is thus a simple read ofLEB 1 and 2 to get the current master node and from there get the location ofthe most recent on-flash index.

The TNC is the in-memory representation of the on-flash index. It contains someadditional runtime attributes per node which are not persisted. One of these isa dirty-flag which marks nodes that have to be persisted the next time theindex is written onto the flash. The TNC acts as a write-back cache and allmodifications of the on-flash index are done through the TNC. Like other caches,the TNC does not have to mirror the full index into memory, but reads parts ofit from flash whenever needed. Acommit is the UBIFS operation of updating theon-flash filesystem structures like the index. On every commit, the TNC nodesmarked as dirty are written to the flash to update the persisted index.

Journal¶

To avoid wearing out the flash, the index is only persisted (committed) whencertain conditions are met (eg.fsync(2)). The journal is used to recordany changes (in form of inode nodes, data nodes etc.) between commitsof the index. During mount, the journal is read from the flash and replayedonto the TNC (which will be created on-demand from the on-flash index).

UBIFS reserves a bunch of LEBs just for the journal calledlog area. Theamount of log area LEBs is configured on filesystem creation (usingmkfs.ubifs) and stored in the superblock node. The log area contains onlytwo types of nodes:reference nodes andcommit start nodes. A commit startnode is written whenever an index commit is performed. Reference nodes arewritten on every journal update. Each reference node points to the position ofother nodes (inode nodes, data nodes etc.) on the flash that are part of thisjournal entry. These nodes are calledbuds and describe the actual filesystemchanges including their data.

The log area is maintained as a ring. Whenever the journal is almost full,a commit is initiated. This also writes a commit start node so that duringmount, UBIFS will seek for the most recent commit start node and just replayevery reference node after that. Every reference node before the commit startnode will be ignored as they are already part of the on-flash index.

When writing a journal entry, UBIFS first ensures that enough space isavailable to write the reference node and buds part of this entry. Then, thereference node is written and afterwards the buds describing the file changes.On replay, UBIFS will record every reference node and inspect the location ofthe referenced LEBs to discover the buds. If these are corrupt or missing,UBIFS will attempt to recover them by re-reading the LEB. This is however onlydone for the last referenced LEB of the journal. Only this can become corruptbecause of a power cut. If the recovery fails, UBIFS will not mount. An errorfor every other LEB will directly cause UBIFS to fail the mount operation.

| ----    LOG AREA     ---- | ----------    MAIN AREA    ------------ | -----+------+-----+--------+----   ------+-----+-----+--------------- \    |      |     |        |   /  /      |     |     |               \ / CS |  REF | REF |        |   \  \ DENT | INO | INO |               / \    |      |     |        |   /  /      |     |     |               \  ----+------+-----+--------+---   -------+-----+-----+----------------          |     |                  ^            ^          |     |                  |            |          +------------------------+            |                |                               |                +-------------------------------+         Figure 2: UBIFS flash layout of log area with commit start nodes                   (CS) and reference nodes (REF) pointing to main area                   containing their buds

LEB Property Tree/Table¶

The LEB property tree is used to store per-LEB information. This includes theLEB type and amount of free anddirty (old, obsolete content) space[1] onthe LEB. The type is important, because UBIFS never mixes index nodes with datanodes on a single LEB and thus each LEB has a specific purpose. This again isuseful for free space calculations. See [UBIFS-WP] for more details.

The LEB property tree again is a B+ tree, but it is much smaller than theindex. Due to its smaller size it is always written as one chunk on everycommit. Thus, saving the LPT is an atomic operation.

[1]

Since LEBs can only be appended and never overwritten, there is adifference between free space ie. the remaining space left on the LEB to bewritten to without erasing it and previously written content that is obsoletebut can’t be overwritten without erasing the full LEB.

UBIFS Authentication¶

This chapter introduces UBIFS authentication which enables UBIFS to verifythe authenticity and integrity of metadata and file contents stored on flash.

Threat Model¶

UBIFS authentication enables detection of offline data modification. While itdoes not prevent it, it enables (trusted) code to check the integrity andauthenticity of on-flash file contents and filesystem metadata. This coversattacks where file contents are swapped.

UBIFS authentication will not protect against rollback of full flash contents.Ie. an attacker can still dump the flash and restore it at a later time withoutdetection. It will also not protect against partial rollback of individualindex commits. That means that an attacker is able to partially undo changes.This is possible because UBIFS does not immediately overwrites obsoleteversions of the index tree or the journal, but instead marks them as obsoleteand garbage collection erases them at a later time. An attacker can use this byerasing parts of the current tree and restoring old versions that are still onthe flash and have not yet been erased. This is possible, because every commitwill always write a new version of the index root node and the master nodewithout overwriting the previous version. This is further helped by thewear-leveling operations of UBI which copies contents from one physicaleraseblock to another and does not atomically erase the first eraseblock.

UBIFS authentication does not cover attacks where an attacker is able toexecute code on the device after the authentication key was provided.Additional measures like secure boot and trusted boot have to be taken toensure that only trusted code is executed on a device.

Authentication¶

To be able to fully trust data read from flash, all UBIFS data structuresstored on flash are authenticated. That is:

The index which includes file contents, file metadata like extendedattributes, file length etc.
The journal which also contains file contents and metadata by recording changesto the filesystem
The LPT which stores UBI LEB metadata which UBIFS uses for free space accounting

Index Authentication¶

Through UBIFS’ concept of a wandering tree, it already takes care of onlyupdating and persisting changed parts from leaf node up to the root nodeof the full B+ tree. This enables us to augment the index nodes of the treewith a hash over each node’s child nodes. As a result, the index basically alsoa Merkle tree. Since the leaf nodes of the index contain the actual filesystemdata, the hashes of their parent index nodes thus cover all the file contentsand file metadata. When a file changes, the UBIFS index is updated accordinglyfrom the leaf nodes up to the root node including the master node. This processcan be hooked to recompute the hash only for each changed node at the same time.Whenever a file is read, UBIFS can verify the hashes from each leaf node up tothe root node to ensure the node’s integrity.

To ensure the authenticity of the whole index, the UBIFS master node stores akeyed hash (HMAC) over its own contents and a hash of the root node of the indextree. As mentioned above, the master node is always written to the flash wheneverthe index is persisted (ie. on index commit).

Using this approach only UBIFS index nodes and the master node are changed toinclude a hash. All other types of nodes will remain unchanged. This reducesthe storage overhead which is precious for users of UBIFS (ie. embeddeddevices).

                  +---------------+                  |  Master Node  |                  |    (hash)     |                  +---------------+                          |                          v                 +-------------------+                 |  Index Node #1    |                 |                   |                 | branch0   branchn |                 | (hash)    (hash)  |                 +-------------------+                    |    ...   |  (fanout: 8)                    |          |            +-------+          +------+            |                         |            v                         v +-------------------+       +-------------------+ |  Index Node #2    |       |  Index Node #3    | |                   |       |                   | | branch0   branchn |       | branch0   branchn | | (hash)    (hash)  |       | (hash)    (hash)  | +-------------------+       +-------------------+      |   ...                     |   ...   |      v                           v         v    +-----------+         +----------+  +-----------+    | Data Node |         | INO Node |  | DENT Node |    +-----------+         +----------+  +-----------+Figure 3: Coverage areas of index node hash and master node HMAC

The most important part for robustness and power-cut safety is to atomicallypersist the hash and file contents. Here the existing UBIFS logic for howchanged nodes are persisted is already designed for this purpose such thatUBIFS can safely recover if a power-cut occurs while persisting. Addinghashes to index nodes does not change this since each hash will be persistedatomically together with its respective node.

Journal Authentication¶

The journal is authenticated too. Since the journal is continuously writtenit is necessary to also add authentication information frequently to thejournal so that in case of a powercut not too much data can’t be authenticated.This is done by creating a continuous hash beginning from the commit start nodeover the previous reference nodes, the current reference node, and the budnodes. From time to time whenever it is suitable authentication nodes are addedbetween the bud nodes. This new node type contains a HMAC over the current stateof the hash chain. That way a journal can be authenticated up to the lastauthentication node. The tail of the journal which may not have a authenticationnode cannot be authenticated and is skipped during journal replay.

We get this picture for journal authentication:

,,,,,,,,,......,...........................................,. CS  ,               hash1.----.           hash2.----.,.  |  ,                    .    |hmac            .    |hmac,.  v  ,                    .    v                .    v,.REF#0,-> bud -> bud -> bud.-> auth -> bud -> bud.-> auth ...,..|...,...........................................,  |   ,,  |   ,,,,,,,,,,,,,,,.  |            hash3,----.,  |                 ,    |hmac,  v                 ,    v, REF#1 -> bud -> bud,-> auth ...,,,|,,,,,,,,,,,,,,,,,,   v  REF#2 -> ...   |   V  ...

Since the hash also includes the reference nodes an attacker cannot reorder orskip any journal heads for replay. An attacker can only remove bud nodes orreference nodes from the end of the journal, effectively rewinding thefilesystem at maximum back to the last commit.

The location of the log area is stored in the master node. Since the masternode is authenticated with a HMAC as described above, it is not possible totamper with that without detection. The size of the log area is specified whenthe filesystem is created usingmkfs.ubifs and stored in the superblock node.To avoid tampering with this and other values stored there, a HMAC is added tothe superblock struct. The superblock node is stored in LEB 0 and is onlymodified on feature flag or similar changes, but never on file changes.

LPT Authentication¶

The location of the LPT root node on the flash is stored in the UBIFS masternode. Since the LPT is written and read atomically on every commit, there isno need to authenticate individual nodes of the tree. It suffices toprotect the integrity of the full LPT by a simple hash stored in the masternode. Since the master node itself is authenticated, the LPTs authenticity canbe verified by verifying the authenticity of the master node and comparing theLTP hash stored there with the hash computed from the read on-flash LPT.

Key Management¶

For simplicity, UBIFS authentication uses a single key to compute the HMACsof superblock, master, commit start and reference nodes. This key has to beavailable on creation of the filesystem (mkfs.ubifs) to authenticate thesuperblock node. Further, it has to be available on mount of the filesystemto verify authenticated nodes and generate new HMACs for changes.

UBIFS authentication is intended to operate side-by-side with UBIFS encryption(fscrypt) to provide confidentiality and authenticity. Since UBIFS encryptionhas a different approach of encryption policies per directory, there can bemultiple fscrypt master keys and there might be folders without encryption.UBIFS authentication on the other hand has an all-or-nothing approach in thesense that it either authenticates everything of the filesystem or nothing.Because of this and because UBIFS authentication should also be usable withoutencryption, it does not share the same master key with fscrypt, but managesa dedicated authentication key.

The API for providing the authentication key has yet to be defined, but thekey can eg. be provided by userspace through a keyring similar to the way itis currently done in fscrypt. It should however be noted that the currentfscrypt approach has shown its flaws and the userspace API will eventuallychange [FSCRYPT-POLICY2].

Nevertheless, it will be possible for a user to provide a single passphraseor key in userspace that covers UBIFS authentication and encryption. This canbe solved by the corresponding userspace tools which derive a second key forauthentication in addition to the derived fscrypt master key used forencryption.

To be able to check if the proper key is available on mount, the UBIFSsuperblock node will additionally store a hash of the authentication key. Thisapproach is similar to the approach proposed for fscrypt encryption policy v2[FSCRYPT-POLICY2].

Future Extensions¶

In certain cases where a vendor wants to provide an authenticated filesystemimage to customers, it should be possible to do so without sharing the secretUBIFS authentication key. Instead, in addition the each HMAC a digitalsignature could be stored where the vendor shares the public key alongside thefilesystem image. In case this filesystem has to be modified afterwards,UBIFS can exchange all digital signatures with HMACs on first mount similarto the way the IMA/EVM subsystem deals with such situations. The HMAC keywill then have to be provided beforehand in the normal way.