1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * Opening fs-verity files 4 * 5 * Copyright 2019 Google LLC 6 */ 7 8 #include "fsverity_private.h" 9 10 #include <linux/mm.h> 11 #include <linux/slab.h> 12 13 static struct kmem_cache *fsverity_info_cachep; 14 15 /** 16 * fsverity_init_merkle_tree_params() - initialize Merkle tree parameters 17 * @params: the parameters struct to initialize 18 * @inode: the inode for which the Merkle tree is being built 19 * @hash_algorithm: number of hash algorithm to use 20 * @log_blocksize: log base 2 of block size to use 21 * @salt: pointer to salt (optional) 22 * @salt_size: size of salt, possibly 0 23 * 24 * Validate the hash algorithm and block size, then compute the tree topology 25 * (num levels, num blocks in each level, etc.) and initialize @params. 26 * 27 * Return: 0 on success, -errno on failure 28 */ 29 int fsverity_init_merkle_tree_params(struct merkle_tree_params *params, 30 const struct inode *inode, 31 unsigned int hash_algorithm, 32 unsigned int log_blocksize, 33 const u8 *salt, size_t salt_size) 34 { 35 const struct fsverity_hash_alg *hash_alg; 36 int err; 37 u64 blocks; 38 u64 blocks_in_level[FS_VERITY_MAX_LEVELS]; 39 u64 offset; 40 int level; 41 42 memset(params, 0, sizeof(*params)); 43 44 hash_alg = fsverity_get_hash_alg(inode, hash_algorithm); 45 if (IS_ERR(hash_alg)) 46 return PTR_ERR(hash_alg); 47 params->hash_alg = hash_alg; 48 params->digest_size = hash_alg->digest_size; 49 50 params->hashstate = fsverity_prepare_hash_state(hash_alg, salt, 51 salt_size); 52 if (IS_ERR(params->hashstate)) { 53 err = PTR_ERR(params->hashstate); 54 params->hashstate = NULL; 55 fsverity_err(inode, "Error %d preparing hash state", err); 56 goto out_err; 57 } 58 59 /* 60 * fs/verity/ directly assumes that the Merkle tree block size is a 61 * power of 2 less than or equal to PAGE_SIZE. Another restriction 62 * arises from the interaction between fs/verity/ and the filesystems 63 * themselves: filesystems expect to be able to verify a single 64 * filesystem block of data at a time. Therefore, the Merkle tree block 65 * size must also be less than or equal to the filesystem block size. 66 * 67 * The above are the only hard limitations, so in theory the Merkle tree 68 * block size could be as small as twice the digest size. However, 69 * that's not useful, and it would result in some unusually deep and 70 * large Merkle trees. So we currently require that the Merkle tree 71 * block size be at least 1024 bytes. That's small enough to test the 72 * sub-page block case on systems with 4K pages, but not too small. 73 */ 74 if (log_blocksize < 10 || log_blocksize > PAGE_SHIFT || 75 log_blocksize > inode->i_blkbits) { 76 fsverity_warn(inode, "Unsupported log_blocksize: %u", 77 log_blocksize); 78 err = -EINVAL; 79 goto out_err; 80 } 81 params->log_blocksize = log_blocksize; 82 params->block_size = 1 << log_blocksize; 83 params->log_blocks_per_page = PAGE_SHIFT - log_blocksize; 84 params->blocks_per_page = 1 << params->log_blocks_per_page; 85 86 if (WARN_ON_ONCE(!is_power_of_2(params->digest_size))) { 87 err = -EINVAL; 88 goto out_err; 89 } 90 if (params->block_size < 2 * params->digest_size) { 91 fsverity_warn(inode, 92 "Merkle tree block size (%u) too small for hash algorithm \"%s\"", 93 params->block_size, hash_alg->name); 94 err = -EINVAL; 95 goto out_err; 96 } 97 params->log_digestsize = ilog2(params->digest_size); 98 params->log_arity = log_blocksize - params->log_digestsize; 99 params->hashes_per_block = 1 << params->log_arity; 100 101 /* 102 * Compute the number of levels in the Merkle tree and create a map from 103 * level to the starting block of that level. Level 'num_levels - 1' is 104 * the root and is stored first. Level 0 is the level directly "above" 105 * the data blocks and is stored last. 106 */ 107 108 /* Compute number of levels and the number of blocks in each level */ 109 blocks = ((u64)inode->i_size + params->block_size - 1) >> log_blocksize; 110 while (blocks > 1) { 111 if (params->num_levels >= FS_VERITY_MAX_LEVELS) { 112 fsverity_err(inode, "Too many levels in Merkle tree"); 113 err = -EFBIG; 114 goto out_err; 115 } 116 blocks = (blocks + params->hashes_per_block - 1) >> 117 params->log_arity; 118 blocks_in_level[params->num_levels++] = blocks; 119 } 120 121 /* Compute the starting block of each level */ 122 offset = 0; 123 for (level = (int)params->num_levels - 1; level >= 0; level--) { 124 params->level_start[level] = offset; 125 offset += blocks_in_level[level]; 126 } 127 128 /* 129 * With block_size != PAGE_SIZE, an in-memory bitmap will need to be 130 * allocated to track the "verified" status of hash blocks. Don't allow 131 * this bitmap to get too large. For now, limit it to 1 MiB, which 132 * limits the file size to about 4.4 TB with SHA-256 and 4K blocks. 133 * 134 * Together with the fact that the data, and thus also the Merkle tree, 135 * cannot have more than ULONG_MAX pages, this implies that hash block 136 * indices can always fit in an 'unsigned long'. But to be safe, we 137 * explicitly check for that too. Note, this is only for hash block 138 * indices; data block indices might not fit in an 'unsigned long'. 139 */ 140 if ((params->block_size != PAGE_SIZE && offset > 1 << 23) || 141 offset > ULONG_MAX) { 142 fsverity_err(inode, "Too many blocks in Merkle tree"); 143 err = -EFBIG; 144 goto out_err; 145 } 146 147 params->tree_size = offset << log_blocksize; 148 params->tree_pages = PAGE_ALIGN(params->tree_size) >> PAGE_SHIFT; 149 return 0; 150 151 out_err: 152 kfree(params->hashstate); 153 memset(params, 0, sizeof(*params)); 154 return err; 155 } 156 157 /* 158 * Compute the file digest by hashing the fsverity_descriptor excluding the 159 * builtin signature and with the sig_size field set to 0. 160 */ 161 static int compute_file_digest(const struct fsverity_hash_alg *hash_alg, 162 struct fsverity_descriptor *desc, 163 u8 *file_digest) 164 { 165 __le32 sig_size = desc->sig_size; 166 int err; 167 168 desc->sig_size = 0; 169 err = fsverity_hash_buffer(hash_alg, desc, sizeof(*desc), file_digest); 170 desc->sig_size = sig_size; 171 172 return err; 173 } 174 175 /* 176 * Create a new fsverity_info from the given fsverity_descriptor (with optional 177 * appended builtin signature), and check the signature if present. The 178 * fsverity_descriptor must have already undergone basic validation. 179 */ 180 struct fsverity_info *fsverity_create_info(const struct inode *inode, 181 struct fsverity_descriptor *desc) 182 { 183 struct fsverity_info *vi; 184 int err; 185 186 vi = kmem_cache_zalloc(fsverity_info_cachep, GFP_KERNEL); 187 if (!vi) 188 return ERR_PTR(-ENOMEM); 189 vi->inode = inode; 190 191 err = fsverity_init_merkle_tree_params(&vi->tree_params, inode, 192 desc->hash_algorithm, 193 desc->log_blocksize, 194 desc->salt, desc->salt_size); 195 if (err) { 196 fsverity_err(inode, 197 "Error %d initializing Merkle tree parameters", 198 err); 199 goto fail; 200 } 201 202 memcpy(vi->root_hash, desc->root_hash, vi->tree_params.digest_size); 203 204 err = compute_file_digest(vi->tree_params.hash_alg, desc, 205 vi->file_digest); 206 if (err) { 207 fsverity_err(inode, "Error %d computing file digest", err); 208 goto fail; 209 } 210 211 err = fsverity_verify_signature(vi, desc->signature, 212 le32_to_cpu(desc->sig_size)); 213 if (err) 214 goto fail; 215 216 if (vi->tree_params.block_size != PAGE_SIZE) { 217 /* 218 * When the Merkle tree block size and page size differ, we use 219 * a bitmap to keep track of which hash blocks have been 220 * verified. This bitmap must contain one bit per hash block, 221 * including alignment to a page boundary at the end. 222 * 223 * Eventually, to support extremely large files in an efficient 224 * way, it might be necessary to make pages of this bitmap 225 * reclaimable. But for now, simply allocating the whole bitmap 226 * is a simple solution that works well on the files on which 227 * fsverity is realistically used. E.g., with SHA-256 and 4K 228 * blocks, a 100MB file only needs a 24-byte bitmap, and the 229 * bitmap for any file under 17GB fits in a 4K page. 230 */ 231 unsigned long num_bits = 232 vi->tree_params.tree_pages << 233 vi->tree_params.log_blocks_per_page; 234 235 vi->hash_block_verified = kvcalloc(BITS_TO_LONGS(num_bits), 236 sizeof(unsigned long), 237 GFP_KERNEL); 238 if (!vi->hash_block_verified) { 239 err = -ENOMEM; 240 goto fail; 241 } 242 spin_lock_init(&vi->hash_page_init_lock); 243 } 244 245 return vi; 246 247 fail: 248 fsverity_free_info(vi); 249 return ERR_PTR(err); 250 } 251 252 void fsverity_set_info(struct inode *inode, struct fsverity_info *vi) 253 { 254 /* 255 * Multiple tasks may race to set ->i_verity_info, so use 256 * cmpxchg_release(). This pairs with the smp_load_acquire() in 257 * fsverity_get_info(). I.e., here we publish ->i_verity_info with a 258 * RELEASE barrier so that other tasks can ACQUIRE it. 259 */ 260 if (cmpxchg_release(&inode->i_verity_info, NULL, vi) != NULL) { 261 /* Lost the race, so free the fsverity_info we allocated. */ 262 fsverity_free_info(vi); 263 /* 264 * Afterwards, the caller may access ->i_verity_info directly, 265 * so make sure to ACQUIRE the winning fsverity_info. 266 */ 267 (void)fsverity_get_info(inode); 268 } 269 } 270 271 void fsverity_free_info(struct fsverity_info *vi) 272 { 273 if (!vi) 274 return; 275 kfree(vi->tree_params.hashstate); 276 kvfree(vi->hash_block_verified); 277 kmem_cache_free(fsverity_info_cachep, vi); 278 } 279 280 static bool validate_fsverity_descriptor(struct inode *inode, 281 const struct fsverity_descriptor *desc, 282 size_t desc_size) 283 { 284 if (desc_size < sizeof(*desc)) { 285 fsverity_err(inode, "Unrecognized descriptor size: %zu bytes", 286 desc_size); 287 return false; 288 } 289 290 if (desc->version != 1) { 291 fsverity_err(inode, "Unrecognized descriptor version: %u", 292 desc->version); 293 return false; 294 } 295 296 if (memchr_inv(desc->__reserved, 0, sizeof(desc->__reserved))) { 297 fsverity_err(inode, "Reserved bits set in descriptor"); 298 return false; 299 } 300 301 if (desc->salt_size > sizeof(desc->salt)) { 302 fsverity_err(inode, "Invalid salt_size: %u", desc->salt_size); 303 return false; 304 } 305 306 if (le64_to_cpu(desc->data_size) != inode->i_size) { 307 fsverity_err(inode, 308 "Wrong data_size: %llu (desc) != %lld (inode)", 309 le64_to_cpu(desc->data_size), inode->i_size); 310 return false; 311 } 312 313 if (le32_to_cpu(desc->sig_size) > desc_size - sizeof(*desc)) { 314 fsverity_err(inode, "Signature overflows verity descriptor"); 315 return false; 316 } 317 318 return true; 319 } 320 321 /* 322 * Read the inode's fsverity_descriptor (with optional appended builtin 323 * signature) from the filesystem, and do basic validation of it. 324 */ 325 int fsverity_get_descriptor(struct inode *inode, 326 struct fsverity_descriptor **desc_ret) 327 { 328 int res; 329 struct fsverity_descriptor *desc; 330 331 res = inode->i_sb->s_vop->get_verity_descriptor(inode, NULL, 0); 332 if (res < 0) { 333 fsverity_err(inode, 334 "Error %d getting verity descriptor size", res); 335 return res; 336 } 337 if (res > FS_VERITY_MAX_DESCRIPTOR_SIZE) { 338 fsverity_err(inode, "Verity descriptor is too large (%d bytes)", 339 res); 340 return -EMSGSIZE; 341 } 342 desc = kmalloc(res, GFP_KERNEL); 343 if (!desc) 344 return -ENOMEM; 345 res = inode->i_sb->s_vop->get_verity_descriptor(inode, desc, res); 346 if (res < 0) { 347 fsverity_err(inode, "Error %d reading verity descriptor", res); 348 kfree(desc); 349 return res; 350 } 351 352 if (!validate_fsverity_descriptor(inode, desc, res)) { 353 kfree(desc); 354 return -EINVAL; 355 } 356 357 *desc_ret = desc; 358 return 0; 359 } 360 361 /* Ensure the inode has an ->i_verity_info */ 362 static int ensure_verity_info(struct inode *inode) 363 { 364 struct fsverity_info *vi = fsverity_get_info(inode); 365 struct fsverity_descriptor *desc; 366 int err; 367 368 if (vi) 369 return 0; 370 371 err = fsverity_get_descriptor(inode, &desc); 372 if (err) 373 return err; 374 375 vi = fsverity_create_info(inode, desc); 376 if (IS_ERR(vi)) { 377 err = PTR_ERR(vi); 378 goto out_free_desc; 379 } 380 381 fsverity_set_info(inode, vi); 382 err = 0; 383 out_free_desc: 384 kfree(desc); 385 return err; 386 } 387 388 int __fsverity_file_open(struct inode *inode, struct file *filp) 389 { 390 if (filp->f_mode & FMODE_WRITE) 391 return -EPERM; 392 return ensure_verity_info(inode); 393 } 394 EXPORT_SYMBOL_GPL(__fsverity_file_open); 395 396 int __fsverity_prepare_setattr(struct dentry *dentry, struct iattr *attr) 397 { 398 if (attr->ia_valid & ATTR_SIZE) 399 return -EPERM; 400 return 0; 401 } 402 EXPORT_SYMBOL_GPL(__fsverity_prepare_setattr); 403 404 void __fsverity_cleanup_inode(struct inode *inode) 405 { 406 fsverity_free_info(inode->i_verity_info); 407 inode->i_verity_info = NULL; 408 } 409 EXPORT_SYMBOL_GPL(__fsverity_cleanup_inode); 410 411 int __init fsverity_init_info_cache(void) 412 { 413 fsverity_info_cachep = KMEM_CACHE_USERCOPY(fsverity_info, 414 SLAB_RECLAIM_ACCOUNT, 415 file_digest); 416 if (!fsverity_info_cachep) 417 return -ENOMEM; 418 return 0; 419 } 420 421 void __init fsverity_exit_info_cache(void) 422 { 423 kmem_cache_destroy(fsverity_info_cachep); 424 fsverity_info_cachep = NULL; 425 } 426