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 <string> 24 #include <vector> 25 26 #include <openssl/evp.h> 27 28 // This class builds a verity hash tree based on the input data and a salt with 29 // the length of hash size. It also supports the streaming of input data while 30 // the total data size should be know in advance. Once all the data is ready, 31 // appropriate functions can be called to build the upper levels of the hash 32 // tree and output the tree to a file. 33 class HashTreeBuilder { 34 public: 35 HashTreeBuilder(size_t block_size, const EVP_MD* md); 36 // Returns the size of the verity tree in bytes given the input data size. 37 uint64_t CalculateSize(uint64_t input_size) const; 38 // Gets ready for the hash tree computation. We expect |expected_data_size| 39 // bytes source data. 40 bool Initialize(int64_t expected_data_size, 41 const std::vector<unsigned char>& salt); 42 // Streams |len| bytes of source data to the hash tree builder. This function 43 // can be called multiple until we processed all the source data. And the 44 // accumulated data_size is expected to be exactly the |data_size_| when we 45 // build the hash tree. 46 bool Update(const unsigned char* data, size_t len); 47 // Computes the upper levels of the hash tree based on the 0th level. 48 bool BuildHashTree(); 49 // Check the built hash tree against |hash_tree|, return true if they match. 50 bool CheckHashTree(const std::vector<unsigned char>& hash_tree) const; 51 // Writes the computed hash tree top-down to |output|. 52 bool WriteHashTreeToFile(const std::string& output) const; 53 bool WriteHashTreeToFd(int fd, uint64_t offset) const; 54 hash_size()55 size_t hash_size() const { return hash_size_; } root_hash()56 const std::vector<unsigned char>& root_hash() const { return root_hash_; } 57 // Converts |bytes| to string for hexdump. 58 static std::string BytesArrayToString( 59 const std::vector<unsigned char>& bytes); 60 // Inverse of the above function. It parses the input hex string and stores 61 // the result in |bytes|. 62 static bool ParseBytesArrayFromString(const std::string& str, 63 std::vector<unsigned char>* bytes); 64 // Returns the hash function given the name of the hash algorithm. Returns 65 // nullptr if the algorithm is unrecongnized or not supported. 66 static const EVP_MD* HashFunction(const std::string& hash_name); 67 68 // Calculates the digest of the root of a verity tree. 69 bool CalculateRootDigest(const std::vector<unsigned char>& root_verity, 70 std::vector<unsigned char>* root_digest); 71 72 private: 73 friend class BuildVerityTreeTest; 74 // Calculates the hash of one single block. Write the result to |out|, a 75 // buffer allocated by the caller. 76 bool HashBlock(const unsigned char* block, unsigned char* out); 77 // Calculates the hash of |len| bytes of data starting from |data|. Append the 78 // result to |output_vector|. 79 bool HashBlocks(const unsigned char* data, size_t len, 80 std::vector<unsigned char>* output_vector); 81 // Aligns |data| with block_size by padding 0s to the end. 82 void AppendPaddings(std::vector<unsigned char>* data); 83 84 size_t block_size_; 85 // Expected size of the source data, which is used to compute the hash for the 86 // base level. 87 uint64_t data_size_; 88 std::vector<unsigned char> salt_; 89 const EVP_MD* md_; 90 // The raw hash size of the hash algorithm specified by md_. 91 size_t hash_size_raw_; 92 // Hash size rounded up to the next power of 2. (e.g. 20 -> 32) 93 size_t hash_size_; 94 95 // Pre-calculated hash of a zero block. 96 std::vector<unsigned char> zero_block_hash_; 97 std::vector<unsigned char> root_hash_; 98 // Storage of the verity tree. The base level hash stores in verity_tree_[0] 99 // and the top level hash stores in verity_tree_.back(). 100 std::vector<std::vector<unsigned char>> verity_tree_; 101 // The remaining data passed to the last call to Update() that's less than a 102 // block. 103 std::vector<unsigned char> leftover_; 104 }; 105 106 #endif // __HASH_TREE_BUILDER_H__ 107