1 /*
2 * encrypted_files.c --- save information about encrypted files
3 *
4 * Copyright 2019 Google LLC
5 *
6 * %Begin-Header%
7 * This file may be redistributed under the terms of the GNU Public
8 * License.
9 * %End-Header%
10 */
11
12 /*
13 * e2fsck pass 1 (inode table scan) creates a map from inode number to
14 * encryption policy for all encrypted inodes. But it's optimized so that the
15 * full xattrs aren't saved but rather only 32-bit "policy IDs", since usually
16 * many inodes share the same encryption policy. This requires also maintaining
17 * a second map, from policy to policy ID. See add_encrypted_file().
18 *
19 * We also use run-length encoding to save memory when many adjacent inodes
20 * share the same encryption policy, which is often the case too.
21 *
22 * e2fsck pass 2 (directory structure check) uses the inode => policy ID map to
23 * verify that all regular files, directories, and symlinks in encrypted
24 * directories use the directory's encryption policy.
25 */
26
27 #include "config.h"
28
29 #include "e2fsck.h"
30 #include "problem.h"
31 #include "ext2fs/rbtree.h"
32
33 #define FSCRYPT_KEY_DESCRIPTOR_SIZE 8
34 #define FSCRYPT_KEY_IDENTIFIER_SIZE 16
35 #define FS_KEY_DERIVATION_NONCE_SIZE 16
36
37 struct fscrypt_context_v1 {
38 __u8 version;
39 __u8 contents_encryption_mode;
40 __u8 filenames_encryption_mode;
41 __u8 flags;
42 __u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
43 __u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
44 };
45
46 struct fscrypt_context_v2 {
47 __u8 version;
48 __u8 contents_encryption_mode;
49 __u8 filenames_encryption_mode;
50 __u8 flags;
51 __u8 __reserved[4];
52 __u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
53 __u8 nonce[FS_KEY_DERIVATION_NONCE_SIZE];
54 };
55
56 /* On-disk format of encryption xattr */
57 union fscrypt_context {
58 __u8 version;
59 struct fscrypt_context_v1 v1;
60 struct fscrypt_context_v2 v2;
61 };
62
63 struct fscrypt_policy_v1 {
64 __u8 version;
65 __u8 contents_encryption_mode;
66 __u8 filenames_encryption_mode;
67 __u8 flags;
68 __u8 master_key_descriptor[FSCRYPT_KEY_DESCRIPTOR_SIZE];
69 };
70
71 struct fscrypt_policy_v2 {
72 __u8 version;
73 __u8 contents_encryption_mode;
74 __u8 filenames_encryption_mode;
75 __u8 flags;
76 __u8 __reserved[4];
77 __u8 master_key_identifier[FSCRYPT_KEY_IDENTIFIER_SIZE];
78 };
79
80 /* The encryption "policy" is the fscrypt_context excluding the nonce. */
81 union fscrypt_policy {
82 __u8 version;
83 struct fscrypt_policy_v1 v1;
84 struct fscrypt_policy_v2 v2;
85 };
86
87 /* A range of inodes which share the same encryption policy */
88 struct encrypted_file_range {
89 ext2_ino_t first_ino;
90 ext2_ino_t last_ino;
91 __u32 policy_id;
92 };
93
94 /* Information about the encrypted files which have been seen so far */
95 struct encrypted_file_info {
96 /*
97 * Map from inode number to encryption policy ID, implemented as a
98 * sorted array of inode ranges, each of which shares the same policy.
99 * Inodes are added in order of increasing inode number.
100 *
101 * Freed after pass 2.
102 */
103 struct encrypted_file_range *file_ranges;
104 size_t file_ranges_count;
105 size_t file_ranges_capacity;
106
107 /*
108 * Map from encryption policy to encryption policy ID, for the unique
109 * encryption policies that have been seen so far. next_policy_id is
110 * the next available ID, starting at 0.
111 *
112 * Freed after pass 1.
113 */
114 struct rb_root policies;
115 __u32 next_policy_id;
116 };
117
118 /* Entry in encrypted_file_info::policies */
119 struct policy_map_entry {
120 union fscrypt_policy policy;
121 __u32 policy_id;
122 struct rb_node node;
123 };
124
cmp_fscrypt_policies(e2fsck_t ctx,const union fscrypt_policy * a,const union fscrypt_policy * b)125 static int cmp_fscrypt_policies(e2fsck_t ctx, const union fscrypt_policy *a,
126 const union fscrypt_policy *b)
127 {
128 if (a->version != b->version)
129 return (int)a->version - (int)b->version;
130
131 switch (a->version) {
132 case 1:
133 return memcmp(a, b, sizeof(a->v1));
134 case 2:
135 return memcmp(a, b, sizeof(a->v2));
136 }
137 fatal_error(ctx, "Unhandled encryption policy version");
138 return 0;
139 }
140
141 /* Read an inode's encryption xattr. */
read_encryption_xattr(e2fsck_t ctx,ext2_ino_t ino,void ** value,size_t * value_len)142 static errcode_t read_encryption_xattr(e2fsck_t ctx, ext2_ino_t ino,
143 void **value, size_t *value_len)
144 {
145 struct ext2_xattr_handle *h;
146 errcode_t retval;
147
148 retval = ext2fs_xattrs_open(ctx->fs, ino, &h);
149 if (retval)
150 return retval;
151
152 retval = ext2fs_xattrs_read(h);
153 if (retval == 0)
154 retval = ext2fs_xattr_get(h, "c", value, value_len);
155
156 ext2fs_xattrs_close(&h);
157 return retval;
158 }
159
160 /*
161 * Convert an fscrypt_context to an fscrypt_policy. Returns 0,
162 * CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
163 */
fscrypt_context_to_policy(const void * xattr,size_t xattr_size,union fscrypt_policy * policy_u)164 static __u32 fscrypt_context_to_policy(const void *xattr, size_t xattr_size,
165 union fscrypt_policy *policy_u)
166 {
167 const union fscrypt_context *ctx_u = xattr;
168
169 if (xattr_size < 1)
170 return CORRUPT_ENCRYPTION_POLICY;
171 switch (ctx_u->version) {
172 case 0:
173 return CORRUPT_ENCRYPTION_POLICY;
174 case 1: {
175 struct fscrypt_policy_v1 *policy = &policy_u->v1;
176 const struct fscrypt_context_v1 *ctx = &ctx_u->v1;
177
178 if (xattr_size != sizeof(*ctx))
179 return CORRUPT_ENCRYPTION_POLICY;
180 policy->version = ctx->version;
181 policy->contents_encryption_mode =
182 ctx->contents_encryption_mode;
183 policy->filenames_encryption_mode =
184 ctx->filenames_encryption_mode;
185 policy->flags = ctx->flags;
186 memcpy(policy->master_key_descriptor,
187 ctx->master_key_descriptor,
188 sizeof(policy->master_key_descriptor));
189 return 0;
190 }
191 case 2: {
192 struct fscrypt_policy_v2 *policy = &policy_u->v2;
193 const struct fscrypt_context_v2 *ctx = &ctx_u->v2;
194
195 if (xattr_size != sizeof(*ctx))
196 return CORRUPT_ENCRYPTION_POLICY;
197 policy->version = ctx->version;
198 policy->contents_encryption_mode =
199 ctx->contents_encryption_mode;
200 policy->filenames_encryption_mode =
201 ctx->filenames_encryption_mode;
202 policy->flags = ctx->flags;
203 memcpy(policy->__reserved, ctx->__reserved,
204 sizeof(policy->__reserved));
205 memcpy(policy->master_key_identifier,
206 ctx->master_key_identifier,
207 sizeof(policy->master_key_identifier));
208 return 0;
209 }
210 }
211 return UNRECOGNIZED_ENCRYPTION_POLICY;
212 }
213
214 /*
215 * Read an inode's encryption xattr and get/allocate its encryption policy ID,
216 * or alternatively use one of the special IDs NO_ENCRYPTION_POLICY,
217 * CORRUPT_ENCRYPTION_POLICY, or UNRECOGNIZED_ENCRYPTION_POLICY.
218 *
219 * Returns nonzero only if out of memory.
220 */
get_encryption_policy_id(e2fsck_t ctx,ext2_ino_t ino,__u32 * policy_id_ret)221 static errcode_t get_encryption_policy_id(e2fsck_t ctx, ext2_ino_t ino,
222 __u32 *policy_id_ret)
223 {
224 struct encrypted_file_info *info = ctx->encrypted_files;
225 struct rb_node **new = &info->policies.rb_node;
226 struct rb_node *parent = NULL;
227 void *xattr;
228 size_t xattr_size;
229 union fscrypt_policy policy;
230 __u32 policy_id;
231 struct policy_map_entry *entry;
232 errcode_t retval;
233
234 retval = read_encryption_xattr(ctx, ino, &xattr, &xattr_size);
235 if (retval == EXT2_ET_NO_MEMORY)
236 return retval;
237 if (retval) {
238 *policy_id_ret = NO_ENCRYPTION_POLICY;
239 return 0;
240 }
241
242 /* Translate the xattr to an fscrypt_policy, if possible. */
243 policy_id = fscrypt_context_to_policy(xattr, xattr_size, &policy);
244 ext2fs_free_mem(&xattr);
245 if (policy_id != 0)
246 goto out;
247
248 /* Check if the policy was already seen. */
249 while (*new) {
250 int res;
251
252 parent = *new;
253 entry = ext2fs_rb_entry(parent, struct policy_map_entry, node);
254 res = cmp_fscrypt_policies(ctx, &policy, &entry->policy);
255 if (res < 0) {
256 new = &parent->rb_left;
257 } else if (res > 0) {
258 new = &parent->rb_right;
259 } else {
260 /* Policy already seen. Use existing ID. */
261 policy_id = entry->policy_id;
262 goto out;
263 }
264 }
265
266 /* First time seeing this policy. Allocate a new policy ID. */
267 retval = ext2fs_get_mem(sizeof(*entry), &entry);
268 if (retval)
269 goto out;
270 policy_id = info->next_policy_id++;
271 entry->policy_id = policy_id;
272 entry->policy = policy;
273 ext2fs_rb_link_node(&entry->node, parent, new);
274 ext2fs_rb_insert_color(&entry->node, &info->policies);
275 out:
276 *policy_id_ret = policy_id;
277 return retval;
278 }
279
handle_nomem(e2fsck_t ctx,struct problem_context * pctx,size_t size_needed)280 static int handle_nomem(e2fsck_t ctx, struct problem_context *pctx,
281 size_t size_needed)
282 {
283 pctx->num = size_needed;
284 fix_problem(ctx, PR_1_ALLOCATE_ENCRYPTED_INODE_LIST, pctx);
285 /* Should never get here */
286 ctx->flags |= E2F_FLAG_ABORT;
287 return 0;
288 }
289
append_ino_and_policy_id(e2fsck_t ctx,struct problem_context * pctx,ext2_ino_t ino,__u32 policy_id)290 static int append_ino_and_policy_id(e2fsck_t ctx, struct problem_context *pctx,
291 ext2_ino_t ino, __u32 policy_id)
292 {
293 struct encrypted_file_info *info = ctx->encrypted_files;
294 struct encrypted_file_range *range;
295
296 /* See if we can just extend the last range. */
297 if (info->file_ranges_count > 0) {
298 range = &info->file_ranges[info->file_ranges_count - 1];
299
300 if (ino <= range->last_ino) {
301 /* Should never get here */
302 fatal_error(ctx,
303 "Encrypted inodes processed out of order");
304 }
305
306 if (ino == range->last_ino + 1 &&
307 policy_id == range->policy_id) {
308 range->last_ino++;
309 return 0;
310 }
311 }
312 /* Nope, a new range is needed. */
313
314 if (info->file_ranges_count == info->file_ranges_capacity) {
315 /* Double the capacity by default. */
316 size_t new_capacity = info->file_ranges_capacity * 2;
317
318 /* ... but go from 0 to 128 right away. */
319 if (new_capacity < 128)
320 new_capacity = 128;
321
322 /* We won't need more than the filesystem's inode count. */
323 if (new_capacity > ctx->fs->super->s_inodes_count)
324 new_capacity = ctx->fs->super->s_inodes_count;
325
326 /* To be safe, ensure the capacity really increases. */
327 if (new_capacity < info->file_ranges_capacity + 1)
328 new_capacity = info->file_ranges_capacity + 1;
329
330 if (ext2fs_resize_mem(info->file_ranges_capacity *
331 sizeof(*range),
332 new_capacity * sizeof(*range),
333 &info->file_ranges) != 0)
334 return handle_nomem(ctx, pctx,
335 new_capacity * sizeof(*range));
336
337 info->file_ranges_capacity = new_capacity;
338 }
339 range = &info->file_ranges[info->file_ranges_count++];
340 range->first_ino = ino;
341 range->last_ino = ino;
342 range->policy_id = policy_id;
343 return 0;
344 }
345
346 /*
347 * Handle an inode that has EXT4_ENCRYPT_FL set during pass 1. Normally this
348 * just finds the unique ID that identifies the inode's encryption policy
349 * (allocating a new ID if needed), and adds the inode number and its policy ID
350 * to the encrypted_file_info so that it's available in pass 2.
351 *
352 * But this also handles:
353 * - If the inode doesn't have an encryption xattr at all, offer to clear the
354 * encrypt flag.
355 * - If the encryption xattr is clearly corrupt, tell the caller that the whole
356 * inode should be cleared.
357 * - To be future-proof: if the encryption xattr has an unrecognized version
358 * number, it *might* be valid, so we don't consider it invalid. But we can't
359 * do much with it, so give all such policies the same ID,
360 * UNRECOGNIZED_ENCRYPTION_POLICY.
361 *
362 * Returns -1 if the inode should be cleared, otherwise 0.
363 */
add_encrypted_file(e2fsck_t ctx,struct problem_context * pctx)364 int add_encrypted_file(e2fsck_t ctx, struct problem_context *pctx)
365 {
366 struct encrypted_file_info *info = ctx->encrypted_files;
367 ext2_ino_t ino = pctx->ino;
368 __u32 policy_id;
369
370 /* Allocate the encrypted_file_info if needed. */
371 if (info == NULL) {
372 if (ext2fs_get_memzero(sizeof(*info), &info) != 0)
373 return handle_nomem(ctx, pctx, sizeof(*info));
374 ctx->encrypted_files = info;
375 }
376
377 /* Get a unique ID for this inode's encryption policy. */
378 if (get_encryption_policy_id(ctx, ino, &policy_id) != 0)
379 return handle_nomem(ctx, pctx, 0 /* unknown size */);
380 if (policy_id == NO_ENCRYPTION_POLICY) {
381 if (fix_problem(ctx, PR_1_MISSING_ENCRYPTION_XATTR, pctx)) {
382 pctx->inode->i_flags &= ~EXT4_ENCRYPT_FL;
383 e2fsck_write_inode(ctx, ino, pctx->inode, "pass1");
384 }
385 return 0;
386 } else if (policy_id == CORRUPT_ENCRYPTION_POLICY) {
387 if (fix_problem(ctx, PR_1_CORRUPT_ENCRYPTION_XATTR, pctx))
388 return -1;
389 return 0;
390 }
391
392 /* Store this ino => policy_id mapping in the encrypted_file_info. */
393 return append_ino_and_policy_id(ctx, pctx, ino, policy_id);
394 }
395
396 /*
397 * Find the ID of an inode's encryption policy, using the information saved
398 * earlier.
399 *
400 * If the inode is encrypted, returns the policy ID or
401 * UNRECOGNIZED_ENCRYPTION_POLICY. Else, returns NO_ENCRYPTION_POLICY.
402 */
find_encryption_policy(e2fsck_t ctx,ext2_ino_t ino)403 __u32 find_encryption_policy(e2fsck_t ctx, ext2_ino_t ino)
404 {
405 const struct encrypted_file_info *info = ctx->encrypted_files;
406 size_t l, r;
407
408 if (info == NULL)
409 return NO_ENCRYPTION_POLICY;
410 l = 0;
411 r = info->file_ranges_count;
412 while (l < r) {
413 size_t m = l + (r - l) / 2;
414 const struct encrypted_file_range *range =
415 &info->file_ranges[m];
416
417 if (ino < range->first_ino)
418 r = m;
419 else if (ino > range->last_ino)
420 l = m + 1;
421 else
422 return range->policy_id;
423 }
424 return NO_ENCRYPTION_POLICY;
425 }
426
427 /* Destroy ctx->encrypted_files->policies */
destroy_encryption_policy_map(e2fsck_t ctx)428 void destroy_encryption_policy_map(e2fsck_t ctx)
429 {
430 struct encrypted_file_info *info = ctx->encrypted_files;
431
432 if (info) {
433 struct rb_root *policies = &info->policies;
434
435 while (!ext2fs_rb_empty_root(policies)) {
436 struct policy_map_entry *entry;
437
438 entry = ext2fs_rb_entry(policies->rb_node,
439 struct policy_map_entry, node);
440 ext2fs_rb_erase(&entry->node, policies);
441 ext2fs_free_mem(&entry);
442 }
443 info->next_policy_id = 0;
444 }
445 }
446
447 /* Destroy ctx->encrypted_files */
destroy_encrypted_file_info(e2fsck_t ctx)448 void destroy_encrypted_file_info(e2fsck_t ctx)
449 {
450 struct encrypted_file_info *info = ctx->encrypted_files;
451
452 if (info) {
453 destroy_encryption_policy_map(ctx);
454 ext2fs_free_mem(&info->file_ranges);
455 ext2fs_free_mem(&info);
456 ctx->encrypted_files = NULL;
457 }
458 }
459