417 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * Opening fs-verity files4 *5 * Copyright 2019 Google LLC6 */7 8#include "fsverity_private.h"9 10#include <linux/mm.h>11#include <linux/slab.h>12 13static struct kmem_cache *fsverity_info_cachep;14 15/**16 * fsverity_init_merkle_tree_params() - initialize Merkle tree parameters17 * @params: the parameters struct to initialize18 * @inode: the inode for which the Merkle tree is being built19 * @hash_algorithm: number of hash algorithm to use20 * @log_blocksize: log base 2 of block size to use21 * @salt: pointer to salt (optional)22 * @salt_size: size of salt, possibly 023 *24 * Validate the hash algorithm and block size, then compute the tree topology25 * (num levels, num blocks in each level, etc.) and initialize @params.26 *27 * Return: 0 on success, -errno on failure28 */29int 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 a61 * power of 2 less than or equal to PAGE_SIZE. Another restriction62 * arises from the interaction between fs/verity/ and the filesystems63 * themselves: filesystems expect to be able to verify a single64 * filesystem block of data at a time. Therefore, the Merkle tree block65 * 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 tree68 * 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 and70 * large Merkle trees. So we currently require that the Merkle tree71 * block size be at least 1024 bytes. That's small enough to test the72 * 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 from103 * level to the starting block of that level. Level 'num_levels - 1' is104 * 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 be130 * allocated to track the "verified" status of hash blocks. Don't allow131 * this bitmap to get too large. For now, limit it to 1 MiB, which132 * 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 block136 * indices can always fit in an 'unsigned long'. But to be safe, we137 * explicitly check for that too. Note, this is only for hash block138 * 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 151out_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 the159 * builtin signature and with the sig_size field set to 0.160 */161static 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 optional177 * appended builtin signature), and check the signature if present. The178 * fsverity_descriptor must have already undergone basic validation.179 */180struct 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 use219 * a bitmap to keep track of which hash blocks have been220 * 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 efficient224 * way, it might be necessary to make pages of this bitmap225 * reclaimable. But for now, simply allocating the whole bitmap226 * is a simple solution that works well on the files on which227 * fsverity is realistically used. E.g., with SHA-256 and 4K228 * blocks, a 100MB file only needs a 24-byte bitmap, and the229 * 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 246fail:247 fsverity_free_info(vi);248 return ERR_PTR(err);249}250 251void fsverity_set_info(struct inode *inode, struct fsverity_info *vi)252{253 /*254 * Multiple tasks may race to set ->i_verity_info, so use255 * cmpxchg_release(). This pairs with the smp_load_acquire() in256 * fsverity_get_info(). I.e., here we publish ->i_verity_info with a257 * 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 270void 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 279static 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 builtin322 * signature) from the filesystem, and do basic validation of it.323 */324int 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 */361static 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;382out_free_desc:383 kfree(desc);384 return err;385}386 387int __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}393EXPORT_SYMBOL_GPL(__fsverity_file_open);394 395int __fsverity_prepare_setattr(struct dentry *dentry, struct iattr *attr)396{397 if (attr->ia_valid & ATTR_SIZE)398 return -EPERM;399 return 0;400}401EXPORT_SYMBOL_GPL(__fsverity_prepare_setattr);402 403void __fsverity_cleanup_inode(struct inode *inode)404{405 fsverity_free_info(inode->i_verity_info);406 inode->i_verity_info = NULL;407}408EXPORT_SYMBOL_GPL(__fsverity_cleanup_inode);409 410void __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