e2fsck/encrypted_files.c

   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
 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. */
 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  */
 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  */
 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
 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
 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  */
 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  */
 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 */
 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 */
 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 }