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