1 // SPDX-License-Identifier: MIT
2 /*
3 * Implementation of libfsverity_compute_digest().
4 *
5 * Copyright 2018 Google LLC
6 * Copyright (C) 2020 Facebook
7 *
8 * Use of this source code is governed by an MIT-style
9 * license that can be found in the LICENSE file or at
10 * https://opensource.org/licenses/MIT.
11 */
12
13 #include "lib_private.h"
14
15 #include <stdlib.h>
16 #include <string.h>
17
18 #define FS_VERITY_MAX_LEVELS 64
19
20 struct block_buffer {
21 u32 filled;
22 u8 *data;
23 };
24
25 /*
26 * Hash a block, writing the result to the next level's pending block buffer.
27 * Returns true if the next level's block became full, else false.
28 */
hash_one_block(struct hash_ctx * hash,struct block_buffer * cur,u32 block_size,const u8 * salt,u32 salt_size)29 static bool hash_one_block(struct hash_ctx *hash, struct block_buffer *cur,
30 u32 block_size, const u8 *salt, u32 salt_size)
31 {
32 struct block_buffer *next = cur + 1;
33
34 /* Zero-pad the block if it's shorter than block_size. */
35 memset(&cur->data[cur->filled], 0, block_size - cur->filled);
36
37 libfsverity_hash_init(hash);
38 libfsverity_hash_update(hash, salt, salt_size);
39 libfsverity_hash_update(hash, cur->data, block_size);
40 libfsverity_hash_final(hash, &next->data[next->filled]);
41
42 next->filled += hash->alg->digest_size;
43 cur->filled = 0;
44
45 return next->filled + hash->alg->digest_size > block_size;
46 }
47
48 /*
49 * Compute the file's Merkle tree root hash using the given hash algorithm,
50 * block size, and salt.
51 */
compute_root_hash(void * fd,libfsverity_read_fn_t read_fn,u64 file_size,struct hash_ctx * hash,u32 block_size,const u8 * salt,u32 salt_size,u8 * root_hash)52 static int compute_root_hash(void *fd, libfsverity_read_fn_t read_fn,
53 u64 file_size, struct hash_ctx *hash,
54 u32 block_size, const u8 *salt, u32 salt_size,
55 u8 *root_hash)
56 {
57 const u32 hashes_per_block = block_size / hash->alg->digest_size;
58 const u32 padded_salt_size = roundup(salt_size, hash->alg->block_size);
59 u8 *padded_salt = NULL;
60 u64 blocks;
61 int num_levels = 0;
62 int level;
63 struct block_buffer _buffers[1 + FS_VERITY_MAX_LEVELS + 1] = {};
64 struct block_buffer *buffers = &_buffers[1];
65 u64 offset;
66 int err = 0;
67
68 /* Root hash of empty file is all 0's */
69 if (file_size == 0) {
70 memset(root_hash, 0, hash->alg->digest_size);
71 return 0;
72 }
73
74 if (salt_size != 0) {
75 padded_salt = libfsverity_zalloc(padded_salt_size);
76 if (!padded_salt)
77 return -ENOMEM;
78 memcpy(padded_salt, salt, salt_size);
79 }
80
81 /* Compute number of levels */
82 for (blocks = DIV_ROUND_UP(file_size, block_size); blocks > 1;
83 blocks = DIV_ROUND_UP(blocks, hashes_per_block)) {
84 if (WARN_ON(num_levels >= FS_VERITY_MAX_LEVELS)) {
85 err = -EINVAL;
86 goto out;
87 }
88 num_levels++;
89 }
90
91 /*
92 * Allocate the block buffers. Buffer "-1" is for data blocks.
93 * Buffers 0 <= level < num_levels are for the actual tree levels.
94 * Buffer 'num_levels' is for the root hash.
95 */
96 for (level = -1; level < num_levels; level++) {
97 buffers[level].data = libfsverity_zalloc(block_size);
98 if (!buffers[level].data) {
99 err = -ENOMEM;
100 goto out;
101 }
102 }
103 buffers[num_levels].data = root_hash;
104
105 /* Hash each data block, also hashing the tree blocks as they fill up */
106 for (offset = 0; offset < file_size; offset += block_size) {
107 buffers[-1].filled = min(block_size, file_size - offset);
108
109 err = read_fn(fd, buffers[-1].data, buffers[-1].filled);
110 if (err) {
111 libfsverity_error_msg("error reading file");
112 goto out;
113 }
114
115 level = -1;
116 while (hash_one_block(hash, &buffers[level], block_size,
117 padded_salt, padded_salt_size)) {
118 level++;
119 if (WARN_ON(level >= num_levels)) {
120 err = -EINVAL;
121 goto out;
122 }
123 }
124 }
125 /* Finish all nonempty pending tree blocks */
126 for (level = 0; level < num_levels; level++) {
127 if (buffers[level].filled != 0)
128 hash_one_block(hash, &buffers[level], block_size,
129 padded_salt, padded_salt_size);
130 }
131
132 /* Root hash was filled by the last call to hash_one_block() */
133 if (WARN_ON(buffers[num_levels].filled != hash->alg->digest_size)) {
134 err = -EINVAL;
135 goto out;
136 }
137 err = 0;
138 out:
139 for (level = -1; level < num_levels; level++)
140 free(buffers[level].data);
141 free(padded_salt);
142 return err;
143 }
144
145 LIBEXPORT int
libfsverity_compute_digest(void * fd,libfsverity_read_fn_t read_fn,const struct libfsverity_merkle_tree_params * params,struct libfsverity_digest ** digest_ret)146 libfsverity_compute_digest(void *fd, libfsverity_read_fn_t read_fn,
147 const struct libfsverity_merkle_tree_params *params,
148 struct libfsverity_digest **digest_ret)
149 {
150 u32 alg_num;
151 u32 block_size;
152 const struct fsverity_hash_alg *hash_alg;
153 struct hash_ctx *hash = NULL;
154 struct libfsverity_digest *digest;
155 struct fsverity_descriptor desc;
156 int err;
157
158 if (!read_fn || !params || !digest_ret) {
159 libfsverity_error_msg("missing required parameters for compute_digest");
160 return -EINVAL;
161 }
162 if (params->version != 1) {
163 libfsverity_error_msg("unsupported version (%u)",
164 params->version);
165 return -EINVAL;
166 }
167
168 alg_num = params->hash_algorithm ?: FS_VERITY_HASH_ALG_DEFAULT;
169 block_size = params->block_size ?: FS_VERITY_BLOCK_SIZE_DEFAULT;
170
171 if (!is_power_of_2(block_size)) {
172 libfsverity_error_msg("unsupported block size (%u)",
173 block_size);
174 return -EINVAL;
175 }
176 if (params->salt_size > sizeof(desc.salt)) {
177 libfsverity_error_msg("unsupported salt size (%u)",
178 params->salt_size);
179 return -EINVAL;
180 }
181 if (params->salt_size && !params->salt) {
182 libfsverity_error_msg("salt_size specified, but salt is NULL");
183 return -EINVAL;
184 }
185 if (!libfsverity_mem_is_zeroed(params->reserved1,
186 sizeof(params->reserved1)) ||
187 !libfsverity_mem_is_zeroed(params->reserved2,
188 sizeof(params->reserved2))) {
189 libfsverity_error_msg("reserved bits set in merkle_tree_params");
190 return -EINVAL;
191 }
192
193 hash_alg = libfsverity_find_hash_alg_by_num(alg_num);
194 if (!hash_alg) {
195 libfsverity_error_msg("unknown hash algorithm: %u", alg_num);
196 return -EINVAL;
197 }
198
199 if (block_size < 2 * hash_alg->digest_size) {
200 libfsverity_error_msg("block size (%u) too small for hash algorithm %s",
201 block_size, hash_alg->name);
202 return -EINVAL;
203 }
204
205 hash = hash_alg->create_ctx(hash_alg);
206 if (!hash)
207 return -ENOMEM;
208
209 memset(&desc, 0, sizeof(desc));
210 desc.version = 1;
211 desc.hash_algorithm = alg_num;
212 desc.log_blocksize = ilog2(block_size);
213 desc.data_size = cpu_to_le64(params->file_size);
214 if (params->salt_size != 0) {
215 memcpy(desc.salt, params->salt, params->salt_size);
216 desc.salt_size = params->salt_size;
217 }
218
219 err = compute_root_hash(fd, read_fn, params->file_size, hash,
220 block_size, params->salt,
221 params->salt_size, desc.root_hash);
222 if (err)
223 goto out;
224
225 digest = libfsverity_zalloc(sizeof(*digest) + hash_alg->digest_size);
226 if (!digest) {
227 err = -ENOMEM;
228 goto out;
229 }
230 digest->digest_algorithm = alg_num;
231 digest->digest_size = hash_alg->digest_size;
232 libfsverity_hash_full(hash, &desc, sizeof(desc), digest->digest);
233 *digest_ret = digest;
234 err = 0;
235 out:
236 libfsverity_free_hash_ctx(hash);
237 return err;
238 }
239