verity/build_verity_tree.cpp - platform/system/extras - Git at Google

 #include <openssl/bn.h>
 #include <openssl/evp.h>
 #include <sparse/sparse.h>

 #undef NDEBUG

 #include <assert.h>
 #include <errno.h>
 #include <getopt.h>
 #include <fcntl.h>
 #include <inttypes.h>
 #include <limits.h>
 #include <stdbool.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
 #include <unistd.h>

 #include <android-base/file.h>

 struct sparse_hash_ctx {
     unsigned char *hashes;
     const unsigned char *salt;
     uint64_t salt_size;
     uint64_t hash_size;
     uint64_t block_size;
     const unsigned char *zero_block_hash;
     const EVP_MD *md;
 };

 #define div_round_up(x,y) (((x) + (y) - 1)/(y))

 #define round_up(x,y) (div_round_up(x,y)*(y))

 #define FATAL(x...) { \
     fprintf(stderr, x); \
     exit(1); \
 }

 size_t verity_tree_blocks(uint64_t data_size, size_t block_size, size_t hash_size,
                           int level)
 {
     size_t level_blocks = div_round_up(data_size, block_size);
     int hashes_per_block = div_round_up(block_size, hash_size);

     do {
         level_blocks = div_round_up(level_blocks, hashes_per_block);
     } while (level--);

     return level_blocks;
 }

 int hash_block(const EVP_MD *md,
                const unsigned char *block, size_t len,
                const unsigned char *salt, size_t salt_len,
                unsigned char *out, size_t *out_size)
 {
     EVP_MD_CTX *mdctx;
     unsigned int s;
     int ret = 1;

     mdctx = EVP_MD_CTX_create();
     assert(mdctx);
     ret &= EVP_DigestInit_ex(mdctx, md, NULL);
     ret &= EVP_DigestUpdate(mdctx, salt, salt_len);
     ret &= EVP_DigestUpdate(mdctx, block, len);
     ret &= EVP_DigestFinal_ex(mdctx, out, &s);
     EVP_MD_CTX_destroy(mdctx);
     assert(ret == 1);
     if (out_size) {
         *out_size = s;
     }
     return 0;
 }

 int hash_blocks(const EVP_MD *md,
                 const unsigned char *in, size_t in_size,
                 unsigned char *out, size_t *out_size,
                 const unsigned char *salt, size_t salt_size,
                 size_t block_size)
 {
     size_t s;
     *out_size = 0;
     for (size_t i = 0; i < in_size; i += block_size) {
         hash_block(md, in + i, block_size, salt, salt_size, out, &s);
         out += s;
         *out_size += s;
     }

     return 0;
 }

 int hash_chunk(void *priv, const void *data, int len)
 {
     struct sparse_hash_ctx *ctx = (struct sparse_hash_ctx *)priv;
     assert(len % ctx->block_size == 0);
     if (data) {
         size_t s;
         hash_blocks(ctx->md, (const unsigned char *)data, len,
                     ctx->hashes, &s,
                     ctx->salt, ctx->salt_size, ctx->block_size);
         ctx->hashes += s;
     } else {
         for (size_t i = 0; i < (size_t)len; i += ctx->block_size) {
             memcpy(ctx->hashes, ctx->zero_block_hash, ctx->hash_size);
             ctx->hashes += ctx->hash_size;
         }
     }
     return 0;
 }

 void usage(void)
 {
     printf("usage: build_verity_tree [ <options> ] -s <size> | <data> <verity>\n"
            "options:\n"
            "  -a,--salt-str=<string>       set salt to <string>\n"
            "  -A,--salt-hex=<hex digits>   set salt to <hex digits>\n"
            "  -h                           show this help\n"
            "  -s,--verity-size=<data size> print the size of the verity tree\n"
            "  -v,                          enable verbose logging\n"
            "  -S                           treat <data image> as a sparse file\n"
         );
 }

 int main(int argc, char **argv)
 {
     char *data_filename;
     char *verity_filename;
     unsigned char *salt = NULL;
     size_t salt_size = 0;
     bool sparse = false;
     size_t block_size = 4096;
     uint64_t calculate_size = 0;
     bool verbose = false;

     while (1) {
         const static struct option long_options[] = {
             {"salt-str", required_argument, 0, 'a'},
             {"salt-hex", required_argument, 0, 'A'},
             {"help", no_argument, 0, 'h'},
             {"sparse", no_argument, 0, 'S'},
             {"verity-size", required_argument, 0, 's'},
             {"verbose", no_argument, 0, 'v'},
             {NULL, 0, 0, 0}
         };
         int c = getopt_long(argc, argv, "a:A:hSs:v", long_options, NULL);
         if (c < 0) {
             break;
         }

         switch (c) {
         case 'a':
             salt_size = strlen(optarg);
             salt = new unsigned char[salt_size]();
             if (salt == NULL) {
                 FATAL("failed to allocate memory for salt\n");
             }
             memcpy(salt, optarg, salt_size);
             break;
         case 'A': {
                 BIGNUM *bn = NULL;
                 if(!BN_hex2bn(&bn, optarg)) {
                     FATAL("failed to convert salt from hex\n");
                 }
                 salt_size = BN_num_bytes(bn);
                 salt = new unsigned char[salt_size]();
                 if (salt == NULL) {
                     FATAL("failed to allocate memory for salt\n");
                 }
                 if((size_t)BN_bn2bin(bn, salt) != salt_size) {
                     FATAL("failed to convert salt to bytes\n");
                 }
             }
             break;
         case 'h':
             usage();
             return 1;
         case 'S':
             sparse = true;
             break;
         case 's': {
                 char* endptr;
                 errno = 0;
                 unsigned long long int inSize = strtoull(optarg, &endptr, 0);
                 if (optarg[0] == '\0' || *endptr != '\0' ||
                         (errno == ERANGE && inSize == ULLONG_MAX)) {
                     FATAL("invalid value of verity-size\n");
                 }
                 if (inSize > UINT64_MAX) {
                     FATAL("invalid value of verity-size\n");
                 }
                 calculate_size = (uint64_t)inSize;
             }
             break;
         case 'v':
             verbose = true;
             break;
         case '?':
             usage();
             return 1;
         default:
             abort();
         }
     }

     argc -= optind;
     argv += optind;

     const EVP_MD *md = EVP_sha256();
     if (!md) {
         FATAL("failed to get digest\n");
     }

     size_t hash_size = EVP_MD_size(md);
     assert(hash_size * 2 < block_size);

     if (!salt || !salt_size) {
         salt_size = hash_size;
         salt = new unsigned char[salt_size];
         if (salt == NULL) {
             FATAL("failed to allocate memory for salt\n");
         }

         int random_fd = open("/dev/urandom", O_RDONLY);
         if (random_fd < 0) {
             FATAL("failed to open /dev/urandom\n");
         }

         ssize_t ret = read(random_fd, salt, salt_size);
         if (ret != (ssize_t)salt_size) {
             FATAL("failed to read %zu bytes from /dev/urandom: %zd %d\n", salt_size, ret, errno);
         }
         close(random_fd);
     }

     if (calculate_size) {
         if (argc != 0) {
             usage();
             return 1;
         }
         size_t verity_blocks = 0;
         size_t level_blocks;
         int levels = 0;
         do {
             level_blocks = verity_tree_blocks(calculate_size, block_size, hash_size, levels);
             levels++;
             verity_blocks += level_blocks;
         } while (level_blocks > 1);

         printf("%" PRIu64 "\n", (uint64_t)verity_blocks * block_size);
         return 0;
     }

     if (argc != 2) {
         usage();
         return 1;
     }

     data_filename = argv[0];
     verity_filename = argv[1];

     int fd = open(data_filename, O_RDONLY);
     if (fd < 0) {
         FATAL("failed to open %s\n", data_filename);
     }

     struct sparse_file *file;
     if (sparse) {
         file = sparse_file_import(fd, false, false);
     } else {
         file = sparse_file_import_auto(fd, false, verbose);
     }

     if (!file) {
         FATAL("failed to read file %s\n", data_filename);
     }

     int64_t len = sparse_file_len(file, false, false);
     if (len % block_size != 0) {
         FATAL("file size %" PRIu64 " is not a multiple of %zu bytes\n",
                 len, block_size);
     }

     int levels = 0;
     size_t verity_blocks = 0;
     size_t level_blocks;

     do {
         level_blocks = verity_tree_blocks(len, block_size, hash_size, levels);
         levels++;
         verity_blocks += level_blocks;
     } while (level_blocks > 1);

     unsigned char *verity_tree = new unsigned char[verity_blocks * block_size]();
     unsigned char **verity_tree_levels = new unsigned char *[levels + 1]();
     size_t *verity_tree_level_blocks = new size_t[levels]();
     if (verity_tree == NULL || verity_tree_levels == NULL || verity_tree_level_blocks == NULL) {
         FATAL("failed to allocate memory for verity tree\n");
     }

     unsigned char *ptr = verity_tree;
     for (int i = levels - 1; i >= 0; i--) {
         verity_tree_levels[i] = ptr;
         verity_tree_level_blocks[i] = verity_tree_blocks(len, block_size, hash_size, i);
         ptr += verity_tree_level_blocks[i] * block_size;
     }
     assert(ptr == verity_tree + verity_blocks * block_size);
     assert(verity_tree_level_blocks[levels - 1] == 1);

     unsigned char zero_block_hash[hash_size];
     unsigned char zero_block[block_size];
     memset(zero_block, 0, block_size);
     hash_block(md, zero_block, block_size, salt, salt_size, zero_block_hash, NULL);

     unsigned char root_hash[hash_size];
     verity_tree_levels[levels] = root_hash;

     struct sparse_hash_ctx ctx;
     ctx.hashes = verity_tree_levels[0];
     ctx.salt = salt;
     ctx.salt_size = salt_size;
     ctx.hash_size = hash_size;
     ctx.block_size = block_size;
     ctx.zero_block_hash = zero_block_hash;
     ctx.md = md;

     sparse_file_callback(file, false, false, hash_chunk, &ctx);

     sparse_file_destroy(file);
     close(fd);

     for (int i = 0; i < levels; i++) {
         size_t out_size;
         hash_blocks(md,
                 verity_tree_levels[i], verity_tree_level_blocks[i] * block_size,
                 verity_tree_levels[i + 1], &out_size,
                 salt, salt_size, block_size);
           if (i < levels - 1) {
               assert(div_round_up(out_size, block_size) == verity_tree_level_blocks[i + 1]);
           } else {
               assert(out_size == hash_size);
           }
     }

     for (size_t i = 0; i < hash_size; i++) {
         printf("%02x", root_hash[i]);
     }
     printf(" ");
     for (size_t i = 0; i < salt_size; i++) {
         printf("%02x", salt[i]);
     }
     printf("\n");

     fd = open(verity_filename, O_WRONLY|O_CREAT, 0666);
     if (fd < 0) {
         FATAL("failed to open output file '%s'\n", verity_filename);
     }
     if (!android::base::WriteFully(fd, verity_tree, verity_blocks * block_size)) {
         FATAL("failed to write '%s'\n", verity_filename);
     }
     close(fd);

     delete[] verity_tree_levels;
     delete[] verity_tree_level_blocks;
     delete[] verity_tree;
     delete[] salt;
 }
	#include <openssl/bn.h>
	#include <openssl/evp.h>
	#include <sparse/sparse.h>

	#undef NDEBUG

	#include <assert.h>
	#include <errno.h>
	#include <getopt.h>
	#include <fcntl.h>
	#include <inttypes.h>
	#include <limits.h>
	#include <stdbool.h>
	#include <stdio.h>
	#include <stdlib.h>
	#include <string.h>
	#include <unistd.h>

	#include <android-base/file.h>

	struct sparse_hash_ctx {
	unsigned char *hashes;
	const unsigned char *salt;
	uint64_t salt_size;
	uint64_t hash_size;
	uint64_t block_size;
	const unsigned char *zero_block_hash;
	const EVP_MD *md;
	};

	#define div_round_up(x,y) (((x) + (y) - 1)/(y))

	#define round_up(x,y) (div_round_up(x,y)*(y))

	#define FATAL(x...) { \
	fprintf(stderr, x); \
	exit(1); \
	}

	size_t verity_tree_blocks(uint64_t data_size, size_t block_size, size_t hash_size,
	int level)
	{
	size_t level_blocks = div_round_up(data_size, block_size);
	int hashes_per_block = div_round_up(block_size, hash_size);

	do {
	level_blocks = div_round_up(level_blocks, hashes_per_block);
	} while (level--);

	return level_blocks;
	}

	int hash_block(const EVP_MD *md,
	const unsigned char *block, size_t len,
	const unsigned char *salt, size_t salt_len,
	unsigned char out, size_t out_size)
	{
	EVP_MD_CTX *mdctx;
	unsigned int s;
	int ret = 1;

	mdctx = EVP_MD_CTX_create();
	assert(mdctx);
	ret &= EVP_DigestInit_ex(mdctx, md, NULL);
	ret &= EVP_DigestUpdate(mdctx, salt, salt_len);
	ret &= EVP_DigestUpdate(mdctx, block, len);
	ret &= EVP_DigestFinal_ex(mdctx, out, &s);
	EVP_MD_CTX_destroy(mdctx);
	assert(ret == 1);
	if (out_size) {
	*out_size = s;
	}
	return 0;
	}

	int hash_blocks(const EVP_MD *md,
	const unsigned char *in, size_t in_size,
	unsigned char out, size_t out_size,
	const unsigned char *salt, size_t salt_size,
	size_t block_size)
	{
	size_t s;
	*out_size = 0;
	for (size_t i = 0; i < in_size; i += block_size) {
	hash_block(md, in + i, block_size, salt, salt_size, out, &s);
	out += s;
	*out_size += s;
	}

	return 0;
	}

	int hash_chunk(void priv, const void data, int len)
	{
	struct sparse_hash_ctx ctx = (struct sparse_hash_ctx )priv;
	assert(len % ctx->block_size == 0);
	if (data) {
	size_t s;
	hash_blocks(ctx->md, (const unsigned char *)data, len,
	ctx->hashes, &s,
	ctx->salt, ctx->salt_size, ctx->block_size);
	ctx->hashes += s;
	} else {
	for (size_t i = 0; i < (size_t)len; i += ctx->block_size) {
	memcpy(ctx->hashes, ctx->zero_block_hash, ctx->hash_size);
	ctx->hashes += ctx->hash_size;
	}
	}
	return 0;
	}

	void usage(void)
	{
	printf("usage: build_verity_tree [ <options> ] -s <size> \| <data> <verity>\n"
	"options:\n"
	" -a,--salt-str=<string> set salt to <string>\n"
	" -A,--salt-hex=<hex digits> set salt to <hex digits>\n"
	" -h show this help\n"
	" -s,--verity-size=<data size> print the size of the verity tree\n"
	" -v, enable verbose logging\n"
	" -S treat <data image> as a sparse file\n"
	);
	}

	int main(int argc, char **argv)
	{
	char *data_filename;
	char *verity_filename;
	unsigned char *salt = NULL;
	size_t salt_size = 0;
	bool sparse = false;
	size_t block_size = 4096;
	uint64_t calculate_size = 0;
	bool verbose = false;

	while (1) {
	const static struct option long_options[] = {
	{"salt-str", required_argument, 0, 'a'},
	{"salt-hex", required_argument, 0, 'A'},
	{"help", no_argument, 0, 'h'},
	{"sparse", no_argument, 0, 'S'},
	{"verity-size", required_argument, 0, 's'},
	{"verbose", no_argument, 0, 'v'},
	{NULL, 0, 0, 0}
	};
	int c = getopt_long(argc, argv, "a:A:hSs:v", long_options, NULL);
	if (c < 0) {
	break;
	}

	switch (c) {
	case 'a':
	salt_size = strlen(optarg);
	salt = new unsigned char[salt_size]();
	if (salt == NULL) {
	FATAL("failed to allocate memory for salt\n");
	}
	memcpy(salt, optarg, salt_size);
	break;
	case 'A': {
	BIGNUM *bn = NULL;
	if(!BN_hex2bn(&bn, optarg)) {
	FATAL("failed to convert salt from hex\n");
	}
	salt_size = BN_num_bytes(bn);
	salt = new unsigned char[salt_size]();
	if (salt == NULL) {
	FATAL("failed to allocate memory for salt\n");
	}
	if((size_t)BN_bn2bin(bn, salt) != salt_size) {
	FATAL("failed to convert salt to bytes\n");
	}
	}
	break;
	case 'h':
	usage();
	return 1;
	case 'S':
	sparse = true;
	break;
	case 's': {
	char* endptr;
	errno = 0;
	unsigned long long int inSize = strtoull(optarg, &endptr, 0);
	if (optarg[0] == '\0' \|\| *endptr != '\0' \|\|
	(errno == ERANGE && inSize == ULLONG_MAX)) {
	FATAL("invalid value of verity-size\n");
	}
	if (inSize > UINT64_MAX) {
	FATAL("invalid value of verity-size\n");
	}
	calculate_size = (uint64_t)inSize;
	}
	break;
	case 'v':
	verbose = true;
	break;
	case '?':
	usage();
	return 1;
	default:
	abort();
	}
	}

	argc -= optind;
	argv += optind;

	const EVP_MD *md = EVP_sha256();
	if (!md) {
	FATAL("failed to get digest\n");
	}

	size_t hash_size = EVP_MD_size(md);
	assert(hash_size * 2 < block_size);

	if (!salt \|\| !salt_size) {
	salt_size = hash_size;
	salt = new unsigned char[salt_size];
	if (salt == NULL) {
	FATAL("failed to allocate memory for salt\n");
	}

	int random_fd = open("/dev/urandom", O_RDONLY);
	if (random_fd < 0) {
	FATAL("failed to open /dev/urandom\n");
	}

	ssize_t ret = read(random_fd, salt, salt_size);
	if (ret != (ssize_t)salt_size) {
	FATAL("failed to read %zu bytes from /dev/urandom: %zd %d\n", salt_size, ret, errno);
	}
	close(random_fd);
	}

	if (calculate_size) {
	if (argc != 0) {
	usage();
	return 1;
	}
	size_t verity_blocks = 0;
	size_t level_blocks;
	int levels = 0;
	do {
	level_blocks = verity_tree_blocks(calculate_size, block_size, hash_size, levels);
	levels++;
	verity_blocks += level_blocks;
	} while (level_blocks > 1);

	printf("%" PRIu64 "\n", (uint64_t)verity_blocks * block_size);
	return 0;
	}

	if (argc != 2) {
	usage();
	return 1;
	}

	data_filename = argv[0];
	verity_filename = argv[1];

	int fd = open(data_filename, O_RDONLY);
	if (fd < 0) {
	FATAL("failed to open %s\n", data_filename);
	}

	struct sparse_file *file;
	if (sparse) {
	file = sparse_file_import(fd, false, false);
	} else {
	file = sparse_file_import_auto(fd, false, verbose);
	}

	if (!file) {
	FATAL("failed to read file %s\n", data_filename);
	}

	int64_t len = sparse_file_len(file, false, false);
	if (len % block_size != 0) {
	FATAL("file size %" PRIu64 " is not a multiple of %zu bytes\n",
	len, block_size);
	}

	int levels = 0;
	size_t verity_blocks = 0;
	size_t level_blocks;

	do {
	level_blocks = verity_tree_blocks(len, block_size, hash_size, levels);
	levels++;
	verity_blocks += level_blocks;
	} while (level_blocks > 1);

	unsigned char verity_tree = new unsigned char[verity_blocks block_size]();
	unsigned char *verity_tree_levels = new unsigned char [levels + 1]();
	size_t *verity_tree_level_blocks = new size_t[levels]();
	if (verity_tree == NULL \|\| verity_tree_levels == NULL \|\| verity_tree_level_blocks == NULL) {
	FATAL("failed to allocate memory for verity tree\n");
	}

	unsigned char *ptr = verity_tree;
	for (int i = levels - 1; i >= 0; i--) {
	verity_tree_levels[i] = ptr;
	verity_tree_level_blocks[i] = verity_tree_blocks(len, block_size, hash_size, i);
	ptr += verity_tree_level_blocks[i] * block_size;
	}
	assert(ptr == verity_tree + verity_blocks * block_size);
	assert(verity_tree_level_blocks[levels - 1] == 1);

	unsigned char zero_block_hash[hash_size];
	unsigned char zero_block[block_size];
	memset(zero_block, 0, block_size);
	hash_block(md, zero_block, block_size, salt, salt_size, zero_block_hash, NULL);

	unsigned char root_hash[hash_size];
	verity_tree_levels[levels] = root_hash;

	struct sparse_hash_ctx ctx;
	ctx.hashes = verity_tree_levels[0];
	ctx.salt = salt;
	ctx.salt_size = salt_size;
	ctx.hash_size = hash_size;
	ctx.block_size = block_size;
	ctx.zero_block_hash = zero_block_hash;
	ctx.md = md;

	sparse_file_callback(file, false, false, hash_chunk, &ctx);

	sparse_file_destroy(file);
	close(fd);

	for (int i = 0; i < levels; i++) {
	size_t out_size;
	hash_blocks(md,
	verity_tree_levels[i], verity_tree_level_blocks[i] * block_size,
	verity_tree_levels[i + 1], &out_size,
	salt, salt_size, block_size);
	if (i < levels - 1) {
	assert(div_round_up(out_size, block_size) == verity_tree_level_blocks[i + 1]);
	} else {
	assert(out_size == hash_size);
	}
	}

	for (size_t i = 0; i < hash_size; i++) {
	printf("%02x", root_hash[i]);
	}
	printf(" ");
	for (size_t i = 0; i < salt_size; i++) {
	printf("%02x", salt[i]);
	}
	printf("\n");

	fd = open(verity_filename, O_WRONLY\|O_CREAT, 0666);
	if (fd < 0) {
	FATAL("failed to open output file '%s'\n", verity_filename);
	}
	if (!android::base::WriteFully(fd, verity_tree, verity_blocks * block_size)) {
	FATAL("failed to write '%s'\n", verity_filename);
	}
	close(fd);

	delete[] verity_tree_levels;
	delete[] verity_tree_level_blocks;
	delete[] verity_tree;
	delete[] salt;
	}