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, num: hash_algorithm); |
45 | if (IS_ERR(ptr: hash_alg)) |
46 | return PTR_ERR(ptr: hash_alg); |
47 | params->hash_alg = hash_alg; |
48 | params->digest_size = hash_alg->digest_size; |
49 | |
50 | params->hashstate = fsverity_prepare_hash_state(alg: hash_alg, salt, |
51 | salt_size); |
52 | if (IS_ERR(ptr: params->hashstate)) { |
53 | err = PTR_ERR(ptr: 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(objp: 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(alg: hash_alg, data: desc, size: sizeof(*desc), out: 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(k: fsverity_info_cachep, GFP_KERNEL); |
187 | if (!vi) |
188 | return ERR_PTR(error: -ENOMEM); |
189 | vi->inode = inode; |
190 | |
191 | err = fsverity_init_merkle_tree_params(params: &vi->tree_params, inode, |
192 | hash_algorithm: desc->hash_algorithm, |
193 | log_blocksize: desc->log_blocksize, |
194 | salt: desc->salt, salt_size: 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(hash_alg: vi->tree_params.hash_alg, desc, |
205 | file_digest: 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, signature: 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 | size: 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(error: 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(objp: vi->tree_params.hashstate); |
276 | kvfree(addr: vi->hash_block_verified); |
277 | kmem_cache_free(s: fsverity_info_cachep, objp: 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(p: desc->__reserved, c: 0, size: 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(size: 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(objp: desc); |
349 | return res; |
350 | } |
351 | |
352 | if (!validate_fsverity_descriptor(inode, desc, desc_size: res)) { |
353 | kfree(objp: 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_ret: &desc); |
372 | if (err) |
373 | return err; |
374 | |
375 | vi = fsverity_create_info(inode, desc); |
376 | if (IS_ERR(ptr: vi)) { |
377 | err = PTR_ERR(ptr: vi); |
378 | goto out_free_desc; |
379 | } |
380 | |
381 | fsverity_set_info(inode, vi); |
382 | err = 0; |
383 | out_free_desc: |
384 | kfree(objp: 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(vi: inode->i_verity_info); |
407 | inode->i_verity_info = NULL; |
408 | } |
409 | EXPORT_SYMBOL_GPL(__fsverity_cleanup_inode); |
410 | |
411 | void __init fsverity_init_info_cache(void) |
412 | { |
413 | fsverity_info_cachep = KMEM_CACHE_USERCOPY( |
414 | fsverity_info, |
415 | SLAB_RECLAIM_ACCOUNT | SLAB_PANIC, |
416 | file_digest); |
417 | } |
418 | |