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 } 243 244 return vi; 245 246 fail: 247 fsverity_free_info(vi); 248 return ERR_PTR(err); 249 } 250 251 void fsverity_set_info(struct inode *inode, struct fsverity_info *vi) 252 { 253 /* 254 * Multiple tasks may race to set ->i_verity_info, so use 255 * cmpxchg_release(). This pairs with the smp_load_acquire() in 256 * fsverity_get_info(). I.e., here we publish ->i_verity_info with a 257 * RELEASE barrier so that other tasks can ACQUIRE it. 258 */ 259 if (cmpxchg_release(&inode->i_verity_info, NULL, vi) != NULL) { 260 /* Lost the race, so free the fsverity_info we allocated. */ 261 fsverity_free_info(vi); 262 /* 263 * Afterwards, the caller may access ->i_verity_info directly, 264 * so make sure to ACQUIRE the winning fsverity_info. 265 */ 266 (void)fsverity_get_info(inode); 267 } 268 } 269 270 void fsverity_free_info(struct fsverity_info *vi) 271 { 272 if (!vi) 273 return; 274 kfree(vi->tree_params.hashstate); 275 kvfree(vi->hash_block_verified); 276 kmem_cache_free(fsverity_info_cachep, vi); 277 } 278 279 static bool validate_fsverity_descriptor(struct inode *inode, 280 const struct fsverity_descriptor *desc, 281 size_t desc_size) 282 { 283 if (desc_size < sizeof(*desc)) { 284 fsverity_err(inode, "Unrecognized descriptor size: %zu bytes", 285 desc_size); 286 return false; 287 } 288 289 if (desc->version != 1) { 290 fsverity_err(inode, "Unrecognized descriptor version: %u", 291 desc->version); 292 return false; 293 } 294 295 if (memchr_inv(desc->__reserved, 0, sizeof(desc->__reserved))) { 296 fsverity_err(inode, "Reserved bits set in descriptor"); 297 return false; 298 } 299 300 if (desc->salt_size > sizeof(desc->salt)) { 301 fsverity_err(inode, "Invalid salt_size: %u", desc->salt_size); 302 return false; 303 } 304 305 if (le64_to_cpu(desc->data_size) != inode->i_size) { 306 fsverity_err(inode, 307 "Wrong data_size: %llu (desc) != %lld (inode)", 308 le64_to_cpu(desc->data_size), inode->i_size); 309 return false; 310 } 311 312 if (le32_to_cpu(desc->sig_size) > desc_size - sizeof(*desc)) { 313 fsverity_err(inode, "Signature overflows verity descriptor"); 314 return false; 315 } 316 317 return true; 318 } 319 320 /* 321 * Read the inode's fsverity_descriptor (with optional appended builtin 322 * signature) from the filesystem, and do basic validation of it. 323 */ 324 int fsverity_get_descriptor(struct inode *inode, 325 struct fsverity_descriptor **desc_ret) 326 { 327 int res; 328 struct fsverity_descriptor *desc; 329 330 res = inode->i_sb->s_vop->get_verity_descriptor(inode, NULL, 0); 331 if (res < 0) { 332 fsverity_err(inode, 333 "Error %d getting verity descriptor size", res); 334 return res; 335 } 336 if (res > FS_VERITY_MAX_DESCRIPTOR_SIZE) { 337 fsverity_err(inode, "Verity descriptor is too large (%d bytes)", 338 res); 339 return -EMSGSIZE; 340 } 341 desc = kmalloc(res, GFP_KERNEL); 342 if (!desc) 343 return -ENOMEM; 344 res = inode->i_sb->s_vop->get_verity_descriptor(inode, desc, res); 345 if (res < 0) { 346 fsverity_err(inode, "Error %d reading verity descriptor", res); 347 kfree(desc); 348 return res; 349 } 350 351 if (!validate_fsverity_descriptor(inode, desc, res)) { 352 kfree(desc); 353 return -EINVAL; 354 } 355 356 *desc_ret = desc; 357 return 0; 358 } 359 360 /* Ensure the inode has an ->i_verity_info */ 361 static int ensure_verity_info(struct inode *inode) 362 { 363 struct fsverity_info *vi = fsverity_get_info(inode); 364 struct fsverity_descriptor *desc; 365 int err; 366 367 if (vi) 368 return 0; 369 370 err = fsverity_get_descriptor(inode, &desc); 371 if (err) 372 return err; 373 374 vi = fsverity_create_info(inode, desc); 375 if (IS_ERR(vi)) { 376 err = PTR_ERR(vi); 377 goto out_free_desc; 378 } 379 380 fsverity_set_info(inode, vi); 381 err = 0; 382 out_free_desc: 383 kfree(desc); 384 return err; 385 } 386 387 int __fsverity_file_open(struct inode *inode, struct file *filp) 388 { 389 if (filp->f_mode & FMODE_WRITE) 390 return -EPERM; 391 return ensure_verity_info(inode); 392 } 393 EXPORT_SYMBOL_GPL(__fsverity_file_open); 394 395 int __fsverity_prepare_setattr(struct dentry *dentry, struct iattr *attr) 396 { 397 if (attr->ia_valid & ATTR_SIZE) 398 return -EPERM; 399 return 0; 400 } 401 EXPORT_SYMBOL_GPL(__fsverity_prepare_setattr); 402 403 void __fsverity_cleanup_inode(struct inode *inode) 404 { 405 fsverity_free_info(inode->i_verity_info); 406 inode->i_verity_info = NULL; 407 } 408 EXPORT_SYMBOL_GPL(__fsverity_cleanup_inode); 409 410 void __init fsverity_init_info_cache(void) 411 { 412 fsverity_info_cachep = KMEM_CACHE_USERCOPY( 413 fsverity_info, 414 SLAB_RECLAIM_ACCOUNT | SLAB_PANIC, 415 file_digest); 416 } 417