1 #include <openssl/evp.h> 2 #include <sparse/sparse.h> 3 4 #undef NDEBUG 5 6 #include <assert.h> 7 #include <errno.h> 8 #include <getopt.h> 9 #include <fcntl.h> 10 #include <inttypes.h> 11 #include <stdbool.h> 12 #include <stdio.h> 13 #include <stdlib.h> 14 #include <string.h> 15 #include <unistd.h> 16 17 struct sparse_hash_ctx { 18 unsigned char *hashes; 19 const unsigned char *salt; 20 uint64_t salt_size; 21 uint64_t hash_size; 22 uint64_t block_size; 23 const unsigned char *zero_block_hash; 24 const EVP_MD *md; 25 }; 26 27 #define div_round_up(x,y) (((x) + (y) - 1)/(y)) 28 29 #define round_up(x,y) (div_round_up(x,y)*(y)) 30 31 #define FATAL(x...) { \ 32 fprintf(stderr, x); \ 33 exit(1); \ 34 } 35 36 size_t verity_tree_blocks(uint64_t data_size, size_t block_size, size_t hash_size, 37 int level) 38 { 39 size_t level_blocks = div_round_up(data_size, block_size); 40 int hashes_per_block = div_round_up(block_size, hash_size); 41 42 do { 43 level_blocks = div_round_up(level_blocks, hashes_per_block); 44 } while (level--); 45 46 return level_blocks; 47 } 48 49 int hash_block(const EVP_MD *md, 50 const unsigned char *block, size_t len, 51 const unsigned char *salt, size_t salt_len, 52 unsigned char *out, size_t *out_size) 53 { 54 EVP_MD_CTX *mdctx; 55 unsigned int s; 56 int ret = 1; 57 58 mdctx = EVP_MD_CTX_create(); 59 assert(mdctx); 60 ret &= EVP_DigestInit_ex(mdctx, md, NULL); 61 ret &= EVP_DigestUpdate(mdctx, salt, salt_len); 62 ret &= EVP_DigestUpdate(mdctx, block, len); 63 ret &= EVP_DigestFinal_ex(mdctx, out, &s); 64 EVP_MD_CTX_destroy(mdctx); 65 assert(ret == 1); 66 if (out_size) { 67 *out_size = s; 68 } 69 return 0; 70 } 71 72 int hash_blocks(const EVP_MD *md, 73 const unsigned char *in, size_t in_size, 74 unsigned char *out, size_t *out_size, 75 const unsigned char *salt, size_t salt_size, 76 size_t block_size) 77 { 78 size_t s; 79 *out_size = 0; 80 for (size_t i = 0; i < in_size; i += block_size) { 81 hash_block(md, in + i, block_size, salt, salt_size, out, &s); 82 out += s; 83 *out_size += s; 84 } 85 86 return 0; 87 } 88 89 int hash_chunk(void *priv, const void *data, int len) 90 { 91 struct sparse_hash_ctx *ctx = (struct sparse_hash_ctx *)priv; 92 assert(len % ctx->block_size == 0); 93 if (data) { 94 size_t s; 95 hash_blocks(ctx->md, (const unsigned char *)data, len, 96 ctx->hashes, &s, 97 ctx->salt, ctx->salt_size, ctx->block_size); 98 ctx->hashes += s; 99 } else { 100 for (size_t i = 0; i < (size_t)len; i += ctx->block_size) { 101 memcpy(ctx->hashes, ctx->zero_block_hash, ctx->hash_size); 102 ctx->hashes += ctx->hash_size; 103 } 104 } 105 return 0; 106 } 107 108 void usage(void) 109 { 110 printf("usage: build_verity_tree [ <options> ] -s <size> | <data> <verity>\n" 111 "options:\n" 112 " -a,--salt-str=<string> set salt to <string>\n" 113 " -A,--salt-hex=<hex digits> set salt to <hex digits>\n" 114 " -h show this help\n" 115 " -s,--verity-size=<data size> print the size of the verity tree\n" 116 " -S treat <data image> as a sparse file\n" 117 ); 118 } 119 120 int main(int argc, char **argv) 121 { 122 char *data_filename; 123 char *verity_filename; 124 unsigned char *salt = NULL; 125 size_t salt_size = 0; 126 bool sparse = false; 127 size_t block_size = 4096; 128 size_t calculate_size = 0; 129 130 while (1) { 131 const static struct option long_options[] = { 132 {"salt-str", required_argument, 0, 'a'}, 133 {"salt-hex", required_argument, 0, 'A'}, 134 {"help", no_argument, 0, 'h'}, 135 {"sparse", no_argument, 0, 'S'}, 136 {"verity-size", required_argument, 0, 's'}, 137 }; 138 int c = getopt_long(argc, argv, "a:A:hSs:", long_options, NULL); 139 if (c < 0) { 140 break; 141 } 142 143 switch (c) { 144 case 'a': 145 salt_size = strlen(optarg); 146 salt = new unsigned char[salt_size](); 147 if (salt == NULL) { 148 FATAL("failed to allocate memory for salt\n"); 149 } 150 memcpy(salt, optarg, salt_size); 151 break; 152 case 'A': { 153 BIGNUM *bn = NULL; 154 if(!BN_hex2bn(&bn, optarg)) { 155 FATAL("failed to convert salt from hex\n"); 156 } 157 salt_size = BN_num_bytes(bn); 158 salt = new unsigned char[salt_size](); 159 if (salt == NULL) { 160 FATAL("failed to allocate memory for salt\n"); 161 } 162 if((size_t)BN_bn2bin(bn, salt) != salt_size) { 163 FATAL("failed to convert salt to bytes\n"); 164 } 165 } 166 break; 167 case 'h': 168 usage(); 169 return 1; 170 case 'S': 171 sparse = true; 172 break; 173 case 's': 174 calculate_size = strtoul(optarg, NULL, 0); 175 break; 176 case '?': 177 usage(); 178 return 1; 179 default: 180 abort(); 181 } 182 } 183 184 argc -= optind; 185 argv += optind; 186 187 const EVP_MD *md = EVP_sha256(); 188 if (!md) { 189 FATAL("failed to get digest\n"); 190 } 191 192 size_t hash_size = EVP_MD_size(md); 193 assert(hash_size * 2 < block_size); 194 195 if (!salt || !salt_size) { 196 salt_size = hash_size; 197 salt = new unsigned char[salt_size]; 198 if (salt == NULL) { 199 FATAL("failed to allocate memory for salt\n"); 200 } 201 202 int random_fd = open("/dev/urandom", O_RDONLY); 203 if (random_fd < 0) { 204 FATAL("failed to open /dev/urandom\n"); 205 } 206 207 ssize_t ret = read(random_fd, salt, salt_size); 208 if (ret != (ssize_t)salt_size) { 209 FATAL("failed to read %zu bytes from /dev/urandom: %zd %d\n", salt_size, ret, errno); 210 } 211 close(random_fd); 212 } 213 214 if (calculate_size) { 215 if (argc != 0) { 216 usage(); 217 return 1; 218 } 219 size_t verity_blocks = 0; 220 size_t level_blocks; 221 int levels = 0; 222 do { 223 level_blocks = verity_tree_blocks(calculate_size, block_size, hash_size, levels); 224 levels++; 225 verity_blocks += level_blocks; 226 } while (level_blocks > 1); 227 228 printf("%zu\n", verity_blocks * block_size); 229 return 0; 230 } 231 232 if (argc != 2) { 233 usage(); 234 return 1; 235 } 236 237 data_filename = argv[0]; 238 verity_filename = argv[1]; 239 240 int fd = open(data_filename, O_RDONLY); 241 if (fd < 0) { 242 FATAL("failed to open %s\n", data_filename); 243 } 244 245 struct sparse_file *file; 246 if (sparse) { 247 file = sparse_file_import(fd, false, false); 248 } else { 249 file = sparse_file_import_auto(fd, false); 250 } 251 252 if (!file) { 253 FATAL("failed to read file %s\n", data_filename); 254 } 255 256 int64_t len = sparse_file_len(file, false, false); 257 if (len % block_size != 0) { 258 FATAL("file size %" PRIu64 " is not a multiple of %zu bytes\n", 259 len, block_size); 260 } 261 262 int levels = 0; 263 size_t verity_blocks = 0; 264 size_t level_blocks; 265 266 do { 267 level_blocks = verity_tree_blocks(len, block_size, hash_size, levels); 268 levels++; 269 verity_blocks += level_blocks; 270 } while (level_blocks > 1); 271 272 unsigned char *verity_tree = new unsigned char[verity_blocks * block_size](); 273 unsigned char **verity_tree_levels = new unsigned char *[levels + 1](); 274 size_t *verity_tree_level_blocks = new size_t[levels](); 275 if (verity_tree == NULL || verity_tree_levels == NULL || verity_tree_level_blocks == NULL) { 276 FATAL("failed to allocate memory for verity tree\n"); 277 } 278 279 unsigned char *ptr = verity_tree; 280 for (int i = levels - 1; i >= 0; i--) { 281 verity_tree_levels[i] = ptr; 282 verity_tree_level_blocks[i] = verity_tree_blocks(len, block_size, hash_size, i); 283 ptr += verity_tree_level_blocks[i] * block_size; 284 } 285 assert(ptr == verity_tree + verity_blocks * block_size); 286 assert(verity_tree_level_blocks[levels - 1] == 1); 287 288 unsigned char zero_block_hash[hash_size]; 289 unsigned char zero_block[block_size]; 290 memset(zero_block, 0, block_size); 291 hash_block(md, zero_block, block_size, salt, salt_size, zero_block_hash, NULL); 292 293 unsigned char root_hash[hash_size]; 294 verity_tree_levels[levels] = root_hash; 295 296 struct sparse_hash_ctx ctx; 297 ctx.hashes = verity_tree_levels[0]; 298 ctx.salt = salt; 299 ctx.salt_size = salt_size; 300 ctx.hash_size = hash_size; 301 ctx.block_size = block_size; 302 ctx.zero_block_hash = zero_block_hash; 303 ctx.md = md; 304 305 sparse_file_callback(file, false, false, hash_chunk, &ctx); 306 307 sparse_file_destroy(file); 308 close(fd); 309 310 for (int i = 0; i < levels; i++) { 311 size_t out_size; 312 hash_blocks(md, 313 verity_tree_levels[i], verity_tree_level_blocks[i] * block_size, 314 verity_tree_levels[i + 1], &out_size, 315 salt, salt_size, block_size); 316 if (i < levels - 1) { 317 assert(div_round_up(out_size, block_size) == verity_tree_level_blocks[i + 1]); 318 } else { 319 assert(out_size == hash_size); 320 } 321 } 322 323 for (size_t i = 0; i < hash_size; i++) { 324 printf("%02x", root_hash[i]); 325 } 326 printf(" "); 327 for (size_t i = 0; i < salt_size; i++) { 328 printf("%02x", salt[i]); 329 } 330 printf("\n"); 331 332 fd = open(verity_filename, O_WRONLY|O_CREAT, 0666); 333 if (fd < 0) { 334 FATAL("failed to open output file '%s'\n", verity_filename); 335 } 336 write(fd, verity_tree, verity_blocks * block_size); 337 close(fd); 338 339 delete[] verity_tree_levels; 340 delete[] verity_tree_level_blocks; 341 delete[] verity_tree; 342 delete[] salt; 343 } 344