0001 .. SPDX-License-Identifier: GPL-2.0
0002
0003 .. UBIFS Authentication
0004 .. sigma star gmbh
0005 .. 2018
0006
0007 ============================
0008 UBIFS Authentication Support
0009 ============================
0010
0011 Introduction
0012 ============
0013
0014 UBIFS utilizes the fscrypt framework to provide confidentiality for file
0015 contents and file names. This prevents attacks where an attacker is able to
0016 read contents of the filesystem on a single point in time. A classic example
0017 is a lost smartphone where the attacker is unable to read personal data stored
0018 on the device without the filesystem decryption key.
0019
0020 At the current state, UBIFS encryption however does not prevent attacks where
0021 the attacker is able to modify the filesystem contents and the user uses the
0022 device afterwards. In such a scenario an attacker can modify filesystem
0023 contents arbitrarily without the user noticing. One example is to modify a
0024 binary to perform a malicious action when executed [DMC-CBC-ATTACK]. Since
0025 most of the filesystem metadata of UBIFS is stored in plain, this makes it
0026 fairly easy to swap files and replace their contents.
0027
0028 Other full disk encryption systems like dm-crypt cover all filesystem metadata,
0029 which makes such kinds of attacks more complicated, but not impossible.
0030 Especially, if the attacker is given access to the device multiple points in
0031 time. For dm-crypt and other filesystems that build upon the Linux block IO
0032 layer, the dm-integrity or dm-verity subsystems [DM-INTEGRITY, DM-VERITY]
0033 can be used to get full data authentication at the block layer.
0034 These can also be combined with dm-crypt [CRYPTSETUP2].
0035
0036 This document describes an approach to get file contents _and_ full metadata
0037 authentication for UBIFS. Since UBIFS uses fscrypt for file contents and file
0038 name encryption, the authentication system could be tied into fscrypt such that
0039 existing features like key derivation can be utilized. It should however also
0040 be possible to use UBIFS authentication without using encryption.
0041
0042
0043 MTD, UBI & UBIFS
0044 ----------------
0045
0046 On Linux, the MTD (Memory Technology Devices) subsystem provides a uniform
0047 interface to access raw flash devices. One of the more prominent subsystems that
0048 work on top of MTD is UBI (Unsorted Block Images). It provides volume management
0049 for flash devices and is thus somewhat similar to LVM for block devices. In
0050 addition, it deals with flash-specific wear-leveling and transparent I/O error
0051 handling. UBI offers logical erase blocks (LEBs) to the layers on top of it
0052 and maps them transparently to physical erase blocks (PEBs) on the flash.
0053
0054 UBIFS is a filesystem for raw flash which operates on top of UBI. Thus, wear
0055 leveling and some flash specifics are left to UBI, while UBIFS focuses on
0056 scalability, performance and recoverability.
0057
0058 ::
0059
0060 +------------+ +*******+ +-----------+ +-----+
0061 | | * UBIFS * | UBI-BLOCK | | ... |
0062 | JFFS/JFFS2 | +*******+ +-----------+ +-----+
0063 | | +-----------------------------+ +-----------+ +-----+
0064 | | | UBI | | MTD-BLOCK | | ... |
0065 +------------+ +-----------------------------+ +-----------+ +-----+
0066 +------------------------------------------------------------------+
0067 | MEMORY TECHNOLOGY DEVICES (MTD) |
0068 +------------------------------------------------------------------+
0069 +-----------------------------+ +--------------------------+ +-----+
0070 | NAND DRIVERS | | NOR DRIVERS | | ... |
0071 +-----------------------------+ +--------------------------+ +-----+
0072
0073 Figure 1: Linux kernel subsystems for dealing with raw flash
0074
0075
0076
0077 Internally, UBIFS maintains multiple data structures which are persisted on
0078 the flash:
0079
0080 - *Index*: an on-flash B+ tree where the leaf nodes contain filesystem data
0081 - *Journal*: an additional data structure to collect FS changes before updating
0082 the on-flash index and reduce flash wear.
0083 - *Tree Node Cache (TNC)*: an in-memory B+ tree that reflects the current FS
0084 state to avoid frequent flash reads. It is basically the in-memory
0085 representation of the index, but contains additional attributes.
0086 - *LEB property tree (LPT)*: an on-flash B+ tree for free space accounting per
0087 UBI LEB.
0088
0089 In the remainder of this section we will cover the on-flash UBIFS data
0090 structures in more detail. The TNC is of less importance here since it is never
0091 persisted onto the flash directly. More details on UBIFS can also be found in
0092 [UBIFS-WP].
0093
0094
0095 UBIFS Index & Tree Node Cache
0096 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
0097
0098 Basic on-flash UBIFS entities are called *nodes*. UBIFS knows different types
0099 of nodes. Eg. data nodes (``struct ubifs_data_node``) which store chunks of file
0100 contents or inode nodes (``struct ubifs_ino_node``) which represent VFS inodes.
0101 Almost all types of nodes share a common header (``ubifs_ch``) containing basic
0102 information like node type, node length, a sequence number, etc. (see
0103 ``fs/ubifs/ubifs-media.h`` in kernel source). Exceptions are entries of the LPT
0104 and some less important node types like padding nodes which are used to pad
0105 unusable content at the end of LEBs.
0106
0107 To avoid re-writing the whole B+ tree on every single change, it is implemented
0108 as *wandering tree*, where only the changed nodes are re-written and previous
0109 versions of them are obsoleted without erasing them right away. As a result,
0110 the index is not stored in a single place on the flash, but *wanders* around
0111 and there are obsolete parts on the flash as long as the LEB containing them is
0112 not reused by UBIFS. To find the most recent version of the index, UBIFS stores
0113 a special node called *master node* into UBI LEB 1 which always points to the
0114 most recent root node of the UBIFS index. For recoverability, the master node
0115 is additionally duplicated to LEB 2. Mounting UBIFS is thus a simple read of
0116 LEB 1 and 2 to get the current master node and from there get the location of
0117 the most recent on-flash index.
0118
0119 The TNC is the in-memory representation of the on-flash index. It contains some
0120 additional runtime attributes per node which are not persisted. One of these is
0121 a dirty-flag which marks nodes that have to be persisted the next time the
0122 index is written onto the flash. The TNC acts as a write-back cache and all
0123 modifications of the on-flash index are done through the TNC. Like other caches,
0124 the TNC does not have to mirror the full index into memory, but reads parts of
0125 it from flash whenever needed. A *commit* is the UBIFS operation of updating the
0126 on-flash filesystem structures like the index. On every commit, the TNC nodes
0127 marked as dirty are written to the flash to update the persisted index.
0128
0129
0130 Journal
0131 ~~~~~~~
0132
0133 To avoid wearing out the flash, the index is only persisted (*commited*) when
0134 certain conditions are met (eg. ``fsync(2)``). The journal is used to record
0135 any changes (in form of inode nodes, data nodes etc.) between commits
0136 of the index. During mount, the journal is read from the flash and replayed
0137 onto the TNC (which will be created on-demand from the on-flash index).
0138
0139 UBIFS reserves a bunch of LEBs just for the journal called *log area*. The
0140 amount of log area LEBs is configured on filesystem creation (using
0141 ``mkfs.ubifs``) and stored in the superblock node. The log area contains only
0142 two types of nodes: *reference nodes* and *commit start nodes*. A commit start
0143 node is written whenever an index commit is performed. Reference nodes are
0144 written on every journal update. Each reference node points to the position of
0145 other nodes (inode nodes, data nodes etc.) on the flash that are part of this
0146 journal entry. These nodes are called *buds* and describe the actual filesystem
0147 changes including their data.
0148
0149 The log area is maintained as a ring. Whenever the journal is almost full,
0150 a commit is initiated. This also writes a commit start node so that during
0151 mount, UBIFS will seek for the most recent commit start node and just replay
0152 every reference node after that. Every reference node before the commit start
0153 node will be ignored as they are already part of the on-flash index.
0154
0155 When writing a journal entry, UBIFS first ensures that enough space is
0156 available to write the reference node and buds part of this entry. Then, the
0157 reference node is written and afterwards the buds describing the file changes.
0158 On replay, UBIFS will record every reference node and inspect the location of
0159 the referenced LEBs to discover the buds. If these are corrupt or missing,
0160 UBIFS will attempt to recover them by re-reading the LEB. This is however only
0161 done for the last referenced LEB of the journal. Only this can become corrupt
0162 because of a power cut. If the recovery fails, UBIFS will not mount. An error
0163 for every other LEB will directly cause UBIFS to fail the mount operation.
0164
0165 ::
0166
0167 | ---- LOG AREA ---- | ---------- MAIN AREA ------------ |
0168
0169 -----+------+-----+--------+---- ------+-----+-----+---------------
0170 \ | | | | / / | | | \
0171 / CS | REF | REF | | \ \ DENT | INO | INO | /
0172 \ | | | | / / | | | \
0173 ----+------+-----+--------+--- -------+-----+-----+----------------
0174 | | ^ ^
0175 | | | |
0176 +------------------------+ |
0177 | |
0178 +-------------------------------+
0179
0180
0181 Figure 2: UBIFS flash layout of log area with commit start nodes
0182 (CS) and reference nodes (REF) pointing to main area
0183 containing their buds
0184
0185
0186 LEB Property Tree/Table
0187 ~~~~~~~~~~~~~~~~~~~~~~~
0188
0189 The LEB property tree is used to store per-LEB information. This includes the
0190 LEB type and amount of free and *dirty* (old, obsolete content) space [1]_ on
0191 the LEB. The type is important, because UBIFS never mixes index nodes with data
0192 nodes on a single LEB and thus each LEB has a specific purpose. This again is
0193 useful for free space calculations. See [UBIFS-WP] for more details.
0194
0195 The LEB property tree again is a B+ tree, but it is much smaller than the
0196 index. Due to its smaller size it is always written as one chunk on every
0197 commit. Thus, saving the LPT is an atomic operation.
0198
0199
0200 .. [1] Since LEBs can only be appended and never overwritten, there is a
0201 difference between free space ie. the remaining space left on the LEB to be
0202 written to without erasing it and previously written content that is obsolete
0203 but can't be overwritten without erasing the full LEB.
0204
0205
0206 UBIFS Authentication
0207 ====================
0208
0209 This chapter introduces UBIFS authentication which enables UBIFS to verify
0210 the authenticity and integrity of metadata and file contents stored on flash.
0211
0212
0213 Threat Model
0214 ------------
0215
0216 UBIFS authentication enables detection of offline data modification. While it
0217 does not prevent it, it enables (trusted) code to check the integrity and
0218 authenticity of on-flash file contents and filesystem metadata. This covers
0219 attacks where file contents are swapped.
0220
0221 UBIFS authentication will not protect against rollback of full flash contents.
0222 Ie. an attacker can still dump the flash and restore it at a later time without
0223 detection. It will also not protect against partial rollback of individual
0224 index commits. That means that an attacker is able to partially undo changes.
0225 This is possible because UBIFS does not immediately overwrites obsolete
0226 versions of the index tree or the journal, but instead marks them as obsolete
0227 and garbage collection erases them at a later time. An attacker can use this by
0228 erasing parts of the current tree and restoring old versions that are still on
0229 the flash and have not yet been erased. This is possible, because every commit
0230 will always write a new version of the index root node and the master node
0231 without overwriting the previous version. This is further helped by the
0232 wear-leveling operations of UBI which copies contents from one physical
0233 eraseblock to another and does not atomically erase the first eraseblock.
0234
0235 UBIFS authentication does not cover attacks where an attacker is able to
0236 execute code on the device after the authentication key was provided.
0237 Additional measures like secure boot and trusted boot have to be taken to
0238 ensure that only trusted code is executed on a device.
0239
0240
0241 Authentication
0242 --------------
0243
0244 To be able to fully trust data read from flash, all UBIFS data structures
0245 stored on flash are authenticated. That is:
0246
0247 - The index which includes file contents, file metadata like extended
0248 attributes, file length etc.
0249 - The journal which also contains file contents and metadata by recording changes
0250 to the filesystem
0251 - The LPT which stores UBI LEB metadata which UBIFS uses for free space accounting
0252
0253
0254 Index Authentication
0255 ~~~~~~~~~~~~~~~~~~~~
0256
0257 Through UBIFS' concept of a wandering tree, it already takes care of only
0258 updating and persisting changed parts from leaf node up to the root node
0259 of the full B+ tree. This enables us to augment the index nodes of the tree
0260 with a hash over each node's child nodes. As a result, the index basically also
0261 a Merkle tree. Since the leaf nodes of the index contain the actual filesystem
0262 data, the hashes of their parent index nodes thus cover all the file contents
0263 and file metadata. When a file changes, the UBIFS index is updated accordingly
0264 from the leaf nodes up to the root node including the master node. This process
0265 can be hooked to recompute the hash only for each changed node at the same time.
0266 Whenever a file is read, UBIFS can verify the hashes from each leaf node up to
0267 the root node to ensure the node's integrity.
0268
0269 To ensure the authenticity of the whole index, the UBIFS master node stores a
0270 keyed hash (HMAC) over its own contents and a hash of the root node of the index
0271 tree. As mentioned above, the master node is always written to the flash whenever
0272 the index is persisted (ie. on index commit).
0273
0274 Using this approach only UBIFS index nodes and the master node are changed to
0275 include a hash. All other types of nodes will remain unchanged. This reduces
0276 the storage overhead which is precious for users of UBIFS (ie. embedded
0277 devices).
0278
0279 ::
0280
0281 +---------------+
0282 | Master Node |
0283 | (hash) |
0284 +---------------+
0285 |
0286 v
0287 +-------------------+
0288 | Index Node #1 |
0289 | |
0290 | branch0 branchn |
0291 | (hash) (hash) |
0292 +-------------------+
0293 | ... | (fanout: 8)
0294 | |
0295 +-------+ +------+
0296 | |
0297 v v
0298 +-------------------+ +-------------------+
0299 | Index Node #2 | | Index Node #3 |
0300 | | | |
0301 | branch0 branchn | | branch0 branchn |
0302 | (hash) (hash) | | (hash) (hash) |
0303 +-------------------+ +-------------------+
0304 | ... | ... |
0305 v v v
0306 +-----------+ +----------+ +-----------+
0307 | Data Node | | INO Node | | DENT Node |
0308 +-----------+ +----------+ +-----------+
0309
0310
0311 Figure 3: Coverage areas of index node hash and master node HMAC
0312
0313
0314
0315 The most important part for robustness and power-cut safety is to atomically
0316 persist the hash and file contents. Here the existing UBIFS logic for how
0317 changed nodes are persisted is already designed for this purpose such that
0318 UBIFS can safely recover if a power-cut occurs while persisting. Adding
0319 hashes to index nodes does not change this since each hash will be persisted
0320 atomically together with its respective node.
0321
0322
0323 Journal Authentication
0324 ~~~~~~~~~~~~~~~~~~~~~~
0325
0326 The journal is authenticated too. Since the journal is continuously written
0327 it is necessary to also add authentication information frequently to the
0328 journal so that in case of a powercut not too much data can't be authenticated.
0329 This is done by creating a continuous hash beginning from the commit start node
0330 over the previous reference nodes, the current reference node, and the bud
0331 nodes. From time to time whenever it is suitable authentication nodes are added
0332 between the bud nodes. This new node type contains a HMAC over the current state
0333 of the hash chain. That way a journal can be authenticated up to the last
0334 authentication node. The tail of the journal which may not have a authentication
0335 node cannot be authenticated and is skipped during journal replay.
0336
0337 We get this picture for journal authentication::
0338
0339 ,,,,,,,,
0340 ,......,...........................................
0341 ,. CS , hash1.----. hash2.----.
0342 ,. | , . |hmac . |hmac
0343 ,. v , . v . v
0344 ,.REF#0,-> bud -> bud -> bud.-> auth -> bud -> bud.-> auth ...
0345 ,..|...,...........................................
0346 , | ,
0347 , | ,,,,,,,,,,,,,,,
0348 . | hash3,----.
0349 , | , |hmac
0350 , v , v
0351 , REF#1 -> bud -> bud,-> auth ...
0352 ,,,|,,,,,,,,,,,,,,,,,,
0353 v
0354 REF#2 -> ...
0355 |
0356 V
0357 ...
0358
0359 Since the hash also includes the reference nodes an attacker cannot reorder or
0360 skip any journal heads for replay. An attacker can only remove bud nodes or
0361 reference nodes from the end of the journal, effectively rewinding the
0362 filesystem at maximum back to the last commit.
0363
0364 The location of the log area is stored in the master node. Since the master
0365 node is authenticated with a HMAC as described above, it is not possible to
0366 tamper with that without detection. The size of the log area is specified when
0367 the filesystem is created using `mkfs.ubifs` and stored in the superblock node.
0368 To avoid tampering with this and other values stored there, a HMAC is added to
0369 the superblock struct. The superblock node is stored in LEB 0 and is only
0370 modified on feature flag or similar changes, but never on file changes.
0371
0372
0373 LPT Authentication
0374 ~~~~~~~~~~~~~~~~~~
0375
0376 The location of the LPT root node on the flash is stored in the UBIFS master
0377 node. Since the LPT is written and read atomically on every commit, there is
0378 no need to authenticate individual nodes of the tree. It suffices to
0379 protect the integrity of the full LPT by a simple hash stored in the master
0380 node. Since the master node itself is authenticated, the LPTs authenticity can
0381 be verified by verifying the authenticity of the master node and comparing the
0382 LTP hash stored there with the hash computed from the read on-flash LPT.
0383
0384
0385 Key Management
0386 --------------
0387
0388 For simplicity, UBIFS authentication uses a single key to compute the HMACs
0389 of superblock, master, commit start and reference nodes. This key has to be
0390 available on creation of the filesystem (`mkfs.ubifs`) to authenticate the
0391 superblock node. Further, it has to be available on mount of the filesystem
0392 to verify authenticated nodes and generate new HMACs for changes.
0393
0394 UBIFS authentication is intended to operate side-by-side with UBIFS encryption
0395 (fscrypt) to provide confidentiality and authenticity. Since UBIFS encryption
0396 has a different approach of encryption policies per directory, there can be
0397 multiple fscrypt master keys and there might be folders without encryption.
0398 UBIFS authentication on the other hand has an all-or-nothing approach in the
0399 sense that it either authenticates everything of the filesystem or nothing.
0400 Because of this and because UBIFS authentication should also be usable without
0401 encryption, it does not share the same master key with fscrypt, but manages
0402 a dedicated authentication key.
0403
0404 The API for providing the authentication key has yet to be defined, but the
0405 key can eg. be provided by userspace through a keyring similar to the way it
0406 is currently done in fscrypt. It should however be noted that the current
0407 fscrypt approach has shown its flaws and the userspace API will eventually
0408 change [FSCRYPT-POLICY2].
0409
0410 Nevertheless, it will be possible for a user to provide a single passphrase
0411 or key in userspace that covers UBIFS authentication and encryption. This can
0412 be solved by the corresponding userspace tools which derive a second key for
0413 authentication in addition to the derived fscrypt master key used for
0414 encryption.
0415
0416 To be able to check if the proper key is available on mount, the UBIFS
0417 superblock node will additionally store a hash of the authentication key. This
0418 approach is similar to the approach proposed for fscrypt encryption policy v2
0419 [FSCRYPT-POLICY2].
0420
0421
0422 Future Extensions
0423 =================
0424
0425 In certain cases where a vendor wants to provide an authenticated filesystem
0426 image to customers, it should be possible to do so without sharing the secret
0427 UBIFS authentication key. Instead, in addition the each HMAC a digital
0428 signature could be stored where the vendor shares the public key alongside the
0429 filesystem image. In case this filesystem has to be modified afterwards,
0430 UBIFS can exchange all digital signatures with HMACs on first mount similar
0431 to the way the IMA/EVM subsystem deals with such situations. The HMAC key
0432 will then have to be provided beforehand in the normal way.
0433
0434
0435 References
0436 ==========
0437
0438 [CRYPTSETUP2] https://www.saout.de/pipermail/dm-crypt/2017-November/005745.html
0439
0440 [DMC-CBC-ATTACK] https://www.jakoblell.com/blog/2013/12/22/practical-malleability-attack-against-cbc-encrypted-luks-partitions/
0441
0442 [DM-INTEGRITY] https://www.kernel.org/doc/Documentation/device-mapper/dm-integrity.rst
0443
0444 [DM-VERITY] https://www.kernel.org/doc/Documentation/device-mapper/verity.rst
0445
0446 [FSCRYPT-POLICY2] https://www.spinics.net/lists/linux-ext4/msg58710.html
0447
0448 [UBIFS-WP] http://www.linux-mtd.infradead.org/doc/ubifs_whitepaper.pdf
