1 .. SPDX-License-Identifier: GPL-2.0
2
3 .. UBIFS Authentication
4 .. sigma star gmbh
5 .. 2018
6
7 ============================
8 UBIFS Authentication Support
9 ============================
10
11 Introduction
12 ============
13
14 UBIFS utilizes the fscrypt framework to provid
15 contents and file names. This prevents attacks
16 read contents of the filesystem on a single po
17 is a lost smartphone where the attacker is una
18 on the device without the filesystem decryptio
19
20 At the current state, UBIFS encryption however
21 the attacker is able to modify the filesystem
22 device afterwards. In such a scenario an attac
23 contents arbitrarily without the user noticing
24 binary to perform a malicious action when exec
25 most of the filesystem metadata of UBIFS is st
26 fairly easy to swap files and replace their co
27
28 Other full disk encryption systems like dm-cry
29 which makes such kinds of attacks more complic
30 Especially, if the attacker is given access to
31 time. For dm-crypt and other filesystems that
32 layer, the dm-integrity or dm-verity subsystem
33 can be used to get full data authentication at
34 These can also be combined with dm-crypt [CRYP
35
36 This document describes an approach to get fil
37 authentication for UBIFS. Since UBIFS uses fsc
38 name encryption, the authentication system cou
39 existing features like key derivation can be u
40 be possible to use UBIFS authentication withou
41
42
43 MTD, UBI & UBIFS
44 ----------------
45
46 On Linux, the MTD (Memory Technology Devices)
47 interface to access raw flash devices. One of
48 work on top of MTD is UBI (Unsorted Block Imag
49 for flash devices and is thus somewhat similar
50 addition, it deals with flash-specific wear-le
51 handling. UBI offers logical erase blocks (LEB
52 and maps them transparently to physical erase
53
54 UBIFS is a filesystem for raw flash which oper
55 leveling and some flash specifics are left to
56 scalability, performance and recoverability.
57
58 ::
59
60 +------------+ +*******+ +-----------+
61 | | * UBIFS * | UBI-BLOCK |
62 | JFFS/JFFS2 | +*******+ +-----------+
63 | | +----------------------
64 | | | UBI
65 +------------+ +----------------------
66 +-------------------------------------
67 | MEMORY TECHNOLOGY D
68 +-------------------------------------
69 +-----------------------------+ +-----
70 | NAND DRIVERS | |
71 +-----------------------------+ +-----
72
73 Figure 1: Linux kernel subsystems
74
75
76
77 Internally, UBIFS maintains multiple data stru
78 the flash:
79
80 - *Index*: an on-flash B+ tree where the leaf
81 - *Journal*: an additional data structure to c
82 the on-flash index and reduce flash wear.
83 - *Tree Node Cache (TNC)*: an in-memory B+ tre
84 state to avoid frequent flash reads. It is b
85 representation of the index, but contains ad
86 - *LEB property tree (LPT)*: an on-flash B+ tr
87 UBI LEB.
88
89 In the remainder of this section we will cover
90 structures in more detail. The TNC is of less
91 persisted onto the flash directly. More detail
92 [UBIFS-WP].
93
94
95 UBIFS Index & Tree Node Cache
96 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
97
98 Basic on-flash UBIFS entities are called *node
99 of nodes. Eg. data nodes (``struct ubifs_data_
100 contents or inode nodes (``struct ubifs_ino_no
101 Almost all types of nodes share a common heade
102 information like node type, node length, a seq
103 ``fs/ubifs/ubifs-media.h`` in kernel source).
104 and some less important node types like paddin
105 unusable content at the end of LEBs.
106
107 To avoid re-writing the whole B+ tree on every
108 as *wandering tree*, where only the changed no
109 versions of them are obsoleted without erasing
110 the index is not stored in a single place on t
111 and there are obsolete parts on the flash as l
112 not reused by UBIFS. To find the most recent v
113 a special node called *master node* into UBI L
114 most recent root node of the UBIFS index. For
115 is additionally duplicated to LEB 2. Mounting
116 LEB 1 and 2 to get the current master node and
117 the most recent on-flash index.
118
119 The TNC is the in-memory representation of the
120 additional runtime attributes per node which a
121 a dirty-flag which marks nodes that have to be
122 index is written onto the flash. The TNC acts
123 modifications of the on-flash index are done t
124 the TNC does not have to mirror the full index
125 it from flash whenever needed. A *commit* is t
126 on-flash filesystem structures like the index.
127 marked as dirty are written to the flash to up
128
129
130 Journal
131 ~~~~~~~
132
133 To avoid wearing out the flash, the index is o
134 certain conditions are met (eg. ``fsync(2)``).
135 any changes (in form of inode nodes, data node
136 of the index. During mount, the journal is rea
137 onto the TNC (which will be created on-demand
138
139 UBIFS reserves a bunch of LEBs just for the jo
140 amount of log area LEBs is configured on files
141 ``mkfs.ubifs``) and stored in the superblock n
142 two types of nodes: *reference nodes* and *com
143 node is written whenever an index commit is pe
144 written on every journal update. Each referenc
145 other nodes (inode nodes, data nodes etc.) on
146 journal entry. These nodes are called *buds* a
147 changes including their data.
148
149 The log area is maintained as a ring. Whenever
150 a commit is initiated. This also writes a comm
151 mount, UBIFS will seek for the most recent com
152 every reference node after that. Every referen
153 node will be ignored as they are already part
154
155 When writing a journal entry, UBIFS first ensu
156 available to write the reference node and buds
157 reference node is written and afterwards the b
158 On replay, UBIFS will record every reference n
159 the referenced LEBs to discover the buds. If t
160 UBIFS will attempt to recover them by re-readi
161 done for the last referenced LEB of the journa
162 because of a power cut. If the recovery fails,
163 for every other LEB will directly cause UBIFS
164
165 ::
166
167 | ---- LOG AREA ---- | ---------
168
169 -----+------+-----+--------+---- ---
170 \ | | | | / /
171 / CS | REF | REF | | \ \ DE
172 \ | | | | / /
173 ----+------+-----+--------+--- ----
174 | | ^
175 | | |
176 +------------------------+
177 |
178 +----------------------
179
180
181 Figure 2: UBIFS flash layout o
182 (CS) and reference n
183 containing their bud
184
185
186 LEB Property Tree/Table
187 ~~~~~~~~~~~~~~~~~~~~~~~
188
189 The LEB property tree is used to store per-LEB
190 LEB type and amount of free and *dirty* (old,
191 the LEB. The type is important, because UBIFS
192 nodes on a single LEB and thus each LEB has a
193 useful for free space calculations. See [UBIFS
194
195 The LEB property tree again is a B+ tree, but
196 index. Due to its smaller size it is always wr
197 commit. Thus, saving the LPT is an atomic oper
198
199
200 .. [1] Since LEBs can only be appended and nev
201 difference between free space ie. the remai
202 written to without erasing it and previousl
203 but can't be overwritten without erasing th
204
205
206 UBIFS Authentication
207 ====================
208
209 This chapter introduces UBIFS authentication w
210 the authenticity and integrity of metadata and
211
212
213 Threat Model
214 ------------
215
216 UBIFS authentication enables detection of offl
217 does not prevent it, it enables (trusted) code
218 authenticity of on-flash file contents and fil
219 attacks where file contents are swapped.
220
221 UBIFS authentication will not protect against
222 Ie. an attacker can still dump the flash and r
223 detection. It will also not protect against pa
224 index commits. That means that an attacker is
225 This is possible because UBIFS does not immedi
226 versions of the index tree or the journal, but
227 and garbage collection erases them at a later
228 erasing parts of the current tree and restorin
229 the flash and have not yet been erased. This i
230 will always write a new version of the index r
231 without overwriting the previous version. This
232 wear-leveling operations of UBI which copies c
233 eraseblock to another and does not atomically
234
235 UBIFS authentication does not cover attacks wh
236 execute code on the device after the authentic
237 Additional measures like secure boot and trust
238 ensure that only trusted code is executed on a
239
240
241 Authentication
242 --------------
243
244 To be able to fully trust data read from flash
245 stored on flash are authenticated. That is:
246
247 - The index which includes file contents, file
248 attributes, file length etc.
249 - The journal which also contains file content
250 to the filesystem
251 - The LPT which stores UBI LEB metadata which
252
253
254 Index Authentication
255 ~~~~~~~~~~~~~~~~~~~~
256
257 Through UBIFS' concept of a wandering tree, it
258 updating and persisting changed parts from lea
259 of the full B+ tree. This enables us to augmen
260 with a hash over each node's child nodes. As a
261 a Merkle tree. Since the leaf nodes of the ind
262 data, the hashes of their parent index nodes t
263 and file metadata. When a file changes, the UB
264 from the leaf nodes up to the root node includ
265 can be hooked to recompute the hash only for e
266 Whenever a file is read, UBIFS can verify the
267 the root node to ensure the node's integrity.
268
269 To ensure the authenticity of the whole index,
270 keyed hash (HMAC) over its own contents and a
271 tree. As mentioned above, the master node is a
272 the index is persisted (ie. on index commit).
273
274 Using this approach only UBIFS index nodes and
275 include a hash. All other types of nodes will
276 the storage overhead which is precious for use
277 devices).
278
279 ::
280
281 +---------------+
282 | Master Node |
283 | (hash) |
284 +---------------+
285 |
286 v
287 +-----------------
288 | Index Node #1
289 |
290 | branch0 branch
291 | (hash) (hash)
292 +-----------------
293 | ... | (
294 | |
295 +-------+ +---
296 |
297 v
298 +-------------------+ +-----
299 | Index Node #2 | | Ind
300 | | |
301 | branch0 branchn | | bran
302 | (hash) (hash) | | (has
303 +-------------------+ +-----
304 | ... |
305 v v
306 +-----------+ +--------
307 | Data Node | | INO Nod
308 +-----------+ +--------
309
310
311 Figure 3: Coverage areas of index n
312
313
314
315 The most important part for robustness and pow
316 persist the hash and file contents. Here the e
317 changed nodes are persisted is already designe
318 UBIFS can safely recover if a power-cut occurs
319 hashes to index nodes does not change this sin
320 atomically together with its respective node.
321
322
323 Journal Authentication
324 ~~~~~~~~~~~~~~~~~~~~~~
325
326 The journal is authenticated too. Since the jo
327 it is necessary to also add authentication inf
328 journal so that in case of a powercut not too
329 This is done by creating a continuous hash beg
330 over the previous reference nodes, the current
331 nodes. From time to time whenever it is suitab
332 between the bud nodes. This new node type cont
333 of the hash chain. That way a journal can be a
334 authentication node. The tail of the journal w
335 node cannot be authenticated and is skipped du
336
337 We get this picture for journal authentication
338
339 ,,,,,,,,
340 ,......,..................................
341 ,. CS , hash1.----.
342 ,. | , . |hmac
343 ,. v , . v
344 ,.REF#0,-> bud -> bud -> bud.-> auth -> bu
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
359 Since the hash also includes the reference nod
360 skip any journal heads for replay. An attacker
361 reference nodes from the end of the journal, e
362 filesystem at maximum back to the last commit.
363
364 The location of the log area is stored in the
365 node is authenticated with a HMAC as described
366 tamper with that without detection. The size o
367 the filesystem is created using `mkfs.ubifs` a
368 To avoid tampering with this and other values
369 the superblock struct. The superblock node is
370 modified on feature flag or similar changes, b
371
372
373 LPT Authentication
374 ~~~~~~~~~~~~~~~~~~
375
376 The location of the LPT root node on the flash
377 node. Since the LPT is written and read atomic
378 no need to authenticate individual nodes of th
379 protect the integrity of the full LPT by a sim
380 node. Since the master node itself is authenti
381 be verified by verifying the authenticity of t
382 LTP hash stored there with the hash computed f
383
384
385 Key Management
386 --------------
387
388 For simplicity, UBIFS authentication uses a si
389 of superblock, master, commit start and refere
390 available on creation of the filesystem (`mkfs
391 superblock node. Further, it has to be availab
392 to verify authenticated nodes and generate new
393
394 UBIFS authentication is intended to operate si
395 (fscrypt) to provide confidentiality and authe
396 has a different approach of encryption policie
397 multiple fscrypt master keys and there might b
398 UBIFS authentication on the other hand has an
399 sense that it either authenticates everything
400 Because of this and because UBIFS authenticati
401 encryption, it does not share the same master
402 a dedicated authentication key.
403
404 The API for providing the authentication key h
405 key can eg. be provided by userspace through a
406 is currently done in fscrypt. It should howeve
407 fscrypt approach has shown its flaws and the u
408 change [FSCRYPT-POLICY2].
409
410 Nevertheless, it will be possible for a user t
411 or key in userspace that covers UBIFS authenti
412 be solved by the corresponding userspace tools
413 authentication in addition to the derived fscr
414 encryption.
415
416 To be able to check if the proper key is avail
417 superblock node will additionally store a hash
418 approach is similar to the approach proposed f
419 [FSCRYPT-POLICY2].
420
421
422 Future Extensions
423 =================
424
425 In certain cases where a vendor wants to provi
426 image to customers, it should be possible to d
427 UBIFS authentication key. Instead, in addition
428 signature could be stored where the vendor sha
429 filesystem image. In case this filesystem has
430 UBIFS can exchange all digital signatures with
431 to the way the IMA/EVM subsystem deals with su
432 will then have to be provided beforehand in th
433
434
435 References
436 ==========
437
438 [CRYPTSETUP2] https://www.saout.de/pipe
439
440 [DMC-CBC-ATTACK] https://www.jakoblell.com
441
442 [DM-INTEGRITY] https://www.kernel.org/do
443
444 [DM-VERITY] https://www.kernel.org/do
445
446 [FSCRYPT-POLICY2] https://www.spinics.net/l
447
448 [UBIFS-WP] http://www.linux-mtd.infr
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.