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