cachepc-linux

Fork of AMDESE/linux with modifications for CachePC side-channel attack
git clone https://git.sinitax.com/sinitax/cachepc-linux
Log | Files | Refs | README | LICENSE | sfeed.txt

ubifs-authentication.rst (22232B)


      1.. SPDX-License-Identifier: GPL-2.0
      2
      3.. UBIFS Authentication
      4.. sigma star gmbh
      5.. 2018
      6
      7============================
      8UBIFS Authentication Support
      9============================
     10
     11Introduction
     12============
     13
     14UBIFS utilizes the fscrypt framework to provide confidentiality for file
     15contents and file names. This prevents attacks where an attacker is able to
     16read contents of the filesystem on a single point in time. A classic example
     17is a lost smartphone where the attacker is unable to read personal data stored
     18on the device without the filesystem decryption key.
     19
     20At the current state, UBIFS encryption however does not prevent attacks where
     21the attacker is able to modify the filesystem contents and the user uses the
     22device afterwards. In such a scenario an attacker can modify filesystem
     23contents arbitrarily without the user noticing. One example is to modify a
     24binary to perform a malicious action when executed [DMC-CBC-ATTACK]. Since
     25most of the filesystem metadata of UBIFS is stored in plain, this makes it
     26fairly easy to swap files and replace their contents.
     27
     28Other full disk encryption systems like dm-crypt cover all filesystem metadata,
     29which makes such kinds of attacks more complicated, but not impossible.
     30Especially, if the attacker is given access to the device multiple points in
     31time. For dm-crypt and other filesystems that build upon the Linux block IO
     32layer, the dm-integrity or dm-verity subsystems [DM-INTEGRITY, DM-VERITY]
     33can be used to get full data authentication at the block layer.
     34These can also be combined with dm-crypt [CRYPTSETUP2].
     35
     36This document describes an approach to get file contents _and_ full metadata
     37authentication for UBIFS. Since UBIFS uses fscrypt for file contents and file
     38name encryption, the authentication system could be tied into fscrypt such that
     39existing features like key derivation can be utilized. It should however also
     40be possible to use UBIFS authentication without using encryption.
     41
     42
     43MTD, UBI & UBIFS
     44----------------
     45
     46On Linux, the MTD (Memory Technology Devices) subsystem provides a uniform
     47interface to access raw flash devices. One of the more prominent subsystems that
     48work on top of MTD is UBI (Unsorted Block Images). It provides volume management
     49for flash devices and is thus somewhat similar to LVM for block devices. In
     50addition, it deals with flash-specific wear-leveling and transparent I/O error
     51handling. UBI offers logical erase blocks (LEBs) to the layers on top of it
     52and maps them transparently to physical erase blocks (PEBs) on the flash.
     53
     54UBIFS is a filesystem for raw flash which operates on top of UBI. Thus, wear
     55leveling and some flash specifics are left to UBI, while UBIFS focuses on
     56scalability, performance and recoverability.
     57
     58::
     59
     60	+------------+ +*******+ +-----------+ +-----+
     61	|            | * UBIFS * | UBI-BLOCK | | ... |
     62	| JFFS/JFFS2 | +*******+ +-----------+ +-----+
     63	|            | +-----------------------------+ +-----------+ +-----+
     64	|            | |              UBI            | | MTD-BLOCK | | ... |
     65	+------------+ +-----------------------------+ +-----------+ +-----+
     66	+------------------------------------------------------------------+
     67	|                  MEMORY TECHNOLOGY DEVICES (MTD)                 |
     68	+------------------------------------------------------------------+
     69	+-----------------------------+ +--------------------------+ +-----+
     70	|         NAND DRIVERS        | |        NOR DRIVERS       | | ... |
     71	+-----------------------------+ +--------------------------+ +-----+
     72
     73            Figure 1: Linux kernel subsystems for dealing with raw flash
     74
     75
     76
     77Internally, UBIFS maintains multiple data structures which are persisted on
     78the flash:
     79
     80- *Index*: an on-flash B+ tree where the leaf nodes contain filesystem data
     81- *Journal*: an additional data structure to collect FS changes before updating
     82  the on-flash index and reduce flash wear.
     83- *Tree Node Cache (TNC)*: an in-memory B+ tree that reflects the current FS
     84  state to avoid frequent flash reads. It is basically the in-memory
     85  representation of the index, but contains additional attributes.
     86- *LEB property tree (LPT)*: an on-flash B+ tree for free space accounting per
     87  UBI LEB.
     88
     89In the remainder of this section we will cover the on-flash UBIFS data
     90structures in more detail. The TNC is of less importance here since it is never
     91persisted onto the flash directly. More details on UBIFS can also be found in
     92[UBIFS-WP].
     93
     94
     95UBIFS Index & Tree Node Cache
     96~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     97
     98Basic on-flash UBIFS entities are called *nodes*. UBIFS knows different types
     99of nodes. Eg. data nodes (``struct ubifs_data_node``) which store chunks of file
    100contents or inode nodes (``struct ubifs_ino_node``) which represent VFS inodes.
    101Almost all types of nodes share a common header (``ubifs_ch``) containing basic
    102information like node type, node length, a sequence number, etc. (see
    103``fs/ubifs/ubifs-media.h`` in kernel source). Exceptions are entries of the LPT
    104and some less important node types like padding nodes which are used to pad
    105unusable content at the end of LEBs.
    106
    107To avoid re-writing the whole B+ tree on every single change, it is implemented
    108as *wandering tree*, where only the changed nodes are re-written and previous
    109versions of them are obsoleted without erasing them right away. As a result,
    110the index is not stored in a single place on the flash, but *wanders* around
    111and there are obsolete parts on the flash as long as the LEB containing them is
    112not reused by UBIFS. To find the most recent version of the index, UBIFS stores
    113a special node called *master node* into UBI LEB 1 which always points to the
    114most recent root node of the UBIFS index. For recoverability, the master node
    115is additionally duplicated to LEB 2. Mounting UBIFS is thus a simple read of
    116LEB 1 and 2 to get the current master node and from there get the location of
    117the most recent on-flash index.
    118
    119The TNC is the in-memory representation of the on-flash index. It contains some
    120additional runtime attributes per node which are not persisted. One of these is
    121a dirty-flag which marks nodes that have to be persisted the next time the
    122index is written onto the flash. The TNC acts as a write-back cache and all
    123modifications of the on-flash index are done through the TNC. Like other caches,
    124the TNC does not have to mirror the full index into memory, but reads parts of
    125it from flash whenever needed. A *commit* is the UBIFS operation of updating the
    126on-flash filesystem structures like the index. On every commit, the TNC nodes
    127marked as dirty are written to the flash to update the persisted index.
    128
    129
    130Journal
    131~~~~~~~
    132
    133To avoid wearing out the flash, the index is only persisted (*commited*) when
    134certain conditions are met (eg. ``fsync(2)``). The journal is used to record
    135any changes (in form of inode nodes, data nodes etc.) between commits
    136of the index. During mount, the journal is read from the flash and replayed
    137onto the TNC (which will be created on-demand from the on-flash index).
    138
    139UBIFS reserves a bunch of LEBs just for the journal called *log area*. The
    140amount of log area LEBs is configured on filesystem creation (using
    141``mkfs.ubifs``) and stored in the superblock node. The log area contains only
    142two types of nodes: *reference nodes* and *commit start nodes*. A commit start
    143node is written whenever an index commit is performed. Reference nodes are
    144written on every journal update. Each reference node points to the position of
    145other nodes (inode nodes, data nodes etc.) on the flash that are part of this
    146journal entry. These nodes are called *buds* and describe the actual filesystem
    147changes including their data.
    148
    149The log area is maintained as a ring. Whenever the journal is almost full,
    150a commit is initiated. This also writes a commit start node so that during
    151mount, UBIFS will seek for the most recent commit start node and just replay
    152every reference node after that. Every reference node before the commit start
    153node will be ignored as they are already part of the on-flash index.
    154
    155When writing a journal entry, UBIFS first ensures that enough space is
    156available to write the reference node and buds part of this entry. Then, the
    157reference node is written and afterwards the buds describing the file changes.
    158On replay, UBIFS will record every reference node and inspect the location of
    159the referenced LEBs to discover the buds. If these are corrupt or missing,
    160UBIFS will attempt to recover them by re-reading the LEB. This is however only
    161done for the last referenced LEB of the journal. Only this can become corrupt
    162because of a power cut. If the recovery fails, UBIFS will not mount. An error
    163for every other LEB will directly cause UBIFS to fail the mount operation.
    164
    165::
    166
    167       | ----    LOG AREA     ---- | ----------    MAIN AREA    ------------ |
    168
    169        -----+------+-----+--------+----   ------+-----+-----+---------------
    170        \    |      |     |        |   /  /      |     |     |               \
    171        / CS |  REF | REF |        |   \  \ DENT | INO | INO |               /
    172        \    |      |     |        |   /  /      |     |     |               \
    173         ----+------+-----+--------+---   -------+-----+-----+----------------
    174                 |     |                  ^            ^
    175                 |     |                  |            |
    176                 +------------------------+            |
    177                       |                               |
    178                       +-------------------------------+
    179
    180
    181                Figure 2: UBIFS flash layout of log area with commit start nodes
    182                          (CS) and reference nodes (REF) pointing to main area
    183                          containing their buds
    184
    185
    186LEB Property Tree/Table
    187~~~~~~~~~~~~~~~~~~~~~~~
    188
    189The LEB property tree is used to store per-LEB information. This includes the
    190LEB type and amount of free and *dirty* (old, obsolete content) space [1]_ on
    191the LEB. The type is important, because UBIFS never mixes index nodes with data
    192nodes on a single LEB and thus each LEB has a specific purpose. This again is
    193useful for free space calculations. See [UBIFS-WP] for more details.
    194
    195The LEB property tree again is a B+ tree, but it is much smaller than the
    196index. Due to its smaller size it is always written as one chunk on every
    197commit. Thus, saving the LPT is an atomic operation.
    198
    199
    200.. [1] Since LEBs can only be appended and never overwritten, there is a
    201   difference between free space ie. the remaining space left on the LEB to be
    202   written to without erasing it and previously written content that is obsolete
    203   but can't be overwritten without erasing the full LEB.
    204
    205
    206UBIFS Authentication
    207====================
    208
    209This chapter introduces UBIFS authentication which enables UBIFS to verify
    210the authenticity and integrity of metadata and file contents stored on flash.
    211
    212
    213Threat Model
    214------------
    215
    216UBIFS authentication enables detection of offline data modification. While it
    217does not prevent it, it enables (trusted) code to check the integrity and
    218authenticity of on-flash file contents and filesystem metadata. This covers
    219attacks where file contents are swapped.
    220
    221UBIFS authentication will not protect against rollback of full flash contents.
    222Ie. an attacker can still dump the flash and restore it at a later time without
    223detection. It will also not protect against partial rollback of individual
    224index commits. That means that an attacker is able to partially undo changes.
    225This is possible because UBIFS does not immediately overwrites obsolete
    226versions of the index tree or the journal, but instead marks them as obsolete
    227and garbage collection erases them at a later time. An attacker can use this by
    228erasing parts of the current tree and restoring old versions that are still on
    229the flash and have not yet been erased. This is possible, because every commit
    230will always write a new version of the index root node and the master node
    231without overwriting the previous version. This is further helped by the
    232wear-leveling operations of UBI which copies contents from one physical
    233eraseblock to another and does not atomically erase the first eraseblock.
    234
    235UBIFS authentication does not cover attacks where an attacker is able to
    236execute code on the device after the authentication key was provided.
    237Additional measures like secure boot and trusted boot have to be taken to
    238ensure that only trusted code is executed on a device.
    239
    240
    241Authentication
    242--------------
    243
    244To be able to fully trust data read from flash, all UBIFS data structures
    245stored on flash are authenticated. That is:
    246
    247- The index which includes file contents, file metadata like extended
    248  attributes, file length etc.
    249- The journal which also contains file contents and metadata by recording changes
    250  to the filesystem
    251- The LPT which stores UBI LEB metadata which UBIFS uses for free space accounting
    252
    253
    254Index Authentication
    255~~~~~~~~~~~~~~~~~~~~
    256
    257Through UBIFS' concept of a wandering tree, it already takes care of only
    258updating and persisting changed parts from leaf node up to the root node
    259of the full B+ tree. This enables us to augment the index nodes of the tree
    260with a hash over each node's child nodes. As a result, the index basically also
    261a Merkle tree. Since the leaf nodes of the index contain the actual filesystem
    262data, the hashes of their parent index nodes thus cover all the file contents
    263and file metadata. When a file changes, the UBIFS index is updated accordingly
    264from the leaf nodes up to the root node including the master node. This process
    265can be hooked to recompute the hash only for each changed node at the same time.
    266Whenever a file is read, UBIFS can verify the hashes from each leaf node up to
    267the root node to ensure the node's integrity.
    268
    269To ensure the authenticity of the whole index, the UBIFS master node stores a
    270keyed hash (HMAC) over its own contents and a hash of the root node of the index
    271tree. As mentioned above, the master node is always written to the flash whenever
    272the index is persisted (ie. on index commit).
    273
    274Using this approach only UBIFS index nodes and the master node are changed to
    275include a hash. All other types of nodes will remain unchanged. This reduces
    276the storage overhead which is precious for users of UBIFS (ie. embedded
    277devices).
    278
    279::
    280
    281                             +---------------+
    282                             |  Master Node  |
    283                             |    (hash)     |
    284                             +---------------+
    285                                     |
    286                                     v
    287                            +-------------------+
    288                            |  Index Node #1    |
    289                            |                   |
    290                            | branch0   branchn |
    291                            | (hash)    (hash)  |
    292                            +-------------------+
    293                               |    ...   |  (fanout: 8)
    294                               |          |
    295                       +-------+          +------+
    296                       |                         |
    297                       v                         v
    298            +-------------------+       +-------------------+
    299            |  Index Node #2    |       |  Index Node #3    |
    300            |                   |       |                   |
    301            | branch0   branchn |       | branch0   branchn |
    302            | (hash)    (hash)  |       | (hash)    (hash)  |
    303            +-------------------+       +-------------------+
    304                 |   ...                     |   ...   |
    305                 v                           v         v
    306               +-----------+         +----------+  +-----------+
    307               | Data Node |         | INO Node |  | DENT Node |
    308               +-----------+         +----------+  +-----------+
    309
    310
    311           Figure 3: Coverage areas of index node hash and master node HMAC
    312
    313
    314
    315The most important part for robustness and power-cut safety is to atomically
    316persist the hash and file contents. Here the existing UBIFS logic for how
    317changed nodes are persisted is already designed for this purpose such that
    318UBIFS can safely recover if a power-cut occurs while persisting. Adding
    319hashes to index nodes does not change this since each hash will be persisted
    320atomically together with its respective node.
    321
    322
    323Journal Authentication
    324~~~~~~~~~~~~~~~~~~~~~~
    325
    326The journal is authenticated too. Since the journal is continuously written
    327it is necessary to also add authentication information frequently to the
    328journal so that in case of a powercut not too much data can't be authenticated.
    329This is done by creating a continuous hash beginning from the commit start node
    330over the previous reference nodes, the current reference node, and the bud
    331nodes. From time to time whenever it is suitable authentication nodes are added
    332between the bud nodes. This new node type contains a HMAC over the current state
    333of the hash chain. That way a journal can be authenticated up to the last
    334authentication node. The tail of the journal which may not have a authentication
    335node cannot be authenticated and is skipped during journal replay.
    336
    337We get this picture for journal authentication::
    338
    339    ,,,,,,,,
    340    ,......,...........................................
    341    ,. CS  ,               hash1.----.           hash2.----.
    342    ,.  |  ,                    .    |hmac            .    |hmac
    343    ,.  v  ,                    .    v                .    v
    344    ,.REF#0,-> bud -> bud -> bud.-> auth -> bud -> bud.-> auth ...
    345    ,..|...,...........................................
    346    ,  |   ,
    347    ,  |   ,,,,,,,,,,,,,,,
    348    .  |            hash3,----.
    349    ,  |                 ,    |hmac
    350    ,  v                 ,    v
    351    , REF#1 -> bud -> bud,-> auth ...
    352    ,,,|,,,,,,,,,,,,,,,,,,
    353       v
    354      REF#2 -> ...
    355       |
    356       V
    357      ...
    358
    359Since the hash also includes the reference nodes an attacker cannot reorder or
    360skip any journal heads for replay. An attacker can only remove bud nodes or
    361reference nodes from the end of the journal, effectively rewinding the
    362filesystem at maximum back to the last commit.
    363
    364The location of the log area is stored in the master node. Since the master
    365node is authenticated with a HMAC as described above, it is not possible to
    366tamper with that without detection. The size of the log area is specified when
    367the filesystem is created using `mkfs.ubifs` and stored in the superblock node.
    368To avoid tampering with this and other values stored there, a HMAC is added to
    369the superblock struct. The superblock node is stored in LEB 0 and is only
    370modified on feature flag or similar changes, but never on file changes.
    371
    372
    373LPT Authentication
    374~~~~~~~~~~~~~~~~~~
    375
    376The location of the LPT root node on the flash is stored in the UBIFS master
    377node. Since the LPT is written and read atomically on every commit, there is
    378no need to authenticate individual nodes of the tree. It suffices to
    379protect the integrity of the full LPT by a simple hash stored in the master
    380node. Since the master node itself is authenticated, the LPTs authenticity can
    381be verified by verifying the authenticity of the master node and comparing the
    382LTP hash stored there with the hash computed from the read on-flash LPT.
    383
    384
    385Key Management
    386--------------
    387
    388For simplicity, UBIFS authentication uses a single key to compute the HMACs
    389of superblock, master, commit start and reference nodes. This key has to be
    390available on creation of the filesystem (`mkfs.ubifs`) to authenticate the
    391superblock node. Further, it has to be available on mount of the filesystem
    392to verify authenticated nodes and generate new HMACs for changes.
    393
    394UBIFS authentication is intended to operate side-by-side with UBIFS encryption
    395(fscrypt) to provide confidentiality and authenticity. Since UBIFS encryption
    396has a different approach of encryption policies per directory, there can be
    397multiple fscrypt master keys and there might be folders without encryption.
    398UBIFS authentication on the other hand has an all-or-nothing approach in the
    399sense that it either authenticates everything of the filesystem or nothing.
    400Because of this and because UBIFS authentication should also be usable without
    401encryption, it does not share the same master key with fscrypt, but manages
    402a dedicated authentication key.
    403
    404The API for providing the authentication key has yet to be defined, but the
    405key can eg. be provided by userspace through a keyring similar to the way it
    406is currently done in fscrypt. It should however be noted that the current
    407fscrypt approach has shown its flaws and the userspace API will eventually
    408change [FSCRYPT-POLICY2].
    409
    410Nevertheless, it will be possible for a user to provide a single passphrase
    411or key in userspace that covers UBIFS authentication and encryption. This can
    412be solved by the corresponding userspace tools which derive a second key for
    413authentication in addition to the derived fscrypt master key used for
    414encryption.
    415
    416To be able to check if the proper key is available on mount, the UBIFS
    417superblock node will additionally store a hash of the authentication key. This
    418approach is similar to the approach proposed for fscrypt encryption policy v2
    419[FSCRYPT-POLICY2].
    420
    421
    422Future Extensions
    423=================
    424
    425In certain cases where a vendor wants to provide an authenticated filesystem
    426image to customers, it should be possible to do so without sharing the secret
    427UBIFS authentication key. Instead, in addition the each HMAC a digital
    428signature could be stored where the vendor shares the public key alongside the
    429filesystem image. In case this filesystem has to be modified afterwards,
    430UBIFS can exchange all digital signatures with HMACs on first mount similar
    431to the way the IMA/EVM subsystem deals with such situations. The HMAC key
    432will then have to be provided beforehand in the normal way.
    433
    434
    435References
    436==========
    437
    438[CRYPTSETUP2]        https://www.saout.de/pipermail/dm-crypt/2017-November/005745.html
    439
    440[DMC-CBC-ATTACK]     https://www.jakoblell.com/blog/2013/12/22/practical-malleability-attack-against-cbc-encrypted-luks-partitions/
    441
    442[DM-INTEGRITY]       https://www.kernel.org/doc/Documentation/device-mapper/dm-integrity.rst
    443
    444[DM-VERITY]          https://www.kernel.org/doc/Documentation/device-mapper/verity.rst
    445
    446[FSCRYPT-POLICY2]    https://www.spinics.net/lists/linux-ext4/msg58710.html
    447
    448[UBIFS-WP]           http://www.linux-mtd.infradead.org/doc/ubifs_whitepaper.pdf