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 <stdio.h> 14 #include <stdlib.h> 15 #include <string.h> 16 #include <unistd.h> 17 #include <vector> 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 std::vector<unsigned char> salt; 130 bool sparse = false; 131 size_t block_size = 4096; 132 uint64_t calculate_size = 0; 133 bool verbose = false; 134 135 while (1) { 136 const static struct option long_options[] = { 137 {"salt-str", required_argument, 0, 'a'}, 138 {"salt-hex", required_argument, 0, 'A'}, 139 {"help", no_argument, 0, 'h'}, 140 {"sparse", no_argument, 0, 'S'}, 141 {"verity-size", required_argument, 0, 's'}, 142 {"verbose", no_argument, 0, 'v'}, 143 {NULL, 0, 0, 0} 144 }; 145 int c = getopt_long(argc, argv, "a:A:hSs:v", long_options, NULL); 146 if (c < 0) { 147 break; 148 } 149 150 switch (c) { 151 case 'a': 152 salt.clear(); 153 salt.insert(salt.end(), optarg, &optarg[strlen(optarg)]); 154 break; 155 case 'A': { 156 BIGNUM *bn = NULL; 157 if(!BN_hex2bn(&bn, optarg)) { 158 FATAL("failed to convert salt from hex\n"); 159 } 160 size_t salt_size = BN_num_bytes(bn); 161 salt.resize(salt_size); 162 if (BN_bn2bin(bn, salt.data()) != 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 char* endptr; 175 errno = 0; 176 unsigned long long int inSize = strtoull(optarg, &endptr, 0); 177 if (optarg[0] == '\0' || *endptr != '\0' || 178 (errno == ERANGE && inSize == ULLONG_MAX)) { 179 FATAL("invalid value of verity-size\n"); 180 } 181 if (inSize > UINT64_MAX) { 182 FATAL("invalid value of verity-size\n"); 183 } 184 calculate_size = (uint64_t)inSize; 185 } 186 break; 187 case 'v': 188 verbose = true; 189 break; 190 case '?': 191 usage(); 192 return 1; 193 default: 194 abort(); 195 } 196 } 197 198 argc -= optind; 199 argv += optind; 200 201 const EVP_MD *md = EVP_sha256(); 202 if (!md) { 203 FATAL("failed to get digest\n"); 204 } 205 206 size_t hash_size = EVP_MD_size(md); 207 assert(hash_size * 2 < block_size); 208 209 if (salt.empty()) { 210 salt.resize(hash_size); 211 212 int random_fd = open("/dev/urandom", O_RDONLY); 213 if (random_fd < 0) { 214 FATAL("failed to open /dev/urandom\n"); 215 } 216 217 ssize_t ret = read(random_fd, salt.data(), salt.size()); 218 if (ret != static_cast<ssize_t>(salt.size())) { 219 FATAL("failed to read %zu bytes from /dev/urandom: %zd %d\n", salt.size(), ret, errno); 220 } 221 close(random_fd); 222 } 223 224 if (calculate_size) { 225 if (argc != 0) { 226 usage(); 227 return 1; 228 } 229 size_t verity_blocks = 0; 230 size_t level_blocks; 231 int levels = 0; 232 do { 233 level_blocks = verity_tree_blocks(calculate_size, block_size, hash_size, levels); 234 levels++; 235 verity_blocks += level_blocks; 236 } while (level_blocks > 1); 237 238 printf("%" PRIu64 "\n", (uint64_t)verity_blocks * block_size); 239 return 0; 240 } 241 242 if (argc != 2) { 243 usage(); 244 return 1; 245 } 246 247 data_filename = argv[0]; 248 verity_filename = argv[1]; 249 250 int fd = open(data_filename, O_RDONLY); 251 if (fd < 0) { 252 FATAL("failed to open %s\n", data_filename); 253 } 254 255 struct sparse_file *file; 256 if (sparse) { 257 file = sparse_file_import(fd, false, false); 258 } else { 259 file = sparse_file_import_auto(fd, false, verbose); 260 } 261 262 if (!file) { 263 FATAL("failed to read file %s\n", data_filename); 264 } 265 266 int64_t len = sparse_file_len(file, false, false); 267 if (len % block_size != 0) { 268 FATAL("file size %" PRIu64 " is not a multiple of %zu bytes\n", 269 len, block_size); 270 } 271 272 int levels = 0; 273 size_t verity_blocks = 0; 274 size_t level_blocks; 275 276 do { 277 level_blocks = verity_tree_blocks(len, block_size, hash_size, levels); 278 levels++; 279 verity_blocks += level_blocks; 280 } while (level_blocks > 1); 281 282 unsigned char *verity_tree = new unsigned char[verity_blocks * block_size](); 283 unsigned char **verity_tree_levels = new unsigned char *[levels + 1](); 284 size_t *verity_tree_level_blocks = new size_t[levels](); 285 if (verity_tree == NULL || verity_tree_levels == NULL || verity_tree_level_blocks == NULL) { 286 FATAL("failed to allocate memory for verity tree\n"); 287 } 288 289 unsigned char *ptr = verity_tree; 290 for (int i = levels - 1; i >= 0; i--) { 291 verity_tree_levels[i] = ptr; 292 verity_tree_level_blocks[i] = verity_tree_blocks(len, block_size, hash_size, i); 293 ptr += verity_tree_level_blocks[i] * block_size; 294 } 295 assert(ptr == verity_tree + verity_blocks * block_size); 296 assert(verity_tree_level_blocks[levels - 1] == 1); 297 298 unsigned char zero_block_hash[hash_size]; 299 unsigned char zero_block[block_size]; 300 memset(zero_block, 0, block_size); 301 hash_block(md, zero_block, block_size, salt.data(), salt.size(), zero_block_hash, NULL); 302 303 unsigned char root_hash[hash_size]; 304 verity_tree_levels[levels] = root_hash; 305 306 struct sparse_hash_ctx ctx; 307 ctx.hashes = verity_tree_levels[0]; 308 ctx.salt = salt.data(); 309 ctx.salt_size = salt.size(); 310 ctx.hash_size = hash_size; 311 ctx.block_size = block_size; 312 ctx.zero_block_hash = zero_block_hash; 313 ctx.md = md; 314 315 sparse_file_callback(file, false, false, hash_chunk, &ctx); 316 317 sparse_file_destroy(file); 318 close(fd); 319 320 for (int i = 0; i < levels; i++) { 321 size_t out_size; 322 hash_blocks(md, 323 verity_tree_levels[i], verity_tree_level_blocks[i] * block_size, 324 verity_tree_levels[i + 1], &out_size, 325 salt.data(), salt.size(), block_size); 326 if (i < levels - 1) { 327 assert(div_round_up(out_size, block_size) == verity_tree_level_blocks[i + 1]); 328 } else { 329 assert(out_size == hash_size); 330 } 331 } 332 333 for (size_t i = 0; i < hash_size; i++) { 334 printf("%02x", root_hash[i]); 335 } 336 printf(" "); 337 for (size_t i = 0; i < salt.size(); i++) { 338 printf("%02x", salt[i]); 339 } 340 printf("\n"); 341 342 fd = open(verity_filename, O_WRONLY|O_CREAT, 0666); 343 if (fd < 0) { 344 FATAL("failed to open output file '%s'\n", verity_filename); 345 } 346 if (!android::base::WriteFully(fd, verity_tree, verity_blocks * block_size)) { 347 FATAL("failed to write '%s'\n", verity_filename); 348 } 349 close(fd); 350 351 delete[] verity_tree_levels; 352 delete[] verity_tree_level_blocks; 353 delete[] verity_tree; 354 } 355