1 /* 2 * Copyright (C) 2018 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef __HASH_TREE_BUILDER_H__ 18 #define __HASH_TREE_BUILDER_H__ 19 20 #include <inttypes.h> 21 #include <stddef.h> 22 23 #include <functional> 24 #include <string> 25 #include <vector> 26 27 #include <openssl/evp.h> 28 29 // This class builds a verity hash tree based on the input data and a salt with 30 // the length of hash size. It also supports the streaming of input data while 31 // the total data size should be know in advance. Once all the data is ready, 32 // appropriate functions can be called to build the upper levels of the hash 33 // tree and output the tree to a file. 34 class HashTreeBuilder { 35 public: 36 HashTreeBuilder(size_t block_size, const EVP_MD* md); 37 // Returns the size of the verity tree in bytes given the input data size. CalculateSize(uint64_t input_size)38 uint64_t CalculateSize(uint64_t input_size) const { 39 return CalculateSize(input_size, block_size_, hash_size_); 40 } 41 static uint64_t CalculateSize(uint64_t input_size, size_t block_size, size_t hash_size); 42 // Gets ready for the hash tree computation. We expect |expected_data_size| 43 // bytes source data. 44 bool Initialize(int64_t expected_data_size, 45 const std::vector<unsigned char>& salt); 46 // Streams |len| bytes of source data to the hash tree builder. This function 47 // can be called multiple until we processed all the source data. And the 48 // accumulated data_size is expected to be exactly the |data_size_| when we 49 // build the hash tree. 50 bool Update(const unsigned char* data, size_t len); 51 // Computes the upper levels of the hash tree based on the 0th level. 52 bool BuildHashTree(); 53 // Check the built hash tree against |hash_tree|, return true if they match. 54 bool CheckHashTree(const std::vector<unsigned char>& hash_tree) const; 55 // Writes the computed hash tree top-down to |output|. 56 bool WriteHashTreeToFile(const std::string& output) const; 57 bool WriteHashTreeToFd(int fd, uint64_t offset) const; 58 bool WriteHashTree(std::function<bool(const void*, size_t)> callback) const; 59 hash_size()60 size_t hash_size() const { return hash_size_; } root_hash()61 const std::vector<unsigned char>& root_hash() const { return root_hash_; } 62 // Converts |bytes| to string for hexdump. 63 static std::string BytesArrayToString( 64 const std::vector<unsigned char>& bytes); 65 // Inverse of the above function. It parses the input hex string and stores 66 // the result in |bytes|. 67 static bool ParseBytesArrayFromString(const std::string& str, 68 std::vector<unsigned char>* bytes); 69 // Returns the hash function given the name of the hash algorithm. Returns 70 // nullptr if the algorithm is unrecongnized or not supported. 71 static const EVP_MD* HashFunction(const std::string& hash_name); 72 73 // Calculates the digest of the root of a verity tree. 74 bool CalculateRootDigest(const std::vector<unsigned char>& root_verity, 75 std::vector<unsigned char>* root_digest); 76 77 private: 78 friend class BuildVerityTreeTest; 79 // Calculates the hash of one single block. Write the result to |out|, a 80 // buffer allocated by the caller. 81 bool HashBlock(const unsigned char* block, unsigned char* out); 82 // Calculates the hash of |len| bytes of data starting from |data|. Append the 83 // result to |output_vector|. 84 bool HashBlocks(const unsigned char* data, size_t len, 85 std::vector<unsigned char>* output_vector); 86 // Aligns |data| with block_size by padding 0s to the end. 87 void AppendPaddings(std::vector<unsigned char>* data); 88 89 size_t block_size_; 90 // Expected size of the source data, which is used to compute the hash for the 91 // base level. 92 uint64_t data_size_; 93 std::vector<unsigned char> salt_; 94 const EVP_MD* md_; 95 // The raw hash size of the hash algorithm specified by md_. 96 size_t hash_size_raw_; 97 // Hash size rounded up to the next power of 2. (e.g. 20 -> 32) 98 size_t hash_size_; 99 100 // Pre-calculated hash of a zero block. 101 std::vector<unsigned char> zero_block_hash_; 102 std::vector<unsigned char> root_hash_; 103 // Storage of the verity tree. The base level hash stores in verity_tree_[0] 104 // and the top level hash stores in verity_tree_.back(). 105 std::vector<std::vector<unsigned char>> verity_tree_; 106 // The remaining data passed to the last call to Update() that's less than a 107 // block. 108 std::vector<unsigned char> leftover_; 109 }; 110 111 #endif // __HASH_TREE_BUILDER_H__ 112